Convex Optimization – Page 2 – Optimization Online

Solving Quasi-Variational Inequalities Using the Progressive Decoupling of Linkages

Published: 2026/08/27

Complementarity and Variational Inequalities, Convex Optimization, Game Theory quasi-variational inequality; generalized Nash equilibrium problem; progressive decoupling; Spingarn’s partial inverse; proximal point method.

Inspired by the progressive decoupling of linkages methodology for optimization and variational inequalities, we propose an algorithm for solving quasi-variational inequalities as a sequence of variational inequalities. Our method is shown to converge locally under some regularity conditions and globally when such conditions hold throughout the entire domain. Separately, under other type of assumptions, global … Read more

Sharp Singularity-Degree Bounds for Equality-Generated SDP–RLT Relaxations of Binary Programs

Published: 2026/08/27

Hao Hu

Convex Optimization, Semi-definite Programming

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

Two Spectral Gaps: Decentralized Optimization over Intersections of Local Convex Sets

Published: 2026/08/27

Sarvagya Jha

Convex Optimization, Nonsmooth Optimization, Parallel Algorithms convex feasibility, decentralized optimization, friedrichs angle, Gossip algorithms, linear regularity, oracle complexity

We study decentralized minimization of an average of strongly convex, smooth local objectives over an intersection of agent-private closed convex sets, where each agent knows only its own objective and its own set and agents communicate over a gossip network. We show that the complexity is controlled by a single geometric scalar, which we call … Read more

Implicit Primal-Dual Guarantees in Unconstrained First-Order Minimization

Published: 2026/08/27

Convex Optimization, Nonsmooth Optimization acceleration, Convergence Guarantees, first-order methods, performance estimation problems, primal-dual gaps

This work considers the design of first-order convex optimization algorithms and convergence proofs. In particular, we consider nonsmooth Lipschitz and smooth problems accessed through a subgradient or gradient oracle, respectively. For the general class of fixed-step first-order methods, prior work on Performance Estimation Problems (PEPs) has shown that structured, tight convergence proofs typically exist. Under … Read more

Tight Nonasymptotic Local Convergence of Sinkhorn-Knopp

Published: 2026/08/12, Updated: 2026/09/27

Wenzhi Gao

Convex Optimization, Unconstrained Optimization

We revisit the Sinkhorn-Knopp (SK) algorithm for the matrix scaling problem. Despite extensive literature on the global convergence of SK and its variants, its local linear convergence behavior remains less understood. We address this gap by providing the first nonasymptotic local analysis of SK that matches the rate obtained from existing asymptotic Jacobian-based arguments. We … Read more

A Domain-Specific Harness for End-to-End Automation of Optimization Research

Published: 2026/08/07

Convex Optimization, Nonlinear Optimization, Optimization Software and Modeling Systems first-order methods, formal verification, Large Language Models (LLMs), performance estimation problems

We present AutoOPT, a domain-specific harness for end-to-end automation of optimization research. AutoOPT organizes the discovery of optimal first-order methods into four stages: numerical design through the BnB-PEP methodology; symbolic discovery of the analytic description and a convergence proof through frontier large language models (LLMs); formal verification in the Lean 4 proof assistant; and human … Read more

Optimal Nonergodic Primal-Dual Complexity of Efficient Inexact Parameter-Free Augmented Lagrangian Methods

Published: 2026/08/04, Updated: 2026/08/10

Constrained Nonlinear Optimization, Convex Optimization, Nonlinear Optimization augmented Lagrangian, composite convex optimization, kkt points, optimal complexity, parameter-free

Augmented Lagrangian (AL) methods are a classical framework for constrained optimization, but for directly verifiable approximate KKT points, known first-order complexity bounds for standard inexact AL methods are suboptimal, while the best known proximal augmented Lagrangian (PAL) bounds retain an additional logarithmic factor. We consider linearly constrained convex composite problems with a smooth convex term … Read more

Entropy-Smooth Convex Optimization Cannot Be Accelerated

Published: 2026/07/30

Convex and Nonsmooth Optimization, Convex Optimization, Optimization in Data Science complexity, convex optimization, nonlinear programming

We prove an $\Omega(L/T)$ lower bound for the convergence rate of minimization in the class of functions that are convex and $L$-smooth relative to negative entropy on the standard $d$-simplex, valid for every first-order method when $d = \Omega(T^2)$. In particular, this shows that mirror descent is optimal up to a logarithmic factor in this … Read more

On the boundedness of infinite products of relaxed projections: perturbations resilience and dynamic string-averaging

Published: 2026/07/29

Basic Sciences Applications, Convex Optimization, Infinite Dimensional Optimization Affine subspace, boundedness, control, dynamic string-averaging, half-space, infinite product, innately regular, perturbation resilience, relaxed projection, strongly nonexpansive mapping

Very recently (2026), Bauschke and Tung extended from finite- to infinite-dimensional Hilbert spaces a result published by Meshulam in 1996 (following an earlier result of Aharoni-Duchet-Wajnryb from 1984) regarding the boundedness of infinite products of relaxed projections onto a finite family of closed affine subspaces. In the present note we extend in various ways the … Read more

Automorphisms of hyperbolic polynomials

Published: 2026/06/11

Michael Orlitzky

Convex Optimization, Linear, Cone and Semidefinite Programming automorphism group, clan, homogeneous cone, hyperbolicity cone, Siegel domain

The pair $ (p,e) $ is hyperbolic if $ p : \mathbb{R}^{n} \to \mathbb{R} $ is a homogeneous polynomial, if $ e \in \mathbb{R}^{n} $, if $ p(e) > 0 $, and if the roots of $ t \mapsto p(te – x) $ are real for all $ x \in \mathbb{R}^{n} $. In that case, … Read more