On minimization of a quadratic function with one negative eigenvalue
It is well known that a quadratic programming minimization problem with one negative eigenvalue is NP-hard. However, in practice one may expect such problems being not so difficult to solve. We suggest to make a single partition of the feasible set in a concave variable only so that a convex approximation of the objective function upon every partition set has an acceptable error. Minimizing convex approximations on partition sets provides an approximate solution of the nonconvex quadratic program that we consider. These minimization problems are to be solved concurrently by parallel computing. An estimation of the number of partition sets is given. The study presents a computational comparison with a standard branch-and-bound procedure. © 2020, Springer-Verlag GmbH Germany, part of Springer Nature.
Библиографическая ссылка Minarchenko I., Khamisov O. On minimization of a quadratic function with one negative eigenvalue // Optimization Letters. 2021. DOI: 10.1007/s11590-020-01653-5
Проиндексировано: WOS
SCOPUS
