Linear, Cone and Semidefinite Programming

Semidefinite hierarchies for diagonal unitary invariant bipartite quantum states

Published: 2025/12/18

Semi-definite Programming Completely positive matrix, copositive matrix, DPS hierarchy, entanglement, Moment approach, Quantum bipartite states, semidefinite programming, Separable states, sparsity, sum-of-squares polynomial

We investigate questions about the cone $\mathrm{SEP}_n$ of separable bipartite states, consisting of the Hermitian matrices acting on $\mathbb{C}^n\otimes\mathbb{C}^n$ that can be written as conic combinations of rank one matrices of the form $xx^*\otimes yy^*$ with $x,y\in\mathbb{C}^n$. Bipartite states that are not separable are said to be entangled. Detecting quantum entanglement is a fundamental task … Read more

Density, Determinacy, Duality and a Regularized Moment-SOS Hierarchy

Published: 2025/12/18

Didier Henrion

Linear, Cone and Semidefinite Programming, Semi-definite Programming polynomial optimization, Semidefinite optimization

The standard moment-sum-of-squares (SOS) hierarchy is a powerful method for solving global polynomial optimization problems. However, its convergence relies on Putinar’s Positivstellensatz, which requires the feasible set to satisfy the algebraic Archimedean property. In this paper, we introduce a regularized moment-SOS hierarchy capable of handling problems on unbounded sets or bounded sets violating the Archimedean … Read more

A Dual Riemannian ADMM Algorithm for Low-Rank SDPs with Unit Diagonal

Published: 2025/12/04

Jie Wang

0-1 Programming, Semi-definite Programming alternating direction method of multipliers, augmented lagrangian method, Burer-Monteiro factorization, low-rank solution, manifold optimization, moment-SOS relaxation, polynomial optimization, semidefinite programming

This paper proposes a dual Riemannian alternating direction method of multipliers (ADMM) for solving low-rank semidefinite programs with unit diagonal constraints. We recast the ADMM subproblem as a Riemannian optimization problem over the oblique manifold by performing the Burer-Monteiro factorization. Global convergence of the algorithm is established assuming that the subproblem is solved to certain … Read more

Semidefinite programming via Projective Cutting Planes for dense (easily-feasible) instances

Published: 2025/12/01

Daniel Porumbel

Linear, Cone and Semidefinite Programming, Semi-definite Programming cutting planes, mixed-integer nonlinear programming, semidefinite programming

The cone of positive semi-definite (SDP) matrices can be described by an infinite number of linear constraints. It is well-known that one can optimize over such a feasible area by standard Cutting Planes, but work on this idea remains a rare sight, likely due to its limited practical appeal compared to Interior Point Methods (IPMs). … Read more

Sparse Multiple Kernel Learning: Alternating Best Response and Semidefinite Relaxations

Published: 2025/12/01

Dimitris Bertsimas

Caio de Próspero Iglesias

Nicholas A. G. Johnson

Convex Optimization, Semi-definite Programming, Statistics alternating best response, classification in machine learning, convex relaxation, kernel, sparsity

We study Sparse Multiple Kernel Learning (SMKL), which is the problem of selecting a sparse convex combination of prespecified kernels for support vector binary classification. Unlike prevailing $\ell_1$‐regularized approaches that approximate a sparsifying penalty, we formulate the problem by imposing an explicit cardinality constraint on the kernel weights and add an $\ell_2$ penalty for robustness. … Read more

The SCIP Optimization Suite 10.0

Published: 2025/11/24

Integer Programming, Linear, Cone and Semidefinite Programming, Optimization Software and Modeling Systems branch-and-cut algorithm, Branch-and-price algorithm, column generation, constraint integer programming, linear programming, mixed-integer linear programming, mixed-integer nonlinear programming, mixed-integer semidefinite programming, optimization solver, parallelization

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization, centered around the constraint integer programming (CIP) framework SCIP. This report discusses the enhancements and extensions included in SCIP Optimization Suite 10.0. The updates in SCIP 10.0 include a new solving mode for exactly solving rational mixed-integer linear programs, a new presolver … Read more

Column Generation for Generalized Min-Cost Flows with Losses

Published: 2025/11/12, Updated: 2025/11/13

Jonas Alker

Marc E. Pfetsch

Combinatorial Optimization, Linear Programming, Network Optimization column generation, generalized min-cost flows

The generalized flow problem deals with flows through a network with losses or gains along the arcs. Motivated by energy networks, this paper concentrates on the case with losses along cycles. Such networks can become extremely large, mostly because they are considered over large time horizons. We therefore develop a column generation approach for a … Read more

On the Convexification of a Class of Mixed-Integer Conic Sets

Published: 2025/11/01

GuxinDU

Rui Chen

Linchuan Wei

(Mixed) Integer Nonlinear Programming, Cone Programming

We investigate mixed-integer second-order conic (SOC) sets with a nonlinear right-hand side in the SOC constraint, a structure frequently arising in mixed-integer quadratically constrained programming (MIQCP). Under mild assumptions, we show that the convex hull can be exactly described by replacing the right-hand side with its concave envelope. This characterization enables strong relaxations for MIQCPs … Read more

Inexact subgradient algorithm with a non-asymptotic convergence guarantee for copositive programming problems

Published: 2025/10/31

Mitsuhiro Nishijima

Pierre-Louis Poirion

Akiko Takeda

Convex and Nonsmooth Optimization, Global Optimization, Linear, Cone and Semidefinite Programming completely positive matrices, copositive programming, semi-infinite programming, standard quadratic programming, subgradient-based method

In this paper, we propose a subgradient algorithm with a non-asymptotic convergence guarantee to solve copositive programming problems. The subproblem to be solved at each iteration is a standard quadratic programming problem, which is NP-hard in general. However, the proposed algorithm allows this subproblem to be solved inexactly. For a prescribed accuracy $\epsilon > 0$ … Read more

A Practical Adaptive Subgame Perfect Gradient Method

Published: 2025/10/30

Alan Luner

Benjamin Grimmer

Convex Optimization, Second-Order Cone Programming adaptive, auto-conditioning, convex optimization, linesearch-free, non-asymptotic complexity, preconditioning, subgame perfect

We present a performant gradient method for smooth convex optimization, drawing inspiration from several recent advances in the field. Our algorithm, the Adaptive Subgame Perfect Gradient Method (ASPGM) is based on the notion of subgame perfection, attaining a dynamic strengthening of minimax optimality. At each iteration, ASPGM makes a momentum-type update, optimized dynamically based on … Read more