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 Research·Captain: mikedeng1

Supermodularity and Complementarity II: Topkis's Monotonicity Theorem for Parameterized OptimizationTextbook

A recurring question in economics and operations research is: when a decision problem depends on a parameter, does the optimal decision move monotonically as the parameter changes? A firm's optimal input mix as a price rises, a consumer's optimal consumption bundle as income grows, a Cournot firm's optimal output as a rival's output changes — in each case…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Introduction to Stochastic Programming II: The Value of Perfect Information and of the Stochastic SolutionTextbook

Every stochastic program is, in practice, compared against a shortcut. A decision maker facing genuine uncertainty is tempted either to replace the random data by its mean and solve one deterministic problem, or to imagine that perfect information about the future were available and solve a separate deterministic problem per scenario. Both temptations have…

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

Dynamic Programming and Optimal Control VII: Infinite Horizon ProblemsTextbook

Infinite-horizon dynamic programming is the mathematical core of Markov decision processes and reinforcement learning: Bellman equations, value iteration, policy iteration, and their guarantees. Chapter 7 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) develops the finite-state theory in its cleanest generality — stochastic…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: wenxinzhang

Vector Space Methods V: Convex Separation and Distance DualityTextbook

Linear approximation is only one instance of distance minimization. Feasible sets in optimization are typically convex rather than subspaces, so a useful certificate must compare a target point with an entire convex set and must allow an affine offset. Chapter 5 of Luenberger's Optimization by Vector Space Methods builds this certificate through geometric…

6 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: Shuze Chen

Convex Optimization IV: Löwner–John EllipsoidsTextbook

Every full-dimensional convex body is sandwiched between an ellipsoid and its nnn-fold dilation: shrinking the minimum-volume covering (Löwner–John) ellipsoid E\mathcal{E}E about its centre x0x_0x0​ by the factor 1/n1/n1/n lands inside the body,

8 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization XII: Interior Point Methods and Path FollowingTextbook

Interior point methods solve linear programs by moving through the interior of the feasible set instead of along its edges — the approach that turned Karmarkar's 1984 breakthrough into today's practical large-scale solvers. This mission formalizes the primal path following algorithm of Chapter 9 of Bertsimas–Tsitsiklis. For μ>0\mu > 0μ>0 the logarithmic barrier

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

Introduction to Linear Optimization XI: The Ellipsoid MethodTextbook

Can the feasibility of a system of linear inequalities be decided in a provably small number of iterations? The ellipsoid method — the algorithm with which Khachiyan showed in 1979 that linear programming is polynomially solvable — answers this with pure convex geometry. This mission formalizes Chapter 8 of Bertsimas–Tsitsiklis. An ellipsoid is

14 thms3 active usersReviewed
🏆Completed
Linear Optimization·Captain: Shuze Chen

Introduction to Linear Optimization IX: Network Flow IntegralityTextbook

Why do network linear programs return integer answers for free? This mission formalizes the structural theory of the minimum cost network flow problem of Chapter 7 of Bertsimas & Tsitsiklis: a directed graph G=(N,A)G=(\mathcal{N},\mathcal{A})G=(N,A) with external supplies bib_ibi​, arc costs cijc_{ij}cij​, and the node-arc incidence matrix A\mathbf{A}A — an n×mn\times mn×m matrix in which…

18 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization VIII: Sensitivity Analysis and Subgradients of the Optimal CostTextbook

