Free Access

An Efficient Splitting Algorithm for Solving the CDT Subproblem

Jinyu Dai

School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, P. R. China

https://doi.org/10.1142/S0217595923500070Cited by:0 (Source: Crossref)

Abstract

The CDT subproblem, which minimizes a quadratic function over the intersection of two ellipsoids, is a classical quadratic programming problem. In this paper, we study a method of solving CDT with a positive Lagrangian duality gap. An efficient splitting algorithm is proposed for finding the global optimal solutions. A cutting plane is firstly added to divide the feasible set of CDT into two subsets, and then two new quadratic programming problems with ellipsoidal and linear constraints are generated accordingly. Using the newly developed technique — second-order cone constraints to enhance the efficiencies of the SDP relaxation-based algorithms on the two subproblems, an optimal solution of CDT can be acquired by comparing the objective values of the two subproblems. Numerical experiments show that the new algorithm outperforms the two recent SDP relaxation-based algorithms, the two-parameter eigenvalue-based algorithm and the solver Gurobi 9.5 for certain types of CDT.

Keywords:

References

Ai, W and S Zhang (2009). Strong duality for the CDT subproblem: A necessary and sufficient condition. SIAM Journal on Optimization, 19, 1735–1756. Crossref, Web of Science, Google Scholar
Beck, A and YC Eldar (2006). Strong duality in nonconvex quadratic optimization with two quadratic constraints. SIAM Journal on Optimization, 17(3), 844–860. Crossref, Web of Science, Google Scholar
Buchheim, C and B Wiegele (2013). Semidefinite relaxations for non-convex quadratic mixed-integer programming. Mathematical Programming, 141, 435–452. Crossref, Web of Science, Google Scholar
Bienstock, D (2016). A note on polynomial solvability of the CDT problem. SIAM Journal on Optimization, 23, 488–498. Crossref, Web of Science, Google Scholar
Bomze, IM and ML Overton (2015). Narrowing the difficulty gap for the Celis-Dennis-Tapia problem. Mathematical Programming, 151, 459–476. Crossref, Web of Science, Google Scholar
Celis, MR, JE Dennis and RA Tapia (1984). A trust region algorithm for nonlinear equality constrained optimization. In Numerical Optimization, Boggs, RT, RH Byrd, RB Schnable (Eds.), pp. 71–82. Philadephia: SIAM. Google Scholar
Consolini, L and M Locatelli (2017). On the complexity of quadratic programming with two quadratic constraints. Mathematical Programming, 164(1), 91–128. Crossref, Web of Science, Google Scholar
Chen, X and Y Yuan (2001). On maxima of dual function of the CDT subproblem. Journal of Computational Mathematics, 19(1), 113–124. Google Scholar
Dai, J (2020). On globally solving the extended trust-region subproblems. Operations Research Letters, 48, 441–445. Crossref, Web of Science, Google Scholar
Huang, K and ND Sidiropoulos (2016). Consensus-ADMM for general quadratically constrained quadratic programming. IEEE Transactions on Signal Processing, 64(20), 5297–5310. Crossref, Web of Science, Google Scholar
Karbasy, SA and M Salahi (2019). A hybrid algorithm for the two-trust-region subproblem. Computational and Applied Mathematics, 38, 115. Crossref, Web of Science, Google Scholar
Karbasy, SA and M Salahi (2020). Quadratic optimization with two ball constraints. Numerical Algebra, Control and Optimization, 10(2), 165–175. Crossref, Web of Science, Google Scholar
Li, GD and Y Yuan (2005). Compute a Celis–Dennis–Tapia step. Journal of Computational Mathematcs, 23(1), 463–478. Google Scholar
Lu, C, Z Deng and Q Jin (2017). An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints. Journal of Global Optimization, 67, 475–493. Crossref, Web of Science, Google Scholar
Sakaue, S, Y Nakatsukasa, A Takeda and S Iwata (2016). Solving generalized CDT problems via two-parameter eigenvalues. SIAM Journal on Optimization, 26(3), 1669–1694. Crossref, Web of Science, Google Scholar
Shu-Cherng, F and W Xing (2013). Linear Conic Programming (in Chinese). Beijing: Sience Press. Google Scholar
Yang, B and S Burer (2016). A two-variable approach to the two-trust-region suproblem. SIAM Journal on Optimization, 26, 661–680. Crossref, Web of Science, Google Scholar
Yuan, Y (1990). On a subproblem of trust region algorithms for constrained optimization. Mathematical Programming, 47, 53–63. Crossref, Web of Science, Google Scholar
Yuan, JH, ML Wang, WB Ai and TP Shuai (2017). New results on narrowing the duality gap of the extended Celis-Dennis-Tapia problem. SIAM Journal on Optimization, 27, 890–909. Crossref, Web of Science, Google Scholar
Ye, Y and S Zhang (2003). New results on quadratic minimization. SIAM Journal on Optimization, 14, 245–267. Crossref, Web of Science, Google Scholar