×

zbMATH — the first resource for mathematics

An optimal algorithm for minimization of quadratic functions with bounded spectrum subject to separable convex inequality and linear equality constraints. (English) Zbl 1223.65041
The authors present an optimal algorithm for the minimization of quadratic functions subject to separable convex inequality and linear equality constraints. Its main feature is an error bound in terms of bounds on the spectrum of the Hessian of the cost function. In a class of problems with the spectrum of the Hessians in a given positive interval, the algorithm obtains approximate solutions in a uniformly bounded number of simple iterations, such as matrix-vector multiplications. If the class of problems admits a sparse representation of the Hessian, it simply follows that the cost of the solution is proportional to the number of unknowns. The authors present numerical experiments to illustrate the theoretical results.

MSC:
65K05 Numerical mathematical programming methods
90C25 Convex programming
90C06 Large-scale problems in mathematical programming
90C20 Quadratic programming
Software:
MatSol
PDF BibTeX XML Cite
Full Text: DOI