Abstract: 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.

Key words: SOC constraints, RLT constraints, Branch and bound, Uniform distribution