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

Critical-Path Planning and Scheduling II: The Project Cost Curve Is Non-Increasing, Piecewise Linear and ConvexResearch Paper

A large engineering or construction project is a set of jobs with precedence constraints, and most jobs can be finished faster at a higher cost (overtime, more crews, faster equipment). Planners want to know, for every possible project duration, the cheapest way to meet it. The resulting trade-off between duration and direct cost is what management compares…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

An Optimal On-Line Algorithm for Metrical Task System 2: The Randomized Competitive Ratio of the Uniform Task System Lies Between H(n) and 2H(n)Research Paper

Metrical task systems, introduced by Borodin, Linial and Saks (J. ACM 39(4), 1992), are a common abstraction of on-line problems in which a server occupies one of finitely many states, pays a cost for each task depending on its current state, and may pay a transition cost to change state first. Paging, list update and the kkk-server problem all fit into this…

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

An Optimal On-Line Algorithm for Metrical Task System 1: Every n-State Metrical Task System Has Competitive Ratio 2n - 1Research Paper

A system that processes a stream of tasks can often be configured in several ways, and the configuration affects both the cost of the current task and the cost of switching before the next one: paging schemes, replicated files, server placements. When the future is unknown, the natural worst-case yardstick is competitive analysis, introduced by Sleator and…

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

Nonmonotone Spectral Projected Gradient Methods on Convex Sets I: SPG2 Is Well Defined and Its Accumulation Points Are StationaryResearch Paper

Minimizing a smooth function over a closed convex set Ω⊆Rn\Omega\subseteq\mathbb R^nΩ⊆Rn on which projection is cheap (a box, a ball, a simplex) is a routine subproblem in large-scale optimization: box-constrained minimization is the inner solver of augmented Lagrangian methods, and bound-constrained least squares, image restoration and density estimation all have…

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

Robust Solutions of Optimization Problems Affected by Uncertain Probabilities II: A Self-Concordant Barrier for the Perspective ConstraintResearch Paper

Robust optimization protects a decision against every scenario in an uncertainty set. When the uncertain data are probabilities, a natural uncertainty set is a ball around a nominal distribution measured by a φ-divergence (Kullback–Leibler, Burg entropy, χ², Hellinger and others). Ben-Tal, den Hertog, De Waegenaere, Melenberg and Rennen (Management Science…

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

Robust Solutions of Optimization Problems Affected by Uncertain Probabilities I: The Robust Counterpart of a Linear Constraint under φ-Divergence UncertaintyResearch Paper

Many decision problems contain a constraint whose coefficients are an expectation under a probability vector that is not known exactly: an expected cost under uncertain scenario probabilities, an expected payoff of an asset under an estimated distribution, the expected demand in a newsvendor model. The probabilities are usually estimated from data, and a…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: naimengye

Understanding Machine Learning XVI: Online LearningTextbook

In PAC learning the learner receives a batch of examples, learns, and only then predicts. Online learning has no such separation: on each round the learner receives an instance, predicts its label, and then sees the true label, and the goal is to make few mistakes over the whole sequence, with no statistical assumption whatsoever on how the sequence is…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: naimengye

Understanding Machine Learning XIII: Multiclass Prediction and RankingTextbook

Binary classification is the exception in practice; most prediction tasks have many labels, a structured label space, or ask for a ranking. Chapter 17 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) extends linear predictors to these settings through one idea: a class-sensitive…

12 thms2 active usersReviewed
🏆Completed
Machine Learning·Captain: naimengye

Understanding Machine Learning XII: Kernel Methods and the Representer TheoremTextbook

Chapter 15 bounded the sample complexity of large-margin halfspaces by the norms of the data and of the separator, independently of the dimension. Chapter 16 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) removes the remaining obstacle to using halfspaces in very high-dimensional…

8 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: naimengye

Understanding Machine Learning XI: Support Vector Machines and MarginTextbook

The sample complexity of learning halfspaces in Rd\mathbb{R}^dRd grows with ddd, which is bad news when features are many or infinite. Chapter 15 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) introduces the support vector machine, the learning rule that replaces dimension by geometry.…

15 thms2 active usersReviewed
🏆Completed
Machine LearningProbability·Captain: naimengye

Understanding Machine Learning X: Gradient Descent, Subgradients and Stochastic Gradient DescentTextbook

Chapter 13 showed that convex-Lipschitz-bounded and convex-smooth-bounded problems are learnable by regularized loss minimization; Chapter 14 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) shows how to learn them with the simplest possible algorithm. Gradient descent moves against…

12 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: naimengye

Understanding Machine Learning IX: Convex Learning Problems, Regularization and StabilityTextbook

Chapters 12 and 13 of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) leave binary classification for the general framework in which a hypothesis is a vector w∈Rdw \in \mathbb{R}^dw∈Rd and the loss ℓ(w,z)\ell(w, z)ℓ(w,z) is a convex function of www. Convexity makes the ERM problem tractable (Lemma 12.11), but…

13 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: naimengye

Understanding Machine Learning VI: Linear Predictors, the Perceptron and Least SquaresTextbook

Part II of Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms (doi:10.1017/CBO9781107298019) turns from the theory of learnability to hypothesis classes that can actually be learned by algorithms, and it starts with the family that almost every practical method is built on: linear predictors. Chapter 9 introduces the…

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

