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

Adaptive Cubic Regularisation Methods for Unconstrained Optimization. Part II: Worst-Case Function- and Derivative-Evaluation Complexity 1: Basic ARC Reaches ‖g‖ ≤ ε in O(ε^(−2)) IterationsResearch Paper

Methods for smooth unconstrained minimization, min⁡x∈Rnf(x)\min_{x\in\mathbb R^n} f(x)minx∈Rn​f(x), are compared by how many evaluations of fff and of its gradient they need, in the worst case, to reach an approximately first-order critical point, an iterate with ∥∇f(xk)∥≤ϵ\|\nabla f(x_k)\|\le\epsilon∥∇f(xk​)∥≤ϵ. For steepest descent with a Lipschitz gradient the answer is O(ϵ−2)O(\epsilon^{-2})O(ϵ−2) (Nesterov, Int…

13 thms3 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

On the Complexity of Nash Equilibria and Other Fixed Points 1: ε-Nash Equilibria Are Weak (n+1)ε-Fixed Points of Nash's Function, and Weak ε²/(4c²n³)-Fixed Points Are ε-Nash EquilibriaResearch Paper

Nash proved that every finite game has an equilibrium by exhibiting a continuous map of the set of mixed profiles into itself whose fixed points are exactly the equilibria, and applying Brouwer's fixed point theorem (Nash, 1951). Computationally, the same map is the bridge between games and fixed-point problems: complexity classes for total search problems…

11 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations Research·Captain: mikedeng1

Variable Metric Method for Minimization: Davidon's Rank-One Variable-Metric Update Recovers the Inverse Hessian of a Quadratic in N Steps and Then Steps to the Exact MinimumResearch Paper

Quasi-Newton methods minimize a smooth function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R using gradients only, while building up an approximation to the inverse of the Hessian matrix from the changes of gradient they observe. They are the default algorithms of unconstrained nonlinear optimization: BFGS and its limited-memory variant L-BFGS sit inside most numerical…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOperations Research·Captain: mikedeng1

Incremental Proximal Methods for Large Scale Convex Optimization I: With a Cyclic Order and a Diminishing Stepsize, Incremental Subgradient-Proximal Methods Converge to an Optimal SolutionResearch Paper

Many optimization problems in machine learning, signal processing and distributed computation have an objective that is a sum of a large number mmm of component functions: one per data point, per sensor, or per processor. Evaluating the whole sum, or a subgradient of it, at every iteration is expensive when mmm is large. Incremental methods process one…

10 thms3 active usersReviewed
🏆Completed
Analysis·Captain: mikedeng1

Semismooth and Semiconvex Functions in Constrained Optimization I: The Pointwise Maximum or Minimum over a Compact Family of Continuously Differentiable Functions Is SemismoothResearch Paper

Many objective functions in engineering design, Chebyshev approximation and game-theoretic planning are extremal-valued: they are the pointwise maximum or minimum of a family of smooth functions, E(x)=max⁡u∈Uf(x,u)E(x)=\max_{u\in U} f(x,u)E(x)=maxu∈U​f(x,u). Such a function is typically not differentiable at points where two or more members of the family are active, so gradient methods do not…

16 thms3 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Retail Assortment Planning in the Presence of Consumer Search V: The Heuristic Equilibrium of No-Search Assortment Planning Is Never Deeper Than OptimalResearch Paper

Retailers decide which product variants to stock, and most assortment-planning tools model consumer choice with the multinomial logit (MNL) model: a consumer who does not find an acceptable variant simply leaves without buying. Cachon, Terwiesch and Xu (Retail Assortment Planning in the Presence of Consumer Search, working paper of December 2002; published…

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

Retail Assortment Planning in the Presence of Consumer Search III: Under Independent-Assortment Search, the Profit Change from Adding a Variant Is Quasi-Convex in Its PreferenceResearch Paper

A retailer deciding which variants of a product to stock trades off two effects. A deeper assortment captures consumers whose favourite variant would otherwise be missing, but it splits demand among more variants, each of which then carries its operational costs (shelf space, handling, inventory) at a smaller, less efficient scale. Van Ryzin and Mahajan (Man…

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

Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications: With Fixed Pick-up Times, the Offline Taxi Routing MIO Formulation (5)-(14) Is IntegralResearch Paper

Taxi fleets, ride-hailing services and dial-a-ride systems assign incoming customer requests to vehicles under time constraints. Bertsimas, Jaillet and Martin (Online Vehicle Routing: The Edge of Optimization in Large-Scale Applications, Operations Research 67(1), 2019) model the online taxi routing problem, a special case of the online dial-a-ride problem…

5 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingReinforcement Learning·Captain: mikedeng1

Global Optimality Guarantees for Policy Gradient Methods 2: Under Closure, a (c, µ)-Gradient-Dominated Policy Iteration Objective Makes ℓ (κc/(1−γ), κµ/(1−γ))-Gradient DominatedResearch Paper

Policy gradient methods optimize a parameterized control policy by gradient descent on its long-run cost. They underlie much of modern reinforcement learning, from REINFORCE and actor-critic methods to trust-region and proximal policy optimization, and they are used in operations problems such as inventory control and optimal stopping. Their objective is…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Supplier Centrality and Auditing Priority in Socially Responsible Supply Chains II: A Stable Joint-Auditing Coalition Audits the Common Supplier and Shares Costs FairlyResearch Paper

Brands that sell consumer goods are held responsible by the public for the labour and safety practices of their suppliers. After the 2013 Rana Plaza collapse in Bangladesh, about 200 clothing brands and retailers signed the Accord on Fire and Building Safety and inspect roughly 1,600 factories jointly; pharmaceutical companies such as Pfizer and GSK audit…

10 thms3 active usersReviewed
🏆Completed
Machine LearningOptimal Transport·Captain: mikedeng1

Computational Optimal Transport XII: The Entropic Barycenter Scalings Are (e^{f_s/ε}, e^{g_s/ε}) for the Solutions of a Dual Program with Σ_s λ_s f_s = 0Textbook

A barycenter summarizes several objects by minimizing a weighted sum of distances to them. For probability histograms, ordinary coordinatewise averages depend strongly on how the bins are labeled. Optimal transport instead lets mass move between bins and charges for those moves through a cost matrix. The resulting Wasserstein barycenter can reflect the…

6 thms3 active usersReviewed
🏆Completed
Information TheoryMachine LearningOptimal Transport·Captain: mikedeng1

Computational Optimal Transport IX: The Entropic Cost L^ε_C(a, b) Equals max ⟨f, a⟩ + ⟨g, b⟩ − ε⟨e^{f/ε}, K e^{g/ε}⟩, with Optimal Scalings (e^{f/ε}, e^{g/ε})Textbook

Optimal transport compares two distributions by finding the least expensive way to move mass between them. For finite histograms, the resulting linear program is precise but its optimal coupling can be sparse. In applications where the coupling represents traffic, matching, or a differentiable loss, a sparse plan may be undesirable or expensive to compute…

9 thms3 active users
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Supplier Centrality and Auditing Priority in Socially Responsible Supply Chains I: Under Downstream Competition No Buyer Audits the Common Supplier in Any EquilibriumResearch Paper

Brands are routinely held responsible for the labour and environmental practices of their suppliers. A brand that is linked in public to a non-compliant supplier loses consumer willingness to pay, and firms answer this risk by auditing their suppliers. Supply networks are not trees, however: one supplier often serves several competing brands. Chen, Qi and…

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

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 5: Dual Bounds from Active-Set Primal Solutions Lose Only O(kε), Independent of pResearch Paper

Best-subset selection with ridge shrinkage, min⁡β12∥y−Xβ∥22+λ0∥β∥0+λ2∥β∥22\min_\beta \tfrac12\|y-X\beta\|_2^2+\lambda_0\|\beta\|_0+\lambda_2\|\beta\|_2^2minβ​21​∥y−Xβ∥22​+λ0​∥β∥0​+λ2​∥β∥22​, is a mixed-integer program that statisticians want to solve to certified optimality at the scale of modern data (ppp up to 10710^7107 features). Hazimeh, Mazumder and Saab (arXiv:2004.06152, Mathematical Programming 2022) built a…

18 thms3 active usersReviewed
🏆Completed
Information TheoryMachine LearningOptimal Transport·Captain: mikedeng1

Computational Optimal Transport VII: The Entropic Optimal Coupling P_ε Tends to the Maximum-Entropy Optimal Plan as ε → 0 and to a ⊗ b as ε → ∞Textbook

The discrete optimal transport problem of Kantorovich asks for the cheapest way to move a probability histogram a\mathbf aa onto a histogram b\mathbf bb when moving a unit of mass from iii to jjj costs Ci,j\mathbf C_{i,j}Ci,j​. Its optimal couplings are vertices of a polytope and are typically sparse: they rely on a few routes. Two communities have reasons to blur them. In…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical SystemsFunctional Analysis+1·Captain: mikedeng1

Tikhonov Regularization of a Second Order Dynamical System with Hessian Driven Damping 3: If ∫ ε(t)/t dt = +∞, the Trajectory Converges Strongly in the Ergodic Sense to the Minimum-Norm MinimizerResearch Paper

Second order dynamical systems with vanishing damping are continuous-time models of accelerated first-order methods. The system x¨+αtx˙+∇g(x)=0\ddot x + \frac{\alpha}{t}\dot x + \nabla g(x) = 0x¨+tα​x˙+∇g(x)=0 is the continuous limit of Nesterov's accelerated gradient method (Su, Boyd, Candès 2016), and its trajectories converge weakly to a minimizer of a convex ggg when α>3\alpha>3α>3 (Attouch,…

8 thms3 active usersReviewed
🏆Completed
Captain: mikedeng1

A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization III: Every Limit Point of BSCA with Armijo Steps Is a Stationary PointResearch Paper

Large optimization models often split their variables into blocks that can be handled separately. A method can then solve one smaller approximation problem per iteration instead of the full problem. The block successive convex approximation (BSCA) method of Razaviyayn, Hong and Luo allows the block approximation to guide the search without requiring it to…

9 thms3 active usersReviewed
🏆Completed
Captain: mikedeng1

A Unified Convergence Analysis of Block Successive Minimization Methods for Nonsmooth Optimization II: Limit Points of Cyclic BSUM with Unique Block Minimizers Are Coordinatewise StationaryResearch Paper

Many large optimization problems in signal processing, statistics and machine learning have a variable that splits naturally into blocks, and are solved by updating one block at a time. The classical method of this kind, block coordinate descent (BCD), minimises the objective exactly in one block while the others are held fixed. In practice the exact block…

8 thms3 active usersReviewed
🏆Completed
Convex Optimization·Captain: mikedeng1

Faster Convergence Rates of Relaxed Peaceman-Rachford and ADMM Under Regularity Assumptions III: With Lipschitz ∇g and Small Stepsize, the DRS Objective Error Is O(1/(k+1)) and o(1/(k+1))Research Paper

Douglas–Rachford splitting is a method for minimizing a sum of two convex functions when each function has an accessible proximal operator. Its iterates are easy to state, but the speed of convergence of the objective at an individual proximal point is less immediate than convergence of an averaged point or of a residual. For optimization models in which…

12 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Quality in Supply Chain Encroachment I: With Endogenous Uniform Quality, an Encroaching Manufacturer Gains and the Retailer Always LosesResearch Paper

Manufacturers increasingly sell directly to consumers through their own stores and websites, alongside the independent retailers that carry their products. This practice is called supply chain encroachment. Retailers routinely resent it, and examples range from beer brewers to personal computers. Arya, Mittendorf and Sappington (Marketing Science, 2007)…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchStatistics·Captain: mikedeng1

Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization 4: Lagrangian Duals of the Reduced Relaxation and Their Closed-Form Optimal Dual VariablesResearch Paper

Best subset selection with ridge shrinkage, the ℓ0ℓ2\ell_0\ell_2ℓ0​ℓ2​-regularized least squares problem

9 thms3 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

Approximation Algorithms for Product Framing and Pricing 3: Under MNL Pricing, Optimal Framing Fills Pages in Descending Quality Order with One Price per PageResearch Paper

Online retailers show their catalogue on a sequence of pages, and most visitors never reach the last one. Which products appear on the first page, and at what prices, therefore decides what a typical consumer can buy at all. Gallego, Li, Truong and Wang (Operations Research, 2020) model this as the product framing problem: the consideration set of a…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical SystemsFunctional Analysis+1·Captain: mikedeng1

Tikhonov Regularization of a Second Order Dynamical System with Hessian Driven Damping 1: For α > 3 and ∫ tε(t) dt < +∞ the Trajectory Converges Weakly to a Minimizer of gResearch Paper

Minimizing a convex function ggg on a real Hilbert space H\mathcal HH by first-order methods has a continuous-time counterpart: second-order differential equations whose trajectories descend ggg. Su, Boyd and Candès (20) showed that Nesterov's accelerated gradient method is a discretization of x¨+αtx˙+∇g(x)=0\ddot x+\frac{\alpha}{t}\dot x+\nabla g(x)=0x¨+tα​x˙+∇g(x)=0 with α=3\alpha=3α=3, along…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical SystemsFunctional Analysis+1·Captain: mikedeng1

Tikhonov Regularization of a Second Order Dynamical System with Hessian Driven Damping 2: lim inf ‖x(t) − x*‖ = 0 at the Minimum-Norm Minimizer, and x(t) → x* If x(t) Ends In or Out of B(0, ‖x*‖)Research Paper

Many methods for minimizing a smooth convex function ggg on a Hilbert space can be read as discretizations of second order ordinary differential equations, and the asymptotic behaviour of the continuous trajectories predicts the behaviour of the iterates. The inertial system with vanishing damping x¨+αtx˙+∇g(x)=0\ddot x+\frac{\alpha}{t}\dot x+\nabla g(x)=0x¨+tα​x˙+∇g(x)=0 is the continuous…

7 thms3 active usersReviewed
🏆Completed
Convex Optimization·Captain: mikedeng1

The Direct Extension of ADMM for Multi-block Convex Minimization Problems is Not Necessarily Convergent III: With a Strongly Convex Objective and β = 1 the Extended ADMM Can Still DivergeResearch Paper

The alternating direction method of multipliers (ADMM) is a standard method for convex problems whose objective splits into two blocks coupled by a linear constraint (Gabay & Mercier 1976; Boyd et al. 2011). Many models in imaging, statistics and sparse or low-rank recovery have three or more blocks, and the scheme practitioners reach for first is the direct…

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