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.
Multistage Adaptive Robust Optimization for the Unit Commitment Problem II: Under the W_it-Policy, Robust Generation and Ramping Limits Reduce to the Extreme Total-Load ScenariosResearch Paper
Unit commitment (UC) is the daily scheduling problem of electricity system operators: decide which generators are switched on in each hour of the next day, and how much each produces, so that supply meets the net load at minimum cost while respecting generation limits, ramping limits and transmission limits. With growing shares of wind and solar power, the…
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization 2: If g Is Restricted Strongly Convex and α < 2μ_g λmin(W̃)/L_f², ‖z^k − z*‖²_G Converges Q-Linearly to 0Research Paper
In decentralized consensus optimization, n agents connected by a communication network cooperatively solve
EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization 1: For 0 < α < 2λmin(W̃)/L_f, EXTRA Converges and Its Optimality Residuals Are O(1/k) on Average, o(1/k) at BestResearch Paper
In decentralized consensus optimization a connected network of n agents cooperatively solves
On Well-Posedness of Forward–Backward SDEs—A Unified Approach 2: With Constant Coefficients and σ₃ = 0 the Dominating ODE Has a Bounded Solution for Every T Iff F Has a Suitable Zero or Is LinearResearch Paper
A forward–backward stochastic differential equation (FBSDE) couples a forward diffusion X with a backward equation for a pair (Y,Z) whose terminal value depends on XT. FBSDEs are the probabilistic form of quasilinear parabolic PDEs and appear in stochastic control (the stochastic maximum principle), in mathematical finance (hedging with large investors,…
K-Adaptability in Two-Stage Robust Binary Programming 5: The ε-Approximation (6ε) Is Equivalent to the Mixed-Integer Bilinear Program (7)Research Paper
Two-stage robust optimization models decisions taken in two steps around an uncertain parameter: a first-stage decision x is fixed before a parameter ξ is revealed from an uncertainty set Ξ, and a second-stage (recourse) decision y is taken afterwards. When the recourse is binary (whether to open a facility, route a vehicle, schedule a task), the exact…
K-Adaptability in Two-Stage Robust Binary Programming 1: Under Objective Uncertainty, min{dim 𝒴, rk Q} + 1 Policies Attain the Two-Stage Optimal ValueResearch Paper
Many planning problems are made in two stages: a first decision is fixed before an uncertain parameter is observed, and a second, corrective decision is made afterwards. When the second-stage decisions are binary (which route, which facility, which crew), the resulting two-stage robust binary programs are notoriously hard: the second-stage decision is a…
K-Adaptability in Two-Stage Robust Binary Programming 4: The ε-Approximations (6ε) Converge Uniformly to the K-Adaptability ProblemResearch Paper
Two-stage robust optimization models decisions taken in two steps around an uncertain parameter: a here-and-now decision x is fixed before the parameter ξ is revealed, and a wait-and-see decision y adapts to it, and the decision maker guards against the worst ξ in an uncertainty set Ξ. When the second-stage decisions are binary, as in routing,…
Tight Complexity Bounds for Optimizing Composite Objectives III: Any Deterministic Algorithm with Gradient and Prox Oracles Needs Ω(m√(γ/λ)·log(λε₀/(γε))) Queries on Smooth Strongly Convex SumsResearch Paper
Many problems in machine learning and statistics minimize an average of component losses, F(x)=m1∑i=1mfi(x): one term per training example, per data shard, or per block of a decomposed objective. Incremental methods such as SAG, SVRG, SAGA, SDCA and their accelerated variants touch one component at a time, so the natural measure of their work…
Isoperimetric Inequalities in Simplicial Complexes 1: For a Finite d-Complex with a Complete Skeleton, the Spectral Gap Is at Most the Cheeger Constant, λ(X) ≤ h(X)Research Paper
For a finite graph, the Cheeger constant measures how hard it is to cut the vertex set into two pieces, and the spectral gap of the graph Laplacian measures how fast random walks mix. The two Cheeger inequalities (Dodziuk 1984; Alon and Milman 1985; Alon 1986) bound each quantity by a function of the other, and they underlie the theory of expander graphs,…
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints II: Gradients of m-Strongly Convex Functions with L-Lipschitz Gradient Satisfy the Weighted Off-by-One ρ-Hard IQCResearch Paper
First-order methods (gradient descent, Nesterov's accelerated method, the Heavy-ball method) are the workhorses of large-scale convex optimization, and their worst-case convergence rates on smooth strongly convex functions are classical objects of study. Lessard, Recht and Packard (arXiv:1408.3595v7, SIAM J. Optim. 26(1), 2016, doi:10.1137/15M1009597)…
Analysis and Design of Optimization Algorithms via Integral Quadratic Constraints III: Heavy-Ball Tuned for Quadratics Converges to a 3-Cycle, Not the Minimizer, of a Strongly Convex f with L/m = 25Research Paper
The Heavy-ball method of Polyak, xk+1=xk−α∇f(xk)+β(xk−xk−1), adds a momentum term to gradient descent. On strongly convex quadratics with curvature between m and L, a classical eigenvalue analysis gives the step size and momentum that minimise the worst-case linear rate, α=4/(L+m)2 and …
Distributionally Robust Joint Chance Constraints with Second-Order Moment Information II: Over Scaling Parameters, Worst-Case CVaR Is Essentially Exact for Joint Chance ConstraintsResearch Paper
A chance constraint asks that a decision x∈Rn satisfy uncertain inequalities with high probability. In the setting of Zymler, Kuhn and Rustem (Math. Program. 137, 2013), m affine inequalities yi0(x)+yi(x)⊤ξ~≤0, whose coefficients depend affinely on x, must hold jointly with probability at least 1−ϵ. Joint chance constraints…
Distributionally Robust Convex Optimization III: The Lifting Theorem — a Conic Bound on E[g(z̃)] Describes Exactly the z̃-Marginals of a Lifted Ambiguity SetResearch Paper
Distributionally robust optimization asks a decision to perform well against every probability distribution in an ambiguity setP, a family of distributions consistent with partial information about an uncertain parameter z~∈RP. Which kinds of information an ambiguity set can encode decides which models a solver can handle.…
A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization II: Interchangeability Holds for Diagonally Dominant Functions iff Measurable Projection and Weak Selection DoResearch Paper
In Wasserstein distributionally robust optimization (DRO) a decision is evaluated against the worst distribution within an optimal-transport ball around a nominal distribution P. Every tractable reformulation rests on a strong duality theorem that replaces the supremum over distributions by a one-dimensional minimization over a multiplier …
Optimization-Based Algorithms for Tensor Decompositions: Canonical Polyadic Decomposition, Decomposition in Rank-(Lr, Lr, 1) Terms, and a New Generalization 1: Block Structure of the Gramian JᴴJResearch Paper
Tensor decompositions express a multiway array as a sum of simple terms. The canonical polyadic decomposition (CPD) writes an N-th order tensor T∈CI1×⋯×IN as a sum of R outer products of vectors; block term decompositions replace each rank-one term by a term of higher multilinear rank. These models are used in signal…
Stochastic Gradient Descent, Weighted Sampling, and the Randomized Kaczmarz Algorithm: SGD with Step γ < 1/sup L Has E‖x_k − x⋆‖² ≤ [1 − 2γμ(1 − γ sup L)]^k ‖x₀ − x⋆‖² + γσ²/(μ(1 − γ sup L))Research Paper
Stochastic gradient descent (SGD) minimizes an objective that is an expectation, F(x)=Ei∼Dfi(x), by stepping along the gradient of one randomly drawn component at a time. It is the workhorse of large-scale machine learning, where F is an average loss over training examples, and it also contains the randomized Kaczmarz method for…
Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 3: Hankel-Matrix SDP Lower Bounds for Minimizing a Power Sum Subject to Fixed Lower Power SumsResearch Paper
Many polynomial optimization problems are invariant under permuting the variables: the objective and the constraints are symmetric polynomials. Lasserre's moment–sum-of-squares hierarchy solves such problems by a sequence of semidefinite programs whose size grows quickly with the number of variables and the degree, and symmetry is the main tool for…
Triangle-Free Intersection Graphs of Line Segments with Large Chromatic Number: For Every k ≥ 1 There Is a Triangle-Free Family of Plane Line Segments with Chromatic Number Greater than kResearch Paper
A proper coloring of a graph assigns colors to its vertices so that adjacent vertices get different colors; the least number of colors that suffices is the chromatic numberχ(G). The clique numberω(G) is the size of a largest set of pairwise adjacent vertices, and χ(G)≥ω(G) always. A class of graphs is χ-bounded if χ is bounded by a…
Linear-Quadratic Optimal Control Problems for Mean-Field Stochastic Differential Equations: Two Riccati Equations Give the Optimal State-Feedback Control and the Value ⟨Π(0)x, x⟩Research Paper
Linear-quadratic (LQ) control is the setting in which stochastic optimal control has a closed-form answer: the optimal control is a linear feedback of the state, and the feedback gain comes from a Riccati differential equation. In the mean-field version, the expectation E[X] of the state and E[u] of the control appear in the dynamics and in…
Tight Complexity Bounds for Optimizing Composite Objectives I: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(mLB/ε) Queries on Sums of m Convex L-Lipschitz FunctionsResearch Paper
Many optimization problems minimize the average of component losses: one loss per observation, machine, or term in an objective. When an algorithm can inspect one component at a time, the number of component queries is a useful measure of work. A component oracle can provide more than a value or subgradient: a proximal point summarizes a global minimization…
A Short and General Duality Proof for Wasserstein Distributionally Robust Optimization I: Worst-Case Loss = min over λ ≥ 0 of λρ + E[sup f − λc] for All ρ > 0 iff Interchangeability HoldsResearch Paper
Wasserstein distributionally robust optimization (DRO) hedges a decision against every probability distribution within a given transport distance of a nominal one, typically the empirical distribution of data. The inner problem, the worst-case loss, is an optimization over an infinite-dimensional set of measures, and every practical use of Wasserstein DRO —…
A Modern Introduction to Online Learning XI: Constrained Online Convex Optimization Reduces to Unconstrained Learning on Distance-Penalized Surrogate LossesTextbook
An online learner repeatedly chooses a point, observes a loss, and is judged by the difference between its accumulated loss and that of a fixed competitor. In practice, an available learner may operate on a broad feasible set W, while the application permits decisions only in a smaller set V. Replacing each output by a feasible point changes the learner's…
A Modern Introduction to Online Learning XIII: Online Mirror Descent Has Dynamic Regret (B_ψ(u_T; x_1) + Q·P(u_1, …, u_T))/η + (η/(2λ)) Σ_t ‖g_t‖⋆²Textbook
In online learning, a learner chooses a point before seeing each round's loss. Ordinary regret compares the learner with one fixed point chosen after all rounds. That comparison can be too coarse when a useful action changes over time. A portfolio allocation, a prediction rule, or an operating point may need to move after the environment shifts. Dynamic…
Fast Rates for Contextual Linear Optimization 3: Under the Margin Condition, a Plug-In Policy Whose Estimate Has Pointwise Sub-Gaussian Tails at Rate aₙ Has Regret O(B·aₙ^(−(1+α)/2))Research Paper
Many operational decisions are linear programs whose cost vector is uncertain but predictable from side information: routing with travel times that depend on weather and time of day, procurement with prices that depend on market signals, assignment with costs that depend on observed features. Contextual linear optimization (CLO) formalizes this: observe…
A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights V: The Speed Restarted ODE Converges Linearly for Strongly Convex fResearch Paper
Nesterov's accelerated gradient method minimizes a convex function f with L-Lipschitz gradient at the rate O(1/k2), which is optimal among first-order methods. For a μ-strongly convex f the method with the generic momentum coefficient (k−1)/(k+2) does not exploit the strong convexity: Su, Boyd and Candès show in §4.2 of arXiv:1503.01243 that its rate…