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
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
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
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
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