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.
Product Price, Quality and Service Decisions under Consumer Choice Models II: The Oligopoly Has a Unique Nash Equilibrium, with Monopoly Qualities and Service Durations and Lower PricesResearch Paper
Firms that sell durable goods set three things at once: a price, a quality level, and the length of an ancillary service that comes free with the product, such as a warranty. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.0947) study these joint decisions under multinomial logit (MNL) demand. For a…
Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation 1: SONATA Converges R-Linearly over Undirected Graphs for Small Step SizesResearch Paper
In distributed optimization, m agents connected by a communication network jointly minimize the average of their private losses, exchanging vectors only with their neighbours. This is the computational model of decentralized machine learning (data held by many machines, no central server), of sensor networks and of multi-agent control. A central family of…
Inf-Convolution, Optimal Allocations, and Model Uncertainty for Tail Risk Measures II: The Inf-Convolution of a VaR and a Monetary Tail Risk Measure, Its Optimal Allocation and Its Tail ParameterResearch Paper
Banks and insurers hold capital against the risk of their positions, and regulators compute that capital with a risk measure, a functional that maps a random loss to a number. The two standard ones are the Value-at-Risk (VaR), a quantile of the loss, and the Expected Shortfall, an average of the upper quantiles (BCBS 2019). Both look only at the upper tail…
Distribution-Free Contextual Dynamic Pricing 2: Every Algorithm Has Expected Regret at Least C₀ C_p T₀ on Some Perturbed Linear Bandit with Perturbation C_pResearch Paper
Dynamic pricing asks a seller to post prices to a stream of customers and learn demand from purchase decisions alone. Luo, Sun and Liu study the contextual version in which a customer's valuation is linear in a covariate vector plus noise with an unknown distribution (arXiv:2109.07340v2; Mathematics of Operations Research, 2024). Their DIP policy estimates…
On the tightness of SDP relaxations of QCQPs 6: For Diagonal QCQPs the SOCP and SDP Relaxations Have the Same Projected Epigraph and Optimal ValueResearch Paper
Quadratically constrained quadratic programs (QCQPs) minimize a quadratic function subject to quadratic inequality and equality constraints. They model trust-region subproblems, robust least squares, max-cut and many problems in signal processing and control. They are NP-hard in general, so practice relies on convex relaxations, and the standard one is the S…
On the tightness of SDP relaxations of QCQPs 2: Polyhedral Γ with 0 ∉ Proj_V(F){b(γ) : γ ∈ F} on Every Semidefinite Face Makes Every SDP Optimizer FeasibleResearch Paper
A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. The class contains nonconvex problems such as max-cut, Boolean least squares, the trust-region subproblem and its generalizations, and robust least squares, and it is NP-hard in general. The standard convex approach…
Product Price, Quality and Service Decisions under Consumer Choice Models I: Under MNL Demand, Optimal Service Durations Are Extreme, Qualities Are Set Product by Product, and Markups Are EqualResearch Paper
Manufacturers rarely sell a bare product. A laptop, a vacuum cleaner or a car comes with an ancillary service (a factory warranty, maintenance, technical support) whose length the firm chooses together with the price and the quality of the product. The three decisions interact: a longer warranty makes a product more attractive to consumers but costs the…
Inf-Convolution, Optimal Allocations, and Model Uncertainty for Tail Risk Measures I: The Inf-Convolution of Left and Right VaRs Is a VaR at the Summed Level, with an Explicit Optimal AllocationResearch Paper
Value-at-Risk (VaR) is the quantile-based capital requirement written into banking and insurance regulation (Basel, Solvency II). When several institutions, desks or subsidiaries each hold capital according to their own VaR, a natural question is how a total loss X should be split among them so that the aggregate capital is as small as possible. This is the …
Product Price, Quality and Service Decisions under Consumer Choice Models V: A Dealer Optimally Offers a Markup-Ordered Assortment and Attaches Long Service to an Adjusted-Markup-Ordered SetResearch Paper
Car dealers, electronics retailers and office suppliers sell products whose prices and features are set upstream by manufacturers, and bundle each product with a service of their own: maintenance, repairs or a warranty. The dealer's short-term problem is then purely combinatorial. Which products should be carried, and which of them should come with a long…
Product Price, Quality and Service Decisions under Consumer Choice Models IV: Under the Two-Stage Nested Logit Model, Qualities Are Set Product by Product and Markups Are Nest-InvariantResearch Paper
A firm that sells durable products with an attached service (a warranty, a maintenance plan, a support contract) chooses three things for each product: its price, its quality, and how long the service lasts. Wang, Ke and Cui (SSRN 3766191, Manufacturing & Service Operations Management, 2022) study this joint decision when consumers choose among the products…
On the tightness of SDP relaxations of QCQPs 1: Polyhedral Γ and Large Shared Zero Eigenspaces on Semidefinite Faces Give conv(D) = D_SDP and Opt = Opt_SDPResearch Paper
Quadratically constrained quadratic programs (QCQPs) minimize a quadratic function subject to quadratic inequality and equality constraints. They model facility location, pooling, max-cut, trust-region steps and robust optimization problems, and every {0,1} integer program can be written as one; in general they are NP-hard. The standard tractable approach…
Understanding the Acceleration Phenomenon via High-Resolution Differential Equations IV: The High-Resolution Heavy-Ball ODE Satisfies f(X(t)) − f(x⋆) ≤ 7‖x₀ − x⋆‖² e^(−√μ t/4)/(2s)Research Paper
Polyak's heavy-ball method and Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) are the two classical momentum methods of smooth convex optimization. With step size s and momentum α=(1−μs)/(1+μs) they differ only by a gradient-correction term, yet NAG-SC is accelerated for every μ-strongly convex, L-smo…
From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 6: Nesterov's Method Has ℒ_k ≤ ℒ₀·min{4L/(√γ₀k + 2√L)², (1 − √(min{γ₁, μ}/L))^k}Research Paper
Nesterov's accelerated gradient method minimises a smooth convex function f to accuracy ε in O(L/ε) gradient evaluations, and a μ-strongly convex one in O(L/μlog(1/ε)); both counts match the lower bounds for first-order methods. Nesterov's own analysis (Y. Nesterov, Introductory Lectures on Convex…
Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results III: ADMM Is Douglas-Rachford Splitting on the Image-Function Problem, for Every RelaxationResearch Paper
The alternating direction method of multipliers (ADMM) solves linearly constrained problems
From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 4: The Predictor–Corrector Scheme Has ℒ_k ≤ ℒ₀·min{4L/(√γ₀k + 2√L)², (1 + √(min{γ₀, μ}/L))^(−k)}Research Paper
Nesterov's accelerated gradient method minimises a smooth convex function f to accuracy ε in O(1/ε) gradient evaluations, and a μ-strongly convex one in O(L/μlog(1/ε)), which is optimal for first-order methods. The method's original derivation by estimate sequences gives little insight into why it…
From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 3: The Implicit Scheme Gives ℒ_{k+1} ≤ ℒ_k/(1 + α_k) for Every μ-Convex f and Every Step α_k > 0Research Paper
Accelerated first-order methods, beginning with Nesterov's 1983 scheme, reach the optimal iteration complexity among gradient methods for smooth convex minimization, but their classical derivations ("estimate sequences") give little insight into why acceleration works. A line of work started by Su, Boyd and Candès (arXiv:1503.01243) reads accelerated…
From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 5: The Gradient-Corrected Scheme Contracts ℒ_k by 1/(1 + α_k) and Has the Rate of Theorem 5.1Research Paper
Nesterov's accelerated gradient method minimises a smooth convex function f to accuracy ε in O(1/ε) gradient evaluations, against O(1/ε) for plain gradient descent, and this rate is optimal for first-order methods (Nesterov 2018). The method is usually presented through estimate sequences, which certify the rate but say…
Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results V: The Image Function (Af) Is Smooth Under Relative Smoothness, Lipschitz Minimizers, or ConvexityResearch Paper
The alternating direction method of multipliers (ADMM) solves problems of the form min{f(x)+g(z)∣Ax+Bz=b} and is a standard tool in signal processing, statistics and distributed optimization (Boyd et al., 2011). For convex problems ADMM is known to be the Douglas–Rachford splitting (DRS) applied to a dual problem. Themelis and Patrinos (arXiv:1709.057…
From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 2: The NAG Flow Has a Unique C² Solution and Its Lyapunov Function Satisfies ℒ(t) ≤ e^(−t)ℒ(0)Research Paper
Accelerated first-order methods, above all Nesterov's accelerated gradient (NAG) method, minimize a convex function with an L-Lipschitz gradient to accuracy ε in O(L/ε) gradient evaluations, and a μ-strongly convex one in O(L/μlog(1/ε)), against O(L/ε) and O((L/μ)log(1/ε)) for gradient…
Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results II: No Stepsize Above 1/L Guarantees a Vanishing DRS ResidualResearch Paper
Douglas–Rachford splitting (DRS) minimizes a sum φ1+φ2 by alternating between the proximal mappings of the two terms. It is one of the most used first-order methods in signal processing, statistics and control, and, through its dual interpretation, it is the engine behind the alternating direction method of multipliers (ADMM). For convex…
Understanding the Acceleration Phenomenon via High-Resolution Differential Equations III: The High-Resolution ODE of NAG-SC Satisfies f(X(t)) − f(x⋆) ≤ 2‖x₀ − x⋆‖² e^(−√μ t/4)/sResearch Paper
Nesterov's accelerated gradient method for μ-strongly convex, L-smooth functions (NAG-SC) reaches accuracy ε in O(L/μlog(1/ε)) gradient steps, against O((L/μ)log(1/ε)) for gradient descent (Nesterov, 1983; Nesterov, 2004). Polyak's heavy-ball method has the same accelerated behaviour on quadratics but not in…
The Bayesian Prophet: A Low-Regret Framework for Online Decision Making: Constant Regret of the Fluid Bayes Selector for the Multi-Secretary ProblemResearch Paper
In online allocation, requests arrive one at a time and each must be accepted or rejected on arrival, using a limited budget of resources. Revenue management, ad allocation and hiring all fit this pattern. A natural benchmark for an online policy is the prophet, or Offline: the decision maker who sees the whole arrival sequence in advance and acts optimally…
Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios IV: The Tight Ratio 1 − e^{−α⁽¹⁾} Exceeds (1 − 1/e)σ⁽¹⁾ and the Price-Continuum RatioResearch Paper
In online matching with multiple prices, a firm sells n items with limited inventories to customers who arrive one at a time; each item can be offered at any price from its own finite price set, and the firm must commit to an offer without knowing future customers. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020) show that the best possible competitive…
From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 1: Gauss–Seidel Splitting of the HB and NAG Transforms Has ρ(E(α, G)) ≤ 1/√(1 + 2α) If 0 < α ≤ 2/√κ(A)Research Paper
Accelerated first-order methods, the heavy-ball method of Polyak and Nesterov's accelerated gradient (NAG) method, reach an error ε on a μ-strongly convex, L-smooth problem in O(κlog(1/ε)) gradient steps, κ=L/μ, against O(κlog(1/ε)) for plain gradient descent. A long line of work has tried to explain…
Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem: The Embedding Operator Q = F ∪ I of a Monotone LCP Is Maximal MonotoneResearch Paper
Many problems in optimization reduce to a linear complementarity problem over a cone: convex quadratic programs, linear and second-order cone programs, and more generally the KKT systems of convex quadratic cone programs (QCPs). First-order solvers for these problems, such as SCS (O'Donoghue–Chu–Parikh–Boyd 2016), must return either a solution or a…