zbMATH — the first resource for mathematics

Inexact solution of auxiliary problems in Polyak type algorithms. (English) Zbl 0972.90052
Summary: The Polyak algorithm is known to be an efficient algorithm for the iterative solution of quadratic programming problems with inequality constraints, especially when applied to small problems or appropriately modified. It reduces the solution of the above problems to the conjugate gradient solution of a sequence of unconstrained minimization problems. The point of this note is to show that before reaching the solution of an auxiliary minimization problem, there is a feasible decrease direction that can be used in order to release some active constraints in such a way that the finite termination property of the original algorithm is preserved.

90C20 Quadratic programming
Full Text: EuDML
[1] Bazaraa M. S., Shetty C. M.: Nonlinear Programming. J. Wiley, New York, 1979. · Zbl 0476.90035
[2] Dostál Z.: Direction of large decrease and quadratic programming. Proceedings of the X-th Summer School on Software and Algorithms of Numerical Mathematics, published by Charles University, Prague, 1993, 1-9.
[3] Dostál Z.: Box constrained quadratic programming with proportioning and projections. SIAM J. Optimization 7, 3 (1997), 871-887. · Zbl 0912.65052
[4] Friedlander A., Martinez M.: On the maximization of a concave quadratic function with box constraints. SIAM J. Optimization 4 (1994), 177-192. · Zbl 0801.65058
[5] O’Leary D. P.: A generalised conjugate gradient algorithm for solving a class of quadratic programming problems. Lin. Alg. Appl. 34 (1980), 371-399. · Zbl 0464.65039
[6] Polyak B. T.: The conjugate gradient method in extremal problems. USSR Comput. Math. and Math. Phys. 9 (1969), 94-112 · Zbl 0191.49003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.