Computing A New Trust Region Subproblem With Conic Model By SDP Relaxation

With the rapid development and an increasingly wide variety of applications of trust region method, it has been extensively studied at home and abroad. As using the conic model instead of the ordinary quadratic model in the trust region subproblem has got much more attention in recent years, how to solve the model becomes a pressing problem. We try to solve it by the SDP relaxation technology in this paper.In this paper, we consider the well-defined trust-region subproblem with conic model and propose an efficient algorithm to solve it:We divided the primal subproblem (P) into two problems (P1) and (P2). After homogenization we proof that (P1) is equivalent to an quadratic problem, and further to an semi-definite programming, which can be solved by resorting to the SDP relaxation, followed by a rank-one solution generation procedure, and the relaxation is tight. (P2) can be solved in a similar way. Backdate the optimal solution to the two problems, pick the smaller one of the two optimal value, so its corresponding solution is optimal in the primal problem. The numerical experiments prove the efficiency of our algorithm.