Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Convex Optimization

746 missions · 569 completed

Missions

Open177Completed569All746
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers V: Sharing ADMM — the z-Update Reduces to One n-Variable Problem and the Dual Variables AgreeTextbook

Many large optimization problems arising in statistics, machine learning, signal processing and resource allocation have an objective that is a sum of terms, each depending on data held by a different processor, or a coupling term that depends on the sum of the agents' decisions. Chapter 7 of Boyd, Parikh, Chu, Peleato and Eckstein's monograph on the alterna…

11 thms2 active usersReviewed
🏆Completed
Discrete GeometryLinear Optimization·Captain: mikedeng1

Integer Programming with a Fixed Number of Variables 2: A Simplex Satisfying (16) Rounds K, B(p,r) ⊂ τK ⊂ B(p,R) with R/r ≤ 2n^(3/2)Research Paper

In 1983 H. W. Lenstra, Jr. proved that integer linear programming with a fixed number of variables is solvable in polynomial time (Lenstra 1983). The algorithm became one of the founding results of algorithmic geometry of numbers: it introduced the strategy of making a convex body "round" by a linear change of coordinates, and then either finding a lattice…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Numerically Stable Dual Method for Solving Strictly Convex Quadratic Programs: The Dual Algorithm Solves the QP or Detects Its Infeasibility in Finitely Many StepsResearch Paper

Strictly convex quadratic programs — minimize a positive definite quadratic subject to linear inequalities — are the subproblems solved at every iteration of successive quadratic programming (SQP) methods for nonlinear optimization, and they arise directly in least-squares estimation with constraints, portfolio selection and model predictive control. In SQP…

9 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers III: Parallel Projections — the Dual Average Vanishes and ADMM Reduces to Project-and-AverageTextbook

Many feasibility problems ask for a point satisfying several constraints at once. When each constraint set admits a manageable Euclidean projection, a parallel method can project onto all sets independently and combine the results. Chapter 5 of Boyd, Parikh, Chu, Peleato and Eckstein (2011) places this construction inside the alternating direction method of…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers I: Under a Lagrangian Saddle Point, ADMM Residuals Vanish and Objective Values ConvergeTextbook

The alternating direction method of multipliers (ADMM) is one of the most widely used algorithms for large-scale convex optimization in statistics, machine learning and signal processing. Its appeal is decomposition: a problem whose objective splits into two parts, coupled only by a linear constraint, is solved by alternately minimizing over each part and…

13 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Projected Newton Methods for Optimization Problems with Simple Constraints: The Projected Newton Method Converges Superlinearly to the Minimum of a Convex Function over the Nonnegative OrthantResearch Paper

Smooth optimization with nonnegative variables appears when the variables are Lagrange multipliers for inequality constraints or when an objective incorporates an augmented Lagrangian or an exact penalty. Bertsekas studies how to retain a Newton-like convergence rate in this setting while using an iteration that projects a scaled gradient step onto the…

9 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity XIII: Newton's Method Converges Quadratically, ‖x_{k+1} − x*‖ ≤ (M/μ)‖x_k − x*‖², from ‖x₀ − x*‖ ≤ μ/(2M)Textbook

Newton's method is the basic second-order method of continuous optimization: at the current point it replaces the objective by its second-order Taylor model and jumps to the stationary point of that model. Its defining property is speed near a nondegenerate minimum, where the error is squared at every step, so that the number of correct digits roughly…

6 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity VII: Conditional Gradient Descent (Frank–Wolfe) with γ_s = 2/(s + 1) Has Rate 2βR²/(t + 1) in Any NormTextbook

Many constrained optimization problems in machine learning and statistics have a feasible set X\mathcal XX over which a linear function is cheap to minimize but a Euclidean projection is expensive: the ℓ1\ell_1ℓ1​-ball, the simplex, the nuclear-norm ball, the convex hull of a combinatorial family. Projected gradient descent needs a projection at every step. Conditi…

6 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity VI: Gradient Descent with η = 2/(α + β) on a β-Smooth α-Strongly Convex Function Has Rate (β/2)exp(−4t/(κ + 1))‖x₁ − x*‖²Textbook

