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.
Scheduling Problems with Two Competing Agents 3: The Least-Cost Backward Rule Gives a Nondominated Schedule Minimizing Total Completion Time Under a Maximum-Cost BoundResearch Paper
Many scheduling situations involve more than one decision maker sharing a resource. Two departments of a firm may share a machine shop, two clients may share a contractor, or two users may share a processor, and each cares only about how its own jobs are served. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) introduced a systematic…
Dynamic Pricing with Loss-Averse Consumers and Peak-End Anchoring: Every Optimal Price Path Converges Monotonically to a Steady State Set by the Initial Minimum PriceResearch Paper
Firms that change prices over time face customers who remember past prices. A large empirical literature in marketing documents reference price effects: demand depends not only on the current price but on how that price compares with a price the customer expects, and losses (prices above the reference) weigh more than gains of the same size, the loss…
On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems 1: Steepest Descent Can Need ε^(−2+τ) Iterations to Reach |g| ≤ εResearch Paper
Steepest descent is the oldest method for unconstrained minimization: to minimize a smooth function f, it moves from the current point xk along the negative gradient −gk=−∇f(xk). It is the prototype of every first-order method, and its worst-case evaluation complexity — how many iterations it may need before the gradient norm drops below a…
Some Numerical Experiments with Variable-Storage Quasi-Newton Algorithms: The Update (A.7) Is the Unique Least-Change Self-Adjoint Secant Update in a Weighted Hilbert–Schmidt NormResearch Paper
Quasi-Newton methods replace a costly exact Hessian with an operator updated from successive changes in position and gradient. A secant update must map the observed step s to the observed gradient difference y. Many operators satisfy that one equation, so the choice of update needs another criterion. Gilbert and Lemaréchal's working paper studies…
Fast Polynomial Factorization and Modular Composition 1: The Inverse Kronecker Map ψ Reduces Modular Composition f(g₀, …, g_{m−1}) mod h to One Multivariate Multipoint EvaluationResearch Paper
Modular composition asks, given univariate polynomials f,g,h over a ring, for f(g(X))modh(X). It is the bottleneck step in the classical algorithms for factoring univariate polynomials over finite fields (Cantor–Zassenhaus, von zur Gathen–Shoup, Kaltofen–Shoup), for irreducibility testing and for computing minimal polynomials. Brent and Kung (1978)…
Branch-and-Bound Performance Estimation Programming: A Unified Methodology for Constructing Optimal Optimization Methods: Subgradient Rate L̃²(2√(4κ²(N+1)+1)−1)/(N+1) on Weakly Convex FunctionsResearch Paper
Many objectives in statistics and machine learning are neither smooth nor convex, yet are well behaved in a weaker sense: robust phase retrieval, blind deconvolution, robust PCA and training with piecewise-linear losses all lead to weakly convex functions, functions that become convex after adding a fixed quadratic. For such functions the plain subgradient…
An Augmented Lagrangian Based Algorithm for Distributed Nonconvex Optimization 2: Near a Regular KKT Point the Decoupled Subproblems Have Locally Unique Minimizers with ‖y−x*‖ ≤ χ₁‖x−x*‖+χ₂‖λ−λ*‖Research Paper
Many large optimization problems arising in networked control, smart grids, distributed estimation and resource allocation have a separable objective with coupled affine constraints: N agents each own a variable xi and a private cost fi, and only a linear constraint ∑iAixi=b ties them together. Distributed algorithms for such problems let each…
On the Complexity of Nash Equilibria and Other Fixed Points 4: The Fixed Points of the Division-Free Map G_I(x)ij = max(x_ij + u_i((i:j); x−i) − t_i, 0) Are Exactly the Nash EquilibriaResearch Paper
Nash's existence theorem for finite games is a fixed-point theorem: one writes down a continuous map from the set of mixed strategy profiles to itself whose fixed points are exactly the Nash equilibria, and applies Brouwer's theorem. Nash's own map (Nash 1951) divides by 1+∑jmax(0,⋅), and the choice of map matters as soon as the question is…
On the Complexity of Nash Equilibria and Other Fixed Points 2: Block Matching Pennies Gives Every Block the Same Probability and the Matching Player Full Support in Every Nash EquilibriumResearch Paper
Reductions that prove hardness for Nash equilibrium computation encode a computation (a circuit, a fixed-point problem) into the probabilities that players put on their strategies in every equilibrium. For the encoding to be meaningful, the designer has to control how each player distributes probability across groups of strategies, independently of the…
On the Complexity of Steepest Descent, Newton's and Regularized Newton's Methods for Nonconvex Unconstrained Optimization Problems 3: ARC Can Need ε^(−3/2+τ) Iterations to Reach |g| ≤ εResearch Paper
Worst-case iteration counts are the standard way to compare unconstrained optimization methods on nonconvex problems. For finding an approximate first-order critical point, a point with ∥∇f(x)∥≤ϵ, steepest descent needs at most O(ϵ−2) iterations on functions with a Lipschitz gradient. The cubic regularization of Newton's method…
Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 1: Basic ARC Reaches ‖g‖ ≤ ε in O(ε^(−2)) IterationsResearch Paper
Methods for smooth unconstrained minimization, minx∈Rnf(x), are compared by how many evaluations of f and of its gradient they need, in the worst case, to reach an approximately first-order critical point, an iterate with ∥∇f(xk)∥≤ϵ. For steepest descent with a Lipschitz gradient the answer is O(ϵ−2) (Nesterov, Int…
On the Complexity of Nash Equilibria and Other Fixed Points 1: ε-Nash Equilibria Are Weak (n+1)ε-Fixed Points of Nash's Function, and Weak ε²/(4c²n³)-Fixed Points Are ε-Nash EquilibriaResearch Paper
Nash proved that every finite game has an equilibrium by exhibiting a continuous map of the set of mixed profiles into itself whose fixed points are exactly the equilibria, and applying Brouwer's fixed point theorem (Nash, 1951). Computationally, the same map is the bridge between games and fixed-point problems: complexity classes for total search problems…
Variable Metric Method for Minimization: Davidon's Rank-One Variable-Metric Update Recovers the Inverse Hessian of a Quadratic in N Steps and Then Steps to the Exact MinimumResearch Paper
Quasi-Newton methods minimize a smooth function f:Rn→R using gradients only, while building up an approximation to the inverse of the Hessian matrix from the changes of gradient they observe. They are the default algorithms of unconstrained nonlinear optimization: BFGS and its limited-memory variant L-BFGS sit inside most numerical…
Continuous-Time Average-Preserving Opinion Dynamics with Opinion-Dependent Communications 1: Every Proper Solution of the Discrete-Agent Model Converges to Clusters at Least 1 ApartResearch Paper
Bounded-confidence opinion dynamics model a population in which each individual revises an opinion, represented by a real number, by looking only at opinions close to its own. The best-known example is the discrete-time model of Krause (1997), also called the Hegselmann–Krause model, in which every agent moves to the average of the opinions within distance…
Incremental Proximal Methods for Large Scale Convex Optimization I: With a Cyclic Order and a Diminishing Stepsize, Incremental Subgradient-Proximal Methods Converge to an Optimal SolutionResearch Paper
Many optimization problems in machine learning, signal processing and distributed computation have an objective that is a sum of a large number m of component functions: one per data point, per sensor, or per processor. Evaluating the whole sum, or a subgradient of it, at every iteration is expensive when m is large. Incremental methods process one…
Lyapunov Equations, Energy Functionals, and Model Order Reduction of Bilinear and Stochastic Systems 1: States Reached from 0 Stay in Im P and Ker Q Gives Zero Output, for Gramians P, Q ≥ 0 of (3.6)Research Paper
Balanced truncation is the standard method for reducing the state dimension of a linear control system while keeping its input–output behaviour: states that are both hard to reach and hard to observe are discarded. Its justification rests on two Gramians, the solutions P and Q of a pair of Lyapunov equations, whose quadratic forms measure how much input…
Semismooth and Semiconvex Functions in Constrained Optimization I: The Pointwise Maximum or Minimum over a Compact Family of Continuously Differentiable Functions Is SemismoothResearch Paper
Many objective functions in engineering design, Chebyshev approximation and game-theoretic planning are extremal-valued: they are the pointwise maximum or minimum of a family of smooth functions, E(x)=maxu∈Uf(x,u). Such a function is typically not differentiable at points where two or more members of the family are active, so gradient methods do not…
Retail Assortment Planning in the Presence of Consumer Search V: The Heuristic Equilibrium of No-Search Assortment Planning Is Never Deeper Than OptimalResearch Paper
Retailers decide which product variants to stock, and most assortment-planning tools model consumer choice with the multinomial logit (MNL) model: a consumer who does not find an acceptable variant simply leaves without buying. Cachon, Terwiesch and Xu (Retail Assortment Planning in the Presence of Consumer Search, working paper of December 2002; published…
Retail Assortment Planning in the Presence of Consumer Search III: Under Independent-Assortment Search, the Profit Change from Adding a Variant Is Quasi-Convex in Its PreferenceResearch Paper
A retailer deciding which variants of a product to stock trades off two effects. A deeper assortment captures consumers whose favourite variant would otherwise be missing, but it splits demand among more variants, each of which then carries its operational costs (shelf space, handling, inventory) at a smaller, less efficient scale. Van Ryzin and Mahajan (Man…
A c^k n 5-Approximation Algorithm for Treewidth 1: If tw(G) ≤ k, Pushed Terminal Separations Around a 3/4-Balanced Separation Glue to a Separation of Order k+1 with Sides ≤ 7/8|V|+(|B|+k+1)/2Research Paper
Treewidth measures how closely a graph resembles a tree. Many problems that are NP-hard on general graphs can be solved in time linear in the number of vertices once a tree decomposition of bounded width is available, so computing such decompositions quickly is a basic task in algorithmic graph theory. Bodlaender, Drange, Dregi, Fomin, Lokshtanov and…
Three-Coloring and List Three-Coloring of Graphs Without Induced Paths on Seven Vertices 1: Every Connected P₇-Free Graph Has a Connected 2-Dominating Set of at Most Three Vertices or a K₄Research Paper
Graph coloring asks whether vertices can be assigned colors so that adjacent vertices receive different colors. Restricting the graphs by forbidden induced paths can expose structure that is absent from general graphs. Bonomo, Chudnovsky, Maceli, Schaudt, Stein and Zhong study list three-coloring when the graph has no induced path on seven vertices,…
Graphon Mean Field Systems II: The Empirical Measure of the Dense Graphon-Weighted Particle System Converges in Probability to the Averaged Graphon LawResearch Paper
Classical mean field theory describes n exchangeable diffusions, each interacting with the empirical average of all the others. As n→∞ the particles become independent copies of a McKean–Vlasov process (propagation of chaos). Many systems of interest are not exchangeable. Particles sit at the vertices of a network and interact only with their…
Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications: With Fixed Pick-up Times, the Offline Taxi Routing MIO Formulation (5)-(14) Is IntegralResearch Paper
Global Optimality Guarantees for Policy Gradient Methods 2: Under Closure, a (c, µ)-Gradient-Dominated Policy Iteration Objective Makes ℓ (κc/(1−γ), κµ/(1−γ))-Gradient DominatedResearch Paper
Policy gradient methods optimize a parameterized control policy by gradient descent on its long-run cost. They underlie much of modern reinforcement learning, from REINFORCE and actor-critic methods to trust-region and proximal policy optimization, and they are used in operations problems such as inventory control and optimal stopping. Their objective is…
More Risk-Sensitive Markov Decision Processes 5: Under Positive Harris Recurrence a Risk-Neutral Optimal Stationary Policy Is Optimal for Power-Utility Average CostResearch Paper
Classical Markov decision theory minimizes expected cost. A decision maker who dislikes variability, such as an insurer, a portfolio manager or an operator of a service system, may instead evaluate a random cost Y by its certainty equivalentU−1(E[U(Y)]) for an increasing utility (disutility) function U. Bäuerle and Rieder (More Risk-Sensitive…