ABSTRACT

A new variant of the Adaptive Method (AM) of Gabasov is presented, to minimize the computation time. Unlike the original method and its some variants, we need not to compute the inverse of the basic matrix at each iteration, or to solve the linear systems with the basic matrix. In fact, to compute the new support feasible solution, the simplex pivoting rule is used by introducing a matrix that we will define. This variant is called “the Pivot Adaptive Method” (PAM); it allows presenting the resolution of a given problem under the shape of successive tables as we will see in example. The proofs that are not given by Gabasov will also be presented here, namely the proofs for the theorem of the optimality criterion and for the theorem of existence of an optimal support, and at the end, a brief comparison between our method and the Simplex Method will be given.

Keywords:

Optimization, Linear Programming, Simplex Method, Adaptive Method

1. Introduction

As a branch of mathematics, linear programming is the domain that had the most successful in optimization [1] [2] [3] [4] [5] . Since its formulation from 1930 to 1940 and the development of the Simplex method of Dantzig in 1949 [1] [6] , researchers in various fields have been led to formulate and solve linear problems.

Although, the Simplex algorithm is often effective in practice, the fact that it is not a polynomial algorithm, as shown by Klee and Minty [7] , has incited researchers to propose other algorithms and led to the birth of the interior point algorithms.

In 1979, L. Khachiyan proposed the first polynomial algorithm for linear programming [8] ; it is based on the ellipsoid method, studied by Arkadi Nemirovski and David B. Yudin, a preliminary version of which having been introduced by Naum Z. Shor. Unfortunately, this ellipsoid method has a poor efficiency.

In 1984, N. K. Karmakar published an interior point algorithm which has a polynomial convergence [9],and this caused a renewed interest to interior point methods, as well in linear programming that in nonlinear programming [10] [11] [12] [13] [14] .

Gabasov and Kirillova have generalized the Simplex method in 1995 [15] [16] [17] , and developed the Adaptive Method (AM), a primal-dual method, for linear programming with bounded variables. As the Simplex method, the Adaptive Method is a support method, but it can start from any support (base) and any feasible solution and can move to the optimal solution by interior or boundary points; this method was extended, later, to solve general linear and convex problems [18] [19] [20], and also optimal control problems [21] .

In linear programming, several variants of the AM have been proposed. They generally address the problem of initialization of the method and the choice of the direction [22] [23] .

In this work, a new variant of the adaptive method called “Pivot adaptive method” (PAM) is presented. Unlike the original method and its variants, we need not to compute the inverse of the basic matrix at each iteration [16] , or to solve the linear systems with the basic matrix [23] . In fact, to compute the new feasible solution and the new support, we only need compute the decomposition of vectors columns of the matrix of the problem in the current basis. For this computation we use the simplex pivoting rule [4] by introducing a new matrix GAMMA which allows to minimize the computation time. This new variant of adaptive method allows us to present the resolution of a given problem under the shape of successive tables (as is done with the Simplex method) as we will see in example. The proofs for the theorem of the optimality criterion and for the theorem of existence of an optimal support that are not given by Gabasov [16] will be presented here, and without giving too many details a brief comparison between our method and the Simplex method will be given at the end of this article.

The paper is organized as follows. In Section 2, after giving the statement of the problem, some important definitions are given. In Section 3, we describe step by step the “Pivot Adaptive Method” and in parallel the proofs of the corresponding theorems are given. In Section 4, an example will be solved to illustrate the PAM, and more details will be given to explain how present the resolution under the shape of successive tables. In Section 5, we give a brief comparison between the PAM and the Simplex Method by solving the Klee-Minty problem. Section 6, concludes the paper.

2. Statement of the Problem and Definitions

In this article we consider the primal linear programming problem with bounded variables presented in the following standard form:

