Document Type

Dissertation

Date of Degree

Summer 2015

Degree Name

PhD (Doctor of Philosophy)

Degree In

Applied Mathematical and Computational Sciences

First Advisor

Samuel Burer

Abstract

The Trust Region Subproblem (TRS), which minimizes a nonconvex quadratic function over the unit ball, is an important subproblem in trust region methods for nonlinear optimization. Even though TRS is a nonconvex problem, it can be solved in polynomial time using, for example, a semidefinite programming (SDP) relaxation. Different variants of TRS have been considered from both theoretical and practical perspectives. In this thesis, we study three variants of TRS and their SDP/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. When m = 0, when m = 1, or when m = 2 and the linear cuts are parallel, it is known that the eTRS optimal value equals the optimal value of a particular conic relaxation, which is solvable in polynomial time. However, it is also known that, when m ≥2 and at least two of the linear cuts intersect within the ball, i.e., some feasible point of the eTRS satisfies both linear constraints at equality, then the same conic relaxation may admit a gap with eTRS. We show that the conic relaxation admits no gap for arbitrary M as long as the linear cuts are non-intersecting.

We then extend our result to a more general setting. We study an eTRS in which a quadratic function is minimized over a structured nonconvex feasible region: the unit ball with M linear cuts and R hollows. In the special case when m = 0 and r = 1, it is known that the eTRS has a tight polynomial-time solvable conic relaxation. We show that a certain conic relaxation is also tight for general R and M as long as the cuts and hollows satisfy some non-intersecting assumptions that generalize the previous paragraph.

Finally, intersecting the feasible region of TRS with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing approaches do not provide a concise conic relaxation. We investigate the use of conic relaxation for TTRS. Starting from the basic SDP relaxation of TTRS, which admits a gap, recent research has tightened the basic relaxation using valid second-order-cone (SOC) inequalities. For the special case of TTRS in dimension n=2, we fully characterize the remaining valid inequalities, which can be viewed as strengthened versions of the SOC inequalities just mentioned. We also demonstrate that these valid inequalities can be used computationally even when n > 2 to solve TTRS instances that were previously unsolved using techniques of conic relaxation.

Public Abstract

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.

Keywords

publicabstract, Nonconvex Quadratic Programming, Semidefinite Programming, Trust Region Subproblems

Pages

xi, 79 pages

Bibliography

Includes bibliographical references (pages 76-79).

Copyright

Copyright 2015 Boshi Yang

Share

COinS