A polynomial optimization problem (POP) consists of minimizing a multivariate real polynomial on a semi-algebraic set $K$ described by polynomial inequalities and equations. In its full generality it is a non-convex, multi-extremal, difficult global optimization problem. More than an decade ago, J.~B.~Lasserre proposed to solve POPs by a hierarchy of convex semidefinite programming (SDP) relaxations … Read more
We consider the projected semi-definite and Euclidean distance cones onto a subset of the matrix entries. These two sets are precisely the input data defining feasible semi-definite and Euclidean distance completion problems. We characterize when these sets are closed, and use the boundary structure of these two sets to elucidate the Krislock-Wolkowicz facial reduction algorithm. … Read more
We consider the problem of constructing an approximation of the Pareto curve associated with the multiobjective optimization problem $\min_{x \in S} \{(f_1(x),f_2(x))\}$, where $f_1$ and $f_2$ are two conflicting positive polynomial criteria and $S \subset R^n$ is a compact basic semialgebraic set. We provide a systematic numerical scheme to approximate the Pareto curve. We start … Read more
In the context of optimal control, we consider the inverse problem of Lagrangian identification given system dynamics and optimal trajectories. Many of its theoretical and practical aspects are still open. Potential applications are very broad as a reliable solution to the problem would provide a powerful modeling tool in many areas of experimental science. We … Read more
The current bottleneck of globally solving mixed-integer (nonconvex) quadratically constrained problem (MIQCP) is still to construct strong but computationally cheap convex relaxations, especially when dense quadratic functions are present. We pro- pose a cutting surface procedure based on multiple diagonal perturbations to derive strong convex quadratic relaxations for nonconvex quadratic problem with separable constraints. Our … Read more
We show that the worst case moment bound on the expected optimal value of a mixed integer linear program with a random objective c is closely related to the complexity of characterizing the convex hull of the points CH{(1 x) (1 x)’: x \in X} where X is the feasible region. In fact, we can … Read more
We consider the problem of partitioning the node set of a graph into $k$ sets of given sizes in order to \emph{minimize the cut} obtained using (removing) the $k$-th set. If the resulting cut has value $0$, then we have obtained a vertex separator. This problem is closely related to the graph partitioning problem. In … Read more
We present the moment cone (MC) relaxation and a hierarchy of sparse Lagrangian-SDP relaxations of polynomial optimization problems (POPs) using the unified framework established in Part I. The MC relaxation is derived for a POP of minimizing a polynomial subject to a nonconvex cone constraint and polynomial equality constraints. It is an extension 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