$\left(P\right)\{\begin{array}{l}\max F\left(x_1,x_2,\cdots ,x_n\right)=\sum _{j=1}^{j=n}{c}_j{x}_j\hfill \\ \sum _{j=1}^{j=n}{a}_{ij}{x}_j=b_i,i\in I\hfill \\ d_j^{-}\le x_j\le d_j^{+},j\in J.\hfill \end{array}$ (1)

where: $J=\left\{1,\cdots ,n\right\}$ is the index set of the variables $x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n$ , $I=\left\{1,\cdots ,m\right\}$ is the index set of the parameters $b_1\mathrm{,}{b}_2\mathrm{,}\cdots \mathrm{,}{b}_m$ (corresponds to the constraints), put: $J=J_B\cup J_N$ , $J_B\cap J_N=\varnothing$ , $\left|J_B\right|=m$ , and introduce the vectors:

・ $x=x\left(J\right)=\left(x_j,j\in J\right)=\left(x_1,x_2,\cdots ,x_n\right)=\left(\begin{array}{c}{x}_B\\ x_N\end{array}\right)$ , with: $x_B=x\left(J_B\right)=\left(x_j,j\in J_B\right)$ , $x_N=x\left(J_N\right)=\left(x_j,j\in J_N\right)$ .

・ $c=c\left(J\right)=\left(c_j,j\in J\right)=\left(c_1,c_2,\cdots ,c_n\right)=\left(\begin{array}{c}{c}_B\\ c_N\end{array}\right)$ , with: $c_B=c\left(J_B\right)=\left(c_j,j\in J_B\right)$ , $c_N=c\left(J_N\right)=\left(c_j,j\in J_N\right)$ .

・ $b^{\text{T}}=b^{\text{T}}\left(J\right)=\left(b_i\mathrm{,}i\in I\right)=\left(b_1\mathrm{,}{b}_2\mathrm{,}\cdots \mathrm{,}{b}_m\right)$ .

・ $d^{-}=d^{-}\left(J\right)=\left(d_j^{-}\mathrm{,}j\in J\right)=\left(d_1^{-}\mathrm{,}{d}_2^{-}\mathrm{,}\cdots \mathrm{,}{d}_n^{-}\right)\mathrm{<mo>\; ;\; </mo>}\Vert d^{-}\Vert \mathrm{<mo>\; <\; </mo>}+\infty$ .

・ $d^{+}=d^{+}\left(J\right)=\left(d_j^{+},j\in J\right)=\left(d_1^{+},d_2^{+},\cdots ,d_n^{+}\right);\Vert d^{+}\Vert <+\infty$ .

and the $\left(m\times n\right)$ matrix

・ $A=A\left(I,J\right)=\left(a_{ij},i\in I,j\in J\right)=\left(a_1,a_2,\cdots ,a_n\right)=\left(\begin{array}{c}{A}_1^{\text{T}}\\ ⋮\\ A_m^{\text{T}}\end{array}\right)$ , with: $a_j=\left(\begin{array}{c}{a}_{1j}\\ ⋮\\ a_{mj}\end{array}\right)$ ,

$j\in J$ ( $a_j$ : the j^th column of the matrix A), and $A_i^{\text{T}}=\left(a_{i1}\mathrm{,}{a}_{i2}\mathrm{,}\cdots \mathrm{,}{a}_{in}\right)\mathrm{,}i\in I$ ( $A_i^{\text{T}}$ : the i^th row of the matrix A), $A=\left(A_B/A_N\right)$ , $A_B=A\left(I,J_B\right)$ , $A_N=A\left(I,J_N\right)$ .

We assume that $rank\left(A\right)=m<n$ . Then the problem (1) takes the following form:

$\left(P\right)\{\begin{array}{l}maxF\left(x\right)=c^{\text{T}}x\hfill \\ Ax=b\hfill \\ d^{-}\le x\le d^{+}\hfill \end{array}$ (2)

$Ax=b$ are called the general constraints of (P).

Denote the feasible region of (P) as: $H=\left\{x\in R^n,Ax=b,d^{-}\le x\le d^{+}\right\}$ .

2.1. Definition 1

Each vector of the set H is called a feasible solution of (P).

2.2. Definition 2

Any vector $x\in R^n$ that satisfies the general constraints $Ax=b$ of the problem (P) is called a pseudo-feasible solution.

2.3. Definition 3

A feasible solution $x^0$ is called optimal if: $F\left(x^0\right)=c^{\text{T}}{x}^0=\underset{x\in H}{\max }{c}^{\text{T}}x$ .

2.4. Definition 4

For given value $ϵ\ge 0$ , the solution $x^{ϵ}$ is called an ò-optimal (or suboptimal) if: $\left(F\left(x^0\right)-F\left(x^{ϵ}\right)\right)\le ϵ$ , where $x^0$ is an optimal solution for the problem (P).

2.5. Definition 5

The set of m indices $J_B\subset J$ ( $\left|J_B\right|=m$ ) is called a support of (P) if the submatrix $A_B=A\left(I\mathrm{,}{J}_B\right)$ is non-singular ( $det{A}_B\ne 0$ ), then the set $J_N=J\backslash J_B$ of ( $n-m$ ) indices is called non-support, $A_B$ is the matrix support, and $A_N=A\left(I\mathrm{,}{J}_N\right)$ is the matrix non-support.

2.6. Definition 6

The pair $\left\{x\mathrm{,}{J}_B\right\}$ formed by a feasible solution x and the support $J_B$ is called a support feasible solution (SF-solution).

2.7. Definition 7

The SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ is called non-degenerate if: $d_j^{-}<x_j<d_j^{+},\forall j\in J_B$ .

Recall that, unlike the Simplex Method in which the feasible solution x and the basic indices $J_B$ are related intimately, in the adaptive method there are independent.

3. Optimality Criterion

For the smooth running of calculations, in the rest of the article, we assume that the sets $J_B$ and $J_N$ are vectors of indices (i.e.: the order of indices in these sets is important and must be respected).

3.1. Formula of the Objective Value Increment

Let $\left\{x\mathrm{,}{J}_B\right\}$ be the initial SF-solution of the problem (P), and $\overline{x}=\overline{x}\left(J\right)=\left(\begin{array}{c}{\overline{x}}_B\\ {\overline{x}}_N\end{array}\right)$ an arbitrary pseudo-feasible solution of (P). We set $\Delta x=\Delta x_B+\Delta x_N=\overline{x}-x$ , then the increment of the objective function value is given by:

$\Delta F\left(x\right)=F\left(\overline{x}\right)-F\left(x\right)=c^{\text{T}}\overline{x}-c^{\text{T}}x=c^{\text{T}}\Delta x=c_B^{\text{T}}\Delta x_B+c_N^{\text{T}}\Delta x_N$ (3)

and since:

$A\Delta x=A_B\Delta x_B+A_N\Delta x_N=A\overline{x}-Ax=0$ (4)

then

$\Delta x_B=-A_B^{-1}{A}_N\Delta x_N$ (5)

Substituting the vector $\Delta x_B$ in (3) we get:

$\Delta F\left(x\right)=\left(c_N^{\text{T}}-c_B^{\text{T}}{A}_B^{-1}{A}_N\right)\Delta x_N$ (6)

Here, we define the m-vector of multipliers y as follows:

$y^{\text{T}}=c_B^{\text{T}}{A}_B^{-1}$ (7)

In [16] , Gabasov defines the support gradient and noted it D as: ${\Delta }^{\text{T}}=y^{\text{T}}A-c^{\text{T}}$ , but he also recognizes that for every $k\in J_N$ , the k^th support derivative is equal to $-{\Delta }_k=c_k-y^{\text{T}}{a}_k$ , in fact, $-{\Delta }_k$ is the rate of change of the objective function when the k^th non-support components of the feasible solution x is increased and all the other non-support components are fixed, at the same time the support components are changed in such way to satisfy the constraints $Ax=b$ .

Then, in the pivot adaptive method, we define the n-vector of reduced gains (or support gradient) δ as follows:

${\delta }^{\text{T}}=-{\Delta }^{\text{T}}=\left({\delta }_j,j\in J\right)=c^{\text{T}}-y^{\text{T}}A=\left({\delta }_B^{\text{T}},{\delta }_N^{\text{T}}\right),\text{where}:{\delta }_B^{\text{T}}=0,\mathrm{<mi>\; </mi>}{\delta }_N^{\text{T}}=c_N^{\text{T}}-y^{\text{T}}{A}_B$ (8)

To reduce the computation time in the adaptive method of Gabasov [16] , we define the ( $m\times n$ ) matrix G as follows:

$\Gamma =A_B^{-1}A=\left({\Gamma }_B\mathrm{,}{\Gamma }_N\right)\mathrm{,}\text{where:}{\Gamma }_B=I_m\mathrm{,\; <mi>\; </mi>}{\Gamma }_N=A_B^{-1}{A}_N$ (9)

which is the decomposition of the columns of the matrix A on the support $J_B$ .

We have: ${\Gamma }_N=\Gamma \left(I\mathrm{,}{J}_N\right)=\left({\Gamma }_{ij}\mathrm{,}i\in I\mathrm{,}j\in J_N\right)$ , ${\Gamma }_{ij}$ is the product of the i^th row of the matrix $A_B^{-1}$ and the j^th column of the matrix $A_N$ . Then the n-vector of support gradient given in (8) can be computed as follows:

$\begin{array}{l}{\delta }^{\text{T}}=\left({\delta }_j\mathrm{,}j\in J\right)=c^{\text{T}}-c_B^{\text{T}}{A}_B^{-1}A=c^{\text{T}}-c_B^{\text{T}}\Gamma =\left({\delta }_B^{\text{T}}\mathrm{,}{\delta }_N^{\text{T}}\right)\mathrm{,}\\ \text{where:}{\delta }_B^{\text{T}}=\mathrm{0,\; <mi>\; </mi>}{\delta }_N^{\text{T}}=c_N^{\text{T}}-c_B^{\text{T}}{\Gamma }_N\end{array}$ (10)

We see that, to compute the quantity $c_B^{\text{T}}{A}_B^{-1}A$ , we begin to compute $\Gamma =A_B^{-1}A$ and not $y^{\text{T}}=c_B^{\text{T}}{A}_B^{-1}$ ; therefore we need not to compute the inverse of the basic matrix $A_B$ .

From (6) and (10) we obtain

$\Delta F\left(x\right)={\delta }_N^{\text{T}}\Delta x_N=\sum _{j\in J_N}{\delta }_j\Delta x_j$ (11)

3.2. Definition 8

For an given support $J_B$ , any vector $\chi =\chi \left(J\right)=\left(\begin{array}{c}{\chi }_B\\ {\chi }_N\end{array}\right)$ of $R^n$ that satisfies

$\{\begin{array}{l}{\chi }_j=d_j^{-}\mathrm{,}\text{if}{\delta }_j<0\hfill \\ {\chi }_j=d_j^{+}\mathrm{,}\text{if}{\delta }_j>0\hfill \\ {\chi }_j=d_j^{-}\text{or}{d}_j^{+}\mathrm{,}\text{if}{\delta }_j=0\hfill \\ {\chi }_B=A_B^{-1}\left(b-A_N{\chi }_N\right)\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J_N\right)$ (12)

is called a primal pseudo-feasible solution accompanying the support $J_B$ .

3.3. Proposition 1

A primal pseudo-feasible solution accompanying a given support $J_B$ , χ, verifies just the general constraints of the problem (P), ie $A\chi =b$ . If more, the support components ${\chi }_B$ of the vector χ verifies: $d_B^{-}\le {\chi }_B\le d_B^{+}$ , then χ is feasible and optimal solution for (P).

3.4. Theorem 1 (The Optimality Criterion)

Let $\left\{x\mathrm{,}{J}_B\right\}$ be an SF-solution of the problem (P), and ${\delta }^{\text{T}}$ be the support gradient computed by (10), then the relations

$\{\begin{array}{l}{\delta }_j<0,\text{for}{x}_j=d_j^{-}\hfill \\ {\delta }_j>0,\text{for}{x}_j=d_j^{+}\hfill \\ {\delta }_j=0,\text{for}{d}_j^{-}\le x_j\le d_j^{+}\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J_N\right)$ (13)

are sufficient, and in the case of non-degeneracy of the SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ also necessary for the optimality of the feasible solution x.

Proof

1) The sufficient condition:

for the SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ , suppose that the relation (13) are verified, we must proof that x is optimal, it amounts to show that:

$\forall \overline{x}\in H,\Delta F\left(x\right)=F\left(x\right)-F\left(\overline{x}\right)\ge 0$ (14)

Let $\overline{x}\in H$ , and $\Delta x=x-\overline{x}$ , then:

$\begin{array}{c}\Delta F\left(x\right)=F\left(x\right)-F\left(\overline{x}\right)=\sum _{j\in J_N}{\delta }_j\Delta x_j\\ =\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j\le 0\end{array}}{\delta }_j\left(x_j-{\overline{x}}_j\right)+\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j\ge 0\end{array}}{\delta }_j\left(x_j-{\overline{x}}_j\right)+\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j=0\end{array}}{\delta }_j\left(x_j-{\overline{x}}_j\right)\\ =\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j\le 0\end{array}}{\delta }_j\left(d_j^{-}-{\overline{x}}_j\right)+\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j\ge 0\end{array}}{\delta }_j\left(d_j^{+}-{\overline{x}}_j\right)\ge 0\end{array}$

