A conic optimization approach to variants of the trust region subproblem

Mathematical optimization is essential in all kinds of mathematical models, and it has broad applications in engineering, management sciences, finance, medical imaging, etc. Based on the features of functions involved, optimization problems can be categorized as convex problems and nonconvex problems. Compared to convex optimization problems, nonconvex ones are generally more difficult because of the existence of local minimizers. However, some nonconvex problems are relatively easy, in the sense that they can be converted into convex problems and solved in polynomial time.

In this thesis, we study three variants of an important nonconvex optimization problem, the Trust Region Subproblem (TRS), and their conic relaxations. We first study an extended trust region subproblem (eTRS) in which the trust region equals the intersection of the unit ball with m linear cuts. Next, we extend our result to an eTRS in which the trust region equals the intersection of the unit ball with m linear cuts and r hollows. Under some non-intersecting assumptions, we prove that both problems have tight conic relaxations, and thus can be solved in polynomial time. We also study the two trust region subproblem (TTRS), in which the trust region equals the intersection of two full dimensional ellipsoids. For TTRS, we introduce a technique to generate a new type of valid inequalities, and prove that the resulting conic relaxation is tight in dimension 2.