Non-convex quadratic optimization on a parallelepiped

E. A. Kotel'nikov

Institute of Computational Mathematics and Mathematical Geophysics (Computing Center), Siberian Branch of the Russian Academy of Sciences

Abstract: The approximating-combinatorial method for solving optimization problems is used for the search for a global maximum of a quadratic function on a parallelepiped. The approximating functions in this method are majorants of an object function. The majorants are constructed on subsets of parallelepiped of admissible solutions. The method is based on a diagonal or block-diagonal $LDL^T$-factorization of a matrix of an object function.

Key words: non-convex quadratic programming, non-convex optimization, branch and bound algorithm, factorization of symmetric matrix.

UDC: 519.853

Received: 24.03.2007
Revised: 26.03.2007

 English version: Numerical Analysis and Applications, 2008, 1:1, 58–68