then x is optimal.

2) The necessary condition:

Suppose that $\left\{x\mathrm{,}{J}_B\right\}$ an SF-solution non-degenerate, i.e.:

$\forall j\in J_B,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}{d}_j^{-}<x_j<d_j^{+}$ (15)

and that x optimal, i.e.:

$\forall \overline{x}\in H,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}\Delta F\left(x\right)=F\left(x\right)-F\left(\overline{x}\right)=\sum _{j\in J_N}{\delta }_j\Delta x_j\ge 0.$ (16)

Reasoning by absurdity:

Suppose that the relations (13) are not verified, thus we have, at least, one of the following three cases:

1) $\exists k\in J_N/{\delta }_k\le 0\text{and}{x}_k>d_k^{-}$ .

2) $\exists k\in J_N/{\delta }_k\ge 0\text{and}{x}_k<d_k^{+}$ .

3) $\exists k\in J_N/{\delta }_k=0\text{and}{x}_k=d_j^{-}\text{or}{x}_k=d_j^{+}$ .

Suppose then we have the first case, i.e.

$\exists k\in J_N/{\delta }_k\le 0\text{and}{x}_k>d_k^{-}$ (17)

(the proof uses the same reasoning for the second and the third cases). Construct the n-vector $\overline{x}\left(\theta \right)=\left({\left(\overline{x}\left(\theta \right)\right)}_1\mathrm{,}{\left(\overline{x}\left(\theta \right)\right)}_2\mathrm{,}\cdots \mathrm{,}{\left(\overline{x}\left(\theta \right)\right)}_n\right)$ as follows:

