����������� ������ 54 (2002), 203–210

UDK 512.644

���������� ������ ��� research paper

TRANSFORMATIONS OF DUAL PROBLEM AND DECREASING DIMENSIONS IN LINEAR PROGRAMMING

Nebojša V. Stojković and Predrag S. Stanimirović

Abstract. We investigate behavior of the potential function in a modification of the Mehrotra’s primal-dual algorithm. This modification reduces dimensions of the problem and eliminates need for the finite termination algorithm. Numerical results on some examples from the Netlib test set are provided.

We also regard problems about applying a stabilization procedure proposed by Kovačević-Vujčić and Ašić in the Mehrotra’s primal dual interior-point algorithm for linear programming. Transformations of the dual problem required for the application of the stabilization procedure are considered.

1. Introduction

Primal-dual algorithms investigate linear programming problem in the standard form as

minimize c^{T} x subject to Ax = b, x ≥ 0,  (1.1)

where c, x ∈ ℝ^{n}, b ∈ ℝ^{m}, A is an m × n real matrix and c^{T} is transpose of the vector c. The dual problem for (1.1) is

maximize b^{T} λ subject to A^{T} λ + s = c, s ≥ 0,  (1.2)

where λ ∈ ℝ^{m} and s ∈ ℝ^{n} and b^{T}, A^{T} denote transpose of the vector b and the matrix A, respectively. It is known that the vector x^{∗} ∈ ℝ^{n} is a solution of (1.1) if and only if there exist vectors s^{∗} ∈ ℝ^{n} and λ^{∗} ∈ ℝ^{m} such that the following conditions hold:

A^{T} λ^{∗} + s^{∗} = c,  Ax^{∗} = b,  (1.3a-b)
x_{i}^{∗}s_{i}^{∗} = 0, i = 1,…, n,  (x^{∗}, s^{∗}) ≥ 0.  (1.3c-d)

The central path C is an arc of strictly feasible points that plays a vital role in the theory of primal-dual algorithms. It is parametrized by a scalar τ > 0, such that each point (x_{τ} , λ_{τ} , s_{τ}) ∈ C solves the following system:

AMS Subject Classification: 90 C 05

Keywords and phrases: Primal-dual interior point methods, potential function.

Communicated at the 5th International Symposium on Mathematical Analysis and its Applications, Niška banja, Yugoslavia, October, 2–6, 2002.

A^{T} λ + s = c,  Ax = b,  (1.4a-b)
x_{i}s_{i} = τ, i = 1,…, n,  (x, s) ≥ 0.  (1.4c-d)

Instead of the complementarity conditions (1.3c), in (1.4) it is required that the pairwise products x_{i}s_{i} have the same value for all indices i. From (1.4) we can define the central path as

C = {(x_{τ} , λ_{τ} , s_{τ}) | τ > 0}.

The primal-dual feasible set F and strictly feasible set F^{0} are defined by (see [7])

\begin{aligned}F & = \{(x, λ, s) | Ax = b, A^{T} λ + s = c, (x, s) ≥ 0\}, \\ F & = \{(x, λ, s) | Ax = b, A^{T} λ + s = c, (x, s) > 0\}. \end{aligned}

The paper is organized as follows. In the second section we consider behavior of the potential-reduction function caused by the elimination of columns and rows of the matrix A, corresponding to zero variables. This part of the paper is a continuation of the paper [6]. The motivation for this section is based on the fact that reducing dimensions of the problem improves the stability and centrality of iterative sequence. We show that reducing dimension decrease the potential function Φ_{ρ}. In the third section we investigate transformations of the dual problem caused by the stabilization procedure introduced in [3]. In the last section we show the decreasing of the potential-reduction function in several known test problems.

2. Reduction of linear programming problem and potential function

In sequel we regard the linear programming problem in the general form

minimize c_{1}x_{1} + ⋯ + c_{k}x_{k}
subject to ∑_{j=1}^{k} a_{ij}x_{j} ≤ b_{i}, i = 1,…, q,

∑_{j=1}^{k} a_{ij}x_{j} = b_{i}, i = q + 1,…, m,

x_{j} ≥ 0, j = 1,…, k.

(2.1)

Standard form of (2.1) is (with k + q = n)

minimize c_{1}x_{1} + ⋯ + c_{k}x_{k} + c_{k+1}x_{k+1} + ⋯ + c_{n}x_{n}
subject to ∑_{j=1}^{k} a_{ij}x_{j} + x_{k+i} = b_{i}, i = 1,…, q,

∑_{j=1}^{k} a_{ij}x_{j} = b_{i}, i = q + 1,…, m,

