The extended trust-region subproblem (eTRS)—the trust-region subproblem equipped with some additional linear constraints, has received lots of attention in recent years. As one of the quadratically constrained quadratic programming problems, eTRS can be solved via the methods of general quadratic programs—the semidefinite programming (SDP) relaxation and its related global optimization techniques are the most commonly used instruments. Recently, researchers use second-order cone (SOC) constraints to strengthen SDP, and the speeds of the previous algorithms have been improved. In this paper, we study eTRS from the computational point of view. A class of eTRS is provided, bringing huge computational pressure to the SOC-accelerated algorithms. However, the reformulation linearization technique has extremely promising effect of acceleration. With the two classes of constraints on hand for acceleration, a new branch and bound algorithm is proposed. Numerical experiments show that the new algorithm runs faster than several algorithms in the literature as well as the solver Gurobi for certain types of eTRS.
Jin-Yu Dai
. Accelerating the Branch and Bound Algorithm for Solving the Extended Trust-Region Subproblems[J]. Journal of the Operations Research Society of China, 2026
, 14(1)
: 229
-245
.
DOI: 10.1007/s40305-023-00516-x
[1] Fukushima, M., Yamamoto, Y.: A second-order algorithm for continuous-time nonlinear optimal control problems. IEEE Trans. Autom. Control 31, 673-676(1986)
[2] Golub, G.H., Matt, U.V.: Quadratically constrained least squares and quadratic problems. Numer. Math. 59, 561-580(1991)
[3] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. MPS-SIAM Series in Optimization, SIAM, Philadelphia (2000)
[4] Locatelli, M.: Exactness conditions for an SDP relaxation of the extended trust region problem. Optim. Lett. 10, 1141-1151(2016)
[5] Jeyakumar, V., Li, G.Y.: Trust-region problems with linear inequality constraints: exact SDP relaxation, global optimality and robust optimization. Math. Prog. 147, 171-206(2014)
[6] Ye, Y., Zhang, S.: New results on quadratic minimization. SIAM J. Optim. 14, 245-267(2003)
[7] Burer, S., Anstreicher, K.M.: Second-order-cone constraints for extended trust-region subproblems. SIAM J. Optim. 23, 432-451(2013)
[8] Burer, S., Yang, B.: The trust region subproblem with non-intersecting linear constraints. Math. Prog. 149, 253-264(2015)
[9] Salahi, M., Taati, A.: A fast eigenvalue approach for solving the trust region subproblem with an additional linear inequality. Comput. Appl. Math. 37, 329-347(2018)
[10] Salahi, M., Taati, A., Wolkowicz, H.: Local nonglobal minima for solving large scale extended trust region subproblems. Comput. Optim. Appl. 66, 223-244(2017)
[11] Deng, Z., Lu, C., Tian, Y., Luo, J.: Globally solving extended trust region subproblems with two intersecting cuts. Optim. Lett. 14, 1855-1867(2020)
[12] Salahi, M., Taati, A.: Alternating direction method of multipliers for the extended trust region subproblem. Iran. J. Numer. Anal. Optim. 7, 107-117(2017)
[13] Beck, A., Pan, D.: A branch and bound algorithm for nonconvex quadratic optimization with ball and linear constraints. J. Glob. Optim. 69, 309-342(2017)
[14] Dai, J.: On globally solving the extended trust-region subproblems. Oper. Res. Lett. 48, 441-445(2020)
[15] Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems. Kluwer Academic Publishing, Boston (1999)
[16] Lu, C., Deng, Z., Jin, Q.: An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints. J. Glob. Optim. 67, 475-493(2017)
