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.
Posted Price Mechanisms and Optimal Threshold Strategies for Random Arrivals III: Even for I.I.D. Variables, No Nonadaptive Threshold Rule Beats the Factor 1 − 1/eResearch Paper
In a prophet inequality, a decision maker observes random rewards one at a time and must choose without seeing future realizations. The benchmark is a prophet who sees all rewards and selects their maximum. A nonadaptive threshold rule chooses a threshold for each reward before observations begin, then accepts the first arriving reward that crosses its…
A Little Charity Guarantees Almost Envy-Freeness II: With Additive Valuations Such an Allocation Gives Every Agent Her Maximin Share Divided by 2 − |P|/nResearch Paper
A set of n agents must share a set M of m indivisible goods, each agent valuing bundles of goods by her own valuation. Two fairness notions dominate the literature. Envy-freeness up to any good (EFX), introduced by Caragiannis, Kurokawa, Moulin, Procaccia, Shah and Wang (EC 2016), asks that no agent prefer another's bundle once any single good is removed…
A game-theoretic approach to computation offloading in mobile cloud computing III: Variational Solutions Are the Nash Equilibria of the Extended Cloudlet-Pricing GameResearch Paper
Mobile devices can divide work between local execution, a nearby shared cloudlet, and a remote cloud. A cloudlet has limited capacity, so one user's choice changes the delay faced by the others. Cardellini and coauthors model this as a generalized Nash equilibrium problem, in which each user's feasible choices depend on the aggregate cloudlet load. The…
Double Counting in Supply Chain Carbon Footprinting II: A Carbon Leader Paying Linear Emission-Contingent Rules That Double-Count Internally Earns Its Effort-Contracting ProfitResearch Paper
Firms increasingly account for, and offset, the greenhouse-gas emissions of their entire supply chain, not only their own operations. Emissions in a supply chain are often jointly produced: the footprint of one process (transport, packaging, a molten-bulk delivery) depends on the abatement efforts of several firms at once. When each firm is charged for…
Persistence-Based Clustering in Riemannian Manifolds: With High Probability the Algorithm Returns as Many Clusters as the Density Has d₂-Prominent PeaksResearch Paper
Mode-seeking clustering groups data points by the peak of an underlying probability density that they "flow up" to. Methods of this kind (mean-shift, graph-based hill climbing) are widely used, but their output depends heavily on noise: a density estimated from finitely many samples has many spurious local maxima, and each of them becomes a cluster. Chazal,…
Scheduling Problems with Two Competing Agents 9: Total Completion Time Against a Maximum Cost Has at Most n_A·n_B + 1 Nondominated PairsResearch Paper
Many scheduling decisions are not owned by a single decision maker. A machine shared by two departments, a production line serving two customers, or a computing resource shared by two users must process the jobs of two agents, each of which judges a schedule by its own criterion. Agnetis, Mirchandani, Pacciarelli and Pacifici introduced this model in Schedul…
Double Counting in Supply Chain Carbon Footprinting I: With Joint Carbon Production, Every Differentiable Increasing Payment Rule That Makes the Social First-Best a Nash Equilibrium Double-CountsResearch Paper
Carbon accounting assigns emissions from a shared supply-chain process to firms that can reduce them. If more than one firm can change the same emissions, charging each firm only a share may leave each with too little incentive to abate. Caro, Corbett, Tan and Zuidwijk study the conflict between avoiding double counting in an emissions ledger and inducing…
Steady-State Analysis of the Join-the-Shortest-Queue Model in the Halfin-Whitt Regime 1: Diffusion-Scaled Stationary Queue Lengths Have Expectations Bounded Uniformly in nResearch Paper
Join-the-shortest-queue (JSQ) is the load-balancing rule in which each arriving job is sent to a server with the fewest jobs. It is a baseline in the design of server farms and data centers, and in the many-server Halfin–Whitt regime, where the load per server approaches one at rate 1/n, it combines near-full utilization with vanishing waiting.…
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…