Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Numerical Analysis

254 missions · 180 completed

Missions

Open74Completed180All254
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Minimization Methods for Non-Differentiable Functions VII: Geometric Convergence of Subgradient Methods with Space Dilation along the GradientTextbook

The subgradient method for a nonsmooth convex function converges, but slowly: when the level sets of the objective are elongated, the subgradient is nearly orthogonal to the direction towards the minimum, and the method zigzags. For smooth functions the remedy is a change of metric (Newton and quasi-Newton methods); for nonsmooth functions no Hessian exists…

17 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Pattern Search Algorithms for Bound Constrained Minimization: Generalized Pattern Search Drives the Projected Stationarity Measure to ZeroResearch Paper

Pattern search methods minimize a function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R by comparing values of fff at points of a structured set of trial points, without evaluating or approximating derivatives. Coordinate search and the method of Hooke and Jeeves (Hooke–Jeeves 1961) are the classical members of the family. Such methods remain in use when derivatives are…

21 thms4 active users
🏆Completed
Convex OptimizationLinear algebraOperations Research+1·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data III: Structured Robust Least Squares Is Solved Exactly by a Semidefinite ProgramResearch Paper

Least squares fits a model Ax≈bAx \approx bAx≈b as if the data (A,b)(A, b)(A,b) were exact. In practice they are measured, rounded or estimated, and the least-squares solution can be very sensitive to such errors. El Ghaoui and Lebret (SIAM J. Matrix Anal. Appl. 18(4), 1997) proposed to treat the errors as deterministic, unknown but bounded, and to choose xxx minimizing the wor…

14 thms4 active users
🏆Completed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Nonsmooth Version of Newton's Method II: global convergence of the generalized-Jacobian Newton method on a ball, with an error estimateResearch Paper

Many problems in optimization and equilibrium modelling reduce to a system of equations F(x)=0F(x) = 0F(x)=0 with F:Rn→RnF : \mathbb{R}^n \to \mathbb{R}^nF:Rn→Rn that is continuous and locally Lipschitz but not differentiable. Complementarity problems rewritten through the min or Fischer–Burmeister functions, Karush–Kuhn–Tucker systems of nonlinear programs, and the gradients of…

11 thms4 active usersReviewed
🏆Completed
Optimization·Captain: iris

Error Analysis of Surrogate Models Constructed through Operations on Sub-models: a product of nnn models exact at x0x_0x0​ has Hessian accuracy of order min⁡{Nig,Nih}\min\{N^g_i,N^h_i\}min{Nig​,Nih​} with constant KFh(x0)K^h_F(x_0)KFh​(x0​)Research Paper

In derivative-free and blackbox optimization, the objective can often be evaluated but not differentiated, and algorithms work with surrogate models built from function values. Their convergence theory depends on how accurate those models are. Conn, Scheinberg and Vicente codified this through fully linear and fully quadratic models; a fully linear class…

17 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchProbability·Captain: mikedeng1

Fast Hybrid Schemes for Fractional Riccati Equations (Rough Is Not So Tough): Explicit Lower and Upper Bounds on the Convergence Radius of the Fractional Power-Series SolutionResearch Paper

In the rough Heston model of El Euch and Rosenbaum, the variance of an asset is driven by a fractional kernel with Hurst exponent H<12H<\tfrac12H<21​, which matches the roughness observed in realized volatility. The model keeps one feature of the classical Heston model: the characteristic function of the log-price is explicit up to the solution of a deterministic…

13 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A First-Order Primal-Dual Method for Nonconvex Constrained Optimization Based on the Augmented Lagrangian 1: NAPP-AL Drives the Best Stationarity Residual to Zero at Rate o(1/√k)Research Paper

Many models in statistics, machine learning and engineering are nonconvex, nonsmooth and coupled by constraints: a sparsity penalty such as SCAD, MCP or capped-ℓ1\ell_1ℓ1​ on one block of variables, a smooth loss coupling the blocks, and a nonlinear equality constraint tying them together. Augmented-Lagrangian methods and ADMM-type splittings are the workhorses…

9 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Markov Decision Processes with Observation Costs: Framework and Computation with a Penalty Scheme: The Quasi-Variational Inequality with Inspection Operator Has a Unique Bounded SolutionResearch Paper

In many sequential decision problems the state of a system is not observed for free. A controller monitoring a machine, a patient or an inventory must pay to inspect it, and between inspections it acts on a belief rather than on the state. The observation cost model (OCM) makes this precise for a finite Markov chain: at each time the controller either pays…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·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
Optimization·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 OptimizationOptimization·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 OptimizationOptimization·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 OptimizationOptimization·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
Optimization·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 SystemsOptimization·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
Optimization·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 OptimizationLinear algebraOptimization·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 OptimizationOptimization·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
🏆Completed
ProbabilityRandom Matrix Theory·Captain: tc