Gradient descent is a basic method for minimizing a differentiable function when evaluating its gradient is practical but solving the optimization problem directly is not. The rate at which its iterates approach an optimizer depends on the assumptions about the function. For a convex function with a Lipschitz gradient, the value error decreases at a…

9 thms2 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity IV: Gradient Descent on a Convex β-Smooth Function Has Rate 2β‖x₁ − x*‖²/(t − 1)Textbook

Gradient descent goes back to Cauchy (1847). It is the simplest method for minimizing a differentiable function, and most of the first-order methods in large-scale optimization and machine learning are variants of it. Its appeal in high dimension is that its oracle complexity, the number of gradient evaluations needed to reach a given accuracy, can be…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming 4: The Primal-Dual Relaxation Solves the Inequality ProgramResearch Paper

Many large convex programs have far more constraints than can be handled at once, but each constraint on its own is simple: a single linear equation or inequality. Row-action methods exploit this by touching one constraint per iteration. L. M. Bregman's 1967 paper (DOI 10.1016/0041-5553(67)90040-7) introduced the general framework behind most of them. A…

9 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

Online Convex Optimization in the Bandit Setting: Gradient Descent without a Gradient: Bandit Gradient Descent Has Expected Regret ≤ 3Cn^{5/6}∛(12dR/r)Research Paper

In online convex optimization a decision maker picks points x1,x2,…,xnx_1,x_2,\dots,x_nx1​,x2​,…,xn​ in a convex set S⊆RdS\subseteq\mathbb R^dS⊆Rd, and after each choice pays ct(xt)c_t(x_t)ct​(xt​) for a convex cost function ctc_tct​ chosen in advance by an adversary. Performance is measured by regret: the total cost paid minus the cost of the best fixed point in hindsight. Zinkevich (ICML 2003) showed…

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

Robust Solutions of Uncertain Linear Programs I: Under Constraint-wise Uncertainty and the Boundedness Assumption the Robust Counterpart Is No Worse Than the Worst InstanceResearch Paper

A linear program is solved with data that, in practice, is rarely known exactly: coefficients come from measurements, estimates or forecasts. Robust optimization asks for a solution that remains feasible for every realization of the data in a prescribed uncertainty set, and among those the one with the best guaranteed objective value. Ben-Tal and Nemirovski…

9 thms2 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms II: With F = 0, Iterates Converge Weakly to a Primal–Dual Solution When στ‖L‖² < 1Research Paper

Many problems in imaging, signal processing and statistics are convex minimizations of the form

16 thms2 active usersReviewed
🏆Completed
Functional AnalysisOptimization·Captain: mikedeng1

A Primal–Dual Splitting Method for Convex Optimization Involving Lipschitzian, Proximable and Linear Composite Terms III: In Finite Dimension with F = 0, Iterates Converge When στ‖L‖² ≤ 1Research Paper

Many problems in imaging, signal processing and statistics take the form

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

The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming 3: A Convergent Relaxation from Z Solves the Equality ProgramResearch Paper

Many large convex programs have the form "minimize a strictly convex function fff subject to linear equations Ax=bAx=bAx=b". Examples are entropy maximization under moment constraints, the estimation of a matrix with prescribed row and column sums (the matrix-scaling or RAS problem of transportation and input–output analysis), and least-norm solutions of linear…

6 thms2 active usersReviewed
🏆Completed
Numerical AnalysisPartial Differential Equations·Captain: mikedeng1

Mean Field Games: Numerical Methods for the Planning Problem II: Solutions of the Penalized Scheme Converge to a Solution of the Discrete Planning Scheme as ε → 0Research Paper

Mean field games (MFG), introduced by Lasry and Lions and by Huang, Caines and Malhamé, describe Nash equilibria of very large populations of identical rational agents. The equilibrium is a coupled system: a backward Hamilton–Jacobi–Bellman equation for the value function uuu of a representative agent and a forward Fokker–Planck equation for the density mmm of…

11 thms2 active usersReviewed
🏆Completed
AnalysisOperations ResearchOptimization·Captain: mikedeng1

The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems II: The Łojasiewicz Inequality for Convex Subanalytic Functions on Bounded SetsResearch Paper

