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.
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
On Minimizing a Convex Function Subject to Linear Inequalities III: The Expected Cost of a Linear Program with Random Coefficients Is ConvexResearch Paper
A linear program is solved with known data, but in planning problems the data are often only known in distribution when the main decision is taken: demands, yields and requirements are revealed later, and a corrective action is taken after they are. E. M. L. Beale's 1955 paper On Minimizing a Convex Function Subject to Linear Inequalities formulates this…
Scheduling Subject to Resource Constraints: Classification and Complexity III: The Two-Machine Algorithm for Q2 with One Resource and Unit-Time Jobs Is OptimalResearch Paper
Many production and computing systems run jobs on parallel machines that also draw on a shared, limited resource: tools, workers, memory, power. Adding such a resource to a scheduling problem can change its complexity entirely. Błażewicz, Lenstra and Rinnooy Kan (DAM 1983) extended the three-field classification α∣β∣γ of Graham, Lawler,…
Randomized Algorithms for Estimating the Trace of an Implicit Symmetric Positive Semi-Definite Matrix I: Sample Bound for the Gaussian Trace EstimatorResearch Paper
Many computations in scientific computing, statistics and machine learning need the trace of a matrix A that is never formed explicitly: A may be f(B) for a large sparse B, an inverse B−1, or a product of operators, and the only access to it is the ability to compute products Az for chosen vectors z. Examples are log-determinant estimation in Gaussian…
Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 2: A Threshold Nash Equilibrium under Announced Fixed-Discount PricingResearch Paper
Retailers of fashion and seasonal goods sell at a premium price early in the season and mark down later. When customers anticipate the markdown, some of them wait, and the seller's pricing problem becomes a game between the seller and a population of forward-looking (strategic) customers. Aviv and Pazgal (MSOM 10(3), 2008) study this game in a model with…
Simultaneous Analysis of Lasso and Dantzig Selector III: A Sparsity Oracle Inequality for the LassoResearch Paper
In high-dimensional regression the number of candidate predictors M can far exceed the number of observations n. A regression function can then be estimated only if it is well approximated by a combination of a few elements of a large dictionary. The Lasso is the most widely used estimator in this regime. The question this mission formalizes is how well the…
Simultaneous Analysis of Lasso and Dantzig Selector I: Sparse Eigenvalue and Correlation Conditions Imply the Restricted Eigenvalue ConditionResearch Paper
In high-dimensional linear regression one observes y=Xβ∗+w∈Rn with a design matrix X∈Rn×M whose number of columns M may far exceed the sample size n. The two standard estimators of a sparse β∗, the Lasso (Tibshirani, 1996) and the Dantzig selector (Candès and Tao, 2007), both come with error bounds of order …
Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits I: The Regret Bound of ILOVETOCONBANDITSResearch Paper
In a contextual bandit problem a learner repeatedly observes a context (a user, a patient, a query), chooses one of K actions, and observes the reward of the chosen action only. It competes with the best policy of a fixed class Π of maps from contexts to actions. This is the standard model for news and advertisement recommendation, adaptive clinical…
Analysis of Generalized Pattern Searches: Nonnegative Clarke Derivatives at Limits of Refining SubsequencesResearch Paper
Generalized pattern search (GPS) is a class of derivative-free methods for minimizing a function that can only be evaluated, not differentiated. Such objectives arise in engineering design, where one evaluation is an expensive simulation that may fail and return no value at all. The helicopter rotor design problem of Booker et al. is one example: no value…
Maximizing Non-Monotone Submodular Functions II: A Nonadaptive Algorithm Achieves 1/3 of the OptimumResearch Paper
Maximizing a submodular set function without constraints contains Max Cut, Max Directed Cut, maximum facility location and several graph and hypergraph cut problems as special cases, and it appears in operations research wherever a value exhibits diminishing returns but is not monotone (profit that combines coverage with a cost, for example). These problems…
On Properties of Stochastic Inventory Systems IV: The (Q, r) Cost Is Flatter in the Order Quantity than the EOQ CostResearch Paper
The continuous-review (Q,r) policy is the standard replenishment rule of inventory theory: whenever the inventory position (stock on hand plus on order minus backorders) drops to the reorder pointr, order a fixed order quantityQ. It is used in practice and taught in every operations management course, usually after the deterministic economic order…
On Properties of Stochastic Inventory Systems II: The Optimal Order Quantity of the Stochastic (Q, r) Model Exceeds the EOQ by a Bounded GapResearch Paper
The continuous-review (Q,r) policy is the standard control rule for a single stocked item with random demand: whenever the inventory position falls to the reorder pointr, an order of fixed size Q is placed. It is implemented in a large share of commercial inventory systems. Choosing the two parameters jointly has traditionally required numerical search…
Asymptotic Optimality of Tailored Base-Surge Policies in Dual-Sourcing Inventory Systems: Asymptotic Optimality of the Best TBS Policy for Long Lead TimesResearch Paper
Firms that can buy the same item from two suppliers, a cheap slow one and a fast expensive one, face the dual-sourcing inventory problem: how much to order from each source in every period when demand is random and unmet demand is backlogged. Global sourcing (offshore regular supply plus a near-shore express supply) is the standard example (Allon and Van…
Markovian Decision Processes with Uncertain Transition Probabilities II: Max-Max and Max-Min Optimal Returns Bound the Bayesian Optimal ReturnResearch Paper
A Markovian decision process (Howard, 1960) models a controller who, in each of finitely many states, picks a decision, earns a reward and moves to a random next state according to known transition probabilities. In applications (inventory control, equipment replacement, quality control) those probabilities are estimated, not known. Satia and Lave (Operation…
A Nonsmooth Version of Newton's Method I: local superlinear convergence of the generalized-Jacobian Newton method at a semismooth regular rootResearch Paper
Many problems in optimization and equilibrium modelling reduce to a system of equations F(x)=0 whose map F:Rn→Rn is Lipschitz but not differentiable: reformulations of nonlinear complementarity problems through the componentwise minimum or the Fischer–Burmeister function, Karush–Kuhn–Tucker systems of constrained programs, and…
Shortest Connection Networks And Some Generalizations: Construction Principles P1 and P2 Yield a Shortest Spanning Subtree of Every Connected Labelled GraphResearch Paper
Connecting a set of terminals by a network of direct links of least total length is one of the oldest problems of combinatorial optimization. R. C. Prim's 1957 paper in the Bell System Technical Journal (DOI) was motivated by the rate structure for Bell System leased-line services, in which the charge for connecting a set of terminals depends on the length…
Updating Quasi-Newton Matrices with Limited Storage: The Limited-Storage BFGS Method Reaches the Minimizer of a Strictly Convex Quadratic in at Most n StepsResearch Paper
Quasi-Newton methods minimize a smooth function f on Rn by moving along dk=−Hkgk, where gk is the gradient and Hk is an approximation of the inverse Hessian built from observed gradient differences. The BFGS update is the most widely used way of building Hk, but it stores a dense n×n matrix, which is prohibitive for large n.
Cubic Regularization of Newton Method and Its Global Performance I: Global Rate of Convergence to Second-Order Stationary PointsResearch Paper
Newton's method is the standard second-order algorithm for unconstrained minimization, but without safeguards it has no global guarantee: far from a minimizer the Newton step can increase the objective, and at a point where the Hessian is indefinite the step can head for a saddle point or a maximum. The usual repairs (line search, trust regions,…