User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Semidefinite relaxation and nonconvex quadratic optimization

Primary tabs

Nesterov, Yurii [UCL]

In this paper we study the quality of semidefinite relaxation for a global quadratic optimization problem with diagonal quadratic consraints. We prove that such relaxation approximates the exact solution of the problem with relative accuracy mu = (pi/2)-1. We consider some applications of this result.

Document type Article de périodique (Journal article) – Article de recherche
Publication date 1998
Language Anglais
Journal information "Optimization Methods and Software" - Vol. 9, no. 1-3, p. 141-160 (1998)
Peer reviewed yes
Publisher Gordon Breach Sci Publ Ltd (Reading)
issn 1055-6788
e-issn 1029-4937
Publication status Publié
Affiliation UCL
Keywords semidefinite optimization ; semidefinite relaxation ; nonconvex quadratic optimization
Links
  1. Ben-Tal A., Robust convex optimization (1996)
  2. Ben-Tal A., Interior point polynomial-time method for truss topology design (1992)
  3. Goemans Michel X., Williamson David P., Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, 10.1145/227683.227684
  4. Lovász L., Schrijver A., Cones of Matrices and Set-Functions and 0–1 Optimization, 10.1137/0801013
  5. Nesterov Yu, Quality of semidefinite relaxation for nonconvex quadratic optimization (1997)
  6. Nesterov Yu, Interior Point Polynomial Algorithms in\ Convex Programming, SIAM, 160 (1994)
  7. Oustry F., SIAM J. on Optimization, 160 (1996)
  8. Shor N., Tekhnicheskaya kibernetika, 160 (1988)
  9. Ye Y., Approximating quadratic programming with bound constraints (1997)
  10. Ye Y., Approximating quadratic programming with quadratic constraints (1997)
Bibliographic reference Nesterov, Yurii. Semidefinite relaxation and nonconvex quadratic optimization. In: Optimization Methods and Software, Vol. 9, no. 1-3, p. 141-160 (1998)
Permanent URL http://hdl.handle.net/2078.1/45610