Interior Point Methods Adapted to Improper Linear Programs
- PDF / 373,877 Bytes
- 9 Pages / 612 x 792 pts (letter) Page_size
- 26 Downloads / 230 Views
terior Point Methods Adapted to Improper Linear Programs L. D. Popov1,2 Received August 24, 2018; revised November 8, 2018; accepted November 12, 2018
Abstract—For linear programs, we consider schemes for the formation of a generalized central path, which arise under the simultaneous use of interior and exterior penalty terms in the traditional Lagrange function and the minimax problems generated by it. The advantage of the new schemes is that they do not require a priori knowledge of feasible interior points in the primal or dual problem. Moreover, when applied to problems with inconsistent constraints, the schemes automatically lead to some of their generalized solutions, which have an important applied content. Descriptions of the algorithms, their justification, and results of numerical experiments are presented. Keywords: linear programming, duality, penalty function methods, regularization methods, improper problems, central path.
DOI: 10.1134/S0081543820040148
INTRODUCTION Suppose that we have a pair of linear programs: the primal problem min{(c, x) : Ax = b, x ≥ 0}
(1)
max{(b, y) : AT y ≤ c},
(2)
and the dual problem where the vectors c ∈ Rn and b ∈ Rm and the matrix A = (aij )m×n are given, the vectors x ∈ Rn and y ∈ Rm correspond to the primal and dual variables, and (·, ·) denotes the inner product of vectors. The most efficient modern methods for solving linear programs (see, for example, [1–5]) are based on replacing the classical Lagrange function associated with the problem by its various extensions, in particular, by the extension Lμ1 (x, y) = (c, x) − (y, Ax − b) − μ
n
ln xi ,
i=1 1
Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia 2 Ural Federal University, Yekaterinburg, 620002 Russia e-mail: [email protected]
S116
INTERIOR POINT METHODS
S117
where the first two terms correspond to the classical Lagrange function, the third term is an interior penalty function corresponding to the requirement of nonnegativity of the primal variables, and μ > 0 is a small parameter. Define Rn++ = {x ∈ Rn : x > 0}. Under certain additional conditions, which will not be x(μ), y¯(μ)] with respect to the discussed here, the function Lμ1 (x, y) has a unique saddle point [¯ n m ¯(μ) and y¯(μ) is the solution of its own problem domain R++ × R , and each of its components x from the standard pair of minimax problems generated by the function Lμ1 (x, y): min max Lμ1 (x, y) = min Φμ (x),
(3)
max min Lμ1 (x, y) = max Φ∗μ (y).
(4)
x
y
y
x
x
y
Recall the specific form of objective functions in problems (3) and (4). Since ∇x Lμ1 (x, y) = c − AT y − μ diag(x)−1 e = 0 for x(y) = μ diag(c − AT y)−1 e, it follows that Φ∗μ (y)
=
min Lμ1 (x, y) x
=
Lμ1 (x(y), y)
= (b, y) + μ
n
ln(ci − (Ai , y)) + ν0 ;
i+1
here A1 , A2 , . . . , An are the columns of the matrix A, diag(z) is a diagonal matrix with the elements zi of the vector z on its diagonal, and e = [1, 1, . . . , 1]T is the vector of appropriate dimension composed of ones
Data Loading...
