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
Convex OptimizationMachine Learning·Captain: mikedeng1

Introduction to Online Convex Optimization II: Convergence Rates for Well-Conditioned Convex OptimizationTextbook

Convex optimization — minimizing a convex function over a convex set — is the offline problem that online convex optimization (OCO) generalizes: an OCO algorithm run against a single, fixed cost function repeated every round is exactly an algorithm for this classical problem. Its convergence theory, developed over decades and surveyed comprehensively in…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: naimengye

Stochastic Networks VIII: Flow Level Models and the Stability of alpha-Fair AllocationsTextbook

Chapter 7 of Frank Kelly and Elena Yudovina's Stochastic Networks (Cambridge University Press, 2014) studies a network with a fixed set of users, and shows that a decentralized rate control converges to a fair allocation. Chapter 8 asks the question one time scale up. Files finish and their flows leave; new files arrive and new flows appear. The number of…

10 thms2 active usersReviewed
🏆Completed
Control TheoryOperations Research·Captain: naimengye

Stochastic Networks VII: Internet Congestion Control and the Primal AlgorithmTextbook

When a file is transferred over the Internet, no part of the network decides how fast it should go. The machines inside the network forward packets; when a resource is heavily loaded it drops or marks one; the destination reports that to the source; and the source slows down, then gradually speeds up again until the next signal. This end-to-end cycle of…

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

Supermodularity and Complementarity I: Lattices and the Tarski-Zhou Fixed Point TheoremTextbook

Many results in economics and operations research reduce to a single question: does a system of interacting, mutually reinforcing choices settle at an equilibrium? A firm choosing input levels that are complements, a Cournot duopoly whose best responses move together, a matching market where agents' preferences reinforce assortative pairings — each is a…

6 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: Shuze Chen

Dynamic Programming and Optimal Control VI: Lookahead and RolloutTextbook

When exact dynamic programming is intractable, practice runs on approximations: one-step and multistep lookahead with a cost-to-go surrogate, open-loop feedback control, and rollout — the algorithm that improved backgammon programs and became a conceptual ancestor of Monte-Carlo tree search and modern policy improvement schemes. Chapter 6 of Bertsekas, Dynam…

9 thms2 active usersReviewed
🏆Completed
Probability·Captain: viratkota

Kelly's Criterion: the optimal fraction for an even-money betResearch Paper

In 1956 Kelly answered a question that looks like gambling and is really about information: if a channel gives you a noisy advance signal about a sequence of bets, how much is that signal worth? His answer was that the maximum exponential rate of growth of a gambler's capital equals the rate of transmission over the channel -- so information rate and…

4 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: Shuze Chen

Dynamic Programming and Optimal Control I: The DP AlgorithmTextbook

Dynamic programming is the backbone of stochastic optimal control, operations research, and reinforcement learning. Its cornerstone — that the backward recursion of Bellman computes the optimal cost of a finite-horizon stochastic control problem — is stated as Proposition 1.3.1 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., Athena…

5 thms2 active usersReviewed
🏆Completed
Numerical Analysis·Captain: wenxinzhang

Vector Space Methods XIII: Conjugate-Gradient ConvergenceTextbook

The conjugate-gradient method in Luenberger's Chapter 10 is one of the most enduring consequences of Hilbert-space geometry in numerical optimization. For a bounded self-adjoint coercive operator, it solves the quadratic first-order equation Q x = b using only operator applications, inner products, and a short recurrence. Luenberger develops the method from…

6 thms2 active usersReviewed
🏆Completed
Numerical Analysis·Captain: wenxinzhang

Vector Space Methods XIV: Quadratic Penalty ConvergenceTextbook

Quadratic exterior penalties in Luenberger's §10.11 replace a constrained problem by a sequence of unconstrained minimizations. The method is simple enough to state in a few lines, yet Luenberger's convergence theorem is strikingly general: no convexity, differentiability, or convergence of the full minimizer sequence is required. If penalty weights…

