Quadratic programming

2020 Mathematics Subject Classification: Primary: 90C20 [MSN][ZBL]

The branch of convex programming devoted to the theory of and methods for solving problems of minimization of convex quadratic functions on sets defined by systems of linear inequalities and equalities. There exists a well worked-out theory of quadratic programming, and numerical methods have been developed for the solution of the problems of quadratic programming; among them, methods of the simplex method type, which lead to a solution in a finite number of steps (iterations).

Actual problems of economic or technological content with models that are problems in quadratic programming are few. However, problems in quadratic programming arise as auxiliary problems for the solution of various problems in mathematical programming. Thus, in one of the variants of the method of feasible directions for the numerical solution of problems in non-linear programming, the problem on the choice of the direction of descent at each iteration reduces to the solution of a problem in quadratic programming. Problems of unconditional minimization of quadratic functions, and also problems in quadratic programming with constraints of the simplest type (for example, that the variables should be non-negative) arise as a result of the application of the method of regularization for the solution of unstable (ill-posed) problems of linear programming and the method of penalty functions (cf. Penalty functions, method of) for the solution of problems of linear programming.

References

[1]	B.N. Pshenichnyi, Yu.M. Danilin, "Numerical methods in extremal problems" , MIR (1978) (Translated from Russian)
[2]	J. Hadley, "Nonlinear and dynamic programming" , Addison-Wesley (1964)
[3]	U.I. Zangwill, "Nonlinear programming: a unified approach" , Prentice-Hall (1969)
[4]	W. Krelle, H.P. Künzi, "Nonlinear programming" , Blaisdell (1966) (Translated from German)
[5]	V.F. Dem'yanov, V.N. Malozemov, "Introduction to minimax" , Wiley (1974) (Translated from Russian)

References

[a1]	M. Minoux, "Mathematical programming: theory and algorithms" , Wiley (1986)