$\{\begin{array}{l}{\left(\overline{x}\left(\theta \right)\right)}_j=x_j,\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\forall j\in J_N\backslash \left\{k\right\}\hfill \\ {\left(\overline{x}\left(\theta \right)\right)}_k=x_k-\theta ,\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\theta \in \left[0,x_k-d_k^{-}\right]\hfill \\ {\left(\overline{x}\left(\theta \right)\right)}_j=x_j+\theta {\Gamma }_{jk},\mathrm{<mi>\; </mi>\; <mi>\; </mi>}\forall j\in J_B\hfill \end{array}$ (18)

where ${\Gamma }_{jk}$ is the product of the j^th row of the matrix $A_B^{-1}$ and the k^th column of the matrix $A_N$ . Let ${\theta }_1=x_k-d_k^{-}>0$ .

we have

$A\overline{x}\left(\theta \right)=A_B{\left(\overline{x}\left(\theta \right)\right)}_B+A_N{\left(\overline{x}\left(\theta \right)\right)}_N=0$ (19)

and

$\forall j\in J_N\mathrm{,\; <mi>\; </mi>}{d}_j^{-}\le {\left(\overline{x}\left(\theta \right)\right)}_j\le d_j^{+}$ (20)

For $j\in J_B,{\left(\overline{x}\left(\theta \right)\right)}_j=x_j+\theta {\Gamma }_{jk}$ , then for have:

$\forall j\in J_B\mathrm{,\; <mi>\; </mi>}{d}_j^{-}\le {\left(\overline{x}\left(\theta \right)\right)}_j\le d_j^{+}$ (21)

a value of θ is chosen such that:

$\forall j\in J_B,\mathrm{<mi>\; </mi>}{d}_j^{-}\le x_j+\theta {\Gamma }_{jk}\le d_j^{+}$ (22)

i.e.

$\{\begin{array}{l}0<\theta \le \frac{d_j^{+}-x_j}{{\Gamma }_{jk}},\text{for}{\Gamma }_{jk}>0\hfill \\ 0<\theta \le \frac{d_j^{-}-x_j}{{\Gamma }_{jk}},\text{for}{\Gamma }_{jk}<0\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J_B\right)$ (23)

Put: ${\theta }_2=\underset{\begin{array}{l}{\Gamma }_{jk}>0\\ j\in J_B\end{array}}{\min }\frac{d_j^{+}-x_j}{{\Gamma }_{jk}}$ , ${\theta }_3=\underset{\begin{array}{l}{\Gamma }_{jk}<0\\ j\in J_B\end{array}}{\min }\frac{d_j^{-}-x_j}{{\Gamma }_{jk}}$ .

we have: ${\theta }_2>0$ , ${\theta }_3>0$ , because $\left\{x\mathrm{,}{J}_B\right\}$ is non-degenerate.

Let ${\theta }^{\mathrm{<mo>\; *\; </mo>}}=min\left({\theta }_1\mathrm{,}{\theta }_2\mathrm{,}{\theta }_3\right)$ , then

$\overline{x}\left({\theta }^{\mathrm{<mo>\; *\; </mo>}}\right)\in H$ (24)

or

$F\left(x\right)-F\left(\overline{x}\left({\theta }^{\mathrm{<mo>\; *\; </mo>}}\right)\right)=\sum _{j\in J_N}{\delta }_j\Delta x_j={\delta }_k\Delta x_k={\delta }_k{\theta }^{\mathrm{<mo>\; *\; </mo>}}<0$ (25)

then

$F\left(\overline{x}\left({\theta }^{\mathrm{<mo>\; *\; </mo>}}\right)\right)>F\left(x\right)$ (26)

contradiction with (16).

3.5. Definition 9

The pair $\left\{x^0\mathrm{,}{J}_B^0\right\}$ satisfying the relations (13) will be called an optimal SF-solution of the problem (P).

3.6. The Suboptimality Criterion

Let $x^0$ an optimal solution of (P), and x a feasible solutions of (P).

From (11) we obtained:

$\begin{array}{c}\underset{\overline{x}\in H}{\max }\Delta F\left(x\right)=F\left(x^0\right)-F\left(x\right)\\ =\underset{\overline{x}\in H}{\max }\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j>0\end{array}}{\delta }_j\left({\overline{x}}_j-x_j\right)+\underset{\overline{x}\in H}{\max }\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j<0\end{array}}{\delta }_j\left({\overline{x}}_j-x_j\right)\\ \le \sum _{\begin{array}{c}j\in J_N\\ {\delta }_j>0\end{array}}{\delta }_j\left(d_j^{+}-x_j\right)+\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j<0\end{array}}{\delta }_j\left(d_j^{-}-x_j\right)\end{array}$

Let

$\beta \left(x,J_B\right)=\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j>0\end{array}}{\delta }_j\left(d_j^{+}-x_j\right)+\sum _{\begin{array}{c}j\in J_N\\ {\delta }_j<0\end{array}}{\delta }_j\left(d_j^{-}-x_j\right)$ (27)

$\beta \left(x\mathrm{,}{J}_B\right)$ is called the suboptimality estimate of the SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ since

$\left(F\left(x^0\right)-F\left(x\right)\right)\le \beta \left(x\mathrm{,}{J}_B\right)$ (28)

We have the following theorem of suboptimality.

3.7. Theorem 2 (Sufficient Condition of Suboptimality)

For a feasible solution x to be ò-optimal for given positive number ò, it is sufficient of the existence of a support $J_B$ such that $\beta \left(x\mathrm{,}{J}_B\right)\le ϵ$ .

3.8. Proposition 2

From (12) and (27) we deduce:

$\beta \left(x,J_B\right)={\delta }_N^{\text{T}}\left({\chi }_N-x_N\right)={\delta }^{\text{T}}\left(\chi -x\right)$ (29)

3.9. The Dual Problem

The dual of the primal problem (P) is given by the following linear problem

