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.
A Supply Chain Theory of Factoring and Reverse Factoring 2: The Retailer's Optimal Reverse Factoring Payment ExtensionResearch Paper
Large retailers pay their suppliers weeks or months after delivery, and small suppliers fill the gap with short-term finance. In factoring the supplier sells the receivable to a factor for immediate cash; in reverse factoring the retailer arranges the program with a bank, which pays the supplier early at a rate priced on the retailer's credit rating.…
Are Call Center and Hospital Arrivals Well Modeled by Nonhomogeneous Poisson Processes?: Combining k Equal Subintervals of a Linear Arrival Rate Bounds the Degree of Nonhomogeneity by C/kResearch Paper
Arrival processes to call centers and hospital emergency departments are routinely modeled as nonhomogeneous Poisson processes (NHPPs): Poisson processes whose arrival rate varies over the day. Staffing and queueing models built on this assumption are only as good as the assumption itself, so practitioners test it on data. The standard test, going back to…
The Structure of Dynamic Programing Models: A Solution of the Principle of Optimality with Vanishing Tail Is the Optimal ReturnResearch Paper
Dynamic programming, as introduced by Bellman in the early 1950s, solves sequential decision problems through a functional equation: the value of a problem started in a given state equals the best one-stage return plus the value of the problem started in the state that decision leads to. In practice the argument usually runs backwards. One writes down the…
Minkowski's Convex Body Theorem and Integer Programming: Lattice-Free Convex Bodies Meet Few Translates of an Integral SubspaceResearch Paper
Integer programming asks whether a system of linear inequalities Ax≤b has a solution x∈Zn. In fixed dimension n it is solvable in polynomial time: Lenstra (1983) proved this by showing that a convex body without integer points is "flat" in some integral direction, so that the search splits into few lower-dimensional subproblems. Kannan's 1987…
Robust Solutions to Uncertain Semidefinite Programs IV: Closed-Form Robust Counterparts under Unstructured PerturbationsResearch Paper
A semidefinite program (SDP) minimizes a linear objective cTx subject to a linear matrix inequality (LMI) F(x)=F0+∑i=1mxiFi⪰0. In applications the coefficient matrices Fi are measured, estimated or rounded. A solution that is feasible for the nominal data can become infeasible for data that differ from it by an arbitrarily small…
Robust Solutions to Uncertain Semidefinite Programs I: Exact SDP Reformulation of the Robust LMI under Full Linear-Fractional PerturbationsResearch Paper
A semidefinite program (SDP) minimizes a linear objective cTx subject to a linear matrix inequality (LMI) F(x)=F0+∑i=1mxiFi⪰0. SDPs model problems in control, combinatorial optimization, statistics and engineering design, and they are solved efficiently by interior-point methods. In applications the data F0,…,Fm are rarely…
Validation of Subgradient Optimization II: A Unique Optimal Assignment Makes the Dual Optimal Set Full-DimensionalResearch Paper
The subgradient method maximizes a concave, piecewise-linear function w(π)=mink{ck+π⋅vk} by moving along a subgradient vk of an active piece with a prescribed step. Held, Wolfe and Crowder's 1974 paper Validation of subgradient optimization tested the method on three families of Lagrangean duals from combinatorial optimization — the…
Lifts of Convex Sets and Cone Factorizations I: A Proper K-Lift of a Convex Body Yields a K-Factorization of Its Slack Operator, and a K-Factorization Yields a K-LiftResearch Paper
Many convex sets that appear in optimization have complicated descriptions in their own space but simple descriptions as projections of higher-dimensional sets. A polytope with exponentially many facets can be the shadow of a polyhedron with polynomially many; the unit disk is the projection of a slice of the cone of 2×2 positive semidefinite…
Robust Solutions to Least-Squares Problems with Uncertain Data IV: A Semidefinite Upper Bound on the Linear-Fractional Worst-Case Residual, Exact for Full PerturbationsResearch Paper
Least-squares fitting is a standard tool in estimation, identification and data analysis, and its data A, b are rarely known exactly. El Ghaoui and Lebret (SIAM J. Matrix Anal. Appl. 18(4), 1997) proposed to choose x to minimize the worst-case residual over a set of admissible data perturbations. Earlier missions of this series treat unstructured…
Robust Solutions to Least-Squares Problems with Uncertain Data I: The Worst-Case Residual and Its Unique MinimizerResearch Paper
The least-squares (LS) problem minx∥Ax−b∥ assumes that the data A∈Rn×m, b∈Rn are exact. In applications they rarely are: they come from measurements, from linearizations, or from models with neglected dynamics. A classical response is sensitivity analysis or regularization (Tikhonov), where a weight trades the size…
The Erdős Matching Conjecture and Concentration Inequalities: The Conjecture in a Linear RangeResearch Paper
In 1965 Erdős asked how large a family of k-element subsets of an n-element set can be if it contains no s+1 pairwise disjoint members. The question, now called the Erdős Matching Conjecture (EMC), contains the Erdős–Ko–Rado theorem (the case s=1) and is one of the central open problems of extremal set theory. Beyond combinatorics it is tied to tail bounds…
Competitive Paging Algorithms III: No Randomized Paging Algorithm Is Better than H_k-CompetitiveResearch Paper
Paging is the problem of managing a two-level memory: a cache holds k of the n pages a program uses, every request must find its page in the cache, and a request to a page outside the cache (a page fault) forces the algorithm to bring the page in and evict another. An on-line algorithm chooses what to evict without seeing future requests. Sleator and Tarjan…
Competitive Paging Algorithms II: Algorithm EATR Is 3/2-Competitive for Two ServersResearch Paper
Paging is the problem of managing a two-level memory: a fast cache holding k pages and a slow memory holding the rest. When a requested page is not in the cache (a page fault), it must be brought in and, if the cache is full, some page must be evicted. An on-line paging algorithm decides which page to evict without knowing future requests. Sleator and…
Conditional and Dynamic Convex Risk Measures II: The Conditional Entropic Risk Measure and Conditional Relative EntropyResearch Paper
A risk measure assigns to a random financial position X a capital requirement ρ(X): the amount of cash that must be added to X to make it acceptable. The axiomatic theory of convex risk measures (Föllmer–Schied 2002; Frittelli–Rosazza Gianin 2002) treats this number as computed with no information beyond the model. In practice a regulator or a risk…
Optimizing Static Linear Feedback: Gradient Method III: Gradient Descent with the Hessian Step Size Converges Linearly on Strongly Convex FunctionsResearch Paper
Gradient descent needs a step size, and the classical choices each ask for something the user may not have. A constant step 1/L needs the Lipschitz constant L of the gradient, which is rarely known and often pessimistic. Backtracking needs repeated function evaluations. The exact line search needs a one-dimensional minimization at every iteration.…
Optimizing Static Linear Feedback: Gradient Method I: The Gradient Method Converges to a Stationary Point, and Linearly to the Optimal Gain under State FeedbackResearch Paper
The linear-quadratic regulator (LQR) is the basic problem of optimal control: steer a linear system x˙=Ax+Bu so as to minimize an integrated quadratic cost. When the full state is measured and the gain may be chosen freely, the optimal feedback is given by the algebraic Riccati equation (Kalman, 1960). In many applications only an output y=Cx is…
Projected Gradient Methods for Linearly Constrained Problems I: The Gradient Projection Method Drives the Projected Gradients to ZeroResearch Paper
The gradient projection method minimizes a continuously differentiable function over a closed convex set by alternating a gradient step with a projection back onto the set. It was proposed by Goldstein (1964) and by Levitin and Polyak (1966), and it is the basic step of many algorithms for bound constrained and linearly constrained optimization, including…
Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma: ℓ1-Proximity of Integer and LP OptimaResearch Paper
Integer programs are routinely solved by first solving their linear programming (LP) relaxation and then searching for an integer optimum near the fractional one. How near an integer optimum must be is the subject of proximity theorems. They bound the search region of branch-and-bound and of dynamic programming, and they turn a fractional optimum into a…
An Analog of the Minimax Theorem for Vector Payoffs: A Closed Convex Set Is Approachable If and Only If It Meets Every T(q), and Is Otherwise ExcludableResearch Paper
Von Neumann's minimax theorem says that in a zero-sum game with real payoffs, Player I can guarantee an expected gain of at least the value v and Player II can hold it to at most v. In a long series of plays, the law of large numbers turns this into a statement about the average payoff: I can make it exceed v−ε, II can keep it below v+ε,…
The Steiner Problem in Graphs: Algorithm A Computes the Length of the Steiner TreeResearch Paper
The Steiner problem in graphs asks for the cheapest way to connect a prescribed set of nodes of a network, where intermediate nodes may be used freely. It is the network version of the classical Euclidean Steiner tree problem surveyed by Gilbert and Pollak (SIAM J. Appl. Math. 16, 1968), and it arises wherever a few sites must be joined through an existing…
Monotone Mappings with Application in Dynamic Programming II: Convergence of the DP Algorithm under Uniform DecreaseResearch Paper
Infinite-horizon sequential decision problems (deterministic optimal control, Markov decision processes, minimax control) share one computational question: does the dynamic programming (DP) algorithm, which starts from a terminal cost and repeatedly applies the Bellman operator, converge to the optimal cost? For discounted problems with bounded costs the…
A Three-Operator Splitting Scheme and its Optimization Applications 3: Accelerated Convergence under Strong MonotonicityResearch Paper
Many problems in convex optimization, variational inequalities and signal processing reduce to finding a zero of a sum of three monotone operators, one of which is single-valued and smooth. Davis and Yin (Set-Valued Var. Anal. 25, 2017) introduced a splitting scheme that evaluates each of the three operators separately: the two set-valued ones through their…
A Three-Operator Splitting Scheme and its Optimization Applications 2: The Objective Rate of the Weighted Ergodic IterateResearch Paper
Many problems in signal processing, statistics and machine learning minimise a sum of three convex terms: a smooth data-fit term and two nonsmooth regularisers or constraints, each of which is easy to handle on its own (through its proximal map) but not in combination. Examples are constrained sparse regression, matrix completion with a nuclear-norm penalty…
On Polyhedral Approximations of the Second-Order Cone III: Closeness of the Relaxed Feasible SetResearch Paper
Conic quadratic problems (also called second-order cone programs) arise directly in applications such as contact problems with Coulomb friction, and a wide range of nonlinear convex problems can be rewritten in this form (Lobo, Vandenberghe, Boyd and Lebret 1998). Interior-point methods solve them in polynomial time, but around 2000 the available software…
Generalized Gradients and Applications I: The Generalized Gradient of a Max FunctionResearch Paper
Many objective functions in optimization are pointwise maxima: the worst case of a loss over an uncertainty set, the value of a minimax problem as a function of the outer variable, a penalty maxigi(x) for a system of constraints, or the largest eigenvalue of a symmetric matrix. Such a function