Month: August 2026

Symmetry-dependence in Rounding of a Convex Body

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

The symmetry measure of a convex body \(S\subset\mathbb{R}^n\) is given by: \(\mathrm{sym}(S):=\max\{\alpha\ge0:\ \mathrm{there\ exists}\ x\in S\ \mathrm{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 that the … Read more

Radial-type error bounds for semidefinite feasibility problems without strict feasibility: qualitative estimates and asymptotic tightness

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

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

UGM: A Unified Framework and New Perspectives for Accelerated Gradient Methods in Smooth and Strongly Convex Optimization

Categories Convex Optimization Tags ,

In this paper, we propose a unified framework for accelerated gradient methods, dubbed UGM, which subsumes a wide range of accelerated and conventional gradient-type methods designed for minimizing $L$-smooth and $\mu$-strongly convex functions. We demonstrate that the iteration update of the proposed framework can be intrinsically interpreted as a hybrid combination of the heavy-ball method … Read more

Classification of facial exposedness of completely positive cones over symmetric cones

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

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

New inexact adaptive proximal gradient algorithms for nonconvex composite optimization problems

Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , ,

In this paper, we propose new inexact adaptive proximal gradient algorithms for solving nonconvex composite optimization problems, where the objective is the sum of a differentiable nonconvex function and a convex non-differentiable function. A new relative error criterion to compute the proximal operator inexactly has been proposed together with new adaptive strate- gies for selecting … Read more

Integrated Master Planning and Demand Fulfillment in Multi-Echelon Supply Chains: Partial vs. All-or-Nothing Fulfillment

Categories Applications - OR and Management Sciences, Network Optimization, Supply Chain Management Tags , , , ,

Modern supply chains differ in lead times, bottlenecks, and demand volatility. Advanced Planning Systems conventionally decouple Master Planning (MP) and Demand Fulfillment (DF) hierarchically, which improves tractability but ignores critical interdependencies between material availability, capacity utilization, and delivery promising. We propose an integrated MP‑DF model, formulate it as a Minimum‑Cost Multicommodity Flow (MCMCF) on a … Read more

Variable Selection for Feature-Based Newsvendor

Categories Applications - OR and Management Sciences, Combinatorial Optimization, Optimization in Data Science

Feature-based newsvendor models use observable covariates to tailor inventory decisions, aiming to balance holding and shortage costs under demand uncertainty. However, high-dimensional feature sets often hinder interpretability and inflate data collection and implementation costs. This paper studies variable selection for the feature-based newsvendor problem under a hard cardinality constraint on the number of selected features. … Read more

The subtle behavior of the facial distance

Categories Combinatorial Optimization, Convex and Nonsmooth Optimization, Polyhedra

We give a simple example that disproves the following 2015 conjecture of Lacoste-Julien and Jaggi concerning the pyramidal width (aka facial distance): The pyramidal width of a set of vertices is non-increasing when another vertex is added (assuming that all previous points remain vertices). In contrast to the recent example by Zhao (arXiv:2607.29555), our counterexample … Read more

An Asymptotic Framework for the Integrality Gap of the Traveling Salesman Problem

Categories 0-1 Programming, Linear Programming Tags , ,

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

The Integrality Gap of the Traveling Salesman Problem is 4/3 if the LP Solution Has at Most n+8 Non-Zero Components

Categories 0-1 Programming, Linear Programming, Polyhedra Tags , ,

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