x_{j} ≥ 0, j = 1,…, n.

(2.2)

The dual problem for (2.2) is

maximize b_{1}λ_{1} + ⋯ + b_{m}λ_{m}
subject to ∑_{j=1}^{m} a_{ji}λ_{j} + s_{i} = c_{i}, i = 1,…, k
λ_{j} + s_{k+j} = 0, j = 1,…, q
s_{i} ≥ 0, i = 1,…, k + q.

(2.3)

It is clear that if x_{i} = 0 for some i, then this x_{i} has no influence on the final solution, so i-th column from the matrix A can be omitted. Also, if s_{k+j} = 0 for some j, then from (2.3) it follows λ_{j} = 0, so jth column and (k + j)-th row from the matrix A^{T} can be omitted. These facts imply the next two statements from [6]. For the sake of simplicity we use the following notations. Let α = {α_{1},…, α_{s}} and β = {β_{1},…, β_{t}} be subsets of {1,…, m} and {1,…, n}, respectively, for some integers 1 ≤ s ≤ m and 1 ≤ t ≤ n. By A^{α} we denote the p × n submatrix of A determined by the entries in rows indexed by α. Similarly, by A_{β} we denote the m × q submatrix of A determined by the entries in columns indexed by β.

Lemma 2.1. [6] Consider the linear programming problem (2.2),(2.3). Assume that x_{i_{1}} =⋯=x_{i_{d}} =0, and consider the set of indices I ={i_{1},…, i_{d}}⊆{1,…, n}. Denote by Â ∈ ℝ^{m×(n−d)} the matrix A_{{1,... ,n}\I}, and let x̂, ĉ, ŝ ∈ ℝ^{n−d} be, respectively, vectors x, c and s without i-th (i ∈ I) coordinates (x̂ = x_{{1,... ,n}\I}, ĉ = c_{{1,... ,n}\I} and ŝ = s_{{1,... ,n}\I}). By φ_{i}(λ) we denote the linear function

φ_{i}(λ) = c_{i} − (a_{1i}λ_{1} + ⋯ + a_{mi}λ_{m}), i ∈ I.

Then the primal-dual problem (2.2), (2.3) is equivalent to minimize ĉ^{T} x̂ subject to Âx̂ = b, x̂ ≥ 0, x_{i} = 0, i ∈ I,

maximize b^{T} λ subject to Â^{T} λ + ŝ = ĉ, ŝ ≥ 0, s_{i} = φ_{i}(λ), i ∈ I,

where Â^{T} is the transpose of Â.

Lemma 2.2. [6] Assume that in the primal-dual problem (2.2),(2.3) the identities s_{k+j_{1}} = ⋯ = s_{k+j_{h}} = 0 are satisfied. Consider the sets J = {j_{1},…, j_{h}} and J^{k} = {k + j| j ∈ J}. Denote by Â^{T} ∈ ℝ^{(n−h)×(m−h)} the matrix

(A^{T})_{{1,... ,m}\J}^{{1,... ,n}\J^{k}} = (A_{{1,... ,n}\J^{k}}^{{1,... ,m}\J})^{T} .

Let x̂, ĉ, ŝ ∈ ℝ^{n−h} be, respectively, vectors x, c, s without (k + j)th (j ∈ J) coordinates, and let λ̂, b̂ ∈ ℝ^{m−h} be, respectively, vectors λ, b without jth (j ∈ J) coordinates. By ψ_{j}(x̂) denote the linear function

ψ_{j}(x̂) = b_{j} − ∑_{i=1, i∉J^{k}}^{n} a_{ji}x_{i}, j ∈ J.

Then the primal-dual problem (2.2),(2.3) is equivalent to minimize ĉ^{T} x̂ subject to Âx̂ = b̂, x̂ ≥ 0, x_{k+j} = ψ_{j}(x̂), j ∈ J,

maximize b̂^{T} λ̂ subject to Â^{T} λ̂ + ŝ = ĉ, ŝ ≥ 0, s_{k+j} = 0, j ∈ J,

where Â = A_{{1,... ,n}\J^{k}}^{{1,... ,m}\J}.

The following statement summarizes the results of above lemmas.

Theorem 2.1. [6] Let x_{i_{1}} = ⋯ = x_{i_{d}} = 0 and s_{k+j_{1}} = ⋯ = s_{k+j_{h}} = 0, where the sets I = {i_{1},…, i_{d}} and J = {j_{1},…, j_{h}} are defined as in Lemma 2.1 and Lemma 2.2, respectively. Under the notations of Lemma 2.1 and Lemma 2.2 the primal-dual problem (2.2)-(2.3) is equivalent to

