Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Optimization

2,311 missions · 1,728 completed

Missions

Open583Completed1728All2311
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Robust Sample Average Approximation 1: A Data-Driven DRO Converges in Objective, Optimal Value and Optimal Solutions for Every Admissible Cost If and Only If Its Test Is Uniformly ConsistentResearch Paper

A decision maker who must choose xxx to minimize an expected cost EF[c(x;ξ)]\mathbb E_F[c(x;\xi)]EF​[c(x;ξ)] rarely knows the distribution FFF of the uncertain parameter ξ\xiξ; what is available is a sample ξ1,…,ξN\xi^1,\dots,\xi^Nξ1,…,ξN. Sample average approximation (SAA) replaces FFF by the empirical distribution. Data-driven distributionally robust optimization (DRO) instead minimizes the worst…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

On the Heavy-Tail Behavior of the Distributionally Robust Newsvendor 2: Below the Critical Ratio η₀ = 1 − (m₁^α/m_α)^{1/(α−1)} the Robust Newsvendor Orders Nothing; Above It Orders at Least q₀Research Paper

The newsvendor problem is the basic single-period inventory decision: a retailer orders q≥0q\ge0q≥0 units at unit cost ccc before a random demand d~\tilde dd~ is observed, sells at unit price p>cp>cp>c, and loses unsold units. When the demand law is known, the optimal order is a quantile of that law. In practice the law is rarely known, and a distributionally robust newsvendo…

6 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisTheoretical Computer Science·Captain: mikedeng1

Low Rank Approximation and Regression in Input Sparsity Time 2: Sketched Multiple-Response Regression Is (1 + 4ε)-Optimal in Squared Error If the Sketch Embeds the Subspace and Approximates ProductsResearch Paper

Least-squares regression, min⁡X∥AX−B∥F\min_X\|AX-B\|_FminX​∥AX−B∥F​ for a tall matrix A∈Rn×dA\in\mathbb R^{n\times d}A∈Rn×d with n≫dn\gg dn≫d, is among the most frequently solved problems in numerical computation. Direct methods (QR or SVD) cost O(nd2)O(nd^2)O(nd2) time, which is prohibitive when nnn is in the millions. Sketching replaces the problem by a much smaller one: choose a matrix S∈Rt×nS\in\mathbb R^{t\times n}S∈Rt×n…

7 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Pricing and Matching with Forward-Looking Buyers and Sellers 2: Both Fixed Prices Rise with the Buyer Arrival Rate and Fall with the Seller Arrival Rate; Matches and Fluid Profit Rise with BothResearch Paper

Two-sided intermediaries charge buyers and pay sellers while trying to match the two groups. A larger arrival stream on one side changes both the number of possible matches and the prices that clear the market. Chen and Hu study this in a model of buyers and sellers who arrive over time and may wait before requesting a match. Their market-size theorem…

8 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Semismooth and Semiconvex Functions in Constrained Optimization III: With Semiconvex Problem Functions, a Stationary Point Is Optimal Unless There Is No Strictly Feasible PointResearch Paper

Many constrained optimization problems in operations research have objective and constraint functions that are continuous but not differentiable: maxima of finitely many smooth functions, value functions of inner optimization problems, piecewise-linear costs. For such problems the classical Karush–Kuhn–Tucker theory does not apply directly, and algorithms…

10 thms2 active usersReviewed
Analysis·Captain: mikedeng1

Semismooth and Semiconvex Functions in Constrained Optimization II: A Semismooth Composition of Semismooth Functions Is Semismooth, with a Chain Rule for Generalized GradientsResearch Paper

Optimization models often build an objective from several intermediate quantities: constraints, penalties, and transformed measurements are evaluated first, then combined by an outer function. These intermediate and outer functions can be Lipschitz without being differentiable at the point of interest. Ordinary differentiation supplies no chain rule there.…

13 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Retail Assortment Planning in the Presence of Consumer Search IV: Under Overlapping-Assortment Search, the Full Assortment Is Optimal Once Search Is Cheap EnoughResearch Paper

A retailer that decides which variants of a product to stock (its assortment) trades off the revenue each variant brings against the operational cost of carrying it. The classical model of this trade-off uses the multinomial logit (MNL) model of consumer choice: a consumer who does not like what the store offers simply buys nothing (van Ryzin & Mahajan 1999)…

10 thms2 active usersReviewed
Machine LearningNumerical Analysis·Captain: mikedeng1

