Abstract
In this paper we consider a quadratically constrained quadratic programming problem with convex objective function and many constraints in which only one of them is non-convex. This problem is transformed to a parametric quadratic programming problem without any non-convex constraint and then by solving the parametric problem via an iterative scheme and updating the parameter in each iteration, the solution of the problem is achieved. The convergence of the proposed method is investigated. Numerical examples are given to show the applicability of the new method.
Similar content being viewed by others
References
Beck, A.: Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB. SIAM, Philadelphia (2014)
Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, Philadelphia (2001)
Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2009)
Deng, Zh, Fang, Sh, Jin, Q., Lu, Q.C.: Conic approximation to non-convex quadratic programming with convex quadratic constraints. J. Glob. Optim. 61, 459–478 (2015)
Dolan, E., More, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91(2), 201–213 (2002)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and co, San Francisco (1979)
Gershman, A.B., Sidiropoulos, N.D., Shahbazpanahi, S., Bengtsson, M., Ottersten, B.: Convex optimization based beamforming. IEEE Signal Process. Mag. 27(3), 62–75 (2010)
Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 1.21. Stanford University. http://cvxr.com/cvx/ (2011)
Hillestad, R.J., Jacobsen, S.E.: Linear programs with an additional reverse convex constraint. Appl. Math. Optim. 6, 257–269 (1980)
Konar, A., Sidiropoulos, N., Mehanna, O.: Parametric frugal sensing of power spectra for moving average models. IEEE Trans. Signal Process. 63(5), 1073–1085 (2015)
Kuno, T., Shi, J.: Linear programs with an additional separable concave constraint. J. Appl. Math. Decis. Sci. 8(3), 155–174 (2004)
Liu, Sh-M, Papavassilopoulos, G.P.: A parallel algorithm for linear programs with an additional reverse convex constraint. J. Parallel Distrib. Comput. 45, 91–103 (1997)
Lobo, M.S., Vandenberghe, L., Boyd, S., Lebret, H.: Applications of second-order cone programming. Linear Algebra Appl 284(1), 193–228 (1998)
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 63(6), 955–980 (2014)
Luo, Z., Ma, W., So, A., Ye, Y., Zhang, S.: Semidefinite relaxation of quadratic optimization problems. IEEE Signal Process. Mag. 27, 20–34 (2010)
De Maio, A., Nicola, S., De Huang, Y., Zhang, Y.S., Farina, A.: Code design to optimize radar detection performance under accuracy and similarity constraints. IEEE Trans. Signal Process. 56(11), 5618–5629 (2008)
Rosen, J.B.: Iterative solution of nonlinear optimal control problems. SIAM J. Control. 4, 223–244 (1966)
Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996)
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)
Shi, Z., Jin, Q.: Second order optimality conditions and reformulations for non-convex quadratically constrained quadratic programming problems. J. Ind. Manag. Optim. 10(3), 871–882 (2014)
Zheng, X.J., Sun, X.L., Li, D.: Non-convex quadratically constrained quadratic programming: best D.C.decomposition and their SDP representations. J. Glob. Optim. 50, 695–712 (2011)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Keyanpour, M., Osmanpour, N. On solving quadratically constrained quadratic programming problem with one non-convex constraint. OPSEARCH 55, 320–336 (2018). https://doi.org/10.1007/s12597-018-0334-0
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12597-018-0334-0