minimize ĉ^{T} x̂ subject to Âx̂=b̂, x̂≥0, x_{i} =0, i∈I, x_{k+j} =ψ_{j}(x̂), j ∈J,

maximize b̂^{T} λ̂ subject to Â^{T} λ̂+ŝ=ĉ, ŝ≥0, s_{k+j} =0, j ∈J, s_{i} =φ_{i}(λ̂), i∈I,

where Â ∈ ℝ^{(m−h)×(n−h−d)}, x̂, ĉ, ŝ ∈ ℝ^{n−h−d}, λ̂, b̂ ∈ ℝ^{m−h}.

Remark 2.1. Theorem 2.1 is a generalization of Theorem 3.1, part (b), proved in [5].

The ability to identify zero variables early on in an iterative method is of considerable value and can be used to computational advantage. The paper [2] gives a formal presentation of the notion of indicators for identifying zero variables, and also studies various indicators. About the numerical experience with various indicators for identifying zero variables see also the paper [4]. The term indicator denotes a function that identifies constraints that are active at a solution of a constrained optimization problem. If some members of a solution x^{∗} are identified early on in an iterative procedure, this information can be used as follows:

1. Reduce dimension of the problem by dropping the columns od A corresponding to zero variables.

2. Help recover an optimal basis for the linear program.

3. Help obtain very accurate solutions.

The reduction of dimension of the problem by dropping the columns of the matrix A corresponding to zero variables is investigated in [2] and [4]. We consider the influence of the elimination of columns and rows in the decreasing the potential function Φ_{ρ}.

Potential-reduction methods use a logarithmic potential function to measure the worth of each point in F^{0} and aim to achieve a certain fixed reduction in this function at each iteration. The most interesting primal-dual potential function is Tanabe-Todd-Ye function Φ_{ρ}, defined by

Φ_{ρ}(x, s) = ρ log x^{T} s − ∑_{i=1}^{n} log x_{i}s_{i}

for some parameter ρ > n. In the next theorem we investigate the influence of reductions enabled by Theorem 2.1 to the function Φ_{ρ}.

Theorem 2.2. Suppose that the central path is not followed and suppose that x_{j}s_{j} < ε < 1 for some j ∈ J ⊂ {1,…, n} and x_{i}s_{i} ≥ ε, i ∉ J. If it is possible to eliminate x_{j} (or s_{j}, for some j > k) and to eliminate j-th columns from the matrix A (j-th rows and (j − k)-th columns from the matrix A^{T}), then

log (1 + \frac{∑_{j∈J} x_{j}s_{j}}{∑_{i∉J} x_{i}s_{i}} )^{ρ} − |J| log ε ≤ Φ_{ρ}(x, s) − Φ̂_{ρ}(x̂, ŝ)

≤ log (1 + \frac{|J|}{n − |J|})^{ρ} − ∑_{j∈J} log x_{j}s_{j}.

Proof. Applying Lemma 2.1 (Lemma 2.2) we can eliminate x_{j}, (s_{j}) and jth columns from the matrix A (j-th rows and (j − k)th columns from the matrix A^{T}). Let Φ̂_{ρ}(x̂, ŝ) = ρ log x̂^{T} ŝ−∑_{i∉J} log x_{i}s_{i} be the potential-reduction function of reduced problem, where x̂ and ŝ denote the vectors x and s without j-th elements, respectively. Then we have

Φ_{ρ}(x, s) − Φ̂_{ρ}(x̂, ŝ) = ρ(log x^{T} s − log x̂^{T} ŝ) − ∑_{j∈J} log x_{j}s_{j}

= ρ log (1 + \frac{∑_{j∈J} x_{j}s_{j}}{∑_{i∉J} x_{i}s_{i}} ) − ∑_{j∈J} log x_{j}s_{j}

≥ ρ log (1 + \frac{∑_{j∈J} x_{j}s_{j}}{∑_{i∉J} x_{i}s_{i}} ) − |J| log ε.

On the other side, since

ρ log (1 + \frac{∑_{j∈J} x_{j}s_{j}}{∑_{i∉J} x_{i}s_{i}} ) ≤ ρ log (1 + \frac{|J|ε}{(n − |J|)ε})

we have

Φ_{ρ}(x, s) − Φ̂_{ρ}(x̂, ŝ) ≤ log (1 + \frac{|J|}{n − |J|})^{ρ} − ∑_{j∈J} log x_{j}s_{j},

which completes the proof.

3. Transformation of dual problem

