semidefinite programming

On the Lasserre hierarchy of semidefinite programming relaxations of convex polynomial optimization problems

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , ,

The Lasserre hierarchy of semidefinite programming approximations to convex polynomial optimization problems is known to converge finitely under some assumptions. [J.B. Lasserre. Convexity in semialgebraic geometry and polynomial optimization. SIAM J. Optim. 19, 1995-2014, 2009.] We give a new proof of the finite convergence property, that does not require the assumption that the Hessian of … Read more

Convex envelopes for quadratic and polynomial functions over polytopes

Categories Global Optimization Theory Tags , , , ,

In this paper we consider the problem of computing the value and a supporting hyperplane of the convex envelope for quadratic and polynomial functions over polytopes with known vertex set. We show that for general quadratic functions the computation can be carried on through a copositive problem, but in some cases (including all the two-dimensional … Read more

The Inexact Spectral Bundle Method for Convex Quadratic Semidefinite Programming

Categories Convex and Nonsmooth Optimization, Semi-definite Programming, Unconstrained Optimization Tags , ,

We present an inexact spectral bundle method for solving convex quadratic semidefinite optimization problems. This method is a first-order method, hence requires much less computational cost each iteration than second-order approaches such as interior-point methods. In each iteration of our method, we solve an eigenvalue minimization problem inexactly, and solve a small convex quadratic semidefinite … Read more

Min-Max Theorems Related to Geometric Representations of Graphs and their SDPs

Categories Combinatorial Optimization, Semi-definite Programming Tags , , ,

Lovasz proved a nonlinear identity relating the theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish min-max theorems and to translate results related to one of the graph invariants above to the other. Classical concepts in tensegrity theory … Read more

SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs

Categories Combinatorial Optimization, Semi-definite Programming Tags , , , ,

We consider low-rank semidefinite programming (LRSDP) relaxations of unconstrained {-1,1} quadratic problems (or, equivalently, of Max-Cut problems) that can be formulated as the nonconvex nonlinear programming problem of minimizing a quadratic function subject to separable quadratic equality constraints. We prove the equivalence of the LRSDP problem with the unconstrained minimization of a new merit function … Read more

Semidefinite Relaxations for Non-Convex Quadratic Mixed-Integer Programming

Categories (Mixed) Integer Nonlinear Programming, Linear, Cone and Semidefinite Programming, Quadratic Programming Tags , ,

We present semidefinite relaxations for unconstrained non-convex quadratic mixed-integer optimization problems. These relaxations yield tight bounds and are computationally easy to solve for medium-sized instances, even if some of the variables are integer and unbounded. In this case, the problem contains an infinite number of linear constraints; these constraints are separated dynamically. We use this … Read more

Parallel solver for semidefinite programming problem having sparse Schur complement matrix

Categories Semi-definite Programming Tags , ,

SemiDefinite Programming (SDP) problem is one of the most central problems in mathematical programming. SDP provides a practical computation framework for many research fields. Some applications, however, require solving large-scale SDPs whose size exceeds the capacity of a single processor in terms of computational time and available memory. SDPARA (SemiDefinite Programming Algorithm paRAllel version) developed … Read more

On Doubly Positive Semidefinite Programming Relaxations

Categories Quadratic Programming, Semi-definite Programming Tags ,

Recently, researchers have been interested in studying the semidefinite programming (SDP) relaxation model, where the matrix is both positive semidefinite and entry-wise nonnegative, for quadratically constrained quadratic programming (QCQP). Comparing to the basic SDP relaxation, this doubly-positive SDP model possesses additional O(n2) constraints, which makes the SDP solution complexity substantially higher than that for the … Read more

The Approach of Moments for Polynomial Equations

Categories Semi-definite Programming Tags , , ,

In this article we present the moment based approach for computing all real solutions of a given system of polynomial equations. This approach builds upon a lifting method for constructing semidefinite relaxations of several nonconvex optimization problems, using sums of squares of polynomials and the dual theory of moments. A crucial ingredient is a semidefinite … Read more

Distributionally Robust Joint Chance Constraints with Second-Order Moment Information

Categories Robust Optimization Tags , ,

We develop tractable semidefinite programming (SDP) based approximations for distributionally robust individual and joint chance constraints, assuming that only the first- and second-order moments as well as the support of the uncertain parameters are given. It is known that robust chance constraints can be conservatively approximated by Worst-Case Conditional Value-at-Risk (CVaR) constraints. We first prove … Read more