Abstract
In this paper, a conic reformulation and approximation is proposed for solving a nonconvex quadratic programming problem subject to several convex quadratic constraints. The original problem is transformed into a linear conic programming problem, which can be approximated by a sequence of linear conic programming problems over the dual cone of the cone of nonnegative quadratic functions. Since the dual cone of the cone of nonnegative quadratic functions has a linear matrix inequality representation, each linear conic programming problem in the sequence can be solved efficiently using the semidefinite programming techniques. In order to speed up the convergence of the approximation sequence and relieve the computational effort in solving the linear conic programming problems, an adaptive scheme is adopted in the proposed algorithm. We prove that the lower bounds generated by the linear conic programming problems converge to the optimal value of the original problem. Several numerical examples are used to illustrate how the algorithm works and the computational results demonstrate the efficiency of the proposed algorithm.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anstreicher, K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43, 471–484 (2009)
Audet, C., Hansen, P., Jaumard, B., Savard, G.: A branch and cut algorithm for nonconvex quadratically constrained quadratic programs. Math. Programm. 87, 131–152 (2000)
Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization, Analysis, Algorithms and Engineering Applications. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2001)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2009)
Burer, S., Anstreicher, K.M.: Second-order-cone constraint for extended trust-region subproblems. SIAM J. Optim. 23(1), 432–451 (2013)
Burer, S., Vandenbussche, D.: A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations. Math. Programm. 113, 259–282 (2008)
Celis, M.R., Dennis, J.E., Tapia, R.A.: A trust region strategy for nonliear equality constrained optimization. In: Boggs, P.T., Byrd, R.H., Schnabel, R.B. (eds.) Numerical Optimzation 1984: Procedding of the SIAM Conference on Numerical Optimization, Boulder, Colorado, pp. 71–82. SIAM, Philadelphia (1985)
Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000)
Czyzyk, J., Mesnier, M., Moré, J.: The NEOS server. J. IEEE Comput. Sci. Eng. 5, 68–75 (1998)
Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1.21. http://cvxr.com/cvx/, April (2011)
Lu, C., Fang, S.-C., Jin, Q., Wang, Z., Xing, W.: KKT solution and conic relaxation for solving quadratically constrained quadratic programming problems. SIAM J. Optim. 21, 1475–1490 (2011)
Lu, C., Jin, Q., Fang, S.-C., Wang, Z., Xing, W.: Adaptive computable approximation to cones of nonnegative quadratic functions. Optimization (2014, to appear). doi:10.1080/02331934.2014.8958993
Luo, Z.-Q., Ma, W.-K., So, A., Ye, Y., Zhang, S.: Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27, 20–34 (2010)
Pardalos, P., Vavasis, S.: Quadratic programming with one negative eigenvalue is NP-hard. J. Glob. Optim. 1, 15–22 (1991)
Poljak, S., Rendl, F., Wolkowicz, H.: A recipe for semidefinite relaxation for (0, 1)-quadratic programming. J. Glob. Optim. 7, 51–73 (1995)
Quist, A.J., de Klerk, E., Roos, C., Terlaky, T.: Copositive relaxation for genreal quadratic programming. Optim. Methods Softw. 9, 185–208 (1998)
Rendl, F., Wolkowicz, H.: A semidefinite framework for trust region subproblems with applications to large scale minimization. Math. Program. 77, 273–299 (1997)
Rockafellar, R.T.: Convex Analysis. Princeton University Press, New Jersey (1972)
Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996)
Sherali, H.D., Adams, W.P.: A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discret. Math. 3, 411–430 (1990)
Shor, N.Z.: Quadratic optimization problems. Sov. J. Comput. Syst. Sci. 25, 1–11 (1987)
Sturm, J.F., Zhang, S.: On cones of nonnegative quadratic functions. Math. Oper. Res. 28, 246–267 (2003)
Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14, 245–267 (2003)
Zheng, X.J., Sun, X.L., Li, D.: Nonconvex quadratically constrained quadratic programming: best D.C. decomposition and their SDP represetations. J. Glob. Optim. 50, 695–712 (2011)
Author information
Authors and Affiliations
Corresponding author
Additional information
Deng’s research has been supported by the Edward P. Fitts Fellowship at NCSU, Fang’s research by the US National Science Foundation Grant No. DMI-0553310, Jin’s research by the National Natural Science Foundation of China Grant No. 11301479 and the project supported by Zhejiang Provincial Natural Science Foundation of China No. LQ13A010001, Lu’s research has been supported by the Doctoral Research Innovation Fund of Tsinghua University.
Rights and permissions
About this article
Cite this article
Deng, Z., Fang, SC., Jin, Q. et al. Conic approximation to nonconvex quadratic programming with convex quadratic constraints. J Glob Optim 61, 459–478 (2015). https://doi.org/10.1007/s10898-014-0195-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-014-0195-x