Research ArticleOpen AccessGoogle Scholar indexed
An Effective Algorithm for Quadratic Optimization with Non-Convex Inhomogeneous Quadratic Constraints
Department of Mathematics, College of Science, Shanghai University, Shanghai, China
- 1 Department of Mathematics, College of Science, Shanghai University, Shanghai, China
Advances in Pure Mathematics·Volume 07 (2017)·Pages 314–323·Published 20 April 2017·DOI10.4236/apm.2017.74018
Copy link · social · email
Abstract
This paper considers the NP (Non-deterministic Polynomial)-hard problem of finding a minimum value of a quadratic program (QP), subject to m non-convex inhomogeneous quadratic constraints. One effective algorithm is proposed to get a feasible solution based on the optimal solution of its semidefinite programming (SDP) relaxation problem.
KeywordsNonconvex Inhomogeneous Quadratic Constrained Quadratic OptimizationSemidefinite Programming RelaxationNp-Hard
- Pardalos, P.M. and Schnitger, G. (1988) Checking Glocal Optimality in Constrained Quadratic Programming is NP-hard. Operations Research Letters, 7, 33-35. https://doi.org/10.1016/0167-6377(88)90049-1
- Pardalos, P.M. and Vavasis, S.A. (1991) Quadratic Programming with One Negative Eigenvalue Is NP-Hard. The Journal of Global Optimization, 1, 15-22. https://doi.org/10.1007/BF00120662
- Luo, Z.-Q., Sidiropoulos, N., Tseng, P. and Zhang, S. (2007) Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints. SIAM Journal on Optimization, 18, 1-28. https://doi.org/10.1137/050642691
- Lovász, L. and Schrijver, A. (1991) Cones of Matrices and Set-functions and 0-1 Optimization. SIAM Journal on Optimization, 1, 166-190. https://doi.org/10.1137/0801013
- Shor, N.Z. (1987) Quadratic Optimization Problems. Soviet Journal of Computer and Systems Sciences, 25, 1-11.
- Alizadeh, F. (1995) Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization. SIAM Journal on Optimization, 5, 13-51. https://doi.org/10.1137/0805002
- Nesterov, Y. and Nemirovskii, A. (1994) Interior-Point Polynomial Algorithms in Convex Programming. Studies in Applied and Numerical Mathematics, Philadelphia, PA. https://doi.org/10.1137/1.9781611970791
- Nemirovsi, A. and Roos, C. and Terlaky, T. (1999) On Maximization of Quadratic form over Intersection of Ellopsoids with Common Center. Math Program, 86, 463-473. https://doi.org/10.1007/s101070050100
- Luo, Z.Q., Sidiropoulos, N.D., Tseng, P. and Zhang, S. (2007) Approximation Bounds for Quadratic Optimization with Homogeneous Quadratic Constraints. SIAM Journal on Optimization, 18, 1-28. https://doi.org/10.1137/050642691
- He, S., Luo, Z.Q., Nie, J. and Zhang, S. (2008) Semidefinite Relaxation Bounds for Indefinite Homogeneous Quadratic Optimization. SIAM Journal on Optimization, 19, 503-523. https://doi.org/10.1137/070679041
- Ye, Y. and Zhang, S. (2003) New Results on Quadratic Minimization. SIAM Journal on Optimization, 14, 245-267. https://doi.org/10.1137/S105262340139001X
- Ye, Y. (1999) Approximating Global Quadratic Optimization with Convex Quadratic Constraints. The Journal of Global Optimization, 15, 1-17. https://doi.org/10.1023/A:1008370723217
- Pataki, G. (2003) Computational Semidefinite and Second Order Cone Programming. The State of the Art, Math, Program, 95, 3-51.