Semi-definite Programming

Sharp Singularity-Degree Bounds for Equality-Generated SDP–RLT Relaxations of Binary Programs

Categories Convex Optimization, Semi-definite Programming

Singularity degree is an important measure of semidefinite programming (SDP) degeneracy, but it is generally unavailable a priori from the problem data. We augment the Shor relaxation of binary sets \(\{x\in\{0,1\}^n:Ax=b\}\) with the first-level Reformulation–Linearization Technique (RLT) equations generated by the defining linear equalities. For the resulting equality-generated SDP–RLT relaxation, we determine the exact worst-case … Read more

Sparsity-Preserving Integration of Convex Curvature Information into Linear Relaxations for Quadratic Unconstrained Binary Optimization

Categories Linear Programming, Quadratic Programming, Semi-definite Programming

We systematically investigate the potentials of improving the lower bound obtained with a linear relaxation of the Quadratic Unconstrained Binary Optimization problem by integrating curvature information from an accompanying quadratic convex underestimator via gradient inequalities. On the one hand, we exemplify to which extent this hybrid approach may provide a lower bound that is strictly … Read more

A Complete Characterization of Optimal Subgradient Methods for Lipschitz Convex Minimization

Categories Nonsmooth Optimization, Semi-definite Programming Tags ,

We consider the design of optimal fixed-step first-order methods for $M$-Lipschitz convex optimization given $\|x_0-x_\star\|\leq D$. Prior works have identified several distinct fixed-step methods, parameterized by a matrix of stepsizes $W$, with the (information-theoretic) minimax optimal rate $MD/\sqrt{N+1}$ of objective gap convergence. We provide a complete characterization of every optimal fixed-step method. Moreover, we show … Read more

Aggregated quadratic formulations and semidefinite relaxations of the stable set polytope

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

The stable set problem admits various binary linear and quadratic formulations. The Shor relaxation of a particular quadratic formulation is the well-known theta body. We consider aggregations of quadratic constraints of this formulation, yielding exact and inexact quadratic formulations of the stable set problem, and then establish conditions under which the aggregated quadratic formulation is … Read more

A Lifting-and-Splitting Framework for Risk-Averse Distributionally Robust Multi-Item Newsvendor Problems

Categories Robust Optimization, Semi-definite Programming, Supply Chain Management

Risk-averse distributionally robust multi-item newsvendor problems provide a fundamental model for inventory decisions under demand uncertainty, limited distributional information, and downside-risk concerns. We study this problem under mean-covariance demand ambiguity, where the decision maker maximizes the worst-case conditional value-at-risk of profit. While cross-item demand correlations are important for portfolio-level inventory decisions, they are difficult to … Read more

Order-2 Tightness of Block-Sparse SOS Relaxations for One-Layer ReLU Network Verification with a Matching Input-Sharing Graph

Categories Data Science Theory, Quadratic Programming, Semi-definite Programming Tags , , , ,

Azuma, Kim, and Yamashita formulated the verification problem for one-layer ReLU networks as a quadratically constrained quadratic program and established tight semidefinite relaxations for the edgeless case and for one-unit settings. In this work, we represent the sharing pattern of undecided ReLUs over a box input set through an input-sharing graph and focus on the … Read more

A Polynomial-Time Algorithm for Coloring Perfect Graphs Based on Walk Counting

Categories Combinatorial Optimization, Semi-definite Programming Tags , ,

We present a polynomial-time algorithm for optimally coloring perfect graphs that is based entirely on graph-theoretic operations. At its core, the algorithm decides whether a perfect graph contains a clique of a given size by iteratively counting walks in the graph with certain weights assigned to its edges and nonedges. These weights are initialized according … Read more

Local-to-Global Exactness of SDP Relaxations for Sparse QCQPs

Categories Global Optimization Theory, Quadratic Programming, Semi-definite Programming Tags , , , , , , , ,

We study exact semidefinite programming (SDP) relaxation for a given sparse quadratically constrained quadratic program (QCQP). The SDP relaxation is exact if, whenever it has an optimal solution, it admits a rank-at-most-one optimal solution that corresponds to an optimal solution of the QCQP. Using the maximal cliques of a chordal extension of the aggregate sparsity … Read more

Disjunctive Sum of Squares

Categories Cone Programming, Convex Optimization, Semi-definite Programming Tags , , , , , , ,

We introduce the concept of disjunctive sum of squares for certifying nonnegativity of polynomials. Unlike the popular sum of squares approach where nonnegativity is certified by a single algebraic identity, the disjunctive sum of squares approach certifies nonnegativity with multiple algebraic identities which can be found in parallel. Our main result is a disjunctive Positivstellensatz … Read more

Maximum Cuts and Fractional Cut Covers: A Computational Study of a Randomized Semidefinite Programming Approach

Categories Approximation Algorithms, Optimization Software and Modeling Systems, Semi-definite Programming

We present experimental work on a primal-dual framework simultaneously approximating maximum cut and weighted fractional cut-covering instances. In this primal-dual framework, we solve a semidefinite programming (SDP) relaxation to either the maximum cut problem or to the weighted fractional cut-covering problem, and then independently sample a collection of cuts via the random-hyperplane technique. We then … Read more