The next procedure is proposed in [3] for stabilization of ill-conditioned linear programming problem. This stabilization procedure is based on the Gaussian elimination.

Procedure 3.1. Step 1. For a given k let j(1),…, j(n) be the indices satisfying conditions (x_{j(1)}^{k}/s_{j(1)}^{k})≥⋯≥(x_{j(n)}^{k}/s_{j(n)}^{k}), and let ĥ ∈ {1,…, n − 1} be the smallest index such that (x_{j(ĥ+1)}^{k}/s_{j(ĥ+1)}^{k})<1.

Step 2. Order the columns of A and c^{T} so that the j(p)-th column comes to the p-th position, p = 1,…, n. Set p = 1, q = 1.

Step 3. Find |a_{i(p),p}| = max{|a_{ip}|, i = q,…, m}. If |a_{i(p),p}| ≠ 0 go to Step 5.

Step 4. If |a_{i(p),p}| = 0 and p = ĥ set r̂ = q − 1 and RETURN. Otherwise replace p by p + 1 and go to Step 3.

Step 5. Exchange the i(p)-th and q-th row in A and b. Using a_{qp} as the pivot element eliminate a_{ip}, i = q + 1,…, m (if any) and c_{p}.

Step 6. If q = min{ĥ, m} or p = ĥ set r̂ = q and RETURN. Otherwise replace p by p + 1, q by q + 1 and go to Step 3.

In order to incorporate this procedure in primal-dual interior point method, we need corresponding modification of Step 5 in the stabilization procedure. This modification gives a specific transformation of the dual problem. We regard linear problem (1.1) with objective functions c^{T} x + d and b^{T} λ + d for primal and dual problem respectively.

Theorem 3.1. Suppose that the matrix A of linear problem (1.1), which satisfies c_{1} = ⋯ = c_{p−1} = 0, has a form

A = [ \begin{matrix}a_{11} & … & a_{1,p−1} & a_{1p} & … & a_{1n} \\ … & … & … & … & … & … \\ 0 & … & a_{q−1,p−1} & a_{q−1,p} & … & a_{q−1,n} \\ 0 & … & 0 & a_{qp} & … & a_{qn} \\ … & … & … & … & … & … \\ 0 & … & 0 & a_{mp} & … & a_{mn} \end{matrix} ] .  (3.1)

If we use a_{qp} as the pivot element to eliminate a_{ip}, i = q + 1,…, m, and c_{p} then the dual problem of transformed problem

minimize c′^{T} x + d′ subject to A′x = b′, x ≥ 0,

is

maximize b′^{T} λ′ + d′ subject to A′^{T} λ′ + s = c′, s ≥ 0,

where

d′ = d + \frac{c_{p}}{a_{qp}} b_{q}, λ′_{i} = λ_{i}, i ≠ q, λ′_{q} = λ_{q} + ∑_{i=q+1}^{m} \frac{a_{ip}}{a_{qp}} λ_{i} − \frac{c_{p}}{a_{qp}} .

Proof. As

b′_{i} = b_{i}, i = 1,…, q, b′_{i} = b_{i} − \frac{a_{ip}}{a_{qp}} b_{q}, i = q + 1,…, m,

the value of dual objective function is

b′^{T} λ′ + d′ = ∑_{i=1}^{m} b′_{i}λ′_{i} + d′

= ∑_{i=1}^{q−1} b_{i}λ_{i} + b_{q}(λ_{q} + ∑_{i=q+1}^{m} \frac{a_{ip}}{a_{qp}} λ_{i} − \frac{c_{p}}{a_{qp}} ) + ∑_{i=q+1}^{m}(b_{i} − \frac{a_{ip}}{a_{qp}} b_{q})λ_{i} + d′

= ∑_{i=1}^{q} b_{i}λ_{i} + ∑_{i=q+1}^{m} \frac{a_{ip}}{a_{qp}} b_{q}λ_{i} − \frac{c_{p}}{a_{qp}} b_{q} + ∑_{i=q+1}^{m} b_{i}λ_{i} − ∑_{i=q+1}^{m} \frac{a_{ip}}{a_{qp}} b_{q}λ_{i} + d′

= b^{T} λ − \frac{c_{p}}{a_{qp}} b_{q} + d′ = b^{T} λ + d

Further, the elements of matrix A′^{T} λ′ have the form ∑_{i=1}^{m} a′_{ij}λ′_{i}, j = 1,…, n. Now we have

∑_{i=1}^{m} a′_{ij}λ′_{i} + s_{j} = ∑_{i=1}^{m} a_{ij}λ_{i} + s_{j} = 0 = c′_{j}, j = 1,…, p − 1,
∑_{i=1}^{m} a′_{ip}λ′_{i} + s_{p} = ∑_{i=1}^{q−1} a_{ip}λ_{i} + a_{qp}(λ_{q} + ∑_{i=q+1}^{m} \frac{a_{ip}}{a_{qp}} λ_{i} − \frac{c_{p}}{a_{qp}} ) + s_{p}

= ∑_{i=1}^{m} a_{ip}λ_{i} + s_{p} − c_{p} = 0 = c′_{p},

∑_{i=1}^{m} a′_{ij}λ′_{i} + s_{j} = ∑_{i=1}^{q−1} a_{ij}λ_{i} + a_{qj}(λ_{q} + ∑_{i=q+1}^{m} \frac{a_{ip}}{a_{qp}} λ_{i} − \frac{c_{p}}{a_{qp}} ) + ∑_{i=q+1}^{m}(a_{ij} − \frac{a_{qj}}{a_{qp}} a_{ip})λ_{i}

+ s_{j} = ∑_{i=1}^{m} a_{ij}λ_{i} + s_{j} − \frac{a_{qj}}{a_{qp}} c_{p} = c_{j} − \frac{a_{qj}}{a_{qp}} c_{j} = c′_{j}, j = p + 1,…, n.

Remark 3.1. It is obvious that the form (3.1) of the matrix A is not restrictive because, if a_{11} is the pivot element for arbitrary matrix A and arbitrary c, we immediately get the matrix of the form (3.1) and after applying the transformation, matrix A′ has the same form.

4. Numerical experiences

The reduction of dimensions in Mehrotra’s algorithm is implemented in the package MATHEMATICA. In the next examples we consider a small subset of known test problems in the literature. We use notation delta = Φ_{ρ}(x, s) − Φ̂_{ρ}(x̂, ŝ). Note that practical value of ρ are n + \sqrt{n}, 10n or n + n^{1.5}. In the following examples we used compromise value ρ = 2n.

Example 4.1. For the test problem Afiro we get the result arranged in the Table. Eliminating threshold is 10^{−1}. Note that in 8th iteration 35 variables are eliminated and we have considerable decreasing of the potential function. Column No iter. denotes the order number of the iteration when the elimination is applied, and in column No var. we give the number of eliminated variables. Afiro

Example 4.2. In the tables on the next page we give results for some Netlib test problems. We see that the potential-reduction function is considerably decreased when the elimination is applied.

5. Concluding remarks

We investigate the elimination of columns and constraints in the primal-dual interior point method which is mainly based on the Mehrotra’s algorithm, restated in [7], [1]. It is well known that reducing dimensions of the problem improve the stability and centrality of iterative sequence. We showed that reducing dimension decrease the potential function. In order to make numerical experience, we develop a research code for the implementation of the Mehrotra’s algorithm and the modification in the package MATHEMATICA.

We also investigate transformations of the dual problem, caused by Step 5 of the stabilization procedure introduced in [3].

REFERENCES

[1] E.D. Andersen, J. Gondzio, C. Mészáros and X. Xu, Implementation of interior point methods for large scale linear programming, Technical report, HEC, Université de Genève, 1996.

[2] A.S. El-Bakry, R.A.Tapia, and Y. Zhang, A study of indicators for identifying zero variables in interior-point methods, SIAM Rev. 36(1) (1994), 45–72.

[3] V.V. Kovačević-Vujčić and M.D. Ašić, Stabilization of interior-point methods for linear programming, Computational Optimization and Applications 14 (1999), 1–16.

[4] I.J. Lustig, R.E. Marsten and D.F. Shanno, Computational experience with a primal-dual interior point method for linear programming, Linear Algebra Appl., 152 (1991), 191–222.

[5] N.V. Stojković, and P.S. Stanimirović, Two direct method in linear programming, EJOR, 131 (2001), 417–439.

[6] N.V. Stojković, On the finite termination in the primal-dual algorithm for linear programming, YUJOR, 11 (2001), 31–40.

[7] S.J Wright, Primal-dual Interior-point Methods, SIAM, Philadelphia, 1997.

(received 19.12.2002)

Faculty of Economics, Trg Kralja Aleksandra 11, 18000 Niš, Yugoslavia, E-mail: nebojsas@orion.eknfak.ni.ac.yu

University of Niš, Faculty of Science, Department of Mathematics, Ćirila i Metodija 2, 18000 Niš, Yugoslavia, E-mail: pecko@pmf.pmf.ni.ac.yu