A coordinated effort to formalize the mathematics of operations research in Lean 4.
Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.
The Proximal Alternating Direction Method of Multipliers in the Nonconvex Setting: Convergence Analysis and Rates 1: Bounded Iterates Converge to a KKT Point with Finite Length Under the KL PropertyResearch Paper
Many problems in signal processing, statistics and machine learning are of the form minx{g(Ax)+h(x)}: a smooth data-fitting term h, plus a possibly nonsmooth and nonconvex regularizer g applied to a linear image Ax of the variable. Examples are total-variation-type penalties with nonconvex potentials, ℓ0-type sparsity terms, and constraints Ax∈C…
First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping II: The Inertial Proximal Algorithm (IPAHD) Satisfies f(x_k) − min f = O(1/δ_k)Research Paper
Accelerated first-order methods, such as Nesterov's method and FISTA, reach a convergence rate of O(1/k2) on the objective values of a smooth convex function, against O(1/k) for plain gradient descent. Since the work of Su, Boyd and Candès (arXiv:1503.01243), these methods are studied through their continuous-time limits, second-order…
First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping III: The Inertial Gradient Algorithm (IGAHD) Satisfies f(x_k) − min f = O(1/k²) and Σ k²‖∇f(x_k)‖² < ∞Research Paper
Accelerated gradient methods use information from earlier iterates to reduce the objective gap of a smooth convex optimization problem faster than ordinary gradient descent. Their behavior depends on the precise momentum rule. Attouch, Chbani, Fadili, and Riahi study a discrete rule with an additional difference of consecutive gradients, motivated by an…
First-Order Optimization Algorithms via Inertial Systems with Hessian Driven Damping IV: For µ-Strongly Convex f, (DIN)2√µ,β Trajectories Satisfy f(x(t)) − min f ≤ Ce^{−√µ(t−t₀)/2}Research Paper
Accelerated first-order methods for convex minimization, such as Nesterov's method and Polyak's heavy ball method, are now routinely studied through their continuous-time limits: second-order differential equations whose trajectories descend toward a minimizer. In the time-continuous setting the convergence analysis is a Lyapunov argument, and a good…
Regularization via Mass Transportation I: Wasserstein-Robust Linear Classification with Label Flipping Is a Finite Convex ProgramResearch Paper
A classifier trained from finitely many examples can perform well on those examples while responding poorly to changes in the feature distribution or to mislabeled observations. Distributionally robust learning addresses this by choosing a classifier against every probability distribution within a specified distance of the empirical distribution. The…
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization 1: All Four Frank-Wolfe Variants Reach Duality Gap ≤ 2βC_f(1+δ)/(K+2), β = 27/8, Within K IterationsResearch Paper
The Frank–Wolfe method, also called the conditional-gradient method, minimizes a smooth convex objective over a compact convex set while asking only for a minimizer of a linear function over that set. In domains where a linear optimization oracle is easier than a projection, this distinction changes which algorithms are practical. Examples in Jaggi's paper…
Stochastic Dual Coordinate Ascent Methods for Regularized Loss Minimization 2: With (1/γ)-Smooth Losses, SDCA Reaches Expected Duality Gap ε after (n + 1/(λγ))·log((n + 1/(λγ))/ε) IterationsResearch Paper
Regularized loss minimization (training a linear predictor with a convex loss and an ℓ2 penalty) covers support vector machines, ridge and logistic regression, and much of classical linear learning. A standard way to solve these problems at scale is dual coordinate ascent: optimize the dual problem one coordinate, i.e. one training example, at a time.…
Constrained Assortment Optimization for the Nested Logit Model 3: Under Cardinality Constraints, O(n²) Candidate Assortments per Nest Include an Optimal Solution of Problem (7) for Every u ≥ 0Research Paper
A retailer that decides which products to put on a shelf, or an airline that decides which fare classes to open, faces an assortment problem: the set of products offered changes which product a customer buys, and the firm wants the offer set that maximizes expected revenue. When customers first pick a category (a brand, a store aisle, a flight time) and…
Constrained Assortment Optimization for the Nested Logit Model 2: If Each Nest's Candidates Include an α-Approximate Solution of Problem (7) for Every u ≥ 0, Some Combination Earns at Least Z*/αResearch Paper
A retailer chooses which products to offer, knowing that what customers buy depends on what is on the shelf. In the nested logit model (Williams 1977) products are grouped into nests, and a customer first picks a nest (or leaves) and then a product inside it. Choosing the offer set to maximize expected revenue is the assortment problem. In practice each…
Most Tensor Problems Are NP-Hard 5: The Stability Number Is Read Off the Largest Eigenvalue of an Explicit Symmetric 3-TensorResearch Paper
For a real symmetric matrix, the largest eigenvalue is the maximum of the quadratic form x⊤Ax on the unit sphere, and it is computable to any accuracy in polynomial time. Tensor eigenvalues, introduced independently by Lim (2005) and Qi (2005), extend this picture to higher order: they are the stationary values of the cubic form …
A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 3: The Exponential-Cone Barrier Does Not Have Negative CurvatureResearch Paper
Interior-point methods for conic optimization are best understood on symmetric cones: the nonnegative orthant, the second-order cone and the cone of positive semidefinite matrices. On these cones the barrier functions are self-scaled, and Nesterov and Todd showed that every primal-dual pair (x,s) then has a unique scaling point w with s=F′′(w)x and …
Most Tensor Problems Are NP-Hard 3: The Clique Number Is the Unique l for Which an Explicit Graph Tensor Has Spectral Norm 1Research Paper
The spectral norm of a matrix, its largest singular value, is computable in polynomial time to any accuracy. Its analogue for 3-tensors appears in the analysis of multilinear systems, in the best rank-1 approximation of a data array, in quantum information (the geometric measure of entanglement), and in the injective norm of tensor products. Hillar and Lim, …
A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 1: Along the Combined Corrector Direction the Residuals and the Complementarity Gap Both Scale by 1 − α(1 − γ)Research Paper
Conic optimization over the exponential coneKexp=cl{x∈R3:x1≥x2ex3/x2,x2>0} models entropy, relative
entropy, logistic regression, log-sum-exp and geometric programming. Unlike the nonnegative orthant, the
second-order cone and the semidefinite cone, the exponential cone is not symmetric (self-scaled), so the…
User-Friendly Tail Bounds for Sums of Random Matrices II: Matrix Gaussian and Rademacher Series Have Subgaussian Tails with Variance Parameter ‖Σ A_k²‖Research Paper
A matrix Gaussian series∑kγkAk, a sum of fixed self-adjoint matrices each multiplied by an independent standard normal variable, is the simplest sum of independent random matrices. It already appears in the analysis of random designs, in compressed sensing, in randomized numerical linear algebra and in quantum information, wherever one needs…
An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem 2: The Best Lagrangean Bound of the Integer Relaxation RF Is at Least the LP Relaxation Bound, Sometimes StrictlyResearch Paper
In two-echelon distribution goods travel from a central depot to intermediate facilities, called satellites, on large first-level vehicles, and from the satellites to customers on smaller second-level vehicles. City logistics schemes that keep heavy trucks out of urban centres are the standard example. The two-echelon capacitated vehicle routing problem (2E-…
Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms II: Iterative Hard Thresholding for Sparse Least Squares Converges to an L-Stationary PointResearch Paper
Many estimation problems ask for a vector with few nonzero entries that fits data well. The best-known case is compressed sensing: recover a sparse x∈Rn from m≪n noisy linear measurements b≈Ax. Fitting such data under an explicit sparsity budget leads to the sparse least-squares problem
A Learning Theory Approach to Non-Interactive Database Privacy 2: An ε-Differentially Private Mechanism Useful on Databases of Size at Most VCDIM(C)/2 Has Error α ≥ Ω(1/(4+16ε))Research Paper
A data curator holds a database of n records and wants to publish answers to a large family of statistical questions about it without revealing any individual record. Differential privacy (Dwork, McSherry, Nissim, Smith 2006) makes the requirement precise, and the most basic questions are counting queries: what fraction of the records satisfy a given…
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 3: For Block-Constrained Problems, Uniform Coordinate Descent Has Rate n/(n + k), Linear Under Strong ConvexityResearch Paper
Coordinate descent methods update one block of variables at a time. They are the method of choice when the number of variables is so large that even one full gradient is too expensive, while a single partial derivative is cheap: support vector machines, ℓ1-regularized regression, and large sparse least-squares problems are the standard examples. Yu.…
User-Friendly Tail Bounds for Sums of Random Matrices I: The Master Tail Bound — the Largest Eigenvalue of an Independent Sum Is Controlled by the Sum of the Matrix Cumulant Generating FunctionsResearch Paper
Sums of independent random matrices appear wherever a large matrix is built from random pieces: sample covariance matrices in statistics, random sparsification and sampling in numerical linear algebra, random graphs and their Laplacians, and compressed sensing. The basic question is how far the largest eigenvalue of such a sum can stray above its typical…
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 4: Accelerated Coordinate Descent ACDM Has Expected Error at Most (n/(k + 1))²·(2‖x₀ − x*‖₁² + (f(x₀) − f*)/n²)Research Paper
Coordinate descent methods update one block of variables at a time. For problems with millions or billions of variables, where even one full gradient is too expensive to compute or store, a step that touches a single block can be orders of magnitude cheaper than a full gradient step. Nesterov's Efficiency of coordinate descent methods on huge-scale…
Optimization Methods on Riemannian Manifolds and Their Application to Shape Space 2: Riemannian Fletcher-Reeves Conjugate Gradient with Strong Wolfe Steps Has liminf of the Gradient Norm ZeroResearch Paper
Many optimization problems in shape analysis, computer vision, numerical linear algebra and statistics have a nonlinear search space: a sphere, a Stiefel or Grassmann manifold, a space of curves modulo reparametrization. Projecting iterates of a Euclidean method back onto the constraint set loses the geometry, so one designs methods that move along the…
An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem 3: Every Solution Cheaper Than an Upper Bound Uses a Configuration of First-Level Routes Passing the Pruning TestsResearch Paper
City logistics often moves goods in two stages: large trucks bring freight from a central depot to a few intermediate satellites, and small vehicles distribute it from the satellites to the customers. The two-echelon capacitated vehicle routing problem (2E-CVRP) is the basic optimization model of such systems; it contains the capacitated location-routing…
Online Learning and Online Convex Optimization 1: Follow-the-Regularized-Leader with a σ-Strongly-Convex Regularizer Has Regret at Most R(u) − min R + TL²/σResearch Paper
Online convex optimization is a repeated game between a learner and an environment. In each round the learner commits to a vector, the environment then reveals a convex loss function, and the learner pays the loss of its vector. No statistical assumption is made about how the losses are generated; they may be chosen adversarially. Performance is measured…
Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 2: On a Regularized Objective, RCDM(1, x₀) Finds an ε-Solution with Probability ≥ β Within the Iteration Bound (3.11)Research Paper
Randomized coordinate descent updates one block of variables per iteration, chosen at random. For problems whose dimension makes even one full gradient expensive (the "huge-scale" problems of the title, such as sparse least squares or truss topology design), a coordinate step can cost a tiny fraction of a gradient step. Nesterov's paper (CORE Discussion…
Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 2: For F Smooth at the Optimum, SGD's Last and Averaged Iterates Attain 2µG²/(λ²T) and 16µG²/(λ²T)Research Paper
Stochastic gradient descent (SGD) is the standard method for minimizing an expected loss F(w)=Ez[ℓ(w,z)] when only noisy gradients are available: in machine learning, w is a predictor, z a random example, and each step uses the gradient of the loss on one fresh example. When F is strongly convex, as for regularized learning problems such as…