How does the optimal cost of a linear program respond when the problem data change? Chapter 5 of Bertsimas-Tsitsiklis studies the standard form problem min⁡{c′x∣Ax=b, x≥0}\min\{c'x \mid Ax = b,\ x \ge 0\}min{c′x∣Ax=b, x≥0} (rows of AAA linearly independent) as the requirement vector bbb and the cost vector ccc vary. On the convex set S={b∣P(b)≠∅}S = \{b \mid P(b) \neq \emptyset\}S={b∣P(b)=∅} of feasible right-hand sides,…

11 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization V: Duality TheoryTextbook

Every linear programming problem has a shadow. To the primal min⁡c′x\min c'xminc′x we associate the dual max⁡p′b\max p'bmaxp′b, whose variables price the primal constraints: one dual variable per primal constraint and one dual constraint per primal variable, with signs governed by the correspondence of Table 4.1. This mission formalizes §4.1–4.5 of Bertsimas–Tsitsiklis: the dual of…

12 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization IV: The Simplex MethodTextbook

How does one actually solve a linear program? Chapter 2 showed that if a standard-form problem min⁡c′x\min c'xminc′x subject to Ax=bAx = bAx=b, x≥0x \ge 0x≥0 has an optimal solution, it has an optimal basic feasible solution; the simplex method searches among basic feasible solutions, moving along edges of the feasible set in cost-reducing directions. This mission formalizes the…

16 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization I: Polyhedra and Basic Feasible SolutionsTextbook

Every linear programming problem asks to minimize a linear cost c′xc'xc′x over a polyhedron — a set of the form P={x∈Rn∣Ax≥b}P = \{x \in \mathbb{R}^n \mid Ax \ge b\}P={x∈Rn∣Ax≥b}, or in standard form {x∣Ax=b, x≥0}\{x \mid Ax = b,\ x \ge 0\}{x∣Ax=b, x≥0}. Chapter 2 of Bertsimas–Tsitsiklis develops the geometry of these feasible sets, and its central achievement is making the intuitive notion of a "corner point"…

9 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism Design·Captain: iris

Compensation DesignResearch Paper

Platforms that aggregate content or data, such as generative-AI answer engines, recommendation services and data marketplaces, depend on independent contributors who decide for themselves whether to take part. Each contributor bears a private cost of participating, and the platform has a fixed budget to distribute. The platform knows how much value any set…

41 thms2 active usersReviewed
🏆Completed
Operations ResearchStatistics·Captain: iris

Rounding, Ranges, and Exact Sample-Removal Audits for Least SquaresResearch Paper

The sign of a least-squares coefficient often carries the substantive conclusion of an empirical study. Giordano, Meager and Broderick showed that deleting a small fraction of the observations can reverse such conclusions in prominent studies (GMB26). This raises an auditing question: how many observations must be removed before a conclusion drawn from an…

21 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine Learning·Captain: iris

Optimal Alternating Regret for Online Learning and GamesResearch Paper

In a repeated two-player game, the players can update simultaneously (both see only the past) or alternately (the second player sees the first player's current move before choosing). Alternating updates are known to speed up learning dynamics in zero-sum games (Wibisono, Tao, Piliouras, NeurIPS 2022; Cevher et al., NeurIPS 2023; Katona, Wang, Wibisono, JMLR…

21 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: iris

Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience: Greedy with a κ-Approximate Star-Graph Black Box Is κ/2-Competitive under Adversarial ArrivalsResearch Paper

Online bipartite matching, introduced by Karp, Vazirani and Vazirani (1990), models a platform that must assign arriving customers to a known stock of items, one customer at a time and irrevocably. In e-commerce, job search and online advertising, a recommendation is only a suggestion: a customer buys an offered item with some known probability, and after…

15 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+1·Captain: iris

Tight Approximation for Unconstrained XOS Maximization: Algorithm 4 Finds a (k−1)(k-1)(k−1)-Maximizer of Every kkk-XOS Function in O(k2n)O(k^2 n)O(k2n) Time, Exactly When k=2k=2k=2Research Paper

Maximizing a set function is a basic task in combinatorial optimization and algorithmic game theory. Computing an agent's demand under prices ppp amounts to maximizing v(X)−∑x∈Xpxv(X)-\sum_{x\in X}p_xv(X)−∑x∈X​px​, which need not be monotone even when the valuation vvv is. XOS functions generalize submodular functions, and they are studied in combinatorial auctions, where they are…

22 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: iris

An Accelerated Newton–Dinkelbach Method and Its Application to Two Variables per Inequality Systems: The Look-Ahead Newton–Dinkelbach Method Halves the Bregman Divergence Every Two IterationsResearch Paper

Many optimization problems ask for the largest root of a concave function of one real variable that can only be accessed through oracles. In linear fractional combinatorial optimization, minimizing a ratio c⊤x/d⊤xc^\top x/d^\top xc⊤x/d⊤x over x∈D⊆{0,1}mx\in D\subseteq\{0,1\}^mx∈D⊆{0,1}m reduces to finding the largest root of the concave, piecewise linear function …

14 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: iris

Coordination of Multiechelon Supply Chains Using the Guaranteed Service Framework: The Centralized Safety-Stock Optimum Equals the Best Split over the Service Time Between the Two PlayersResearch Paper

Multi-echelon supply chains are rarely run by a single firm. A manufacturer of a finished product buys a component from a supplier, and each firm places its own safety stock. The guaranteed-service model of safety-stock placement, going back to Simpson (1958) and developed by Graves and Willems (2000), lets a planner choose, for each stage, the service time…

5 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: iris

A Unifying Framework for Submodular Mean Field Games: Abstract Submodular MFGs Have Least and Greatest Equilibria, Reached by Iterating the Best-Response MapResearch Paper

Mean field games (MFGs), introduced by Lasry and Lions and by Huang, Malhamé and Caines in 2006–2007, describe the limit of symmetric stochastic games with many small players. A representative player optimizes against the distribution of the population, and an equilibrium is a distribution that reproduces itself when every player best responds to it.…

17 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation VII: expectation, worst case and CVaR are coherent risk measuresTextbook

A stochastic linear program evaluates a decision x∈Rnx\in\mathbb R^nx∈Rn through a random outcome, typically the linear-affine random variable ζ(x,η,ξ)=η⊤x−ξ\zeta(x,\eta,\xi)=\eta^\top x-\xiζ(x,η,ξ)=η⊤x−ξ, where η\etaη is a random vector and ξ\xiξ a random variable. Chapter 2 of Kall and Mayer's Stochastic Linear Programming (Springer, 2005) builds its single-stage models in two steps: a…

34 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation II: joint probability constraints are closed, and convex at high levels under finite discrete distributionsTextbook

A linear program whose technology matrix and right-hand side are random cannot simply require its constraints to hold: for most realizations of the data, no decision satisfies them all. A joint probability constraint (also called a chance constraint) asks instead that the random system T(ξ)x≥h(ξ)T(\xi)x\ge h(\xi)T(ξ)x≥h(ξ) hold with probability at least a prescribed level …

16 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: Shuze Chen

Online Assortment Optimization with Reusable Resources: The myopic policy earns at least half the clairvoyant optimal revenueResearch Paper

A server, storage unit or production machine can serve a customer and then become available again. Offering it now earns revenue but may prevent serving a later customer while it remains occupied. Online assortment optimization with reusable resources studies these decisions when each customer chooses among the products offered and an outside option. The…

11 thms2 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: iris

Implied Ambiguity: Mean-Variance Inefficiency and Pricing Errors: the smallest ambiguity aversion making a portfolio optimal is an explicit decreasing function of its normalized Sharpe ratioResearch Paper

Observed portfolios, from mutual fund holdings to market capitalization weights, are rarely mean-variance efficient: their Sharpe ratio falls short of that of the tangency portfolio. In a classical CARA–normal model this cannot happen, so the gap needs an explanation. Hara and Honda (working paper, 2018; Management Science, 2022) explain it by ambiguity…

13 thms2 active usersReviewed
🏆Completed
EconomicsOperations ResearchRevenue Management and Pricing·Captain: mikeh

Optimal Feature-Based Market Segmentation and PricingResearch Paper

A seller can often predict a customer's willingness to pay from observed features, yet may be limited to a small number of prices. The decisions are then coupled: the seller must choose both the customer groups and the price assigned to each group. Grouping customers first and optimizing prices afterward does not generally solve the joint problem. Cui and…

24 thms2 active usersReviewed
PreviousPage 46 of 70Next

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