$\left(D\right)\{\begin{array}{l}\min \varphi \left(y,v,w\right)=b^{\text{T}}y-{\left(d^{-}\right)}^{\text{T}}v+{\left(d^{+}\right)}^{\text{T}}w\hfill \\ A^{\text{T}}y-v+w=c\hfill \\ y\in R^m,\mathrm{<mi>\; </mi>}v\ge 0,\mathrm{<mi>\; </mi>}w\ge 0.\hfill \end{array}$ (30)

where $A^{\text{T}}=\left(\begin{array}{c}{a}_1^{\text{T}}\\ ⋮\\ a_n^{\text{T}}\end{array}\right)$ , with $\forall j\in J$ , $a_j^{\text{T}}$ is the transpose of the j^th column $a_j$ of the matrix A. The problem D has n general constraints, and $\left(m+2n\right)$ variables.

Like (P), the problem (D) has an optimal solution ${\lambda }^0=\left(y^0\mathrm{,}{v}^0\mathrm{,}{w}^0\right)$ , and $F\left(x^0\right)=\varphi \left({\lambda }^0\right)$ , where $x^0$ is the optimal solution of (P).

3.10. Definition 10

Any $\left(m+2n\right)$ -vector $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ satisfying all the constraints of the problem D is called a dual feasible solution.

3.11. Definition 11

Let $J_B$ be a support of the problem (P), and δ the corresponding support gradient defined in (10), the $\left(m+2n\right)$ -vector $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ which satisfies:

$\{\begin{array}{l}{y}^{\text{T}}=c_B^{\text{T}}{A}_B^{-1}\hfill \\ v_j=-{\delta }_j,\mathrm{<mi>\; </mi>}{w}_j=0\text{if}{\delta }_j\le 0\hfill \\ v_j=0,\mathrm{<mi>\; </mi>}{w}_j={\delta }_j\text{if}{\delta }_j>0\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J\right)$ (31)

is called the dual feasible solution accompanying the support $J_B$ .

3.12. Proposition 3

・ A dual feasible solution $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ accompanying a given support $J_B$ , is dual feasible, i.e.: $A^{\text{T}}y-v+w=c,\mathrm{<mi>\; </mi>}v\ge 0,\mathrm{<mi>\; </mi>}w\ge 0,\mathrm{<mi>\; </mi>}y\in R^m$ .

・ For any support $J_B$ we have

$c^{\text{T}}\chi =\varphi \left(\lambda \right)$ (32)

where λ and χ are respectively the dual feasible solution and an primal pseudo-feasible solution accompanying the support $J_B$ .

3.13. Definition 12

Let y be dual feasible solution: $A^{\text{T}}y-v+w=c\mathrm{,\; <mi>\; </mi>}v\ge \mathrm{0,\; <mi>\; </mi>}w\ge 0$ . The $\left(m+2n\right)$ -vector ${\lambda }^{\mathrm{<mo>\; *\; </mo>}}=\left(y\mathrm{,}{v}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{w}^{\mathrm{<mo>\; *\; </mo>}}\right)$ such that:

$\{\begin{array}{l}{v}_j^{\mathrm{<mo>\; *\; </mo>}}=\mathrm{0,\; <mi>\; </mi>\; <mi>\; </mi>}{w}_j^{\mathrm{<mo>\; *\; </mo>}}=\left(c_j-a_j^{\text{T}}y\right)\text{if}\left(c_j-a_j^{\text{T}}y\right)\ge 0\hfill \\ v_j^{\mathrm{<mo>\; *\; </mo>}}=-\left(c_j-a_j^{\text{T}}y\right)\mathrm{,\; <mi>\; </mi>}{w}_j^{\mathrm{<mo>\; *\; </mo>}}=0\text{if}\left(c_j-a_j^{\text{T}}y\right)\le 0\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J\right)$ (33)

is called a coordinated dual feasible point to the m-vector y.

3.14. Proposition 4

The coordinated dual feasible point ${\lambda }^{*}=\left(y,v^{*},w^{*}\right)$ to y is dual feasible, i.e.: $A^{\text{T}}y-v^{\mathrm{<mo>\; *\; </mo>}}+w^{\mathrm{<mo>\; *\; </mo>}}=c$ , $v^{\mathrm{<mo>\; *\; </mo>}}\ge 0$ , $w^{\mathrm{<mo>\; *\; </mo>}}\ge 0$ .

3.15. Decomposition of the Suboptimality Estimate of an SF-Solution $\left\{x\mathrm{,}{J}_B\right\}$

Let $\left\{x\mathrm{,}{J}_B\right\}$ be a SF-solution of the problem (P), $\beta \left(x\mathrm{,}{J}_B\right)$ be its suboptimality estimate calculated by (27), $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ be the dual feasible solution accompanying the support $J_B$ , χ the primal pseudo-feasible solution accompanying the support $J_B$ , $x^0$ be the optimal solution for the problem (P), ${\lambda }^0$ be the optimal solution for the dual problem (D).

From (9), (10), (29), (32), and proposition 1 we have:

$\begin{array}{c}\beta \left(x,J_B\right)={\delta }_N^{\text{T}}\left({\chi }_N-x_N\right)={\delta }^{\text{T}}\left(\chi -x\right)=\left(c^{\text{T}}-c_B^{\text{T}}\Gamma \right)\left(\chi -x\right)\\ =c^{\text{T}}\chi -c^{\text{T}}x-c_B^{\text{T}}{A}_B^{-1}A\chi +c_B^{\text{T}}{A}_B^{-1}Ax=c^{\text{T}}\chi -c^{\text{T}}x\\ =\varphi \left(\lambda \right)-F\left(x\right)=\varphi \left(\lambda \right)-\varphi \left({\lambda }^0\right)+F\left(x^0\right)-F\left(x\right)\end{array}$ .

then

$\beta \left(x\mathrm{,}{J}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(x\right)+\mathrm{<mi>\; </mi>}\beta \left(J_B\right)$ (34)

where: $\beta \left(J_B\right)=\varphi \left(\lambda \right)-\varphi \left({\lambda }^0\right)$ is the degree of non-optimality of the support $J_B$ , and $\beta \left(x\right)=F\left(x^0\right)-F\left(x\right)$ is the degree of non-optimality of the feasible solution x.

3.16. Proposition 5

・ The feasible solution x will be optimal if $\beta \left(x\right)=0$ , and the support $J_B$ will be optimal if $\beta \left(J_B\right)=0$ , but the pair $\left\{x\mathrm{,}{J}_B\right\}$ will be an optimal SF-solution if $\beta \left(x\right)=\mathrm{<mi>\; </mi>}\beta \left(J_B\right)=0$ , so the optimality of the feasible solution x can be not identified if it is examined with an unfit support, because in this case there will be $\beta \left(J_B\right)\ne 0$ , and $\beta \left(x\mathrm{,}{J}_B\right)\ne 0$ .

・ As $\beta \left(J_B\right)=\varphi \left(\lambda \right)-\varphi \left({\lambda }^0\right)$ , then the support $J_B$ will be optimal if its accompanying dual feasible solution λ is optimal solution for the dual problem D.

3.17. Theorem 3 (Existence of an Optimal Support)

For each problem (P), there is always an optimal support.

Proof

As (P) has an optimal solution, its dual (D) given by (30) has also an optimal solution, let $\overline{\lambda }=\left(\overline{y}\mathrm{,}\overline{v}\mathrm{,}\overline{w}\right)$ this solution, and define the sets:

$I^{+}=\left\{j\in J\mathrm{<mo>\; /\; </mo>}\left(c_j-a_j^{\text{T}}\overline{y}\right)\ge 0\right\}$ , $I^{-}=\left\{j\in J\mathrm{<mo>\; /\; </mo>}\left(c_j-a_j^{\text{T}}\overline{y}\right)\le 0\right\}$ ,

and

$\overline{C}=\left\{y\in R^m\mathrm{<mo>\; /\; </mo>}\left(c_j-a_j^{\text{T}}y\right)\ge \mathrm{0,}\forall i\in I^{+}\text{and}\left(c_j-a_j^{\text{T}}y\right)\le \mathrm{0,}\forall i\in I^{-}\right\}$ ,

we have $\overline{y}\in \overline{C}$ .

Let $y\in \overline{C}$ , and define the following linear problem:

$\left(\overline{D}\right)\{\begin{array}{l}min\psi \left(y\right)=b^{\text{T}}y+\sum _{j\in J^{+}}{d}_j^{+}\left(c_j-a_j^{\text{T}}y\right)+\sum _{j\in J^{-}}{d}_j^{-}\left(c_j-a_j^{\text{T}}y\right)\hfill \\ y\in \overline{C}\subset R^m\hfill \end{array}$ (35)

We have $\psi \left(y\right)=\varphi \left(y\mathrm{,}v\mathrm{,}w\right)$ , where $\left(y\mathrm{,}v\mathrm{,}w\right)$ is the coordinated dual feasible point to the vector y, and $\overline{y}$ is an optimal feasible solution of the problem ( $\overline{D}$ ).

On the other hand, there exists a “vertex” $y^{\mathrm{<mo>\; *\; </mo>}}$ of the set $\overline{C}$ that is an optimal feasible solution for ( $\overline{D}$ ), and this vertex is the intersection of at least m hyperplane $a_j^{\text{T}}{y}^{*}=c_j,j\in \left(I^{+}\cup I^{-}\right)$ .

Put $J_B=\left\{i\in \left(I^{+}\cup I^{-}\right)\mathrm{<mo>\; /\; </mo>}{a}_j^{\text{T}}{y}^{\mathrm{<mo>\; *\; </mo>}}=c_j\right\}$ where $\left|J_B\right|=m$ .

Then: $A^{\text{T}}\left(I\mathrm{,}{J}_B\right)y^{\mathrm{<mo>\; *\; </mo>}}=c_B$ , and so: $y^{\mathrm{<mo>\; *\; </mo>}}=c_B^{\text{T}}{A}_B^{-1}$ , further the coordinated dual feasible point to $y^{\mathrm{<mo>\; *\; </mo>}}$ is the dual feasible solution accompanying the support $J_B$ , and its optimal feasible solution for the problem (D), then, according to the proposition (4), we conclude that $J_B$ is an optimal support for (P).

4. The Description of the Pivot Adaptive Method “PAM”

As the Simplex Method, to solve the problem (P), the adaptive method (and therefore also the pivot adaptive method) has two phases: the initialization phase, and the second phase, we will detail each one in the following.

1) The initialization phase:

In this phase an initial support feasible solution SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ will be determined, and thus the matrix G defined in (9).

We assume that $b_i\ge \mathrm{0,}\forall i\in I$ , and $d_j^{-}=0,\forall j\in J$ .

Remark 1

Notice that each problem (P) can be reduced to this case,i.e.:
$b_i\ge \mathrm{0,}\forall i\in I$ ,and $d_j^{-}=\mathrm{0,}\forall j\in J$ ,in fact:

a) if $\exists i^0\in I/b_{i^0}<0$ then both term of the corresponding constraint is multiplied by (−1).

b) if $\exists k\in J\mathrm{<mo>\; /\; </mo>}{d}_k^{-}\ne 0$ , then we do the change of variable: ${\left(x^{\prime }\right)}_k=x_k-d_k^{-}$ , then:

