We present a new framework to solve the generalized trust region subproblem(GTRS) of minimizing a quadratic objective over a quadratic constraint. Morespecifically, we derive a convex quadratic reformulation (CQR) of minimizing alinear objective over one or two convex quadratic constraints for the GTRS. Wealso show that an optimal solution of the GTRS can be recovered from an optimalsolution of the CQR. We further demonstrate that this CQR is equivalent to aminimization of a maximum of two convex quadratic functions derived from theCQR. Although the latter minimization problem is nonsmooth, it is convex withgood structure and we derived two steepest descent algorithms corresponding totwo different line search rules to solve it. Global convergence for bothalgorithms is demonstrated. A local linear convergence rate of the firstalgorithm is also obtained by an estimation of the Kurdyka- Lojasiewiczexponent at any optimal solution under mild conditions. Numerical resultsillustrate the efficiency of our algorithm.
展开▼
