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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
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.
S. Kim and M. Kojima, “Second order cone programming relaxations of quadratic optimization problems,” Optimization Methods and Software, vol. 15, pp. 201-224, 2001.
L. Lováasz and A. Schrijver, “Cones of matrices and set functions and 0-1 optimization,” SIAM J. on Optimization, vol. 1, pp. 166-190, 1991.
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.
Yu. E. Nesterov, “Semidefinite relaxation and nonconvex quadratic optimization,” Optimization Methods and Software, vol. 9, pp. 141-160, 1998.
Yu. E. Nesterov, “Global quadratic optimization via conic optimization,” Working paper, CORE, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, November, 1998.
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.
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.
Y. Ye, “Approximating quadratic programming with bound and quadratic constraints,” Mathematical Programming, vol. 84, pp. 219-226, 1999.
S. Zhang, “Quadratic optimization and semidefinite relaxation,” Mathematical Programming, vol. 87, pp. 453-465, 2000.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kim, S., Kojima, M. Exact Solutions of Some Nonconvex Quadratic Optimization Problems via SDP and SOCP Relaxations. Computational Optimization and Applications 26, 143–154 (2003). https://doi.org/10.1023/A:1025794313696
Issue Date:
DOI: https://doi.org/10.1023/A:1025794313696