The Theory and Practice of Revenue Management III: Dynamic PricingTextbook

A retailer marking down a seasonal line, an airline raising fares as seats sell, a manufacturer pricing while restocking: each sets prices over time against a finite and changing inventory. Chapter 5 of Talluri and van Ryzin's The Theory and Practice of Revenue Management (2004) collects the structural theory of that problem. Without replenishment, the…

5 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

Fundamentals of Supply Chain Theory IX: Facility Location ModelsTextbook

Choosing where to open distribution centers is the strategic decision that fixes a supply chain's shape for years. The basic model, the uncapacitated fixed-charge location problem (UFLP) of Balinski (1965), trades the fixed cost of opening sites against the cost of transporting demand from open sites to customers. It is NP-hard, yet routinely solved to…

10 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: naimengye

Inventory Control VII: Multi-Echelon Lot Sizing and Roundy's 98 % ApproximationTextbook

Chapter 9 of Axsäter's Inventory Control opens with the observation that in a multi-echelon system it is not optimal to choose batch quantities installation by installation: the batch at one site is the demand pattern of the next site upstream. Even with constant customer demand the exact optimum can be complicated, and the book's Example 9.4 shows a…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: naimengye

Inventory Control VI: Optimality of (R, Q) Policies When Ordering in BatchesTextbook

Every model in Chapters 5 and 6 of Axsäter's Inventory Control assumes at the outset that the ordering policy is of (R,Q)(R,Q)(R,Q) or (s,S)(s,S)(s,S) type. Section 6.2 asks whether better policies exist and answers, for the case in which there are no ordering costs but every order must be a multiple of a fixed batch quantity QQQ, that none do: Proposition 6.1, "an (R,Q)(R,Q)(R,Q) policy…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: naimengye

Inventory Control V: Joint Optimization of Reorder Point and Batch QuantityTextbook

An (R,Q)(R,Q)(R,Q) policy has two parameters. Chapter 4 of Axsäter's Inventory Control chooses the batch quantity QQQ from a deterministic model, and Chapter 5 chooses the reorder point RRR from a stochastic one with QQQ held fixed; the book presents this two-step practice as an adequate approximation. Section 6.1 asks what is lost by it and shows how to optimize both…

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

Inventory Control IV: Reorder Points under Normally Distributed DemandTextbook

Chapter 4 of Axsäter's Inventory Control fixes the batch quantity QQQ from a deterministic model, and Chapter 5 asks the question that deterministic models cannot answer: with demand random and a replenishment lead-time LLL, when should the next batch be ordered? Under a continuous review (R,Q)(R,Q)(R,Q) policy the answer is a single number, the reorder point RRR, and…

16 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityRandom Matrix Theory+1·Captain: mikedeng1

High-Dimensional Probability X: Exact Sparse RecoveryTextbook

Compressed sensing asks a question that looks impossible at first: can a signal x∈Rnx\in\mathbb R^nx∈Rn be reconstructed exactly from far fewer than nnn linear measurements y=Ax∈Rmy=Ax\in\mathbb R^my=Ax∈Rm, m≪nm\ll nm≪n? Classical linear algebra says no — an underdetermined system has infinitely many solutions. But if xxx is known in advance to be sparse (most of its coordinates are…

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

Supermodularity and Complementarity VI: The Core of a Convex GameTextbook

A cooperative game with side payments models a set of economic agents who can form coalitions and split the proceeds. The central question is stability: is there a way to split the total payoff among all the players so that no subset of them would do better by breaking away and acting on its own? The set of such stable splits is the core, introduced by…

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

Supermodularity and Complementarity III: Assortative Matching under SupermodularityTextbook

Which workers end up at which firms, and does higher quality always land at the more productive employer? This is the question of assortative matching: whether an efficient assignment pairs the best workers with the best firms, the second-best with the second-best, and so on down the line. The question has a long history in labor economics. Becker [1973]…

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

Introduction to Stochastic Programming V: The Integer L-Shaped MethodTextbook

Two-stage stochastic programs with recourse are already hard to optimize when the recourse problem is a linear program: Chapters 4–6 of this series show how the L-shaped method exploits the recourse function's convexity and polyhedrality to converge finitely by cutting planes. Adding integrality restrictions destroys both properties. Birge and Louveaux open…

6 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Introduction to Stochastic Programming IV: Nested Decomposition for Multistage ProgramsTextbook

Sequential planning problems — inventory replenishment, hydro-thermal power scheduling, asset-liability management — routinely span more than two decision epochs, with information about the future revealed gradually as each period unfolds. A two-stage recourse model (decide now, observe once, recourse once) is too coarse for these: it either collapses the…

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

Introduction to Online Convex Optimization XI: Boosting via Online Convex OptimizationTextbook

A "rule of thumb" classifier — a single pixel's brightness distinguishing handwritten "0" from "1" — is trivial to produce and barely better than a coin flip. A rule that gets every example right is, in general, far harder. Boosting asks whether many weak, easy-to-produce rules can be combined into one strong, hard-to-produce rule, and Chapter 11 answers it…

3 thms2 active usersReviewed
PreviousPage 68 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