Author's summary: "In linear programming the simple upper bound method (SUB in short) is well known. It is a modification of the simplex method which finds a minimum of the target function on an admissible set with some additional conditions of the form β≤x≤α imposed on x. "In this paper we present a method which solves the problem of minimization of a quadratic, convex target function on an admissible set defined by conditions of the form β≤x≤α. It is a modification of the C. E. Lemke algorithm [Management Sci. 8 (1961/62), 442–453; MR0148483] for problems of quadratic programming. Because of the special form of the conditions defining the admissible set this method is in a sense a counterpart of the SUB method in linear programming. Therefore we call the algorithm the SUBQ algorithm (the simple upper bound algorithm for quadratic programming). "In Section 2 we give a description of the method based mainly on a geometric interpretation. In Section 3 we present the algorithm and in Section 4 we give a proof of the convergence of the method.''
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The strictly convex quadratic programming problem is transformed to the least distance problem - finding the solution of minimum norm to the system of linear inequalities. This problem is equivalent to the linear least squares problem on the positive orthant. It is solved using orthogonal transformations, which are memorized as products. Like in the revised simplex method, an auxiliary matrix is used for computations. Compared to the modified-simplex type methods, the presented dual algorithm QPLS requires less storage and solves ill-conditioned problems more precisely. The algorithm is illustrated by some difficult problems.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.