\(\) A geometric nonconvex conic optimization problem (COP) was recently proposed by Kim, Kojima and Toh asa unified framework for convex conic reformulation of a class of quadratic optimization problems and polynomial optimization problems. The nonconvex COP minimizes a linear function over the intersection of a nonconvex cone K, a convex subcone J of the … Read more
Conflict analysis originally tried to exploit the knowledge that certain nodes in a relaxation-based branch-and-bound are infeasible. It has been extended to derive valid constraints also from feasible nodes. This paper adapts this approach to mixed-integer semidefinite programs. Using dual solutions, the primal constraints are aggregated and the resulting inequalities can be used at different … Read more
This note proposes a new reformulation of complex semidefinite programs (SDPs) as real SDPs. As an application, we present an economical reformulation of complex SDP relaxations of complex polynomial optimization problems as real SDPs and derive some further reductions by exploiting inner structure of the complex SDP relaxations. Various numerical examples demonstrate that our new … Read more
This work establishes provably faster convergence rates for gradient descent in smooth convex optimization via a computer-assisted analysis technique. Our theory allows nonconstant stepsize policies with frequent long steps potentially violating descent by analyzing the overall effect of many iterations at once rather than the typical one-iteration inductions used in most first-order method analyses. We … Read more
It is well-known that by adding integrality constraints to the semidefinite programming (SDP) relaxation of the max-cut problem, the resulting integer semidefinite program is an exact formulation of the problem. In this paper we show similar results for a wide variety of discrete optimization problems for which SDP relaxations have been derived. Based on a … Read more
We study a class of polynomial optimization problems with a robust polynomial matrix inequality constraint for which the uncertainty set is defined also by a polynomial matrix inequality (including robust polynomial semidefinite programs as a special case). Under certain SOS-convexity assumptions, we construct a hierarchy of moment-SOS relaxations for this problem to obtain convergent upper … Read more
Low-rank matrix completion consists of computing a matrix of minimal complexity that recovers a given set of observations as accurately as possible. Unfortunately, existing methods for matrix completion are heuristics that, while highly scalable and often identifying high-quality solutions, do not possess any optimality guarantees. We reexamine matrix completion with an optimality-oriented eye. We reformulate … Read more
Moment-based distributionally robust optimization (DRO) provides an optimization framework to integrate statistical information with traditional optimization approaches. Under this framework, one assumes that the underlying joint distribution of random parameters runs in a distributional ambiguity set constructed by moment information and makes decisions against the worst-case distribution within the set. Although most moment-based DRO problems … Read more
\(\) This paper studies hidden convexity properties associated with constrained optimization problems over the set of rotation matrices \(\text{SO}(n)\). Such problems are nonconvex due to the constraint\(X\in\text{SO}(n)\). Nonetheless, we show that certain linear images of \(\text{SO}(n)\) are convex, opening up the possibility for convex optimization algorithms with provable guarantees for these problems. Our main technical … Read more
\(\) Let \(({\bf P},{\bf D})\) be a primal-dual pair of SDPs with a nonzero finite duality gap. Under such circumstances, \({\bf P}\) and \({\bf D}\) are weakly feasible and if we perturb the problem data to recover strong feasibility, the (common) optimal value function \(v\) as a function of the perturbation is not well-defined at … Read more