Boshi Yang \(\) We develop a new method called \emph{affine FR} for recovering Slater’s condition for semidefinite programming (SDP) relaxations of combinatorial optimization (CO) problems. Affine FR is a user-friendly method, as it is fully automatic and only requires a description of the problem. We provide a rigorous analysis of differences between affine FR and the existing … Read more
Motivated by encouraging numerical results in the literature, in this note we consider two specific variants of the trust-region subproblem and provide exact semidefinite representable reformulations. The first is over the intersection of two balls; the second is over the intersection of a ball and a special second-order conic representable set. Different from the technique … Read more
Let F be a set defined by quadratic constraints. Understanding the structure of the closed convex hull cl(C(F)) := cl(conv{xx’ | x in F}) is crucial to solve quadratically constrained quadratic programs related to F. A set G with complicated structure can be constructed by intersecting simple sets. This paper discusses the relationship between cl(C(F)) … Read more
Let $\F$ be a quadratically constrained, possibly nonconvex, bounded set, and let $\E_1, \ldots, \E_l$ denote ellipsoids contained in $\F$ with non-intersecting interiors. We prove that minimizing an arbitrary quadratic $q(\cdot)$ over $\G := \F \setminus \cup_{k=1}^\ell \myint(\E_k)$ is no more difficult than minimizing $q(\cdot)$ over $\F$ in the following sense: if a given semidefinite-programming … Read more
The trust-region subproblem minimizes a general quadratic function over an ellipsoid and can be solved in polynomial time using a semidefinite-programming (SDP) relaxation. Intersecting the feasible set with a second ellipsoid results in the two-trust-region subproblem (TTRS). Even though TTRS can also be solved in polynomial-time, existing algorithms do not use SDP. In this paper, … Read more
This paper studies an extended trust region subproblem (eTRS)in which the trust region intersects the unit ball with m linear inequality constraints. When m=0, m=1, or m=2 and the linear constraints are parallel, it is known that the eTRS optimal value equals the optimal value of a particular convex relaxation, which is solvable in polynomial … Read more