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

Distributionally Robust Optimization: A Review: Variation²/4 ≤ Hellinger ≤ Kullback–Leibler ≤ J-Divergence, so the J, KL and Hellinger Balls of Radius ε Lie in the Variation Ball of Radius 2√εResearch Paper

Distributionally robust optimization evaluates a decision against a set of plausible probability laws rather than against a single estimated law. A common way to specify that set is to choose a nominal law P0P_0P0​ and allow every law PPP whose discrepancy from P0P_0P0​ is below a radius ε\varepsilonε. Different discrepancies produce different ambiguity sets, so…

10 thms6 active usersReviewed
🏆Completed
Quantum Information·Captain: Goku

Quantum algorithms for optimizers 9: QAOA with enough layers reaches a maximum eigenstate of H_FTextbook

This mission develops Chapter 9 of Quantum algorithms for optimizers by Giacomo Nannicini. The chapter's selected results describe the mathematical guarantees below.

15 thms6 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Product Price, Quality and Service Decisions under Consumer Choice Models III: The Optimal Uniform Service Duration Is the Shortest or the LongestResearch Paper

Firms that sell durable goods compete on price, on product quality and on the services bundled with the product: a factory warranty, free maintenance, technical support. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.0947) study the joint choice of all three when consumers choose among the firm's…

18 thms6 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

A Modern Introduction to Online Learning I: Projected Online Gradient Descent Has Regret D²/(2η_T) + Σ_t η_t‖g_t‖²/2Textbook

In online learning, a decision is made before the loss for that round is revealed. The learner cannot optimize a known objective once and use its minimizer forever: the sequence of objectives may be arbitrary. A basic performance measure is regret, the learner's total loss minus the loss of one fixed decision chosen with hindsight. A regret bound that grows…

9 thms6 active users
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition V: Under the Proximal-PL Inequality, Proximal-Gradient Converges at Rate (1 − μ/L)^kResearch Paper

Many problems in machine learning and signal processing minimize a smooth loss plus a simple non-smooth regularizer: ℓ1\ell_1ℓ1​-regularized least squares, group-sparse regression, and constrained problems written with an indicator function. The standard algorithm for this composite form is the proximal-gradient method, a gradient step on the smooth part…

11 thms6 active users
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming 3: The Two-Phase RSG Method Finds an (ε, Λ)-Solution within S(Λ)[N(ε) + T(ε, Λ)] Oracle CallsResearch Paper

Stochastic optimization methods often see only noisy gradients. For a nonconvex objective, a useful guarantee is that an output point has a small gradient: this is a first-order stationarity certificate, even when there is no claim that the point is globally optimal. A guarantee on the expected squared gradient leaves open how often one particular run…

14 thms6 active users
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 6: PARTITION Reduces to Two Agents Each Bounding Their Own Total Completion Time on One MachineResearch Paper

In many production and service settings a single resource is shared by parties with different goals: two departments sending orders to the same machine, two customers of a contract manufacturer, or two classes of requests on one processor. Multi-agent scheduling models this directly. Each agent owns its own jobs and its own objective, and a schedule is…

16 thms6 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 2: KNAPSACK Reduces to Minimizing One Agent's Total Weighted Completion Time Under a Makespan Bound for the OtherResearch Paper

In many production and logistics settings a single resource is shared by parties with different goals: two departments of a plant that send orders to the same machine, two customers of a contract manufacturer, or two classes of traffic on one processor. Multi-agent scheduling models this directly. Each agent owns its own jobs and its own objective, and a…

14 thms6 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Consumer Returns Policies and Supply Chain Performance 1: With Valuations Learned after Purchase, the Seller's Optimal Policy Is p* = E max(V, s), F̄(q*) = (c − s)/(p* − s), r* = sResearch Paper

Retailers accept large volumes of returned merchandise, and a common default is the full refund: a buyer who is unhappy with a product brings it back and gets the whole price back. Many consumers only learn how much they value a product after they have it at home — clothes that do not fit, a gadget that does not suit the buyer's needs. A returns policy…

15 thms6 active users
🏆Completed
Operations Research·Captain: mikedeng1

Scenarios and Policy Aggregation in Optimization Under Uncertainty 2: A Limit of Locally Optimal Progressive Hedging Steps Is a Stationary Point of the Nonconvex ProblemResearch Paper