Gaussian Random Matrices II: Inverse Moments of the PseudoinverseTextbook

The expected error of the randomized SVD with a k×(k+p)k\times(k+p)k×(k+p) Gaussian test matrix is (1+kp−1)1/2\bigl(1+\tfrac{k}{p-1}\bigr)^{1/2}(1+p−1k​)1/2 times the optimal error (Halko–Martinsson–Tropp 2011, Theorem 10.5). The factor kp−1\tfrac{k}{p-1}p−1k​ is E∥G†∥F2\mathbb E\|G^{\dagger}\|_F^2E∥G†∥F2​ for a k×(k+p)k\times(k+p)k×(k+p) standard Gaussian matrix GGG: the quality of every Gaussian sketching method is governed by inve…

19 thms3 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity 5: The Three-Operator Forward-Reflected-Backward Method Converges Weakly to a Zero of A + B + CResearch Paper

Many problems in convex optimization and variational analysis have the form of a monotone inclusion with three pieces of structure: a nonsmooth part that is only accessible through its resolvent (a subdifferential of a proximable function, or a normal cone of a constraint set), a smooth convex part whose gradient is Lipschitz, and a monotone but…

7 thms3 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity 2: For Strongly Monotone A the Forward-Reflected-Backward Method Converges R-Linearly to the Unique ZeroResearch Paper

Many problems in optimization, variational inequalities and saddle-point problems reduce to a monotone inclusion: find xxx in a real Hilbert space HHH with

10 thms3 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Forward-Backward Splitting Method for Monotone Inclusions Without Cocoercivity 4: The Relaxed Inertial Forward-Reflected-Backward Method Converges Weakly to a Zero of A + BResearch Paper

Many problems in optimization, game theory and partial differential equations reduce to a monotone inclusion: find xxx in a real Hilbert space HHH with 0∈(A+B)(x)0\in(A+B)(x)0∈(A+B)(x), where AAA is a maximally monotone set-valued operator with an easily computed resolvent and BBB is a single-valued monotone operator. Saddle-point problems, variational inequalities and composite…

11 thms3 active usersReviewed
🏆Completed
Linear algebraOptimization·Captain: mikedeng1

Optimization-Based Algorithms for Tensor Decompositions: Canonical Polyadic Decomposition, Decomposition in Rank-(Lr, Lr, 1) Terms, and a New Generalization 1: Block Structure of the Gramian JᴴJResearch Paper

Tensor decompositions express a multiway array as a sum of simple terms. The canonical polyadic decomposition (CPD) writes an NNN-th order tensor T∈CI1×⋯×IN\mathcal T\in\mathbb C^{I_1\times\cdots\times I_N}T∈CI1​×⋯×IN​ as a sum of RRR outer products of vectors; block term decompositions replace each rank-one term by a term of higher multilinear rank. These models are used in signal…

7 thms3 active usersReviewed
🏆Completed
Linear algebraProbabilityRandom Matrix Theory·Captain: mikedeng1

An Introduction to Matrix Concentration Inequalities II: A Random Row-and-Column Submatrix Z = PBR Satisfies E‖Z‖² ≤ 3(p/d)(r/n)‖B‖² Plus Logarithmic Row, Column and Entry TermsTextbook

Large matrices are often reduced by retaining only some rows or columns. The reduced matrix is cheaper to store and apply, but its spectral norm can be distorted by a single unusually large row, column, or entry. A useful estimate must show both the average effect of sampling and the cost of these local concentrations. In §5.2 of Tropp's monograph, matrix…

11 thms3 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

A Differential Equation for Modeling Nesterov's Accelerated Gradient Method: Theory and Insights III: The Generalized Nesterov Scheme Has f(x_k) − f⋆ ≤ (r − 1)²‖x₀ − x⋆‖²/(2s(k + r − 2)²)Research Paper

Nesterov's accelerated gradient method minimizes a smooth convex function with an error of order 1/k21/k^21/k2 after kkk steps, against 1/k1/k1/k for plain gradient descent, and this rate is optimal among first-order methods. Its momentum coefficient (k−1)/(k+2)(k-1)/(k+2)(k−1)/(k+2) has long been regarded as delicate. Su, Boyd and Candès (arXiv:1503.01243, J. Mach. Learn. Res. 17(153), 2016)…

9 thms3 active usersReviewed
PreviousPage 2 of 8Next

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