5 thms2 active usersReviewed
🏆Completed
Convex Optimization·Captain: wenxinzhang

Vector Space Methods XI: Generalized Kuhn–Tucker ConditionsTextbook

Luenberger's generalized Kuhn–Tucker theorem turns inequality-constrained optimization into an order-theoretic statement on normed vector spaces. Instead of listing scalar inequalities, it lets a convex cone P define positivity in a target space Z; one condition G x ≤ₚ 0 can therefore represent finite, infinite, or function-valued families of constraints.…

5 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: wenxinzhang

Vector Space Methods X: Equality-Constrained Lagrange MultipliersTextbook

Equality-constrained optimization is the point where the geometric language of vector spaces becomes an operational calculus. In finite dimensions, the familiar rule says that the gradient of an objective at a regular constrained optimum is a linear combination of the constraint gradients. Luenberger's Chapter 9 replaces coordinate gradients by continuous…

4 thms2 active usersReviewed
🏆Completed
Calculus of Variations·Captain: wenxinzhang

Vector Space Methods VII: Euler–Lagrange EquationsTextbook

The calculus of variations replaces optimization over finitely many coordinates by optimization over paths. Its necessary conditions underlie geodesics, minimum-energy curves, classical mechanics, and many optimal-control models. Chapter 7 of David G. Luenberger's Optimization by Vector Space Methods presents this transition as an application of…

6 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: wenxinzhang

Vector Space Methods VI: Pseudoinverse OperatorsTextbook

Linear equations between Hilbert spaces need not have unique solutions and may not even be exactly solvable for a given right-hand side. Least squares selects a vector with the smallest residual; when several such vectors exist, minimum norm selects one canonical representative. Luenberger packages this two-stage optimization into the pseudoinverse of a…

7 thms2 active usersReviewed
🏆Completed
Functional Analysis·Captain: wenxinzhang

Vector Space Methods IV: Minimum-Distance DualityTextbook

Best approximation asks how closely a point can be represented by a prescribed linear model. In a Hilbert space, orthogonality turns this into a geometric projection problem. A general normed space has no inner product and may have no nearest point, so the corresponding certificate must live in the continuous dual rather than in the original space. Chapter…

4 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization VI: Farkas' Lemma and Separating HyperplanesTextbook

When is a system of linear constraints infeasible? Sections 4.6-4.7 of Bertsimas-Tsitsiklis answer with the archetypal theorem of the alternative. The capstone is Farkas' lemma (Theorem 4.6): for an m×nm \times nm×n matrix AAA and b∈Rmb \in \mathbb{R}^mb∈Rm, exactly one of the following holds — (a) some x≥0x \ge 0x≥0 satisfies Ax=bAx = bAx=b, or (b) some ppp satisfies p′A≥0′p'A \ge 0'p′A≥0′ and …

8 thms2 active usersReviewed
🏆Completed
Linear Optimization·Captain: Shuze Chen

Introduction to Linear Optimization III: Fourier–Motzkin Elimination and Projections of PolyhedraTextbook

Is the shadow of a polyhedron again a polyhedron? §2.8 of Bertsimas–Tsitsiklis answers this with perhaps the oldest method for solving linear programming problems: Fourier–Motzkin elimination. Given P={x∈Rn∣∑j=1naijxj≥bi, i=1,…,m}P = \{x \in \mathbb{R}^n \mid \sum_{j=1}^n a_{ij}x_j \ge b_i,\ i = 1, \dots, m\}P={x∈Rn∣∑j=1n​aij​xj​≥bi​, i=1,…,m}, one sorts the constraints by the sign of the coefficient of xnx_nxn​ — rewriting…

6 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: Shuze Chen

Introduction to Linear Optimization II: Existence and Optimality of Extreme PointsTextbook