Multistage decision problems under uncertainty are often modelled by a finite set of scenarios: each scenario sss fixes one possible future, and for it a deterministic problem can be solved. What makes the problem stochastic is the requirement that decisions may depend only on information available at the time they are taken. Rockafellar and Wets (WP-87-119,…

15 thms6 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Revenue Management Under a General Discrete Choice Model of Consumer Behavior 3: The Multinomial Logit Model Has the Nesting-by-Fare-Order PropertyResearch Paper

Airline and hotel revenue management sells one perishable resource (seats on a flight, rooms on a night) through several fare products at different prices. The classical models of Littlewood (1972), Belobaba (1989) and Lee and Hersh (1993) assume independent demand: a customer who wants fare class jjj either buys class jjj or leaves, whatever else is on offer.…

16 thms6 active users
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

Revenue Management Under a General Discrete Choice Model of Consumer Behavior 2: Nesting by Fare Order Holds Iff Purchase Probability Increases and Mixtures of Complete Sets Majorize Incomplete SetsResearch Paper

Airline and hotel revenue-management systems have traditionally been built around nesting by fare order: classes are ranked by price, and as capacity runs short the cheapest open class is closed first, so that the set of open fares is always a top segment {1,…,k}\{1, \dots, k\}{1,…,k} of the fare ladder. This structure is what makes booking limits, protection levels and…

10 thms6 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStochastic Systems·Captain: mikedeng1

Loss Networks 2: The Erlang Fixed Point Is E_j = 1 − exp(−y_j) for the Unique Optimum y of the Strictly Convex Revised Dual ProblemResearch Paper

A loss network is a model of a circuit-switched network: telephone networks, and more generally any system in which a request seizes several resources at once and is lost if any of them is unavailable. Exact loss probabilities in such networks are given by a product-form distribution over a state space whose size grows exponentially with the number of…

15 thms6 active usersReviewed
🏆Completed
Convex OptimizationLinear algebra·Captain: mikedeng1

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers II: Soft Thresholding Is the Proximity Operator of the ℓ1 NormTextbook

The alternating direction method of multipliers (ADMM) solves problems of the form min⁡f(x)+g(z)\min f(x)+g(z)minf(x)+g(z) subject to Ax+Bz=cAx+Bz=cAx+Bz=c by alternating a minimization in xxx, a minimization in zzz and a dual ascent step. Its practical appeal, as surveyed by Boyd, Parikh, Chu, Peleato and Eckstein in Distributed Optimization and Statistical Learning via the Alternating Direction…

12 thms6 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingOperations Research·Captain: mikedeng1

Stochastic Optimal Control: The Discrete-Time Case III: Monotone Increase Models — Accumulation Points of DP-Optimal Controls Give an Optimal Stationary PolicyTextbook

Infinite-horizon dynamic programming with positive (nonnegative) costs and no discounting, or with discount factors that do not make the Bellman operator a contraction, is the setting of Blackwell's and Strauch's positive and negative programming models and of many deterministic control and reachability problems. In this regime the classical contraction…

21 thms6 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis XXIX: M2-Convex and L2-Convex FunctionsTextbook

Mission 29-ch08b-conjugacyduality opened chapter 8's account of M2-convex functions — sums of M-convex functions — proving their domains and minimizers are M2-convex and that they are integrally convex. This mission completes that program and builds its exact mirror for L2-convex functions (integer infimal convolutions of L-convex functions), the class that…

58 thms6 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research·Captain: mikedeng1

A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization II: R-Linear Convergence for Strongly Convex FunctionsResearch Paper

Line search methods for unconstrained minimization of a smooth function f:Rn→Rf : \mathbb{R}^n \to \mathbb{R}f:Rn→R choose a direction dkd_kdk​ and a step αk>0\alpha_k > 0αk​>0 and set xk+1=xk+αkdkx_{k+1} = x_k + \alpha_k d_kxk+1​=xk​+αk​dk​. Classical rules (Armijo, Wolfe) insist that every step decrease fff. For quasi-Newton and conjugate gradient directions this monotonicity requirement often forces short…

16 thms6 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·Captain: Shuze Chen

Discrete Convex Analysis XXVI: Polyhedral L-Convex FunctionsTextbook

L-convex functions were defined purely combinatorially, on the integer lattice. Chapter 6's M-convex theory showed that combinatorial definition always extends to a genuine convex function on real space (missions 23-ch06c-mconvexfunctions/24-ch06d-mconvexfunctions); this mission carries out the identical program for the L side. It first shows L♮^\natural♮-conv…

53 thms6 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems 3: Capacity Scaling for the Hitchcock ProblemResearch Paper

The Hitchcock transportation problem asks how to ship a commodity from mmm supply points to nnn demand points at minimum total cost. It was posed by Hitchcock in 1941 and is one of the founding problems of linear programming and network optimization; it is solved routinely in logistics, and its structure (a bipartite network with supplies, demands and per-unit…

12 thms6 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

Logarithmic Regret Algorithms for Online Convex Optimization 2: Logarithmic Regret of the Online Newton StepResearch Paper

Online convex optimization models repeated decision making against an unknown, possibly adversarial environment: in each round t=1,…,Tt=1,\dots,Tt=1,…,T a player picks a point xtx_txt​ of a convex set P⊆Rn\mathcal P\subseteq\mathbb R^nP⊆Rn, and only then learns a convex cost function ftf_tft​ and pays ft(xt)f_t(x_t)ft​(xt​). Performance is measured by regret, the excess of the total cost over that of…

16 thms6 active users
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Wasserstein Distributionally Robust Optimization III: Finite-Sample and Asymptotic Performance GuaranteesTextbook

A decision maker who solves a distributionally robust optimization (DRO) problem over a Wasserstein ball chooses a radius ε\varepsilonε by hand, and it is natural to ask what guarantee that choice actually buys: how large must ε\varepsilonε be, as a function of the sample size NNN and a desired confidence level, before the resulting worst-case risk is provably…

21 thms6 active users
🏆Completed
Convex OptimizationOperations Research·Captain: Shuze Chen

Convex Optimization VI: Self-Concordance and the Barrier MethodTextbook

Why do interior-point methods solve convex programs in O(mlog⁡(1/ε))O(\sqrt{m}\log(1/\varepsilon))O(m​log(1/ε)) Newton steps? Nesterov and Nemirovskii's answer is self-concordance: a convex function whose third derivative is controlled by its second, ∣φ′′′(t)∣≤2 φ′′(t)3/2|\varphi'''(t)| \le 2\,\varphi''(t)^{3/2}∣φ′′′(t)∣≤2φ′′(t)3/2 along every line, admits a Newton analysis with absolute constants and no condition number —…

20 thms6 active users
🏆Completed
Dynamic ProgrammingOperations ResearchProbability·Captain: iris

Markov Decision Processes with Applications to Finance VII: The Multiperiod Mean-Variance Problem Has an Explicit Efficient Frontier and Optimal PortfolioTextbook

Mean-variance portfolio selection, introduced by Markowitz in 1952 (and slightly earlier by de Finetti), measures the risk of a portfolio by the variance of its return: among all portfolios that reach at least a prescribed expected return, choose one of smallest variance. The single-period problem was solved in the 1950s and is still the standard tool of…

12 thms5 active usersReviewed
🏆Completed
Control TheoryDynamic ProgrammingProbability·Captain: iris

Markov Decision Processes with Applications to Finance III: The Stochastic Linear-Quadratic Problem Has Quadratic Value Functions and Linear Optimal Controls Given by a Riccati RecursionTextbook

A linear-quadratic (LQ) problem asks for a control that keeps a linear stochastic system close to zero at quadratic cost. It is the one model of sequential decision making under uncertainty with general Euclidean state and action spaces whose optimal value and optimal policy are known in closed form, which is why it serves as the reference model of control…

19 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationMachine Learning·Captain: iris

Solving Optimization Problems with Blackwell Approachability: CBA+ Has θ-Weighted Average Regret at Most 2κL(θ_T/ω_T)√(Σω_t²)/Σθ_t Whenever θ_{t+1}/θ_t ≥ ω_{t+1}/ω_tResearch Paper

Large convex–concave saddle-point problems min⁡x∈Xmax⁡y∈YF(x,y)\min_{x\in\mathcal X}\max_{y\in\mathcal Y}F(x,y)minx∈X​maxy∈Y​F(x,y) arise in matrix games, extensive-form games, distributionally robust optimization and many convex programs written in min–max form. A standard way to solve them is the repeated game framework: two regret minimizers, one per player, play against each other, and the…

24 thms5 active usersReviewed
PreviousPage 2 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