We study the convergence rate of the moment-SOS (sum-of-squares) hierarchy for polynomial optimization problems (POPs) on a bounded subset of the real line described by arbitrary polynomial inequalities. We prove that, for every fixed univariate POP, the relaxation error is bounded by $O(1/r^2)$, where $r$ is the relaxation order. In particular, boundary degeneracies in the … Read more
Consider a discrete optimal transport problem that has at least two consumers. We show that the Monge and Kantorovich versions of such a discrete optimal transport problem are equivalent for all cost functions if and only if the supply from all the suppliers are equal, and the demand from every consumer is an integral multiple … Read more
The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \[ \mathrm{sym}(S):=\max\{\alpha\ge0:\text{ there exists }x\in S\text{ such that } -\alpha(S-x)\subseteq S-x\}\,, \]where such an \(x\) is called a Minkowski center. We prove that every convex body \(S\) admits a \(\sqrt{\frac{n}{\mathrm{sym}(S)}}\)-rounding of \(S\), namely, there exists an origin-centered ellipsoid \(E\) and a center \(c\) such … Read more
In this paper, we develop a systematic framework for deriving explicit error bounds for semidefinite feasibility problems without assuming strict feasibility (Slater’s condition), a setting in which existing results are limited. Our main technical contribution is the introduction of radial-type H\”{o}lder error bounds, where the error bound constant depends explicitly on the norm of the … Read more
We classify the facial exposedness of completely positive cones over symmetric cones in terms of the rank of the associated Euclidean Jordan algebras. The completely positive cones are facially exposed when the rank is at most $2$, but are not facially exposed when the rank is at least $5$. Facial exposedness is not completely determined … Read more
The integrality gap of the subtour elimination relaxation for the Traveling Salesman Problem is a longstanding open problem, epitomized by the \(\frac{4}{3}\)-conjecture. Understanding this gap requires a detailed analysis of the extreme points of the subtour elimination polytope. In this work, we introduce a new perspective for studying the integrality gap through what we call … Read more
We address the classical Dantzig – Fulkerson – Johnson formulation of the symmetric metric Traveling Salesman Problem and study the integrality gap of its linear relaxation, namely the Subtour Elimination Problem (SEP). This integrality gap is conjectured to be 4/3. We prove that, when solving a problem on n nodes, if the optimal SEP solution … Read more
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
This paper presents a Matlab implementation of an arc-search infeasible interior point algorithm for linear programming (LP), which has a proven polynomial bound of O(√nL), the best among all interior-point algorithms for LP. Software architecture and major functions are discussed. Its ease of use is described by a simple example. Crucial strategies are summarized. Quality … Read more
Dadush et al.\ (2024) recently developed a scaling-invariant layered least squares algorithm for linear programming whose complexity depends on the optimal condition measure $\bar{\chi}_A^*$. Their work builds on Vavasis and Ye’s (1996) algorithm whose running time depends only on the constraint matrix $A$ through the condition number $\bar{\chi}_A$. Monteiro-Tsuchiya (2003) defined the optimal condition number … Read more