Conservative Set Valued Fields, Automatic Differentiation, Stochastic Gradient Methods and Deep Learning 2: Forward and Reverse Mode Automatic Differentiation Yield Conservative FieldsResearch Paper

Training a neural network means running a first-order method on a loss that is built from compositions of elementary operations, many of them nonsmooth: ReLU, max-pooling, absolute values, sorting, norms. The gradient the optimizer uses is not computed by hand. It is computed by automatic differentiation (autodiff), most often in its reverse mode, backpropag…

13 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 8: When Both Agents Minimize a Maximum of Regular Costs, There Are at Most n_A·n_B + 1 Nondominated PairsResearch Paper

In many production and service settings a single resource is shared by several parties, each judging the outcome only by how its own work is treated. Multi-agent scheduling studies this situation. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) introduced the two-agent single-machine model in which two agents, A and B, each own a set…

7 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations Research·Captain: mikedeng1

An Augmented Lagrangian Based Algorithm for Distributed Nonconvex Optimization 1: With ρ = 0, the ALADIN Dual Update Equals the Levenberg–Marquardt Dual Newton Step of Dual DecompositionResearch Paper

Large optimization problems often split into blocks owned by different agents (subsystems of a power grid, vehicles in a formation, scenarios of a stochastic program) that are coupled only through a few linear constraints. Distributed optimization methods solve such problems by letting each agent work on its own block and exchanging a small amount of…

7 thms2 active usersReviewed
🏆Completed
Analysis·Captain: mikedeng1

Conservative Set Valued Fields, Automatic Differentiation, Stochastic Gradient Methods and Deep Learning 1: A Conservative Field Equals the Gradient of Its Potential Almost EverywhereResearch Paper

Training a neural network with nonsmooth activations (ReLU, max-pooling, absolute values) means running a stochastic gradient method in which the "gradient" is whatever the automatic differentiation library returns. For nonsmooth programs that output is in general neither a gradient nor a Clarke subgradient: the chain rule fails for the Clarke…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research+1·Captain: mikedeng1

Incremental Proximal Methods for Large Scale Convex Optimization II: With a Randomized Order and a Diminishing Stepsize, Incremental Subgradient-Proximal Methods Converge Almost Surely to an OptimumResearch Paper

Many problems in statistical learning, signal processing and distributed optimization minimize a sum of a large number mmm of convex components over a convex set: a data-fit term per sample plus a regularizer or constraint per sample. When mmm is large, a method that processes one component per iteration is often far cheaper per step than one that evaluates the…

7 thms2 active usersReviewed
Operations Research·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 5: A Dynamic Program Gives the Minimum Number of Late Jobs of One Agent When the Other Accepts at Most Q Late JobsResearch Paper

Multi-agent scheduling studies a machine shared by parties with their own jobs and their own objectives. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) introduced the two-agent single-machine model: agents AAA and BBB each own a set of jobs, and the schedule must serve both. The paper frames this within multiagent systems, where agents…

10 thms2 active users
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Obtaining Lower Bounds from the Progressive Hedging Algorithm for Stochastic Mixed-Integer Programs: The Dual Prices Give a Lower Bound on the Optimal Value in Every IterationResearch Paper

Progressive hedging separates a stochastic optimization problem by scenario, solves those smaller problems, and coordinates their first-stage decisions through weighted aggregation and price updates. It is useful when the full extensive formulation is too large to solve directly. For stochastic mixed-integer programs, its iterates can provide feasible…

4 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Logic-Based Benders Decomposition: With Valid Benders Cuts (B1), the Generic Benders Algorithm Stops Only at an Optimal Solution, an Infeasible Problem or an Unbounded OneResearch Paper

Benders decomposition solves an optimization problem in two groups of variables by fixing one group, solving the remaining subproblem, and turning what the subproblem's solution proves into a constraint, the Benders cut, on the fixed variables. In the classical method of Benders (1962) the subproblem is a linear program and the cut comes from its LP dual.…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Retail Assortment Planning in the Presence of Consumer Search I: Under Independent-Assortment Search, a Variant's Demand Falls Strictly as the Assortment ExpandsResearch Paper

A retailer choosing which variants of a product to stock (colours, sizes, models) faces a trade-off that operations management has studied since van Ryzin and Mahajan (1999): a deeper assortment attracts more purchases, but each added variant takes demand away from the variants already on the shelf. This loss is called cannibalization. In the standard model…

11 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Retail Assortment Planning in the Presence of Consumer Search II: Under MNL Without Search, the Profit Change from Adding a Variant Is Quasi-Convex in Its PreferenceResearch Paper

