In this paper, we present an inexact block-decomposition (BD) first-order method for solving standard form conic semidefinite programming (SDP) which avoids computations of exact projections onto the manifold defined by the affine constraints and, as a result, is able to handle extra large SDP instances. The method is based on a two-block reformulation of the … Read more
Utilizing dual descriptions of the normal cone of convex optimization problems in conic form, we characterize the vertices of semidefinite representations arising from Lovász theta body, generalizations of the elliptope, and related convex sets. Our results generalize vertex characterizations due to Laurent and Poljak from the 1990’s. Our approach also leads us to nice characterizations … Read more
Many important NP-hard combinatorial problems can be efficiently approximated using semidefinite programming relaxations. We propose a new hierarchy of semidefinite relaxations for classes of such problems that based on graphs and for which the projection of the problem onto a subgraph shares the same structure as the original problem. This includes the well-studied max-cut and … Read more
The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the total weight of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes … Read more
In this article, we present a geometric theoretical analysis of semidefinite feasibility problems (SDFPs). We introduce the concept of hyper feasible partitions and sub-hyper feasible directions, and show how they can be used to decompose SDFPs into smaller ones, in a way that preserves most feasibility properties of the original problem. With this technique, we … Read more
Given a telecommunication network, modeled by a graph with capacities, we are interested in comparing the behavior and usefulness of two information propagation schemes, namely multicast and network coding, when the aforementioned network is subject to single arc failure. We consider the case with a single source node and a set of terminal nodes. The … Read more
We study non-convex quadratic minimization problems under (possibly non-convex) quadratic and linear constraints, and characterize both Lagrangian and Semi-Lagrangian dual bounds in terms of conic optimization. While the Lagrangian dual is equivalent to the SDP relaxation (which has been known for quite a while, although the presented form, incorporating explicitly linear constraints, seems to be … Read more
Packing problems in discrete geometry can be modeled as finding independent sets in infinite graphs where one is interested in independent sets which are as large as possible. For finite graphs one popular way to compute upper bounds for the maximal size of an independent set is to use Lasserre’s semidefinite programming hierarchy. We generalize … 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
Many scientific and engineering applications feature large-scale non-smooth convex minimization problems over convex sets. In this paper, we address an important instance of this broad class where we assume that the non-smooth objective is equipped with a tractable proximity operator and that the convex constraints afford a self-concordant barrier. We provide a new joint treatment … Read more