Abstract Generated abstract
This note proposes an iterative method for linear and quadratic programming problems with nonnegativity inequalities and linear equality constraints, extending the method of steepest descent to constrained extremal problems. For linear programming, the method defines dual estimates through a weighted least squares system depending on the current feasible point, constructs a feasible descent direction, and updates the point with a step length determined by the associated residual norm. The author states that any limit point of the generated sequence is an optimal solution, supported by properties ensuring preservation of constraints, decrease of the objective, positivity of iterates, and upper semicontinuity of the dual-estimate mapping. An analogous construction is then given for convex quadratic programming, with a modified residual and step selection based on the quadratic form.
Full Text
UDC 512.25/26 + 519.3:330.115
MATHEMATICS
I. I. Dikin
ITERATIVE SOLUTION OF PROBLEMS OF LINEAR AND QUADRATIC PROGRAMMING
(Presented by Academician L. V. Kantorovich, 19 VII 1966)
In the present note, problems of linear and quadratic programming are solved by a method that is an extension of the method of steepest descent \((^1)\) to certain extremal problems among whose constraints there are inequalities.
Consider the linear programming problem:
find the minimum
\[ \sum_{j=1}^{n} c_j x_j \]
under the conditions
\[ x_j \geqslant 0,\quad j=1,2,\ldots,n; \tag{1} \]
\[ \sum_{j=1}^{n} a_{ij}x_j=b_i,\quad i=1,2,\ldots,m, \tag{2} \]
where \(c=(c_1,c_2,\ldots,c_n)\) and \(x=(x_1,x_2,\ldots,x_n)\) are vectors of the \(n\)-dimensional Euclidean space \(E_n\); the rank of the matrix \(\|a_{ij}\|\) is equal to \(m\); \(b=(b_1,b_2,\ldots,b_m)\) is a vector from \(E_m\). Let \(T\subset E_n\) be the set of vectors satisfying conditions (1) and (2).
We shall call the dual estimates of \(x\in T\) the system of numbers
\[
u(x)=(u_1(x),u_2(x),\ldots,u_m(x)),
\]
satisfying the system of equations
\[ \sum_{t=1}^{m} b_{st}u_t=d_s, \tag{3} \]
where
\[ b_{st}=\sum_{j=1}^{n} x_j^2 a_{sj}a_{tj},\quad d_s=\sum_{j=1}^{n} x_j^2 c_j a_{sj},\quad s=1,2,\ldots,m. \]
Remark. The vector \((u_1(x),u_2(x),\ldots,u_m(x))\) is the solution of the problem: find
\[ \min_{u\in E_m}\sum_{j=1}^{n} x_j^2 \left(\sum_{i=1}^{m} a_{ij}u_i-c_j\right)^2 . \]
Let \(U(x)\) be the set of all solutions of system (3). Note that if \(x_j>0\) for \(j=1,2,\ldots,n\), then system (3) has a unique solution.
Set
\[ \Phi(x)=\sum_{j=1}^{n} x_j^2 \left(\sum_{i=1}^{m} a_{ij}u_i(x)-c_j\right)^2, \]
\[ s_j(x)=x_j^2\left(\sum_{i=1}^{m} a_{ij}u_i(x)-c_j\right). \]
We now give the algorithm for solving the linear programming problem. Let \(x_j^0>0\) for \(j=1,2,\ldots,n\); compute
\[
x_j^{k+1}=x_j^k+\lambda_k s_j(x^k)
\]
for \(j=1,2,\ldots,n\),
\[
\lambda_k=\frac{1}{\sqrt{\Phi(x^k)}}.
\]
Theorem. If \(\bar{x}\) is a limit point of the sequence \(\{x^k\}\), then \(\bar{x}\) is a solution of the linear programming problem.
The proof of the theorem follows from the validity of the following assertions, each of which is not difficult to establish.
-
\[ \sum_{j=1}^{n} a_{ij}s_j(x)=0,\quad i=1,2,\ldots,m. \]
-
\[ \sum_{j=1}^{n} c_js_j(x)=-\Phi(x). \]
-
If \(x>0\), then
\[ x+s(x)/\sqrt{\Phi(x)}>0. \] -
The mapping \(x\to U(x)\) is upper semicontinuous.
Suppose a quadratic programming problem is given: minimize
\[ \sum_{i=1}^{n}\sum_{j=1}^{n} b_{ij}x_i x_j-2\sum_{j=1}^{n} d_jx_j \]
subject to
\[ x_j\geq 0,\quad j=1,2,\ldots,n; \]
\[ \sum_{j=1}^{n} a_{ij}x_j=b_i,\quad i=1,2,\ldots,m, \]
where the matrix \(\|b_{ij}\|\) is nonnegative definite, the rank of the matrix \(\|a_{ij}\|\) is equal to \(m\), \(d=(d_1,d_2,\ldots,d_n)\) and \(x=(x_1,x_2,\ldots,x_n)\) are vectors in \(E_n\), and \(b=(b_1,b_2,\ldots,b_m)\) is a vector in \(E_m\).
Set
\[ r_j(x)=\sum_{i=1}^{n} b_{ij}x_i-d_j. \]
Construct a system of equations differing from (3) in that we replace \(c_j\) by \(r_j(x)\). From the new system find
\[ u(x)=(u_1(x),u_2(x),\ldots,u_m(x)). \]
Let
\[ \Phi(x)=\sum_{j=1}^{n} x_j^2\left(\sum_{i=1}^{m} a_{ij}u_i(x)-r_j(x)\right)^2, \]
\[ s_j(x)=x_j^2\left(\sum_{i=1}^{m} a_{ij}u_i(x)-r_j(x)\right). \]
The following algorithm is proposed for solving the quadratic programming problem. Let \(x^0>0\),
\[ x^{k+1}=x^k+\lambda_k s(x^k); \]
if
\[ \sum_{i=1}^{n}\sum_{j=1}^{n} b_{ij}s_i(x^k)s_j(x^k)>0, \]
compute
\[ \lambda_k'=-\sum_{j=1}^{n} r_j(x^k)s_j(x^k)\Bigg/\sum_{i=1}^{n}\sum_{j=1}^{n} b_{ij}s_i(x^k)s_j(x^k). \]
If
\[ \lambda_k'<1/\sqrt{\Phi(x^k)}, \]
set \(\lambda_k=\lambda_k'\). In all other cases take
\[ \lambda_k=1/\sqrt{\Phi(x^k)}. \]
A theorem analogous to the one formulated above is valid.
Institute of Mathematics
Siberian Branch of the Academy of Sciences of the USSR
Received
12 VII 1966
CITED LITERATURE
- L. V. Kantorovich, DAN, 56, 233 (1947).