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

Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation 2: SONATA with Push-Sum Converges R-Linearly over Time-Varying Directed GraphsResearch Paper

In distributed optimization a network of mmm agents minimizes a sum of private functions while each agent talks only to its neighbours. Applications include federated and decentralized learning, sensor networks and multi-robot systems, where the data cannot be pooled at one site. Many of these networks are directed (communication links are one-way, for…

13 thms3 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationLinear algebra·Captain: mikedeng1

Quadratic Matrix Inequalities with Applications to Data-Based Control II: Matrix Finsler's Lemma — Z⁰ᵣ(N) ⊆ Zᵣ(M) iff M − αN ⪰ 0 for Some α ≥ 0Research Paper

Finsler's lemma (P. Finsler, 1937) states that for symmetric matrices M,N∈SnM,N\in\mathbb S^nM,N∈Sn, the quadratic form x⊤Mxx^\top Mxx⊤Mx is positive on every nonzero xxx with x⊤Nx=0x^\top Nx=0x⊤Nx=0 if and only if M−αN>0M-\alpha N>0M−αN>0 for some real α\alphaα. Together with the S-lemma of Yakubovich it is one of the basic tools for converting a statement about all vectors satisfying a quadratic…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

On Solving Multistage Stochastic Programs with Coherent Risk Measures: The Inner-Approximation Policy's Nested Risk-Adjusted Cost Is at Most the Upper Bound yResearch Paper

Multistage stochastic linear programs model decisions taken over time under uncertainty: reservoir releases in hydro-thermal scheduling, production and inventory plans, capacity expansion. Their standard solution method, stochastic dual dynamic programming (SDDP, Pereira and Pinto 1991), approximates each stage's cost-to-go function from below by cutting…

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

Product Price, Quality and Service Decisions under Consumer Choice Models VI: Consumer Surplus Rises as the Firm Also Controls Service Duration, and Again as It Also Controls QualityResearch Paper

A firm that sells differentiated products sets more than prices. It chooses quality levels (features, materials, reliability) and the ancillary services that come free with a product, such as a factory warranty or free maintenance for a fixed period. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.09…

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

Product Price, Quality and Service Decisions under Consumer Choice Models II: The Oligopoly Has a Unique Nash Equilibrium, with Monopoly Qualities and Service Durations and Lower PricesResearch Paper

Firms that sell durable goods set three things at once: a price, a quality level, and the length of an ancillary service that comes free with the product, such as a warranty. Wang, Ke and Cui (SSRN 3766191; Manufacturing & Service Operations Management, 2022, doi:10.1287/msom.2020.0947) study these joint decisions under multinomial logit (MNL) demand. For a…

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

Distributed Optimization Based on Gradient Tracking Revisited: Enhancing Convergence Rate via Surrogation 1: SONATA Converges R-Linearly over Undirected Graphs for Small Step SizesResearch Paper

In distributed optimization, mmm agents connected by a communication network jointly minimize the average of their private losses, exchanging vectors only with their neighbours. This is the computational model of decentralized machine learning (data held by many machines, no central server), of sensor networks and of multi-agent control. A central family of…

14 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·Captain: mikedeng1

On the tightness of SDP relaxations of QCQPs 6: For Diagonal QCQPs the SOCP and SDP Relaxations Have the Same Projected Epigraph and Optimal ValueResearch Paper

Quadratically constrained quadratic programs (QCQPs) minimize a quadratic function subject to quadratic inequality and equality constraints. They model trust-region subproblems, robust least squares, max-cut and many problems in signal processing and control. They are NP-hard in general, so practice relies on convex relaxations, and the standard one is the S…

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

On the tightness of SDP relaxations of QCQPs 2: Polyhedral Γ with 0 ∉ Proj_V(F){b(γ) : γ ∈ F} on Every Semidefinite Face Makes Every SDP Optimizer FeasibleResearch Paper

A quadratically constrained quadratic program (QCQP) minimizes a quadratic function subject to quadratic inequality and equality constraints. The class contains nonconvex problems such as max-cut, Boolean least squares, the trust-region subproblem and its generalizations, and robust least squares, and it is NP-hard in general. The standard convex approach…

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

Product Price, Quality and Service Decisions under Consumer Choice Models I: Under MNL Demand, Optimal Service Durations Are Extreme, Qualities Are Set Product by Product, and Markups Are EqualResearch Paper

Manufacturers rarely sell a bare product. A laptop, a vacuum cleaner or a car comes with an ancillary service (a factory warranty, maintenance, technical support) whose length the firm chooses together with the price and the quality of the product. The three decisions interact: a longer warranty makes a product more attractive to consumers but costs the…

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

Product Price, Quality and Service Decisions under Consumer Choice Models V: A Dealer Optimally Offers a Markup-Ordered Assortment and Attaches Long Service to an Adjusted-Markup-Ordered SetResearch Paper

Car dealers, electronics retailers and office suppliers sell products whose prices and features are set upstream by manufacturers, and bundle each product with a service of their own: maintenance, repairs or a warranty. The dealer's short-term problem is then purely combinatorial. Which products should be carried, and which of them should come with a long…

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

Product Price, Quality and Service Decisions under Consumer Choice Models IV: Under the Two-Stage Nested Logit Model, Qualities Are Set Product by Product and Markups Are Nest-InvariantResearch Paper

A firm that sells durable products with an attached service (a warranty, a maintenance plan, a support contract) chooses three things for each product: its price, its quality, and how long the service lasts. Wang, Ke and Cui (SSRN 3766191, Manufacturing & Service Operations Management, 2022) study this joint decision when consumers choose among the products…

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

On the tightness of SDP relaxations of QCQPs 1: Polyhedral Γ and Large Shared Zero Eigenspaces on Semidefinite Faces Give conv(D) = D_SDP and Opt = Opt_SDPResearch Paper

Quadratically constrained quadratic programs (QCQPs) minimize a quadratic function subject to quadratic inequality and equality constraints. They model facility location, pooling, max-cut, trust-region steps and robust optimization problems, and every {0,1}\{0,1\}{0,1} integer program can be written as one; in general they are NP-hard. The standard tractable approach…

16 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical Systems·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations IV: The High-Resolution Heavy-Ball ODE Satisfies f(X(t)) − f(x⋆) ≤ 7‖x₀ − x⋆‖² e^(−√μ t/4)/(2s)Research Paper

Polyak's heavy-ball method and Nesterov's accelerated gradient method for strongly convex functions (NAG-SC) are the two classical momentum methods of smooth convex optimization. With step size sss and momentum α=(1−μs)/(1+μs)\alpha=(1-\sqrt{\mu s})/(1+\sqrt{\mu s})α=(1−μs​)/(1+μs​) they differ only by a gradient-correction term, yet NAG-SC is accelerated for every μ\muμ-strongly convex, LLL-smo…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 6: Nesterov's Method Has ℒ_k ≤ ℒ₀·min{4L/(√γ₀k + 2√L)², (1 − √(min{γ₁, μ}/L))^k}Research Paper

Nesterov's accelerated gradient method minimises a smooth convex function fff to accuracy ε\varepsilonε in O(L/ε)O(\sqrt{L/\varepsilon})O(L/ε​) gradient evaluations, and a μ\muμ-strongly convex one in O(L/μ log⁡(1/ε))O(\sqrt{L/\mu}\,\log(1/\varepsilon))O(L/μ​log(1/ε)); both counts match the lower bounds for first-order methods. Nesterov's own analysis (Y. Nesterov, Introductory Lectures on Convex…

9 thms3 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results III: ADMM Is Douglas-Rachford Splitting on the Image-Function Problem, for Every RelaxationResearch Paper

The alternating direction method of multipliers (ADMM) solves linearly constrained problems

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 4: The Predictor–Corrector Scheme Has ℒ_k ≤ ℒ₀·min{4L/(√γ₀k + 2√L)², (1 + √(min{γ₀, μ}/L))^(−k)}Research Paper

Nesterov's accelerated gradient method minimises a smooth convex function fff to accuracy ε\varepsilonε in O(1/ε)O(1/\sqrt{\varepsilon})O(1/ε​) gradient evaluations, and a μ\muμ-strongly convex one in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)), which is optimal for first-order methods. The method's original derivation by estimate sequences gives little insight into why it…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 3: The Implicit Scheme Gives ℒ_{k+1} ≤ ℒ_k/(1 + α_k) for Every μ-Convex f and Every Step α_k > 0Research Paper

Accelerated first-order methods, beginning with Nesterov's 1983 scheme, reach the optimal iteration complexity among gradient methods for smooth convex minimization, but their classical derivations ("estimate sequences") give little insight into why acceleration works. A line of work started by Su, Boyd and Candès (arXiv:1503.01243) reads accelerated…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 5: The Gradient-Corrected Scheme Contracts ℒ_k by 1/(1 + α_k) and Has the Rate of Theorem 5.1Research Paper

Nesterov's accelerated gradient method minimises a smooth convex function fff to accuracy ε\varepsilonε in O(1/ε)O(1/\sqrt{\varepsilon})O(1/ε​) gradient evaluations, against O(1/ε)O(1/\varepsilon)O(1/ε) for plain gradient descent, and this rate is optimal for first-order methods (Nesterov 2018). The method is usually presented through estimate sequences, which certify the rate but say…

10 thms3 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results V: The Image Function (Af) Is Smooth Under Relative Smoothness, Lipschitz Minimizers, or ConvexityResearch Paper

The alternating direction method of multipliers (ADMM) solves problems of the form min⁡{f(x)+g(z)∣Ax+Bz=b}\min\{f(x)+g(z)\mid Ax+Bz=b\}min{f(x)+g(z)∣Ax+Bz=b} and is a standard tool in signal processing, statistics and distributed optimization (Boyd et al., 2011). For convex problems ADMM is known to be the Douglas–Rachford splitting (DRS) applied to a dual problem. Themelis and Patrinos (arXiv:1709.057…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical SystemsNumerical Analysis·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 2: The NAG Flow Has a Unique C² Solution and Its Lyapunov Function Satisfies ℒ(t) ≤ e^(−t)ℒ(0)Research Paper

Accelerated first-order methods, above all Nesterov's accelerated gradient (NAG) method, minimize a convex function with an LLL-Lipschitz gradient to accuracy ε\varepsilonε in O(L/ε)O(\sqrt{L/\varepsilon})O(L/ε​) gradient evaluations, and a μ\muμ-strongly convex one in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)), against O(L/ε)O(L/\varepsilon)O(L/ε) and O((L/μ)log⁡(1/ε))O((L/\mu)\log(1/\varepsilon))O((L/μ)log(1/ε)) for gradient…

11 thms3 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Douglas-Rachford Splitting and ADMM for Nonconvex Optimization: Tight Convergence Results II: No Stepsize Above 1/L Guarantees a Vanishing DRS ResidualResearch Paper

Douglas–Rachford splitting (DRS) minimizes a sum φ1+φ2\varphi_1+\varphi_2φ1​+φ2​ by alternating between the proximal mappings of the two terms. It is one of the most used first-order methods in signal processing, statistics and control, and, through its dual interpretation, it is the engine behind the alternating direction method of multipliers (ADMM). For convex…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationDynamical Systems·Captain: mikedeng1

Understanding the Acceleration Phenomenon via High-Resolution Differential Equations III: The High-Resolution ODE of NAG-SC Satisfies f(X(t)) − f(x⋆) ≤ 2‖x₀ − x⋆‖² e^(−√μ t/4)/sResearch Paper

Nesterov's accelerated gradient method for μ\muμ-strongly convex, LLL-smooth functions (NAG-SC) reaches accuracy ε\varepsilonε in O(L/μlog⁡(1/ε))O(\sqrt{L/\mu}\log(1/\varepsilon))O(L/μ​log(1/ε)) gradient steps, against O((L/μ)log⁡(1/ε))O((L/\mu)\log(1/\varepsilon))O((L/μ)log(1/ε)) for gradient descent (Nesterov, 1983; Nesterov, 2004). Polyak's heavy-ball method has the same accelerated behaviour on quadratics but not in…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 1: Gauss–Seidel Splitting of the HB and NAG Transforms Has ρ(E(α, G)) ≤ 1/√(1 + 2α) If 0 < α ≤ 2/√κ(A)Research Paper

Accelerated first-order methods, the heavy-ball method of Polyak and Nesterov's accelerated gradient (NAG) method, reach an error ε\varepsilonε on a μ\muμ-strongly convex, LLL-smooth problem in O(κlog⁡(1/ε))O(\sqrt{\kappa}\log(1/\varepsilon))O(κ​log(1/ε)) gradient steps, κ=L/μ\kappa=L/\muκ=L/μ, against O(κlog⁡(1/ε))O(\kappa\log(1/\varepsilon))O(κlog(1/ε)) for plain gradient descent. A long line of work has tried to explain…

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

Operator Splitting for a Homogeneous Embedding of the Linear Complementarity Problem: The Embedding Operator Q = F ∪ I of a Monotone LCP Is Maximal MonotoneResearch Paper

Many problems in optimization reduce to a linear complementarity problem over a cone: convex quadratic programs, linear and second-order cone programs, and more generally the KKT systems of convex quadratic cone programs (QCPs). First-order solvers for these problems, such as SCS (O'Donoghue–Chu–Parikh–Boyd 2016), must return either a solution or a…

10 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

From Differential Equation Solvers to Accelerated First-Order Methods for Convex Optimization 8: Semi-AFB for min over Q of h + g Contracts ℒ_k by 1/(1 + α_k) and Has the Rate of Theorem 5.1Research Paper

Many convex problems in signal processing, statistics and control have the composite form "smooth loss plus nonsmooth regulariser, subject to a simple constraint": a least-squares or entropy term hhh, a sparsity or total-variation penalty ggg, and a feasible set QQQ such as a box, a simplex or a cone. Accelerated proximal gradient methods (FISTA, Beck and…

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