Quadratic optimization with a ball and a reverse ball constraints

Document Type : Original paper

Authors

• Abdelouahed Hamdi ¹
• Maziar Salahi ²
• Saeid Ansary Karbasy ²
• Temadher Almaadeed ¹

¹ Department of Mathematics and Statistics, College of Art and Science, Qatar University, Doha, Qatar

² Department of Applied Mathematics, Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran

Abstract

Keywords

• Nonconvex quadratic program
• Trust-region subproblem
• SDP relaxation

Main Subjects

• Operations research, mathematical programming

[1] E. Abbe, A.S. Bandeira, and G. Hall, Exact recovery in the stochastic block model, IEEE Trans. Inf. Theory. 62 (2015), no. 1, 471–487. https://doi.org/10.1109/TIT.2015.2490670

[2] S. Adachi, S. Iwata, Y. Nakatsukasa, and A. Takeda, Solving the trust-region subproblem by a generalized eigenvalue problem, SIAM J. Optim. 27 (2017), no. 1, 269–291. https://doi.org/10.1137/16M1058200

[3] S. Adachi and Y. Nakatsukasa, Eigenvalue-based algorithm and analysis for non-convex QCQP with one constraint, Math. Program. 173 (2019), no. 1, 79–116. https://doi.org/10.1007/s10107-017-1206-8

[4] T.A. Almaadeed, S. Ansary Karbasy, M. Salahi, and A. Hamdi, On indefinite quadratic optimization over the intersection of balls and linear constraints, J. Optim. Theory Appl. 194 (2022), no. 1, 246–264. https://doi.org/10.1007/s10957-022-02018-x

[5] S. Ansary Karbasy and M. Salahi, A hybrid algorithm for the two-trust-region subproblem, Comput. Appl. Math. 38 (2019), no. 3, Article ID: 115. https://doi.org/10.1007/s40314-019-0864-y

[6] S. Ansary Karbasy and M. Salahi, Quadratic optimization with two ball constraints, Numer. Algebra Control Optim. 10 (2020), no. 2, p165. https://doi.org/10.3934/naco.2019046

[7] A. Beck and D. Pan, A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints, J. Glob. Optim. 69 (2017), no. 2, 309–342.  https://doi.org/10.1007/s10898-017-0521-1

[8] A. Ben-Tal, L.E. Ghaoui, and A. Nemirovski, Robust optimization, Princeton Series in Applied Mathematics, Princeton University Press, 2009.

[9] Samuel Burer and Yinyu Ye, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Math. Program. 181 (2020), no. 1, 1–17. https://doi.org/10.1007/s10107-019-01367-2

[10] E.J. Candes, Y.C. Eldar, T. Strohmer, and V. Voroninski, Phase retrieval via matrix completion, SIAM review 57 (2015), no. 2, 225–251.  https://doi.org/10.1137/151005099

[11] S. Ceria and R.A. Stubbs, Incorporating estimation errors into portfolio selection: Robust portfolio construction, pp. 270–294, Springer International Publishing, Cham, 2016.

[12] A.R. Conn, N.I.M. Gould, and P.L. Toint, Trust Region Methods, SIAM Philadelphia, 2000.

[13] Z. Deng, S.C. Fang, Q. Jin, and C. Lu, Conic approximation to nonconvex quadratic programming with convex quadratic constraints, J. Glob. Optim. 61 (2015), no. 3, 459–478. https://doi.org/10.1007/s10898-014-0195-x

[14] M. Grant and S. Boyd, Cvx: Matlab software for disciplined convex programming, Available from: https://cvxr.com/cvx, 2017.

[15] Z. Lu and Y. Zhang, Sparse approximation via penalty decomposition methods, SIAM J. Optim. 23 (2013), no. 4, 2448–2478.  https://doi.org/10.1137/100808071

[16] H. Luo, X. Bai, G. Lim, and J. Peng, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, Math. Program. Comput. 11 (2019), no. 1, 119–171.
https://doi.org/10.1007/s12532-018-0142-9

[17] J.J. Moré and D.C. Sorensen, Computing a trust region step, SIAM J. Sci. Stat. Comput. 4 (1983), no. 3, 553–572.
https://doi.org/10.1137/0904038

[18] Y. Nesterov, H. Wolkowicz, and Y. Ye, Semidefinite programming relaxations of nonconvex quadratic optimization, Handbook of Semidefinite Programming: Theory, Algorithms, and Applications (H. Wolkowicz, R. Saigal, and L. Vandenerghe, eds.), Springer US, Boston, MA, 2000, pp. 361–419.

[19] E. Phan-huy Hao, Quadratically constrained quadratic programming: Some applications and a method for solution, Z. Operations Res. 26 (1982), no. 1, 105–119. https://doi.org/10.1007/BF01917102

[20] T.K. Pong and H. Wolkowicz, The generalized trust region subproblem, Comput. Optim. Appl. 58 (2014), no. 2, 273–322. https://doi.org/10.1007/s10589-013-9635-7

[21] N. Rujeerapaiboon, K. Schindler, D. Kuhn, and W. Wiesemann, Size matters: Cardinality-constrained clustering and outlier detection via conic optimization, SIAM J. Optim. 29 (2019), no. 2, 1211–1239. https://doi.org/10.1137/17M1150670

[22] S. Sakaue, Y. Nakatsukasa, A. Takeda, and S. Iwata, Solving generalized CDT problems via two-parameter eigenvalues, SIAM J. Optim. 26 (2016), no. 3, 1669–1694. https://doi.org/10.1137/15100624X

[23] M. Salahi, A. Taati, and H. Wolkowicz, Local nonglobal minima for solving large-scale extended trust-region subproblems, Comput. Optim. Appl. 66 (2017), no. 2, 223–244. https://doi.org/10.1007/s10589-016-9867-4

[24] A. Wang, On quadratically constrained quadratic programs and their semidefinite program relaxations, Ph.D. thesis, Carnegie Mellon University, 2022.

[25] J. Zhou, D. Zhang, L. Wang, and Z. Xu, A new SOCP relaxation of nonconvex quadratic programming problems with a few negative eigenvalues, J. Comput. Appl. Math. 423 (2023), Article ID: 114944. https://doi.org/10.1016/j.cam.2022.114944