The Łojasiewicz inequality states that near a critical point aaa of a real-analytic function fff there are θ∈[0,1)\theta\in[0,1)θ∈[0,1) and CCC with ∣f(x)−f(a)∣θ≤C ∥∇f(x)∥|f(x)-f(a)|^{\theta}\le C\,\|\nabla f(x)\|∣f(x)−f(a)∣θ≤C∥∇f(x)∥. Łojasiewicz used it in the 1960s to prove that every bounded trajectory of the gradient flow x˙=−∇f(x)\dot x=-\nabla f(x)x˙=−∇f(x) has finite length and converges to a single critical point, a conclusion…

21 thms2 active usersReviewed
🏆Completed
Linear OptimizationStatistics·Captain: mikedeng1

Conditional Logit Analysis of Qualitative Choice Behavior 4: Existence of the Maximum Likelihood Estimate Is Decided by a Quadratic ProgramResearch Paper

The conditional logit model assigns probabilities to choices among alternatives whose observable attributes differ from trial to trial. A fitted parameter vector is usually obtained by maximizing a log-likelihood. For a finite data set, however, maximization need not produce a finite vector: some directions in parameter space can keep improving the…

5 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningOptimization·Captain: mikedeng1

Blackwell Approachability and No-Regret Learning are Equivalent 2: A No-Regret Algorithm and a Valid Halfspace Oracle Approach a Compact Convex Set at Rate 2·Regret_T/TResearch Paper

Blackwell approachability is the vector-payoff analogue of von Neumann's minimax theorem. In a repeated game where each round's outcome is a vector u(xt,yt)∈Rdu(x_t, y_t) \in \mathbb R^du(xt​,yt​)∈Rd, a player wants the running average of these vectors to converge to a target set SSS, whatever the opponent does. Blackwell (1956) showed when this is possible, and approachability has…

6 thms2 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

A Nonlinear Programming Algorithm for Solving Semidefinite Programs via Low-rank Factorization: A Regular Local Minimum That Stays Locally Minimal After Adding a Zero Column Solves the SDPResearch Paper

Semidefinite programs (SDPs) arise as convex relaxations of combinatorial problems such as maximum cut and the Lovász theta function, and in control and eigenvalue optimization. Interior-point methods solve them reliably but manipulate dense n×nn\times nn×n matrices, which limits the size of the instances they can handle. Burer and Monteiro (Math. Program. 95…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Project Scheduling with Time Windows and Scarce Resources VII: A Locally Quasiconcave Objective Always Has a Quasistable Optimal ScheduleTextbook

Resource-constrained project scheduling asks for start times of the activities of a project that respect precedence-type time lags and the capacities of renewable resources (machines, crews, equipment). Classical project scheduling minimizes the project duration, a regular objective: delaying an activity never helps. Many objectives met in practice are not…

11 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems V: Bandit Convex Optimization with One-Point FeedbackTextbook

In bandit convex optimization a forecaster repeatedly picks a point xtx_txt​ of a convex set K⊆Rd\mathcal K\subseteq\mathbb R^dK⊆Rd, and an adversary picks a convex loss ℓt\ell_tℓt​. The forecaster pays ℓt(xt)\ell_t(x_t)ℓt​(xt​) and observes only that number: it never sees the function, its gradient, or its value elsewhere. This is the model of online optimization with only function-value…

11 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research+1·Captain: mikedeng1

Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems IV: Online Stochastic Mirror Descent for Combinatorial Semi-BanditsTextbook

Many sequential decision problems ask a learner to choose, round after round, a combination of items: a set of mmm ads out of ddd, a path in a network, a matching. After each choice the learner sees the loss of the items it used, not of those it did not. This is online combinatorial optimization with semi-bandit feedback. It contains the classical adversarial…

12 thms2 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Stability and Generalization 3: Tikhonov Regularization in a Reproducing Kernel Hilbert Space Has Uniform Stability σ²κ²/(2λm)Research Paper

Learning from a finite sample is useful only if changing the sample has a controlled effect on the learned predictor. Uniform stability asks for a bound on the change in loss at every test point when one training example is removed. Bousquet and Elisseeff use this property to obtain generalization bounds for learning algorithms, and identify regularization…

9 thms2 active usersReviewed
PreviousPage 21 of 23Next

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