Global quadratic optimization via conic relaxation

Yurii Nesterov ()
Additional contact information
Yurii Nesterov: Center for Operations Research and Econometrics (CORE), Université catholique de Louvain (UCL), Louvain la Neuve, Belgium

No 1998060, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We present a convex conic relaxation for a problem of maximizing an indefinite quadratic form over a set of convex constraints on the squared variables. We show that for all these problems we get at least 12/37-relative accuracy of the approximation. In the second part of the paper we derive the conic relaxation by another approach based on the second order optimality conditions. We show that for lp-balls, p>=2, intersected by a linear subspace, it is possible to guarantee (1- 2/p)-relative accuracy of the solution. As a consequence, we prove (1 - 1/eln-n)-relative accuracy of the conic relaxation for an indefinite quadratic maximization problem over an n-dimensional unit box with homogeneous linear equality constraints. We discuss the implications of the results for the discussion around the question P = NP.

Date: 1998-02-21
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp1998.html (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:cor:louvco:1998060

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().