A finite gradient-projective solver for a quadratic programming problem

DOI10.1515/RNAM-2013-0017MaRDI QIDQ2870272zbMATH OpenOpenAlexFDO

Authors A. Tret'yakov, E. E. Tyrtyshnikov

Publication date 17 January 2014

Published in Russian Journal of Numerical Analysis and Mathematical Modelling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/rnam-2013-0017

zbMATH Keywords

algorithmgradient method with step doublingKuhn-Tucker systemquadratic programming

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Quadratic programming (90C20)

Review text

The minimization method for a quadratic functional with linear constraints, which is proposed in this paper, generalizes the technique previously published by the first author (see [\textit{A. A. Tret'yakov}, Russ. J. Numer. Anal. Math. Model. 25, No. 3, 279--288 (2010; Zbl 1193.65102)]). The aim of the authors is to obtain the solution in a finite number of steps, not using a priori information. The algorithm constructs a sequence of iterative approximations of the gradient method with step doubling. Each iteration generates the set of active constraints and forms the equivalent Kuhn-Tucker system that gives the minimum condition. The iterative approximations are initial points of a sequence of projections. The final point of this sequence gives the required point of minimum after a finite number of iterations. The number of iterations at each step polynomially depends on the dimension of the problem.

Recommendations

• scientific article; zbMATH DE number 3880458
• scientific article; zbMATH DE number 4201503
• scientific article; zbMATH DE number 4185389
• A finite-termination gradient projection method for solving systems of linear inequalities
• Dual fast projected gradient method for quadratic programming
• Exact differentiable penalty for a problem of quadratic programming with the use of a gradient-projective method
• scientific article; zbMATH DE number 4025156
• scientific article; zbMATH DE number 1911046
• scientific article; zbMATH DE number 590053
• IMPROVED PROJECTED GRADIENT ALGORITHMS FOR SINGLY LINEARLY CONSTRAINED QUADRATIC PROGRAMS SUBJECT TO LOWER AND UPPER BOUNDS

Cited in

(14)

• Locally polynomial method for solving systems of linear inequalities
• Soft inequality constraints in gradient method and fast gradient method for quadratic programming
• An incremental approach for the solution of quadratic problems
• scientific article; zbMATH DE number 1810375 (Why is no real title available?)
• IMPROVED PROJECTED GRADIENT ALGORITHMS FOR SINGLY LINEARLY CONSTRAINED QUADRATIC PROGRAMS SUBJECT TO LOWER AND UPPER BOUNDS
• scientific article; zbMATH DE number 3922383 (Why is no real title available?)
• scientific article; zbMATH DE number 4033492 (Why is no real title available?)
• Solving the general quadratic programming problem in a finite number of steps
• A two-phase gradient method for quadratic programming problems with a single linear constraint and bounds on the variables
• Minimization of a convex quadratic function subject to separable conical constraints in granular dynamics.
• Gradient projection-based performance improvement for JLQ problems
• Constraint exploration method for quadratic programming problem.
• scientific article; zbMATH DE number 7753388 (Why is no real title available?)
• On the decrease of a quadratic function along the projected-gradient path

This page was built for publication: A finite gradient-projective solver for a quadratic programming problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2870272)