article

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations

Authors:

Sunyoung Kim,

Masakazu KojimaAuthors Info & Claims

Computational Optimization and Applications, Volume 26, Issue 2

Pages 143 - 154

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

Published: 01 November 2003 Publication History

Publisher Site

Abstract

We show that SDP (semidefinite programming) and SOCP (second order cone programming) relaxations provide exact optimal solutions for a class of nonconvex quadratic optimization problems. It is a generalization of the results by S. Zhang for a subclass of quadratic maximization problems that have nonnegative off-diagonal coefficient matrices of quadratic objective functions and diagonal coefficient matrices of quadratic constraint functions. A new SOCP relaxation is proposed for the class of nonconvex quadratic optimization problems by extracting valid quadratic inequalities for positive semidefinite cones. Its effectiveness to obtain optimal values is shown to be the same as the SDP relaxation theoretically. Numerical results are presented to demonstrate that the SOCP relaxation is much more efficient than the SDP relaxation.

References

[1]

1. K. Fujisawa, M. Kojima, K. Nakata, and M. Yamashita, SDPA (SemiDefinite Programming Algorithm) user's manual--Version 6.0, Research Report B-308, Dept. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Oh-Okayama, Meguro, Tokyo 152-8552, Japan, 1995. Revised July 2002.

Google Scholar

[2]

2. M.X. Goemans and D.P. Williamson, "Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming," Journal of Assoc. Comput. Mach., vol. 42, pp. 1115-1145, 1995.

Digital Library

Google Scholar

[3]

3. S. Kim and M. Kojima, "Second order cone programming relaxations of quadratic optimization problems," Optimization Methods and Software, vol. 15, pp. 201-224, 2001.

Crossref

Google Scholar

[4]

4. L. Lovász and A. Schrijver, "Cones of matrices and set functions and 0-1 optimization," SIAM J. on Optimization, vol. 1, pp. 166-190, 1991.

Crossref

Google Scholar

[5]

5. M. Muramatsu and T. Suzuki, "A new second order cone programming relaxation for max-cut problems," J. of Operation Research Society of Japan, vol. 46, pp. 164-177, 2003.

Crossref

Google Scholar

[6]

6. Yu. E. Nesterov, "Semidefinite relaxation and nonconvex quadratic optimization," Optimization Methods and Software, vol. 9, pp. 141-160, 1998.

Crossref

Google Scholar

[7]

7. Yu. E. Nesterov, "Global quadratic optimization via conic optimization," Working paper, CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, November, 1998.

Google Scholar

[8]

8. F.J. Sturm, "Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones," Optimization Methods and Software, vol. 11/12, pp. 625-653, 1999.

Crossref

Google Scholar

[9]

9. K. Toh, M.J. Todd, and R.H. Tütüntü, SDPT3--aMATLAB software package for semidefinite programming," Dept. of Mathematics, National University of Singapore, Singapore, 1998.

Google Scholar

[10]

10. Y. Ye, "Approximating quadratic programming with bound and quadratic constraints," Mathematical Programming, vol. 84, pp. 219-226, 1999.

Crossref

Google Scholar

[11]

11. S. Zhang, "Quadratic optimization and semide finite relaxation," Mathematical Programming, vol. 87, pp. 453- 465, 2000.

Crossref

Google Scholar

Cited By

View all

Qiu YYıldırım E(2025)Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxationsMathematical Programming: Series A and B10.1007/s10107-024-02070-7209:1(397-433)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s10107-024-02070-7
Qiu YYıldırım E(2024)On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraintsJournal of Global Optimization10.1007/s10898-024-01407-y90:2(293-322)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10898-024-01407-y
Locatelli M(2024)A new technique to derive tight convex underestimators (sometimes envelopes)Computational Optimization and Applications10.1007/s10589-023-00534-887:2(475-499)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10589-023-00534-8
Show More Cited By

Index Terms

Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations
1. Mathematics of computing
  1. Mathematical analysis
    1. Mathematical optimization
      1. Continuous optimization
        Quadratic programming
