article

Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming

Authors:

Immanuel M. Bomze,

Etienne De KlerkAuthors Info & Claims

Journal of Global Optimization, Volume 24, Issue 2

Pages 163 - 185

https://doi.org/10.1023/A:1020209017701

Published: 01 October 2002 Publication History

Abstract

The problem of minimizing a (non-convex) quadratic function over the simplex (the standard quadratic optimization problem) has an exact convex reformulation as a copositive programming problem. In this paper we show how to approximate the optimal solution by approximating the cone of copositive matrices via systems of linear inequalities, and, more refined, linear matrix inequalities (LMI's). In particular, we show that our approach leads to a polynomial-time approximation scheme for the standard quadratic optimzation problem. This is an improvement on the previous complexity result by Nesterov who showed that a 2/3-approximation is always possible. Numerical examples from various applications are provided to illustrate our approach.

References

[1]

{1} Bellare, M. and Rogaway, P. (1995), The Complexity of Approximating a Nonlinear Program, Mathematical Programming 69, 429-441.

Digital Library

[2]

{2} Berkelaar, A.B., Jansen, B., Roos, C. and Terlaky, T. (1996), Sensitivity Analysis in (Degenerate) Quadratic Programming. Technical Report TWI 96-26, Reports of the Faculty of Technical Mathematics and Informatics, Delft University of Technology.

[3]

{3} Bomze, I.M. (1998), On Standard Quadratic Optimization Problems, Journal of Global Optimization 13, 369-387.

Digital Library

[4]

{4} Bomze, I.M., Dür, M., de Klerk, E., Roos, C., Quist, A. and Terlaky, T. (2000), On Copositive Programming and Standard Quadratic Optimization Problems, Journal of Global Optimization 18, 301-320.

Digital Library

[5]

{5} de Klerk, E. and Pasechnik, D.V. (2002), Approximation of the Stability Number of a Graph via Copositive Programming, SIAM Journal of Optimization 12(4), 875-892.

Digital Library

[6]

{6} Goemans, M.X. and Williamson, D.P. (1995), Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM 42, 1115-1145.

Digital Library

[7]

{7} Hastad, J. (1999), Clique is Hard to Approximate Within |V ^1-¿|, Acta Mathematica 182, 105-142.

[8]

{8} Motzkin, T.S. and Straus, E.G. (1965), Maxima for Graphs and a New Proof of a Theorem of Túran, Canadian J. Math. 17, 533-540.

[9]

{9} Murty, K.G. and Kabadi, S.N. (1987), Some NP-Complete Problems in Quadratic and Linear Programming, Mathematical Programming 39, 117-129.

Digital Library

[10]

{10} Nesterov, Y.E. (1999), Global Quadratic Optimization on the Sets with Simplex Structure. Discussion paper 9915, CORE, Katholic University of Louvain, Belgium.

[11]

{11} Nesterov, Y.E. and Nemirovskii, A.S. (1994), Interior Point Methods in Convex Programming: Theory and Applications. SIAM, Philadelphia, PA.

[12]

{12} Nesterov, Y.E., Wolkowicz, H. and Ye, Y. (2000), Nonconvex Quadratic Optimization, in Wolkowicz, H., Saigal, R. and Vandenberghe, L. (eds.), Handbook of Semidefinite Programming , pp. 361-416. Kluwer Academic Publishers, Dordrecht.

[13]

{13} Papadimitriou, C.H. and Steiglitz, K. (1982), Combinatorial Optimization. Algorithms and Complexity. Prentice Hall, Inc., Englewood Cliffs, N.J.

Digital Library

[14]

{14} Parrilo, P.A. (2000), Structured Semidefinite Programs and Semi-algebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology, Pasadena, California, USA. Available at: http://www.cds.caltech.edu/~pablo/.

[15]

{15} Parrilo, P.A. and Sturmfels, B. (2001), Minimizing polynomial functions, Tech. Rep. math. OC/0103170, DIMACS, Rutgers University, March.

[16]

{16} Pólya, G. (1928), Über positive Darstellung von Polynomen. Vierteljschr. Naturforsch. Ges. Zürich, 73, 141-145 (also Collected Papers 2, 309-313, MIT Press, Cambridge, MA, London, 1974).

[17]

{17} Powers, V. and Reznick, B. (2001), A New Bound for Pólya's Theorem with Applications to Polynomials Positive on Polyhedra, J. Pure Appl. Alg. 164, 221-229.

[18]

{18} J. Renegar (2001), A Mathematical View of Interior-Point Methods in Convex Optimization. Forthcoming, SIAM, Philadelphia, PA.

Digital Library

[19]

{19} Quist, A.J., de Klerk, E., Roos, C. and Terlaky, T. (1998), Copositive Relaxation for General Quadratic Programming, Optimization Methods and Software 9, 185-209.

[20]

{20} Sturm, J.F. (1999), Using SeDuMi 1.02, a MATLAB Toolbox for Optimization Over Symmetric Cones, Optimization Methods and Software 11-12, 625-653.

[21]

{21} Vickers, G.T. and Cannings, C. (1988), Patterns of ESS's I, J. Theor. Biol. 132, 387-408.

Cited By

Bomze IPeng BQiu YYıldırım E(2025)On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity ConstraintsJournal of Optimization Theory and Applications10.1007/s10957-024-02593-1204:3Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10957-024-02593-1
Gao L(2024)Finding local optima in quadratic optimization problems in RPSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08262-128:1(495-508)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00500-023-08262-1
Cifuentes DDey SXu J(2024)Sensitivity Analysis for Mixed Binary Quadratic ProgrammingInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_33(446-459)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_33
Show More Cited By

Index Terms

Solving Standard Quadratic Optimization Problems via Linear, Semidefinite and Copositive Programming
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Convex optimization
        Quadratic programming
    2. Numerical analysis
      1. Computations on matrices
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Convex optimization
        Quadratic programming

Recommendations

Approximation of the Stability Number of a Graph via Copositive Programming

Lovász and Schrijver [SIAM J. Optim., 1 (1991), pp. 166--190] showed how to formulate increasingly tight approximations of the stable set polytope of a graph by solving semidefinite programs (SDPs) of increasing size (lift-and-project method). In this ...
Analysis of copositive optimization based linear programming bounds on standard quadratic optimization

The problem of minimizing a quadratic form over the unit simplex, referred to as a standard quadratic optimization problem, admits an exact reformulation as a linear optimization problem over the convex cone of completely positive matrices. This ...
Tightening a copositive relaxation for standard quadratic optimization problems

We focus in this paper the problem of improving the semidefinite programming (SDP) relaxations for the standard quadratic optimization problem (standard QP in short) that concerns with minimizing a quadratic form over a simplex. We first analyze the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Global Optimization

Journal of Global Optimization Volume 24, Issue 2

October 2002

169 pages

ISSN:0925-5001

Issue’s Table of Contents

Copyright © Copyright © 2002 Kluwer Academic Publishers.

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 October 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

63
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bomze IPeng BQiu YYıldırım E(2025)On Tractable Convex Relaxations of Standard Quadratic Optimization Problems under Sparsity ConstraintsJournal of Optimization Theory and Applications10.1007/s10957-024-02593-1204:3Online publication date: 1-Mar-2025
https://dl.acm.org/doi/10.1007/s10957-024-02593-1
Gao L(2024)Finding local optima in quadratic optimization problems in RPSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-023-08262-128:1(495-508)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1007/s00500-023-08262-1
Cifuentes DDey SXu J(2024)Sensitivity Analysis for Mixed Binary Quadratic ProgrammingInteger Programming and Combinatorial Optimization10.1007/978-3-031-59835-7_33(446-459)Online publication date: 3-Jul-2024
https://dl.acm.org/doi/10.1007/978-3-031-59835-7_33
Badenbroek Rde Klerk E(2022)An Analytic Center Cutting Plane Method to Determine Complete Positivity of a MatrixINFORMS Journal on Computing10.1287/ijoc.2021.110834:2(1115-1125)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1287/ijoc.2021.1108
Zamani M(2022)New bounds for nonconvex quadratically constrained quadratic programmingJournal of Global Optimization10.1007/s10898-022-01224-185:3(595-613)Online publication date: 26-Aug-2022
https://dl.acm.org/doi/10.1007/s10898-022-01224-1
Eichfelder GGroetzner P(2022)A note on completely positive relaxations of quadratic problems in a multiobjective frameworkJournal of Global Optimization10.1007/s10898-021-01091-282:3(615-626)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10898-021-01091-2
Gökmen YYıldırım E(2022)On standard quadratic programs with exact and inexact doubly nonnegative relaxationsMathematical Programming: Series A and B10.1007/s10107-020-01611-0193:1(365-403)Online publication date: 1-May-2022
https://dl.acm.org/doi/10.1007/s10107-020-01611-0
Bomze IKahr MLeitner M(2021)Trust Your Data or Not—StQP Remains StQPMathematics of Operations Research10.1287/moor.2020.105746:1(301-316)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1287/moor.2020.1057
Flores-Bazán FGonzález-Valencia L(2021)Characterizing Existence of Minimizers and Optimality to Nonconvex Quadratic IntegralsJournal of Optimization Theory and Applications10.1007/s10957-020-01794-8188:2(497-522)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s10957-020-01794-8
Gondzio JYıldırım E(2021)Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulationsJournal of Global Optimization10.1007/s10898-021-01017-y81:2(293-321)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s10898-021-01017-y
Show More Cited By

View Options

View options

Figures

Tables

Media

View Issue’s Table of Contents