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,729 completed

Missions

Open582Completed1729All2311
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems 1: For Symmetric Right-Hand-Side Uncertainty, the Robust Optimum Is at Most Twice the Stochastic OptimumResearch Paper

Many planning problems are made in two stages: a first decision xxx (capacity, inventory, a network design) is fixed before an uncertain demand is revealed, and a second decision yyy (recourse, routing, overtime) is taken afterwards. Two-stage stochastic optimization models the demand as random and minimizes expected cost; its second stage is a whole policy …

10 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity VII: Conditional Gradient Descent (Frank–Wolfe) with γ_s = 2/(s + 1) Has Rate 2βR²/(t + 1) in Any NormTextbook

Many constrained optimization problems in machine learning and statistics have a feasible set X\mathcal XX over which a linear function is cheap to minimize but a Euclidean projection is expensive: the ℓ1\ell_1ℓ1​-ball, the simplex, the nuclear-norm ball, the convex hull of a combinatorial family. Projected gradient descent needs a projection at every step. Conditi…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity VI: Gradient Descent with η = 2/(α + β) on a β-Smooth α-Strongly Convex Function Has Rate (β/2)exp(−4t/(κ + 1))‖x₁ − x*‖²Textbook

Gradient descent is a basic method for minimizing a differentiable function when evaluating its gradient is practical but solving the optimization problem directly is not. The rate at which its iterates approach an optimizer depends on the assumptions about the function. For a convex function with a Lipschitz gradient, the value error decreases at a…

9 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research·Captain: mikedeng1

An Analysis of Stochastic Shortest Path Problems: If Every Improper Policy Has Infinite Cost, the Optimal Cost Is the Unique Fixed Point of Bellman's Operator and Value Iteration Converges to ItResearch Paper

A shortest path problem asks how to reach a destination at minimum cost. In a stochastic shortest path problem, a decision at a state selects a probability distribution over successor states, so both the route and its total cost are random. Costs may have either sign. This makes the problem relevant to finite-state control models where rewards and expenses…

11 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity IV: Gradient Descent on a Convex β-Smooth Function Has Rate 2β‖x₁ − x*‖²/(t − 1)Textbook

Gradient descent goes back to Cauchy (1847). It is the simplest method for minimizing a differentiable function, and most of the first-order methods in large-scale optimization and machine learning are variants of it. Its appeal in high dimension is that its oracle complexity, the number of gradient evaluations needed to reach a given accuracy, can be…

10 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingGraph TheoryOperations Research·Captain: mikedeng1

On a Routing Problem: Successive Approximations from the Direct-Route Policy Decrease to the Unique Solution of the Routing Equation Within N − 1 IterationsResearch Paper

Finding the quickest route between two points of a road network is among the oldest problems of operations research. It is the subproblem inside vehicle routing, network flow and many dynamic programs. Richard Bellman's four-page note On a routing problem (Quarterly of Applied Mathematics, 1958) treats it as a dynamic program. The minimal travel times…

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

Airline Seat Allocation with Multiple Nested Fare Classes 1: Protection Levels Solving f₁Pr[X₁ > p₁ ∩ … ∩ X₁ + … + X_k > p_k] = f_{k+1} Maximize Expected RevenueResearch Paper

An airline sells the seats of one flight leg at several fares. Cheaper fares are booked earlier, so the airline must decide, while low-fare requests arrive, how many seats to hold back for later and more valuable passengers. In nested booking control a seat that could be sold at a low fare is always available to a higher fare. The airline therefore chooses p…

8 thms2 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research·Captain: mikedeng1

Optimality of Affine Policies in Multistage Robust Optimization: In One-Dimensional Constrained Min-Max Control, Disturbance-Affine Policies with Affine Stage Costs Attain the Optimal ValueResearch Paper