A retailer that sells a product in many variants (colours, sizes, flavours) has to decide which variants to stock. This is the assortment planning problem. Each variant added to the shelf brings new demand. It also cannibalizes demand from the variants already stocked, and it lowers their cost efficiency, because operational costs (shelf space, handling,…

6 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 4: In Finite-Horizon Problems with a Non-Stationary Policy Class Containing an Optimal Policy, Every Stationary Point Is OptimalResearch Paper

Policy gradient methods optimize a parameterized policy by gradient descent on its expected total cost. They are a staple of reinforcement learning and of simulation-based optimization in operations research, but the objective is nonconvex in the policy parameters, and the standard theory guarantees convergence only to a stationary point. J. Bhandari and D.…

10 thms2 active usersReviewed
Dynamic ProgrammingReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 3: Under Closure up to Inherent Bellman Error ε, Every Stationary Point Is Within κε/(1−γ) of OptimalResearch Paper

Policy gradient methods search for a policy by changing a finite vector of parameters. The method can reach a stationary point of its objective without finding an optimal policy: a small change in the available parameters might not represent the policy improvement that the underlying control problem calls for. Bhandari and Russo identify a condition on the…

10 thms2 active usersReviewed
Dynamic ProgrammingReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 1: If the Policy Class Is Closed Under Policy Improvement, Every Stationary Point of the Policy Gradient Objective Is Globally OptimalResearch Paper

Policy gradient methods optimize a parameterized policy for a Markov decision process by running gradient descent on its expected cost. They underlie most large-scale reinforcement learning, from robotics to game playing, and are also natural in operations research, where structured policy classes (linear feedback, base-stock levels, thresholds) are…

9 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 6: In the KL-Regularized Finite MDP, a Regularized-Optimal Policy Is Within λ(1 + log(1 + c/λ)) of OptimalResearch Paper

Policy gradient methods for Markov decision processes are frequently run on a regularized objective rather than on the cost of interest: a convex penalty on the action distribution is added to every single-period cost. Regularization smooths the problem, makes optimal policies strictly stochastic, and keeps iterates away from the boundary of the probability…

13 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Disruption and Rerouting in Supply Chain Networks I: Every Supply Chain Network Has a Unique General Equilibrium of Rerouting Prices, Switching Costs and Default CascadesResearch Paper

A failed buyer can leave a supplier with goods it can no longer sell through an existing order. A failed supplier can leave a buyer without inputs for future production. In a network, either loss can weaken another firm and start a sequence of defaults. Birge, Capponi and Chen model these effects together with two responses: suppliers reroute unsold goods…

9 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Disruption and Rerouting in Supply Chain Networks II: A More Diversified Tiered Supply Chain Network Is More ResilientResearch Paper

A firm can lose a planned input when one of its suppliers defaults. Safety stock can absorb some of that loss, while the rest becomes demand for replacement supply. A network with more buyer and supplier links spreads orders across more firms, but the resulting benefit depends on which firms default, how much each link carries, and the price of replacement…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationMachine LearningOperations Research·Captain: mikedeng1

Strong Mixed-Integer Programming Formulations for Trained Neural Networks 2: Under Strict Activity Every Inequality of the Exponential Family (6b) Is Facet-DefiningResearch Paper

Trained neural networks are increasingly embedded inside optimization models: to verify that a classifier is robust to small input perturbations, to optimize over a learned surrogate of an expensive system, or to choose decisions whose outcome is predicted by a network. When the network uses rectified linear units (ReLU), each neuron y=max⁡{0, w⋅x+b}y=\max\{0,\,w\cdot x+b\}y=max{0,w⋅x+b}…

5 thms2 active usersReviewed
🏆Completed
Linear OptimizationMachine LearningOperations Research·Captain: mikedeng1

Strong Mixed-Integer Programming Formulations for Trained Neural Networks 1: A ReLU Neuron over a Box Has an Ideal Formulation with One Binary Variable and the Exponential Family (6b)Research Paper

A trained feed-forward neural network with ReLU activations, ReLU(v)=max⁡{0,v}\mathrm{ReLU}(v)=\max\{0,v\}ReLU(v)=max{0,v}, is a piecewise linear function of its input. Many tasks ask for an optimization over such a network with its weights held fixed: verifying that no small perturbation of an image changes its classification, finding adversarial examples, or embedding a learned model of…

7 thms2 active usersReviewed
PreviousPage 72 of 93Next

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me