$0\le {\left(x^{\prime }\right)}_k\le d_k^{+}-d_k^{-}$ (36)

and the general constraints $Ax=b$ of (P) will be write as:

$a_1{x}_1+a_1{x}_1+\cdots +a_{k-1}{x}_{k-1}+a_k\left({x^{\prime }}_k+d_k^{-}\right)+a_{k+1}{x}_{k+1}+\cdots +a_n{x}_n=b$ (37)

where $\forall j\in J$ , $a_j$ is the j^th column of the matrix A, from this relation we obtain:

$a_1{x}_1+a_1{x}_1+\cdots +a_{k-1}{x}_{k-1}+a_k{x^{\prime }}_k+a_{k+1}{x}_{k+1}+\cdots +a_n{x}_n=b-a_k{d}_k^{-}$ (38)

in (36), if $\left(b-a_k{d}_k^{-}\right)<0$ we multiple the two terms by (−1).

Then to determine an initial SF-solution to the problem (P), define the artificial problem of (P) as follows:

$\left(\tilde{P}\right)\{\begin{array}{l}\max F\left(\tilde{x}\right)=-\sum _{j=1}^{j=m}{\tilde{x}}_j\hfill \\ Ax+\tilde{x}=b\hfill \\ d^{-}\le x\le d^{+},0\le \tilde{x}\le b\hfill \end{array}$ (39)

where $b_i\ge \mathrm{0,}\forall i\in I$ , and $\tilde{x}=\tilde{x}\left(J\right)=\left({\tilde{x}}_i\mathrm{,}i\in I\right)=\left({\tilde{x}}_1\mathrm{,}{\tilde{x}}_2\mathrm{,}\cdots \mathrm{,}{\tilde{x}}_m\right)$ are the m artificial variables added to the problem (P).

We resolve the artificial problem $\tilde{P}$ with the “pivot adaptive method” starting with the obvious initial feasible solution: $\left(x,\tilde{x}\right),x=0_{R^n},\tilde{x}=b$ , and the canonical support (determined by the indices of the artificial variables), and we take the matrix $\Gamma =A$ .

If H is not empty, at the optimum of $\tilde{P}$ $\tilde{x}=0$ , $Ax=b$ , and $d^{-}\le x\le d^{+}$ , so x is a feasible solution of (P), and the optimal SF-solution of the problem $\tilde{P}$ can be taken as the initial SF-solution for the problem P.

2) The second phase:

