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
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Applied Combinatorics VIII: The Max Flow–Min Cut TheoremTextbook

Moving as much as possible of something — freight, water, data — from an origin to a destination through connections of limited capacity is one of the basic problems of operations research. Its mathematical form, the maximum flow problem, was posed in the 1950s in work on rail networks and solved independently by Ford and Fulkerson (Maximal flow through a…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis IX: The Discrete Conjugacy TheoremTextbook

The Legendre-Fenchel transform is the single most structurally important operation in convex analysis: for a proper closed convex function fff, its conjugate f∙(p)=sup⁡x{⟨p,x⟩−f(x)}f^\bullet(p) = \sup_x \{\langle p,x\rangle - f(x)\}f∙(p)=supx​{⟨p,x⟩−f(x)} is again proper closed convex, and the transform is an involution — f∙∙=ff^{\bullet\bullet} = ff∙∙=f. This one fact underlies duality theory across optimization:…

13 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis VIII: Quasi L-Convex Functions and the Quasi-Proximity TheoremTextbook

Milgrom and Shannon's theory of quasi-supermodularity, developed for monotone comparative statics in economics, showed that many of the consequences of lattice submodularity survive under a much weaker, purely ordinal relaxation of the defining inequality. Chapter 7's final section imports this idea into discrete convex analysis: does L-convexity's…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes XIX: Theory of Optimal Stopping ProblemsTextbook

A gambler watching a sequence unfold has to decide, at each moment and knowing only the past, whether to take what is on the table or wait for something better. That is the whole of optimal stopping, and it is one of the few problems in stochastic control with a clean and completely general answer: the value of the problem is the smallest superharmonic…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationDiscrete Geometry+1·Captain: Shuze Chen

Discrete Convex Analysis XXI: The Exchange Axiom as Local OptimalityTextbook

Convexity on the integer lattice cannot be defined by the classical secant-line inequality alone: a function can be midpoint-convex along every line and still admit no useful global optimality theory, because integer points off a chosen line are invisible to it. M-convex functions, introduced by Murota, resolve this by replacing the secant condition with an …

38 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

Star-Shaped Risk Measures 1: star-shaped risk measures are the minima of convex risk measuresResearch Paper

A risk measure turns the random loss of a financial position into a single number: the amount of capital a regulator or a risk manager requires to hold the position. Two families of risk measures dominate practice and theory. Value-at-Risk (VaR), a quantile of the loss distribution, is used in banking and insurance regulation; it is positively homogeneous…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis VI: Quasi M-Convex Functions and the Quasi-Proximity TheoremTextbook

Convexity is normally defined additively — a function's value at a mixture is bounded by the mixture of its values — but many of the properties that make convexity useful in optimization (a local minimum is global, level sets are well-behaved) survive under a much weaker, purely ordinal notion: quasi-convexity, which compares function values rather than…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes XV: Optimal Play in Red-and-Black and the Gittins IndexTextbook

Chapter 7's abstract machinery — contracting Markov Decision Models, the Structure Theorem, value iteration with an explicit convergence rate — earns its keep by solving concrete problems. Section 7.6 works through four kinds of application: a return to the classical cash-balance inventory problem, now over an infinite horizon; the "red-and-black" gambling…

17 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis V: The M-Optimality Criterion and the Proximity TheoremTextbook

Scaling algorithms are one of the standard techniques for solving discrete optimization problems efficiently: instead of searching a huge integer domain directly, an algorithm first solves a coarsened version of the problem — checking optimality only against neighbors reached by a large step size α\alphaα — and then refines the resulting approximate solution…

14 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: mikedeng1

Existence of an Equilibrium for a Competitive Economy II: Equilibrium Exists When Every Consumer Can Supply Productive LaborResearch Paper

A competitive equilibrium is a list of production plans, consumption plans and prices at which every firm maximizes profit, every consumer maximizes utility within the budget, and no market has excess demand. Whether such prices exist at all is the consistency question behind general equilibrium theory, the welfare theorems, and applied equilibrium models…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationDiscrete Geometry+1·Captain: Shuze Chen

Discrete Convex Analysis XIX: Discrete Separation for M-Convex SetsTextbook

Submodular set functions are the combinatorial stand-in for convexity: a function ρ:2V→R\rho : 2^V \to \mathbb Rρ:2V→R on the subsets of a finite ground set VVV is submodular if ρ(X)+ρ(Y)≥ρ(X∪Y)+ρ(X∩Y)\rho(X) + \rho(Y) \ge \rho(X \cup Y) + \rho(X \cap Y)ρ(X)+ρ(Y)≥ρ(X∪Y)+ρ(X∩Y), and this single diminishing-returns inequality drives an enormous range of combinatorial optimization — matroid rank functions, graph cut…

29 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis XVIII: Integral Convexity of Minimizer SetsTextbook

A classical convex function's global minimality is equivalent to its local minimality — the single fact that makes convex optimization tractable, since checking a small neighborhood suffices to certify a global guarantee. The discrete analogue is not automatic: a function on the integer lattice can fail to have any well-behaved "local" notion at all, and…

28 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis XVII: Fenchel Duality and Linear-Programming IntegralityTextbook

Duality is the organizing principle of convex optimization: a minimization problem's optimal value equals a maximization problem's optimal value, and this coincidence, rather than being a lucky accident, follows from a separating-hyperplane argument that applies whenever the two problems' feasible regions are shaped compatibly enough. Werner Fenchel…

37 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes VII: Consumption-Investment Problems and Regime SwitchingTextbook

Real investors do not merely accumulate wealth for a single terminal payoff; they consume along the way, and the market they invest in is rarely a single fixed statistical regime for years at a time — bull and bear markets, business cycles, and volatility regimes shift the distribution of returns. Bäuerle and Rieder's §4.3 extends the terminal-wealth theory…

16 thms3 active usersReviewed
Convex OptimizationNumerical AnalysisOperations Research·Captain: mikedeng1

Golden Ratio Algorithms for Variational Inequalities II: The Explicit Golden Ratio Algorithm Converges for Locally Lipschitz Monotone OperatorsResearch Paper

Monotone variational inequalities cover convex minimisation, convex–concave saddle-point problems, Nash equilibria of monotone games and complementarity problems, and they are the standard model for these in optimization and operations research. First-order methods for them (extragradient, forward–backward–forward, reflected and projected gradient methods)…

18 thms3 active users
🏆Completed
CombinatoricsComplexity TheoryOperations Research+2·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions V: Beating 1/2 for Symmetric Functions Requires Exponentially Many Value QueriesResearch Paper

Maximizing a nonnegative submodular set function without constraints contains Max Cut, Max Directed Cut and facility-location problems as special cases. In the value-oracle model an algorithm knows nothing about the function except the values f(S)f(S)f(S) of the sets SSS it queries, and it is judged by the number of queries it makes. Feige, Mirrokni and Vondrák (SIAM…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsConvex OptimizationDiscrete Geometry+1·Captain: mikedeng1

Lifts of Convex Sets and Cone Factorizations II: Antichain and Face-Count Lower Bounds on the Nonnegative Rank of a PolytopeResearch Paper

Many polytopes that arise in combinatorial optimization, such as the matching, cut, stable set and travelling salesman polytopes, have exponentially many facets, yet some of them can be written as the linear projection of a polyhedron with far fewer facets. The smallest number of facets of such a lift decides whether the polytope admits a compact…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions IV: Smooth Local Search Achieves 2/5 of the OptimumResearch Paper

Many optimization problems ask for a subset of a finite ground set that maximizes a submodular function, a set function with diminishing marginal returns. Max Cut and Max Directed Cut in graphs, facility location with fixed costs, and the maximization of mutual information or entropy of a subset of random variables are all of this form. Unlike the monotone…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryLinear Optimization+1·Captain: mikedeng1

On Polyhedral Approximations of the Second-Order Cone II: A Lower Bound on the Size of Polyhedral ApproximationsResearch Paper

A conic quadratic program minimizes a linear objective subject to constraints of the form ∥Aℓx−bℓ∥2≤cℓTx−dℓ\|A_\ell x-b_\ell\|_2\le c_\ell^Tx-d_\ell∥Aℓ​x−bℓ​∥2​≤cℓT​x−dℓ​. Interior-point methods solve such programs in polynomial time, but around 2000 the available solvers handled far smaller instances than linear programming codes did. Ben-Tal and Nemirovski (Math. Oper. Res. 26(2), 2001) asked…

10 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: Shuze Chen

Markov Decision Processes II: Existence of Optimal Policies under Compactness and ContinuityTextbook

The finite-horizon theory of chunk 02a-model-bellman-equation (Bäuerle and Rieder's Theorem 2.3.8, the Structure Theorem) reduces the existence of an optimal policy and the validity of the Bellman equation to a single abstract hypothesis: the Structure Assumption (SAN), the existence of function classes IMn\mathrm{IM}_nIMn​ and decision-rule classes Δn\Delta_nΔn​ closed…

14 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: mikedeng1

An Overview of Pricing Models for Revenue Management: Performance Guarantee of the Deterministic Price Heuristic in Periodic-Review PricingResearch Paper

Dynamic pricing under limited inventory is a core problem of revenue management: a seller holds C0C_0C0​ units of a perishable product (airline seats, hotel rooms, seasonal goods) and must choose prices over a finite selling horizon while demand is random and responds to price. The exactly optimal policy solves a stochastic dynamic program whose state is the…

9 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Decomposition and Partitioning Methods for Multistage Stochastic Linear Programs: Binding Cuts Force Degenerate Descendant Problems in Nested DecompositionResearch Paper

Multistage stochastic linear programs model decisions taken in periods t=1,…,Tt = 1, \dots, Tt=1,…,T while a random vector ξt\xi_tξt​ is revealed period by period: production and capacity planning, energy scheduling, asset–liability management. With finitely many scenarios the problem is one very large linear program with a tree structure, and decomposition methods solve it…

5 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research·Captain: mikedeng1

A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization: The IFB Iterates Minimize the Objective and Converge Weakly to a MinimizerResearch Paper

Many problems in signal processing, statistics and operations research ask to minimize a sum Θ=Φ+Ψ\Theta = \Phi + \PsiΘ=Φ+Ψ of a nonsmooth convex term Φ\PhiΦ (a constraint indicator, an ℓ1\ell^1ℓ1 penalty) and a smooth term Ψ\PsiΨ. The standard method is the forward-backward (proximal-gradient) algorithm: an explicit gradient step on Ψ\PsiΨ followed by a proximal step on Φ\PhiΦ.…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: mikedeng1

Dual Stochastic Dominance and Related Mean-Risk Models 1: Second-Degree Stochastic Dominance Is Dominance of Absolute Lorenz CurvesResearch Paper

Comparing uncertain outcomes is the basic problem of decision making under risk. Second-degree stochastic dominance (SSD) is the comparison that every risk-averse decision maker who prefers larger outcomes agrees with: XXX dominates YYY in this sense exactly when E U(X)≥E U(Y)\mathbb E\,U(X)\ge\mathbb E\,U(Y)EU(X)≥EU(Y) for every nondecreasing concave utility UUU for which the…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchProbability·Captain: mikedeng1

Robust Control of Markov Decision Processes with Uncertain Transition Matrices 4: The Dual of the Worst-Case Expectation over a Kullback-Leibler BallResearch Paper

A robust Markov decision process replaces the unknown transition probabilities of an MDP by sets of plausible values and optimises against the worst case. Nilim and El Ghaoui (Oper. Res. 53 (2005)) showed that, when the uncertainty is rectangular (each row of each transition matrix varies independently in its own set), the robust problem is solved by a…

10 thms3 active usersReviewed
PreviousPage 52 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