Where should one look for the optimum of a linear programming problem? Chapter 1 of Bertsimas–Tsitsiklis suggests that optima "tend to occur at corners" of the feasible polyhedron; §§2.5–2.6 turn this intuition into theorems. Not every polyhedron has a corner — a halfspace in Rn\mathbb{R}^nRn (n>1n > 1n>1) has none — and the exact dividing line is the presence of an…

12 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningMarkov Chain+1·Captain: QianJaneXie

Cost-aware Bayesian Optimization via the Pandora's Box Gittins IndexResearch Paper

Formal verification complete: all 12 mission targets, including Theorem 2, are Proved. These results apply to the formalized independent-box model described below. Paper: Cost-aware Bayesian Optimization via the Pandora's Box Gittins Index, NeurIPS 2024. The formalization follows Theorem 2 and Appendix B.5 of the paper.

13 thms1 active userReviewed
🏆Completed
Machine LearningProbability·Captain: Minghui

Optimization Methods for Large-Scale Machine Learning: Stochastic Gradient ConvergenceResearch Paper

Training a machine-learning model often means choosing a vector of parameters to minimize an average loss. Evaluating the full gradient can require processing an entire dataset. A stochastic-gradient method instead updates the parameters using a random direction obtained from a smaller amount of information. Its computational appeal raises a mathematical…

6 thms1 active userReviewed
🏆Completed
Machine LearningProbability·Captain: Minghui

SCAFFOLD: Convergence with Client SamplingResearch Paper

Federated optimization trains one model using objectives held by many clients. Performing several local updates between communication rounds saves communication, but clients with different objectives can move in different directions. SCAFFOLD maintains a correction for each client to address this disagreement, including when only some clients participate.…

6 thms1 active userReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: moutei

Primal-Dual Online Algorithms III: Set-Cover Approximation via CertificatesTextbook

Set cover is the standard worked example of the primal-dual method, and Chapter 2 of Buchbinder's thesis uses it that way: it is where the machinery of §2.1 is first turned on a concrete NP-hard problem. Two analyses appear. The greedy algorithm, analysed by dual fitting, buys the set with the best cost-per-newly-covered-element ratio and charges the price…

10 thms1 active userReviewed
🏆Completed
Linear OptimizationTheoretical Computer Science·Captain: moutei

Primal-Dual Online Algorithms I: Fractional Ski RentalTextbook

An online algorithm must commit to decisions before it knows the rest of its input, and it is judged by competitive analysis: the ratio between its cost and the cost of an optimal solution computed with full knowledge of the input. A recurring obstacle in this area is that each problem seems to need its own ad hoc potential-function argument. Buchbinder's…

9 thms1 active userReviewed
🏆Completed
Logic·Captain: FiniteUniverse

APF Reconstruction — Research Archive (to 2026-10-02)Research Paper

For the same original source U, history binding S and occupant x, compare two eligible finite tables: transported rows act q (r i) against the unchanged suffixes t j, and the original rows r i against the corresponding prefixed suffixes prefixSuffix p.val (t j), where p is a supported representative of q. There are real linear equivalences between their…

484 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: Goku

Oracle-Parameterized Convergence Rates: SPIDER, Q-SPIDER, and the Exact CrossoverResearch Paper

Quantum algorithms for stochastic optimization are usually presented one paper at a time: a schedule is fixed, a quantum mean estimator is substituted for a classical minibatch, and a new rate is derived from scratch. The derivations are near-identical, and the step that actually differs — the price of one gradient query — is buried inside each proof rather…

37 thms1 active userReviewed
🏆Completed
Operations ResearchProbability·Captain: StellaXin

Capped Base-Stock Policies: A 2.33-ApproximationResearch Paper

When replenishment takes several periods, an inventory decision commits stock before the demand that will consume it is known. Too much stock incurs holding costs; too little loses sales. An optimal decision can depend on the entire pipeline of outstanding orders. A rule with only two adjustable parameters is easier to implement, but its simplicity alone…

14 thms1 active userReviewed
PreviousPage 69 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