Multistage robust optimization chooses decisions over time while an adversary picks the uncertain data from a known set; every later decision may react to what has been observed. The exact problem is a nested min-max over functions of the past, and is intractable in general. The standard workaround, proposed by Ben-Tal, Goryashko, Guslitzer and Nemirovski (M…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments I: Revenue-Ordered Assortments Earn OPT/(1 + ln(r_k/r_1)) Under Any Regular Choice ModelResearch Paper

A retailer, an airline or an online platform decides which products to show a customer. Showing more is not always better: a customer who would have bought an expensive product may switch to a cheap one once it is offered. The assortment problem asks for the set of products that maximises expected revenue, given a model of how customers choose. It is a…

9 thms2 active usersReviewed
🏆Completed
Control TheoryOperations Research·Captain: mikedeng1

Optimal Dynamic Pricing of Inventories with Stochastic Demand over Finite Horizons 2: The Optimal Revenue Is Strictly Concave in Stock and Time; the Optimal Price Falls with Stock, Rises with TimeResearch Paper

A retailer holding a fixed stock of a perishable or seasonal good (fashion items, airline seats, hotel rooms, concert tickets) must sell it before a deadline, after which unsold units are worthless. Demand is random and depends on the posted price, and the firm may change its price at any time. Dynamic pricing asks how the price should depend on the…

10 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Non-Strongly-Convex Smooth Stochastic Approximation with Convergence Rate O(1/n): Averaged Constant-Step-Size LMS Has Expected Excess Risk at Most (1/2n)[σ√d/(1−√(γR²)) + R‖θ₀−θ*‖/√(γR²)]²Research Paper

Least-squares regression fitted by stochastic gradient descent — the least-mean-square (LMS) algorithm — is the basic large-scale learning procedure: each observation is touched once, at a cost linear in the dimension. Classical analyses of stochastic approximation give the rate O(1/n)O(1/\sqrt n)O(1/n​) for non-strongly-convex objectives, and O(1/(μn))O(1/(\mu n))O(1/(μn)) when the…

15 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming 4: The Primal-Dual Relaxation Solves the Inequality ProgramResearch Paper

Many large convex programs have far more constraints than can be handled at once, but each constraint on its own is simple: a single linear equation or inequality. Row-action methods exploit this by touching one constraint per iteration. L. M. Bregman's 1967 paper (DOI 10.1016/0041-5553(67)90040-7) introduced the general framework behind most of them. A…

9 thms2 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

Oracle-Based Robust Optimization via Online Learning 2: Follow the Perturbed Leader with an ε-Approximate Linear Oracle Has Expected Regret at Most 2√(DRAT) + 2εTResearch Paper

Many decision problems are solved repeatedly against data that arrive over time: routing traffic, allocating budgets, choosing portfolios or combinatorial structures. Online linear optimization models this. At each round t=1,…,Tt = 1, \ldots, Tt=1,…,T a learner picks a decision xtx_txt​ from a fixed domain K⊆Rn\mathcal K\subseteq\mathbb R^nK⊆Rn, then a reward vector ftf_tft​ is revealed…

7 thms2 active usersReviewed
🏆Completed
ProbabilityStatistics·Captain: mikedeng1

Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems 1: Finite-Sample Confidence Region for the Mean and CovarianceResearch Paper

An optimization model often needs a probability distribution for an uncertain cost or demand, while a practitioner has only a finite sample from that distribution. Replacing the distribution by the empirical one can hide uncertainty in its estimated mean and covariance. Delage and Ye use a finite-sample confidence region for these two moments to justify a…

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

Assortment Optimization under Variants of the Nested Logit Model 1: If the Restricted LP Optimum Scaled by α Is Feasible for the Full LP, Its Assortment Earns Within a Factor α of the Optimal RevenueResearch Paper

A retailer that sells products in several categories, channels or stores has to decide which products to offer in each. Customers substitute: a product left out of the assortment sends some of its demand to other products, and some of it away. The nested logit model (McFadden 1974, 1981) is the standard choice model for this situation. It groups products…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: mikedeng1

A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms II: With F = 0, Iterates Converge Weakly to a Primal–Dual Solution When στ‖L‖² < 1Research Paper

Many problems in imaging, signal processing and statistics are convex minimizations of the form

16 thms2 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: mikedeng1

A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms III: In Finite Dimension with F = 0, Iterates Converge When στ‖L‖² ≤ 1Research Paper

Many problems in imaging, signal processing and statistics take the form

13 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case IV: The Generalized Abstract Model — Restricted Policy Classes under ContractionTextbook

Abstract dynamic programming, in the form developed by Denardo (1967) and Bertsekas (1977), studies sequential decision problems through a single monotone mapping H(x,u,J)H(x,u,J)H(x,u,J): the cost of using control uuu at state xxx when the future is valued by the function JJJ. Chapters 2–5 of Bertsekas and Shreve, Stochastic Optimal Control: The Discrete-Time Case (1978; Athena…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Solving Linear Programs in the Current Matrix Multiplication Time: The Stochastic Central Path Falls Back to a Classical Step with Probability at Most 10/n² per IterationResearch Paper

Linear programming, min⁡{c⊤x:Ax=b, x≥0}\min\{c^\top x : Ax=b,\ x\ge0\}min{c⊤x:Ax=b, x≥0} with A∈Rd×nA\in\mathbb R^{d\times n}A∈Rd×n, is the basic model of operations research, and the complexity of solving it is a central question of algorithm theory. Interior-point methods follow the central path: primal–dual pairs (x,s)(x,s)(x,s) with x,s>0x,s>0x,s>0 and xisi=tx_is_i=txi​si​=t for every iii, as the path parameter ttt decreases to 000. A…

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

Supply Chain Coordination with Revenue-Sharing Contracts: Strengths and Limitations 3: The Optimal Wholesale-Price Contract with R′(q) = 1 − q^α Has Efficiency (2+α)/(1+α)^((1+α)/α)Research Paper

A supplier who sells to a retailer at a per-unit wholesale price above her own production cost induces the retailer to order less than an integrated firm would. This effect, double marginalization, goes back to Spengler (1950) and is the standard benchmark against which supply chain contracts are judged: a contract coordinates the channel if it makes the…

10 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

Discounted Dynamic Programming: An Optimal Stationary Plan Exists When the Action Set Is Essentially FiniteResearch Paper

Sequential decisions often change the distribution of future states. A planner choosing an action today must account for both its immediate reward and the later rewards made possible by the resulting state. The mathematical question is whether an optimal rule can be chosen once and reused at every stage, even when a competing plan may randomize and use the…

11 thms2 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case I: Finite-Horizon Abstract Dynamic Programming — the DP Algorithm Yields the N-Stage Optimal CostTextbook

Dynamic programming (DP) solves sequential decision problems by backward recursion: compute the optimal cost of the last stage, then of the last two stages, and so on. For problems with finitely many states and controls and real-valued costs, the recursion obviously gives the optimal cost. Applications are rarely like that. Control spaces are continuous,…

12 thms2 active usersReviewed
🏆Completed
AnalysisDifferential Geometry·Captain: mikedeng1

Projection-like Retractions on Matrix Manifolds I: Coming Back to a Submanifold Along a Smooth Field of Transverse Subspaces Defines a RetractionResearch Paper

Iterative methods for optimization and equation solving on a smooth constraint set M\mathcal MM (orthogonal matrices, fixed-rank matrices, spheres, Stiefel and Grassmann manifolds) compute an update vector uuu in the tangent space at the current iterate xxx and then have to return to M\mathcal MM. The Riemannian exponential map does this along geodesics, but…

10 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming 3: A Convergent Relaxation from Z Solves the Equality ProgramResearch Paper

Many large convex programs have the form "minimize a strictly convex function fff subject to linear equations Ax=bAx=bAx=b". Examples are entropy maximization under moment constraints, the estimation of a matrix with prescribed row and column sums (the matrix-scaling or RAS problem of transportation and input–output analysis), and least-norm solutions of linear…

6 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Optimal Sequencing of a Single Machine Subject to Precedence Constraints: Repeatedly Placing Last a Least-Cost Eligible Job Yields a Minmax Optimal SequenceResearch Paper

Single-machine sequencing is the base case of deterministic scheduling theory. Many multi-machine and shop problems are analysed by reduction to it, and many bounds and approximation algorithms for harder models use it as a subroutine. A central objective class is the bottleneck or minmax objective. Each job carries a nondecreasing cost of its completion…

13 thms2 active usersReviewed
PreviousPage 80 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