Assume that an initial SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ of the problem (P) is found in the initialization phase, and let G the correspondent matrix computed by (9), $ϵ\ge 0$ an arbitrary number, the problem will be solved with the pivot adaptive method that we describe in the following.

At the iterations of the pivot adaptive method the transfer $\left\{x\mathrm{,}{J}_B\right\}\to \left\{\overline{x}\mathrm{,}{\overline{J}}_B\right\}$ from one SF-solution to a new one is carried out in such a way that:

$\beta \left(\overline{x}\mathrm{,}{\overline{J}}_B\right)\le \mathrm{<mi>\; </mi>}\beta \left(x\mathrm{,}{J}_B\right)$ (40)

the transfer will be realized as two procedures making up the iteration:

i) The procedure of the feasible solution change $x\to \overline{x}$ :

During this procedure we decrease the degree of non-optimality of the feasible solution: $\beta \left(\overline{x}\right)\le \mathrm{<mi>\; </mi>}\beta \left(x\right)$ , and then improve the primal criterion $F\left(\overline{x}\right)\ge F\left(x\right)$ :

i.1) compute the support gradient δ by (10), and the suboptimality estimate by (27).

i.2) If $\beta \left(x\mathrm{,}{J}_B\right)\le \epsilon$ , then stop the resolution with: x is an ò-optimal feasible solution for (P) (P).

i.3) If $\beta \left(x,J_B\right)>\epsilon$ , we compute the non-support components ${\chi }_N$ of the primal pseudo-feasible solution accompanying the support $J_B$ by (12), and the search direction $l=\left(l_B,l_N\right)$ with:

$\{\begin{array}{l}{l}_N={\chi }_N-x_N\hfill \\ l_B=-{\Gamma }_N{l}_N\hfill \end{array}$ (41)

i.4) Find the primal step length ${\theta }^0$ with:

${\theta }^0=min\left\{\mathrm{1,}{\theta }_{j_0}\right\}\mathrm{,}\text{where}\mathrm{<mo>\; :\; </mo>}{\theta }_{j_0}=\underset{j\in J_B}{min}{\theta }_j\mathrm{,}{\theta }_j=(\begin{array}{l}\frac{d_j^{+}-x_j}{l_j}\mathrm{,}\text{if}{l}_j>\mathrm{0\; <mo>\; ;\; </mo>}\hfill \\ \frac{d_j^{-}-x_j}{l_j}\mathrm{,}\text{if}{l}_j<\mathrm{0\; <mo>\; ;\; </mo>}\hfill \\ \infty \mathrm{<mo>\; ;\; </mo>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\text{if}{l}_j=0.\hfill \end{array}\left(j\in J_B\right)$ (42)

Let $j_{00}$ such that: $J_B\left(j_{00}\right)=j_0$ which is the position of $j_0$ in the vector of indices $J_B$ .

i.5) Compute the new feasible solution: $\overline{x}=x+{\theta }^{0}l$ , and $F\left(\overline{x}\right)=F\left(x\right)+{\theta }^0\beta \left(x\mathrm{,}{J}_B\right)$ .

i.6) If ${\theta }^0=1$ , then stop the resolution with: $\left\{\overline{x}\mathrm{,}{J}_B\right\}$ is the optimal SF-solution of (P).

i.7) If ${\theta }^0<1$ , then compute:

$\beta \left(\overline{x}\mathrm{,}{J}_B\right)=\left(1-{\theta }^0\right)\beta \left(x\mathrm{,}{J}_B\right)$ (43)

i.8) If $\beta \left(\overline{x}\mathrm{,}{J}_B\right)\le ϵ$ , then stop the resolution with: $\left\{\overline{x}\mathrm{,}{J}_B\right\}$ is the ò-optimal SF-solution of (P).

i.9) if $\beta \left(\overline{x},J_B\right)>ϵ$ , then go to ii) to change the support $J_B$ to ${\overline{J}}_B$ .

ii) The procedure of the support change $J_B\to {\overline{J}}_B$ :

During this procedure we decrease the degree of non-optimality of the support: $\beta \left({\overline{J}}_B\right)\le \mathrm{<mi>\; </mi>}\beta \left(J_B\right)$,and then improve the dual criterion $\varphi \left(\overline{\lambda }\right)\ge \varphi \left(\lambda \right)$ , where $\overline{\lambda }$ is the dual feasible solution accompanying the support ${\overline{J}}_B$ , and $\lambda$ is the dual feasible solution accompanying the support $J_B$ .

In this procedure there are two rules to change support: rule of “the short step”, and rule of “the long step”, the two rules will be presented.

ii.1) to the $j_0$ found in (i.4), compute ${\chi }_{j_0}=x_{j_0}+l_{j_0}$ , and ${\alpha }_0={\chi }_{j_0}-{\overline{x}}_{j_0}$ .

ii.2) compute the dual direction t with:

$\{\begin{array}{l}{t}_{j_0}=-sign\left({\alpha }_0\right);\\ t_j=0,\mathrm{<mi>\; </mi>}j\in J_B\backslash \left\{j_0\right\};\\ t_N^{\text{T}}=t_B^{\text{T}}{\Gamma }_N.\end{array}$ (44)

ii.3) compute:

${\sigma }_j=\{\begin{array}{l}\frac{{\delta }_j}{t_j}\mathrm{,}\text{if}{\delta }_j{t}_j>\mathrm{0\; <mo>\; ;\; </mo>}\\ \mathrm{0,\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\text{if}{\delta }_j=0,t_j<0,{\xi }_j=d_j^{-}\mathrm{<mo>\; ;\; </mo>}\\ \mathrm{0,\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\text{if}{\delta }_j=0,t_j>0,{\xi }_j=d_j^{+}\mathrm{<mo>\; ;\; </mo>}\\ \infty \mathrm{,\; <mi>\; </mi>\; <mi>\; </mi>}\text{inothercases}\mathrm{.}\end{array}\left(j\in J_N\right)$ (45)

and arrange the obtained values in increasing order as:

${\sigma }_{j_1}\le {\sigma }_{j_2}\le \cdots \le {\sigma }_{j_p},\mathrm{<mi>\; </mi>}{j}_k\in J_N,\mathrm{<mi>\; </mi>}{\sigma }_{j_k}\ne \infty ,\mathrm{<mi>\; </mi>}k\in \left\{1,\cdots ,p\right\}.$ (46)

As was said before, the change of support can be done with two different rules, to use the “short step rule” go to a), and to use the “long step rule” go to b).

a) Change of the support with the “short step rule”:

a.1) From (46) put:

${\sigma }^0={\sigma }_{j_1}={\sigma }_{j^{*}}=\underset{j\in J_N}{\min }{\sigma }_j.$ (47)

Let $j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}$ such that: $J_N\left(j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ which is the position of $j^{\mathrm{<mo>\; *\; </mo>}}$ in the vector of indices $J_N$ .

Put: ${\overline{J}}_B=\left(J_B\backslash \left\{j_0\right\}\right)\cup \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}$ , ${\overline{J}}_N=\left(J_N\backslash \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}\right)\cup \left\{j_0\right\}$ , then ${\overline{J}}_B\left(j_{00}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ , ${\overline{J}}_N\left(j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}\right)=j_0$ .

a.2) Compute:

$\begin{array}{c}\overline{\delta }=\delta -{\sigma }^{0}t,\mathrm{<mi>\; </mi>}\\ \beta \left(\overline{x},{\overline{J}}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\overline{x},J_B\right)+{\sigma }^0{\alpha }_0\end{array}$ (48)

go to ii.4).

b) Change of the support with the “long step rule”:

b.1) for every $j_k\mathrm{,}k\in \left\{\mathrm{1,}\cdots \mathrm{,}p\right\}$ of (47) compute

$\Delta {\alpha }_{j_k}=\left|{\Gamma }_{j_{00}{j}_k}\right|\left(d_{j_k}^{+}-d_{j_k}^{-}\right)$ (49)

b.2) as $j^{\mathrm{<mo>\; *\; </mo>}}$ we choose $j_q$ such that

${\alpha }_{j_{q-1}}=\left[{\alpha }_0+\sum _{k=1}^{k=q-1}\Delta {\alpha }_{j_k}\right]<0,\mathrm{<mi>\; </mi>}{\alpha }_{j_q}=\left[{\alpha }_0+\sum _{k=1}^{k=q}\Delta {\alpha }_{j_k}\right]\ge 0$ (50)

Let $j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}$ such that: $J_N\left(j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ which is the position of $j_0$ in the vector of indices $J_B$ .

b.3) put: ${\sigma }^0={\sigma }_{j^{*}}$ , and ${\overline{J}}_B=\left(J_B\backslash \left\{j_0\right\}\right)\cup \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}$ , ${\overline{J}}_N=\left(J_N\backslash \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}\right)\cup \left\{j_0\right\}$ , then ${\overline{J}}_B\left(j_{00}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ , ${\overline{J}}_N\left(j_{**}\right)=j_0$ .

b.4) Compute:

・ $\overline{\delta }=\delta -{\sigma }^{0}t$ .

・ $\beta \left(\overline{x},{\overline{J}}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\overline{x},J_B\right)+\sum _{k=1}^{k=q}{\alpha }_{j_{k-1}}\left({\sigma }_{j_k}-{\sigma }_{j_{k-1}}\right)$ where: ${\alpha }_{j_0}={\alpha }_0$ , ${\sigma }_{j_0}=0$ .

Go to ii.4). ii.4) compute $\overline{\Gamma }$ as follows:

$\{\begin{array}{l}{\overline{\Gamma }}_{j_{00}j}=\frac{{\Gamma }_{j_{00}j}}{{\Gamma }_{j_{00}{j}^{*}}},\mathrm{<mi>\; </mi>\; <mi>\; </mi>}j\in J;\\ {\overline{\Gamma }}_{ij}={\Gamma }_{ij}-{\Gamma }_{i{j}^{*}}{\overline{\Gamma }}_{j_{00}j},\mathrm{<mi>\; </mi>\; <mi>\; </mi>}i\in I\backslash \left\{j_{00}\right\},j\in J.\end{array}$ (51)

${\Gamma }_{j_{00}{j}^{\mathrm{<mo>\; *\; </mo>}}}$ is “the pivot”. Go to ii.5).

ii.5) Set: $x=\overline{x}$ , $J_B={\overline{J}}_B$ , $\beta \left(x\mathrm{,}{J}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\overline{x}\mathrm{,}{\overline{J}}_B\right)$ , $\delta =\overline{\delta }$ , and $\Gamma =\overline{\Gamma }$ . Go to i.2).

5. The Pivot Adaptive Method

Let $\left\{x\mathrm{,}{J}_B\right\}$ be an initial SF-solution for the problem (P), G the matrix computed by (9), and $ϵ\ge 0$ are given.

The “Pivot Adaptive Method” (rule of the “short step” and rule of “the long step” are presented) is summarized in the following steps:

Algorithm 1 (The Pivot Adaptive Method)

1) compute the support gradient ${\delta }^{\text{T}}$ by (10), and $\beta \left(x\mathrm{,}{J}_B\right)$ by (27).

2) if $\beta \left(x\mathrm{,}{J}_B\right)\le ϵ$ , then STOP with: x is an ò-optimal feasible solution for (P).

3) if $\beta \left(x\mathrm{,}{J}_B\right)>ϵ$ , then compute the non-support components ${\chi }_N$ of the primal pseudo-feasible solution accompanying the support $J_B$ by (12), and the search direction l with (41).

4) find the primal step length ${\theta }^0$ with (42). Let $j_{00}$ such that: $J_B\left(j_{00}\right)=j_0$ which is the position of $j_0$ in the vector of indices $J_B$ .

5) Compute the new feasible solution: $\overline{x}=x+{\theta }^{0}l$ , and $F\left(\overline{x}\right)=F\left(x\right)+{\theta }^0\beta \left(x\mathrm{,}{J}_B\right)$ .