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 Distributionally Robust Mixed-Integer Programming with Decision-Dependent Moment-Based Ambiguity Sets III: Under Slater, the Delage–Ye-Type Stage Bellman Equation Is One SDP MinimizationResearch Paper
In many multistage decision problems the probability law of the next uncertainty depends on the decision taken now: opening a facility changes the demand it attracts, a price changes the distribution of sales, maintenance changes failure rates. Distributionally robust optimization (DRO) handles an imperfectly known law by optimizing against the worst…
Linear Convergence of First Order Methods for Non-Strongly Convex Optimization II: Quadratic Functional Growth with Constant κ Gives the Global Error Bound with Constant κ/(1 + μ + √(1 + μ))Research Paper
First order methods (projected gradient, fast gradient) converge only sublinearly on general smooth convex problems, at rates O(1/k) and O(1/k2) in function value. Linear convergence is classically proved under strong convexity, which fails for many problems arising in practice: least squares with a rank-deficient matrix, dual problems of linearly…
Linear Convergence of First Order Methods for Non-Strongly Convex Optimization VII: g(Ax) with g Strongly Convex and Smooth Is Quasi-Strongly Convex on a Polyhedron with κ = σ_g/θ²(A, C)Research Paper
Linear convergence of gradient-type methods is classically proved under strong convexity. Many problems that arise in practice are not strongly convex: dual formulations of linearly constrained convex problems, least-squares and logistic-type regression with rank-deficient data matrices, convex quadratic programs, and routing problems in data networks all…
Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 1: Under G, g ≥ 0 Every Minimal Optimal Schedule Stays inside the Ultimate Pit LimitResearch Paper
Strategic planning of an open pit mine decides, over a horizon of 20 to 50 years, which parts of an ore body are excavated, when, and where the excavated material is sent. A deposit is discretized into blocks, often millions of them, and the decisions are constrained by wall-slope precedences between blocks, by mining and processing capacities, and by…
Solving Chance-Constrained Problems via a Smooth Sample-Based Nonlinear Approximation 1: Smoothed Sample Feasible Sets Lie in the True Feasible Set with Probability ≥ 1 − ⌈1/β⌉⌈2LD/t⌉ⁿ exp(−2NM²)Research Paper
A chance-constrained program minimizes a cost f(x) over a closed set X⊆Rn subject to a constraint that must hold with high probability rather than surely:
Linear Convergence of First Order Methods for Non-Strongly Convex Optimization I: Strong ⇒ Quasi-Strong Convexity ⇒ Quadratic Gradient Growth ⇒ Quadratic Under-Approximation ⇒ Functional GrowthResearch Paper
First-order methods (projected gradient, fast gradient, feasible descent) converge linearly on smooth strongly convex problems, but many problems met in practice are not strongly convex: least squares with a rank-deficient matrix, the dual of a linearly constrained problem, or g(Ax) with g strongly convex and A singular. Such problems have a whole set of…
Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality 3: Under T₂(τ), W₂-Robust Loss at Radius ρ̃ₙ Bounds True Loss up to 4r⋆+2εₙ+ħρ̃ₙ²Research Paper
Wasserstein distributionally robust optimization (Wasserstein DRO) replaces the empirical loss EPn[f] of a decision by its worst case over all distributions within Wasserstein distance ρ of the empirical distribution Pn. It is used in operations research (newsvendor, portfolio selection) and machine learning (adversarially…
Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature II: Column-Subset Selection Has Total Curvature at Most 1 − 1/κ(A)²Research Paper
The column-subset selection problem (CSSP) asks for k columns of a real matrix A whose span approximates all of A as well as possible in squared Frobenius norm. It is a basic primitive of low-rank approximation, feature selection and numerical linear algebra, studied both for its exact complexity and for approximation algorithms (see Boutsidis, Drineas and…
Dynamic Pricing in the Presence of Social Learning and Strategic Consumers 3: With Social Learning, Responsive Pricing Beats Pre-Announced Pricing When Consumers Are ImpatientResearch Paper
A recurring question in revenue management with strategic consumers is whether a seller gains from price commitment. When customers are forward-looking, a seller who announces its whole price path in advance (pre-announced pricing) removes the customers' incentive to wait for a markdown the seller would otherwise be tempted to give; a seller who keeps the…
Production Scheduling for Strategic Open Pit Mine Planning: A Mixed-Integer Programming Approach 4: Hourglass Production Cuts Are Valid under Full and Partial IntegralityResearch Paper
Strategic open pit mine planning decides which parts of an ore body are excavated, in which period, and to which destination (a processing plant, a stockpile, a waste dump) each block of material is sent. Rivera Letelier, Espinoza, Goycoolea, Moreno and Muñoz (Operations Research 68(5), 2020) model this as a mixed-integer program, the precedence-constrained…
Finite-Sample Guarantees for Wasserstein Distributionally Robust Optimization: Breaking the Curse of Dimensionality 2: Under T₁(τ), W₁-Robust Loss at Radius 2√(τt/n)+√(4r⋆+2/n) Bounds the True LossResearch Paper
Wasserstein distributionally robust optimization (DRO) replaces the empirical loss EPn[f] of a decision or model f by its worst case over all distributions within a Wasserstein distance ρ of the empirical distribution Pn. It is used in operations research (newsvendor, portfolio and inventory problems) and in machine learning…
Dynamic Pricing in the Presence of Social Learning and Strategic Consumers 2: Under Responsive Pricing, Social Learning Raises Optimal Expected Profit When Consumers Are Impatient or PatientResearch Paper
A firm launching a new experience good does not know how good the product is, and neither do its customers. Early buyers post reviews, and customers who wait learn from them: this is social learning (SL). Forward-looking customers anticipate this and may delay their purchase until reviews are available, which cuts into the firm's early sales. Papanastasiou…
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.…