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.
Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence Under Bregman Distance Growth Conditions: PLIAG Converges Linearly at Rate 1/(1+αμ)Research Paper
Large-scale learning and signal-processing problems often have the form of a sum of many convex components plus a nonsmooth regularizer, minx∑n=1Nfn(x)+h(x). Incremental aggregated gradient (IAG) methods process such sums by refreshing the gradient of only some components per iteration and reusing older, delayed gradients for the rest. This…
The Value of Robust Assortment Optimization Under Ranking-Based Choice Models: Some Optimal Robust Assortment Is Revenue-Ordered Relative to the Past AssortmentsResearch Paper
A retailer choosing which products to offer, its assortment, must predict how customers substitute between products. A standard and very general model of substitution is the ranking-based choice model: each customer carries a ranking of all products (including the option of buying nothing) and buys the most preferred product on offer. A probability…
Constant Regret Resolving Heuristics for Price-Based Revenue Management: Under Limited Inventory the Resolving Heuristic Earns Within a Horizon-Independent Constant of the Optimal Pricing PolicyResearch Paper
Price-based revenue management studies a seller with a fixed stock of a product and a finite selling season who adjusts prices over time to maximize expected revenue. The exact optimal policy solves a dynamic program whose state is the remaining inventory and time; it is rarely computed in practice, and the network version with many products and resources…
Data-Driven Distributionally Robust CVaR Portfolio Optimization Under A Regime-Switching Ambiguity Set: For Every ℓm Cost, the Worst-Case CVaR Problem Is the Convex Program (12)Research Paper
A portfolio manager who minimizes the conditional value-at-risk (CVaR) of the portfolio loss needs the distribution of asset returns, but only has a finite history of them. Plugging the empirical distribution into the CVaR formula of Rockafellar and Uryasev (2002) gives portfolios that perform poorly out of sample. Distributionally robust optimization (DRO)…
Difference-of-Convex Algorithm with Extrapolation for Nonconvex, Nonsmooth Optimization Problems: Bounded DCAe Sequences Converge to a Critical Point under the Kurdyka–Łojasiewicz PropertyResearch Paper
Many estimation problems in statistics and machine learning minimize a smooth data-fitting loss plus a nonconvex sparsity-promoting penalty: compressed sensing, sparse dictionary learning, phase retrieval, Poisson inverse problems and nonnegative matrix completion. Penalties such as SCAD, MCP and the exponential penalty are differences of convex functions (D…
Rank-One Boolean Tensor Factorization and the Multilinear Polytope: The Flower LP Recovers the Planted Rank-One Tensor w.h.p. Under Semi-Random Corruption When p<rw/(1+2rw)Research Paper
Boolean tensor factorization writes a binary data tensor as a Boolean combination of a few binary rank-one tensors. It is used in data mining for binary relational data (subject–relation–object triples, user–item–context records) and in latent-structure discovery, where the factors are read directly as sets of rows, columns and slices. Even its rank-one…
Asymptotic Consistency for Nonconvex Risk-Averse Stochastic Optimization with Infinite Dimensional Decision Spaces: Empirical Optimal Values and Approximate Solutions Converge Almost SurelyResearch Paper
Optimization problems governed by partial differential equations with uncertain inputs (random coefficients, random boundary data, random forcing) are routinely solved in a risk-averse form: instead of the expected cost, one minimizes a risk measure such as the average value-at-risk of the random cost, so that bad realizations are penalized. Because the…
Computing Approximate Equilibria in Weighted Congestion Games via Best-Responses: A Polynomial-Time Best-Response Algorithm Reaches a dd+o(d)-Approximate EquilibriumResearch Paper
Weighted congestion games model players who share resources (links of a network, machines, servers) and whose cost on a resource grows with the total weight using it. They are standard models of selfish routing and load balancing. Unlike unweighted congestion games, they need not have a pure Nash equilibrium once costs are polynomials of degree d≥2 (Harks–…
Maximizing the Benefits of an On-Demand Workforce: Fill Rate-Based Allocation and Coordination Mechanisms: fill-rate contracts with membership fees achieve system-wide optimal staffingResearch Paper
On-demand staffing platforms supply short-notice workers to restaurants, retailers and warehouses. A firm that uses one decides how many permanent workers to hire before its demand is known and asks the platform to cover the shortfall afterwards. The platform posts a wage, which determines how many self-scheduling workers become available, and then splits…
Monotone Inclusions, Acceleration and Closed-Loop Control: Every Global Trajectory Has Ergodic Gap O(t−(p+1)/2) and Pointwise Residue O(t−p/2)Research Paper
A monotone inclusion asks for a point x of a real Hilbert space H with 0∈Ax, where A is a set-valued monotone operator. Convex minimization, convex-concave saddle points and monotone variational inequalities are all of this form. The basic method is the proximal point algorithm of Rockafellar (1976), the fixed-point iteration of the resolvent …
Incentive-Aware Models of Financial Networks: A Stable Network of Contracts and Prices Exists iff a Linear System in the Prices Is Solvable, and Is Unique When Its Matrix Has Full RankResearch Paper
Financial institutions are linked by bilateral contracts: loans, interest rate swaps, insurance, derivative trades. The resulting network of exposures determines how shocks propagate, and most of the literature on systemic risk (for example the clearing model of Eisenberg and Noe) takes this network as given. Jalan, Chakrabarti and Sarkar (arXiv:2212.06808,…
On the Convex Formulations of Robust Markov Decision Processes: The Fixed Point of the Entropy-Regularized Robust Bellman Operator Is log_b of the Unique Optimum of a Convex ProgramResearch Paper
A Markov decision process (MDP) models sequential decisions under uncertainty: in each state an agent picks an action, collects a reward and moves to a random next state. Its optimal value function is the fixed point of the Bellman operator, and since the 1960s it has also been the optimum of a linear program over value functions (Puterman, Markov Decision…
Sales Effort Management Under All-or-Nothing Constraint: The Optimal Sales Rate Has a Watershed Structure in the Time-to-Go, With a Cutoff Strictly Increasing in the Sales Still NeededResearch Paper
Sales targets with a bonus are a standard incentive in practice: a car dealership earns a manufacturer bonus only if it sells a quota of vehicles in a quarter, and a salesperson earns a lump sum only when a quota is met. Contracts of this all-or-nothing type pay nothing below the target and a bonus plus a per-unit commission above it. They raise a dynamic…
A Perturbation Framework for Convex Minimization and Monotone Inclusion Problems with Nonlinear Compositions: Lagrangian, Dual and Kuhn–Tucker Operator Whose Zeros Are Primal–Dual SolutionsResearch Paper
Many optimization models couple a convex function f with a nonlinear outer function φ: a constraint f(x)≤0 is φ=ι]−∞,0], a penalty-barrier term α(ρ)θ(f(x)/ρ) is a smooth increasing φ, and a power ∥x∥p of a norm is φ∘∥⋅∥. Standard splitting methods handle sums of convex functions composed…
The Online Saddle Point Problem and Online Convex Optimization with Knapsacks: Saddle-Point Follow-the-Leader Has SP-Regret at Most 8G2/H⋅(1+logT) on Strongly Convex-Concave Lipschitz GamesResearch Paper
Many decisions are made by two parties with opposed interests who interact repeatedly while the game between them changes: a seller and a buyer facing shifting demand, a planner and an adversarial environment, or the primal and dual players of a constrained online optimization problem. Rivera Cardoso, Wang and Xu (arXiv:1806.08301v3) formalize this as the on…
Fluid Approximations for Revenue Management under High-Variance Demand: the Universal Fluid approximate policy earns at least a 1 − √(2 log c_min / c_min) − L / c_min fraction of the fluid valueResearch Paper
Network revenue management decides which products to offer while a stock of shared resources (seats on flight legs, hotel room-nights) sells out. Exact dynamic programs have a state with one coordinate per resource, so practice relies on fluid approximations: linear programs that replace random demand by its mean, give an upper bound on the optimal revenue,…
Dynamic Pricing (and Assortment) under a Static Calendar: Under Stationary Demand the Randomized LP Calendar Earns at Least E[min{Bin(T,b/T),b}]/b ≥ 1 − 1/e Times the LP OptimumResearch Paper
Revenue management usually assumes a firm can react: when inventory runs low it changes prices or
drops products in real time. Many firms cannot. Promotions in consumer packaged goods are set on a
calendar weeks ahead, and catalogue prices are printed. A static policy fixes in advance what
is offered in each period and ignores how much has been sold. The…
Understanding the Value of Fulfillment Flexibility in an Online Retailing Environment: A Spillover Limit Policy Costs at Most (1+O(T−1/2)) Times the DLP Lower BoundResearch Paper
An online retailer stores each product in several distribution centers (DCs) and tries to ship every order from the DC next to the customer. When that DC has run out, the order can often be shipped from another DC, at a higher cost and with a longer delivery time, and some customers then walk away. Allowing such spillover is the fulfillment flexibility of…
Multiple Beliefs, Dominance and Dynamic Consistency: belief dominance is weakly consistent, hence immune to fallacious inconsistency, but not to fallible inconsistencyResearch Paper
A decision-maker who cannot settle on one probability distribution often holds a set of plausible ones: disagreeing experts, or several models that all fit the data. Belief dominance compares options without weighting those distributions: an option is preferred when it is at least as good under every belief and strictly better under some belief. The…
Quantum Field Theory on Curved Backgrounds, I. The Euclidean Functional Integral: sharp-time localization — the time-zero vectors exp(iΦ(f₀)) lie in ℰ₊ and span a dense isometric copy in ℋResearch Paper
Osterwalder–Schrader (OS) quantization turns a Euclidean field theory, a probability measure on fields over a Riemannian space, into a quantum theory: a Hilbert space H of physical states with a Hamiltonian. On flat Rd this is the content of the OS axioms (Osterwalder–Schrader 1973, 1975) and of the textbook treatment of the free field in G…
From Classical to Quantum Shannon Theory V: The Zhang–Audenaert Inequality ∣H(X)−H(Y)∣≤Tlog(∣A∣−1)+h2(T) and Its OptimalityTextbook
Information theory measures the uncertainty of a random variable X on a finite alphabet by its Shannon entropyH(X). Most of its theorems are first proved for exact distributions and then have to survive small perturbations: an estimated distribution, a code with a small error probability, a channel known only up to some accuracy. To transfer a statement…
From Classical to Quantum Shannon Theory VI: Near Saturation of Strong Subadditivity: ln22Δ2≤I(X;Y∣Z)≤Δlog(min{∣X∣,∣Y∣}−1)+h2(Δ)Textbook
The converse parts of most classical capacity theorems rest on a handful of entropy inequalities: non-negativity of relative entropy and of mutual information, strong subadditivityI(X;Y∣Z)≥0, and the data-processing inequalities for mutual information and for relative entropy. Each of these comes with an exact saturation condition. Strong subadditivity,…
An Improved Analysis of LP-based Control for Revenue Management: Horizon-Independent Regret of the Re-Solving Algorithm Under NondegeneracyResearch Paper
In network revenue management and online linear programming, orders arrive one per period over a horizon of T periods. Each order requests a bundle of m resources and offers a reward. The decision maker accepts or rejects it at once and irrevocably, without exceeding the stock of each resource. Airline seat allocation, hotel booking and ad allocation are…
Learning to collude in a pricing duopoly: under self-play, Composite SPSA prices converge to the global optimal price and relative regret vanishes at rate T^(-1/5)Research Paper
Firms increasingly delegate pricing to learning algorithms, and regulators ask whether such algorithms can raise prices without any agreement between the firms. Meylahn and den Boer (SSRN:3741385, MSOM, doi:10.1287/msom.2021.1074) answer with a concrete construction: a data-driven policy which, when both duopolists use it, reaches the joint-revenue maximum…
On Greedy-Like Policies in Online Matching with Reusable Network Resources and Decaying Rewards: Random-Threshold Greedy Is αβ/((1+αβL)(1+lnR))-CompetitiveResearch Paper
Online platforms repeatedly match arriving demand to resources that are used up only temporarily. A rented item, a cloud server or a hotel room is reusable: once used it is unavailable for a random time and then returns. Requests often need several resources at once (a multi-night stay, a bundle of products), which makes the resources a network, and rewards…