Linear, Cone and Semidefinite Programming

A One-Factorization Predictor–Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding

Published: 2026/09/30

In a predictor-corrector arc-search method, a point on the predictor arc is first selected and a corrector is then computed at that point. Since the Karush-Kuhn-Tucker (KKT) matrix changes with the selected point, this correction may require a second factorization in each iteration. We propose a one-factorization arc-search method (OFAS) for semidefinite programming (SDP) that … Read more

Level-Set Geometry and the Theoretical Performance of PDHG for Conic Linear Optimization

Published: 2026/09/30

Cone Programming, Linear Programming condition measures, conic optimization, Convergence Guarantees, first-order methods, Linear Optimization

We consider solving (convex) conic linear optimization problems, at the scale where matrix-factorization-free methods are attractive or necessary. The restarted primal-dual hybrid gradient method (rPDHG) — with heuristic enhancements and GPU implementation — has been very successful in solving huge-scale linear optimization problems (LPs). However, its application to more general conic convex optimization problems is … Read more

Applications of the Lorentz positive cone in nonconvex quadratic optimization

Published: 2026/09/24

Linear, Cone and Semidefinite Programming, Quadratic Programming, Second-Order Cone Programming lorentz cone, nonconvex quadratic optimization, second-order cone, semidefinite programming

We consider the Lorentz positive cone of $n \times m$ matrices that map the Lorentz cone in $R^m$ into the Lorentz cone in $R^n$. The Lorentz positive cone and its dual, the cone of Lorentz separable matrices, are shown to provide polynomial-time algorithms for the problem of minimizing a bilinear objective over variables contained in … Read more

A Computational Toolbox for Linear Optimization with Joint Affine Chance Constraints

Published: 2026/09/21

Constrained Nonlinear Optimization, Linear Programming, Optimization Software Benchmark computational toolbox, joint chance constraints, linear programming, proximal methods, spherical--radial decomposition

We present a Julia computational toolbox for linear optimization problems with joint affine chance constraints under elliptically symmetric uncertainty. The toolbox combines a spherical–radial oracle for estimating the joint probability and its gradient with three structured optimization methods: Proximal, Feasible, and Penalty. The oracle supports several elliptically symmetric distributions and is integrated with these methods … Read more

On Spanning-Tree Integrality and a new Branching Rule for the Maximum Cut Problem

Published: 2026/09/17

Combinatorial Optimization, Integer Programming, Semi-definite Programming binary quadratic programming, Branch-and-Bound, combinatorial optimization, integer programming, Maximum Cut Problem, QUBO, semidefinite programming

State-of-the-art exact methods for the Maximum Cut problem are based on solving linear and semidefinite programming relaxations embedded into a branch-and-bound algorithm. For linear programming formulations, it was shown recently that it is thereby sufficient to enforce the integrality of the variables associated with the edges of a spanning tree. Our first contribution is to … Read more

Unshackling Column Generation for Linearized Unconstrained Binary Quadratic Programs

Published: 2026/09/13

Sven Mallach

Integer Programming, Linear Programming, Nonlinear Optimization binary quadratic programming, column generation, linearization, QUBO

When linearizing binary quadratic programs, the most usual way is to replace bilinear products with additional variables constrained to take on consistent values in any feasible solution. In this setting, column generation is a principally desirable solution technique, for instance because the number of such additional linearization variables may be large while many of them … Read more

Convergence rate of the moment-SOS hierarchy for univariate polynomial optimization

Published: 2026/09/02

Global Optimization Theory, Semi-definite Programming polynomial optimization; moments; sums-of-squares

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

On the Equivalence of Monge and Kantarovich Problems in Discrete Optimal Transport

Published: 2026/09/01

Thirumulanathan Dhayaparan

Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming, Optimization of Systems modeled by PDEs

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

Symmetry-dependence in Rounding of a Convex Body

Published: 2026/08/31, Updated: 2026/09/23

Convex Optimization, Linear, Cone and Semidefinite Programming, Polyhedra john ellipsoid, lowner ellipsoid, Minkowski center, rounding, symmetry

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

Published: 2026/08/31

Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Error bounds, facial residual functions, Semidefinite feasibility problems, semidefinite programming

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