2. Theory of computation
  1. Design and analysis of algorithms
    1. Mathematical optimization
      1. Continuous optimization
        Quadratic programming

Recommendations

Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation

We study approximation bounds for the semidefinite programming (SDP) relaxation of quadratically constrained quadratic optimization: $\min f^0(x)$ subject to $f^k(x)\le 0$, $k=1,\dots,m$, where f ^k ( x )= x ^TA ^kx +( b ^k ) ^Tx + c ^k . In the special ...
Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets

Let F be a compact subset of the n-dimensional Euclidean space Rn represented by (finitely or infinitely many) quadratic inequalities. We propose two methods, one based on successive semidefinite programming (SDP) relaxations and the other on successive ...
SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs
Abstract
We consider the global optimization of nonconvex mixed-integer quadratic programs with linear equality constraints. In particular, we present a new class of convex quadratic relaxations which are derived via quadratic cuts. To construct these ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computational Optimization and Applications

Computational Optimization and Applications Volume 26, Issue 2

November 2003

102 pages

ISSN:0926-6003

Issue’s Table of Contents

Publisher

Kluwer Academic Publishers

United States

Publication History

Published: 01 November 2003

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Qiu YYıldırım E(2025)Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxationsMathematical Programming: Series A and B10.1007/s10107-024-02070-7209:1(397-433)Online publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1007/s10107-024-02070-7
Qiu YYıldırım E(2024)On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraintsJournal of Global Optimization10.1007/s10898-024-01407-y90:2(293-322)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1007/s10898-024-01407-y
Locatelli M(2024)A new technique to derive tight convex underestimators (sometimes envelopes)Computational Optimization and Applications10.1007/s10589-023-00534-887:2(475-499)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1007/s10589-023-00534-8
Suppakitpaisarn VHao J(2024)Utilizing Graph Sparsification for Pre-processing in Max Cut QUBO SolverMetaheuristics10.1007/978-3-031-62912-9_22(219-233)Online publication date: 4-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-62912-9_22
Bunton JTabuada P(2022)Joint continuous and discrete model selection via submodularityThe Journal of Machine Learning Research10.5555/3586589.358691823:1(14813-14854)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.5555/3586589.3586918
Azuma GFukuda MKim SYamashita M(2022)Exact SDP relaxations for quadratic programs with bipartite graph structuresJournal of Global Optimization10.1007/s10898-022-01268-386:3(671-691)Online publication date: 31-Dec-2022
https://dl.acm.org/doi/10.1007/s10898-022-01268-3
Zhang BGao YLiu XHuang X(2022)Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problemsJournal of Global Optimization10.1007/s10898-022-01255-886:1(61-92)Online publication date: 19-Dec-2022
https://dl.acm.org/doi/10.1007/s10898-022-01255-8
Azuma GFukuda MKim SYamashita M(2022)Exact SDP relaxations of quadratically constrained quadratic programs with forest structuresJournal of Global Optimization10.1007/s10898-021-01071-682:2(243-262)Online publication date: 1-Feb-2022
https://dl.acm.org/doi/10.1007/s10898-021-01071-6
Cifuentes DAgarwal SParrilo PThomas R(2022)On the local stability of semidefinite relaxationsMathematical Programming: Series A and B10.1007/s10107-021-01696-1193:2(629-663)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10107-021-01696-1
Luo HChen SWu H(2021)A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxationNumerical Algorithms10.1007/s11075-020-01065-788:2(993-1024)Online publication date: 1-Oct-2021
https://dl.acm.org/doi/10.1007/s11075-020-01065-7
Show More Cited By

Abstract

References

Cited By

Index Terms

Recommendations

Further Results on Approximating Nonconvex Quadratic Optimization by Semidefinite Programming Relaxation

Cones of Matrices and Successive Convex Relaxations of Nonconvex Sets

SDP-quality bounds via convex quadratic relaxations for global optimization of mixed-integer quadratic programs

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations