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
Numerical AnalysisOptimizationTheoretical Computer Science·Captain: iris

Solving ppp-norm regression in matrix multiplication timeResearch Paper

Given a matrix A∈Rn×dA\in\mathbb R^{n\times d}A∈Rn×d of full column rank and a vector b∈Rnb\in\mathbb R^nb∈Rn, ℓp\ell_pℓp​ regression asks for a minimizer of ∥Ax−b∥p\|Ax-b\|_p∥Ax−b∥p​. The case p=2p=2p=2 is least squares; p∈{1,∞}p\in\{1,\infty\}p∈{1,∞} is equivalent to linear programming; the values in between interpolate between linear system solving and linear programming and arise in data analysis and in flow…

34 thms3 active usersReviewed
Machine LearningOptimization·Captain: iris

Exact Feasibility and Privacy Amplification for Linearly Constrained OptimizationResearch Paper

Many allocation problems split a fixed public budget among participants whose costs depend on private records. They are instances of linearly constrained composite optimization,

49 thms3 active usersReviewed
OptimizationTheoretical Computer Science·Captain: iris

Optimal Competitive Ratios for Chasing Convex Functions with Quadratic GrowthResearch Paper

Convex function chasing is an online game between a learner and an adversary. In each round the adversary reveals a convex hitting cost ftf_tft​, and the learner moves to a decision xtx_txt​ in a fixed feasible set X⊆RdX\subseteq\mathbb R^dX⊆Rd, paying ft(xt)f_t(x_t)ft​(xt​) plus a movement cost for leaving xt−1x_{t-1}xt−1​. The model is used for dynamic resource provisioning and online control (Ar…

26 thms3 active usersReviewed
Optimization·Captain: iris

Anchored Extra-Proximal Methods: Optimal Higher-Order Methods for Monotone Inclusion ProblemsResearch Paper

Convex-concave min-max problems, monotone variational inequalities and nonexpansive fixed-point problems can all be written as monotone inclusions: find a zero of the sum of two monotone operators. A natural accuracy measure for such problems is the tangent residual, the distance from the origin to the set of operator values at a point; it reduces to the…

44 thms3 active usersReviewed
Numerical AnalysisOptimization·Captain: iris

Benign Degeneracy for First-Order Methods in Exact Boolean Moment-SOS RelaxationsResearch Paper

Minimizing a polynomial fff over the Boolean cube {±1}n\{\pm1\}^n{±1}n contains MAX-CUT, Ising ground states and many other combinatorial problems. The moment–sum-of-squares (moment–SOS) hierarchy replaces the cube by a semidefinite program (SDP) of order ddd; when the relaxation is exact, its optimum is the rank-one moment matrix of the Boolean minimizer, and an optimal …

31 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Silver Rate Is (Almost) Optimal for Gradient DescentResearch Paper

Gradient descent (GD) with a predetermined stepsize schedule H=(h1,…,hn)H=(h_1,\dots,h_n)H=(h1​,…,hn​) is the method xt=xt−1−ht∇f(xt−1)x_t=x_{t-1}-h_t\nabla f(x_{t-1})xt​=xt−1​−ht​∇f(xt−1​), 1≤t≤n1\le t\le n1≤t≤n, with the stepsizes fixed before the run. With the constant stepsize 1/L1/L1/L it converges at rate O(n−1)O(n^{-1})O(n−1) on convex LLL-smooth functions, and the classical lower bound Ω(n−2)\Omega(n^{-2})Ω(n−2) of Nemirovsky and Yudin holds for every…

33 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: iris

Markov Decision Processes with Applications to Finance II: In Convex Markov Decision Models the Convex Functions in Bb+\mathbb{B}_b^+Bb+​ Satisfy the Structure AssumptionTextbook

In a finite-horizon Markov decision problem the value functions VnV_nVn​ are computed backwards by the Bellman equation Vn=TnVn+1V_n = T_nV_{n+1}Vn​=Tn​Vn+1​. Bäuerle and Rieder (Springer 2011) organize the general theory around one hypothesis, the Structure Assumption (SAN)(\mathrm{SA}_N)(SAN​): if a class of functions IMn\mathbb{IM}_nIMn​ is stable under the maximal reward operator TnT_nTn​ and every…

15 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Batching and Optimal Multi-stage Bipartite Allocations: PR-MWM Is (1 − (1 − 1/K)^K)-Competitive for K-Stage Fractional Vertex-Weighted MatchingResearch Paper

Matching platforms rarely decide on one request at a time. A ride-hailing marketplace clears requests in short windows, an ad exchange serves a video session's slots together, and cloud and retail systems process demand in rounds. Between the fully offline problem and the online model of Karp, Vazirani and Vazirani (STOC 1990) lies a question with an…

18 thms3 active usersReviewed
Graph TheoryOptimizationProbability·Captain: marwahaha

Grothendieck inequalities for semidefinite programs with rank constraintResearch Paper

The graphical Grothendieck problem with rank constraint maximizes a quadratic form over unit vectors assigned to the vertices of a graph. Depending on the rank, the same problem is MAX CUT, Grothendieck's inequality, the ground state of a spin model, or the value of a quantum XOR game.

22 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Efficient Algorithms for a Class of Stochastic Hidden Convex Optimization and Its Applications in Network Revenue Management: Explicit Global Convergence Bound for Mirror Stochastic GradientResearch Paper

Many operations management models choose a decision xxx whose effect is filtered through randomness: a booking limit xxx is truncated by random demand ξ\xiξ, so the realized sales are x∧ξx\wedge\xix∧ξ; an order quantity is scaled by a random yield. The resulting stochastic program

25 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Proximal-Like Incremental Aggregated Gradient Method with Linear Convergence Under Bregman Distance Growth Conditions: PLIAG Converges Linearly at Rate 1/(1+αμ)Research Paper

Large-scale learning and signal-processing problems often have the form of a sum of many convex components plus a nonsmooth regularizer, min⁡x∑n=1Nfn(x)+h(x)\min_x \sum_{n=1}^N f_n(x) + h(x)minx​∑n=1N​fn​(x)+h(x). Incremental aggregated gradient (IAG) methods process such sums by refreshing the gradient of only some components per iteration and reusing older, delayed gradients for the rest. This…

26 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Data-Driven Distributionally Robust CVaR Portfolio Optimization Under A Regime-Switching Ambiguity Set: For Every ℓm Cost, the Worst-Case CVaR Problem Is the Convex Program (12)Research Paper

A portfolio manager who minimizes the conditional value-at-risk (CVaR) of the portfolio loss needs the distribution of asset returns, but only has a finite history of them. Plugging the empirical distribution into the CVaR formula of Rockafellar and Uryasev (2002) gives portfolios that perform poorly out of sample. Distributionally robust optimization (DRO)…

30 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Difference-of-Convex Algorithm with Extrapolation for Nonconvex, Nonsmooth Optimization Problems: Bounded DCAe Sequences Converge to a Critical Point under the Kurdyka–Łojasiewicz PropertyResearch Paper

Many estimation problems in statistics and machine learning minimize a smooth data-fitting loss plus a nonconvex sparsity-promoting penalty: compressed sensing, sparse dictionary learning, phase retrieval, Poisson inverse problems and nonnegative matrix completion. Penalties such as SCAD, MCP and the exponential penalty are differences of convex functions (D…

24 thms3 active usersReviewed
Dynamical SystemsOperations ResearchOptimization·Captain: iris

Monotone Inclusions, Acceleration and Closed-Loop Control: Every Global Trajectory Has Ergodic Gap O(t−(p+1)/2)O(t^{-(p+1)/2})O(t−(p+1)/2) and Pointwise Residue O(t−p/2)O(t^{-p/2})O(t−p/2)Research Paper

A monotone inclusion asks for a point xxx of a real Hilbert space H\mathcal HH with 0∈Ax0\in Ax0∈Ax, where AAA is a set-valued monotone operator. Convex minimization, convex-concave saddle points and monotone variational inequalities are all of this form. The basic method is the proximal point algorithm of Rockafellar (1976), the fixed-point iteration of the resolvent …

16 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOptimizationReinforcement Learning·Captain: iris

On the Convex Formulations of Robust Markov Decision Processes: The Fixed Point of the Entropy-Regularized Robust Bellman Operator Is log_b of the Unique Optimum of a Convex ProgramResearch Paper

A Markov decision process (MDP) models sequential decisions under uncertainty: in each state an agent picks an action, collects a reward and moves to a random next state. Its optimal value function is the fixed point of the Bellman operator, and since the 1960s it has also been the optimum of a linear program over value functions (Puterman, Markov Decision…

14 thms3 active usersReviewed
Functional AnalysisOperations ResearchOptimization·Captain: iris

A Perturbation Framework for Convex Minimization and Monotone Inclusion Problems with Nonlinear Compositions: Lagrangian, Dual and Kuhn–Tucker Operator Whose Zeros Are Primal–Dual SolutionsResearch Paper

Many optimization models couple a convex function fff with a nonlinear outer function φ\varphiφ: a constraint f(x)≤0f(x)\le0f(x)≤0 is φ=ι]−∞,0]\varphi=\iota_{]-\infty,0]}φ=ι]−∞,0]​, a penalty-barrier term α(ρ)θ(f(x)/ρ)\alpha(\rho)\theta(f(x)/\rho)α(ρ)θ(f(x)/ρ) is a smooth increasing φ\varphiφ, and a power ∥x∥p\|x\|^p∥x∥p of a norm is φ∘∥⋅∥\varphi\circ\|\cdot\|φ∘∥⋅∥. Standard splitting methods handle sums of convex functions composed…

39 thms3 active usersReviewed
Algorithmic Game TheoryMachine LearningOperations Research·Captain: iris

The Online Saddle Point Problem and Online Convex Optimization with Knapsacks: Saddle-Point Follow-the-Leader Has SP-Regret at Most 8G2/H⋅(1+log⁡T)8G^2/H\cdot(1+\log T)8G2/H⋅(1+logT) on Strongly Convex-Concave Lipschitz GamesResearch Paper

Many decisions are made by two parties with opposed interests who interact repeatedly while the game between them changes: a seller and a buyer facing shifting demand, a planner and an adversarial environment, or the primal and dual players of a constrained online optimization problem. Rivera Cardoso, Wang and Xu (arXiv:1806.08301v3) formalize this as the on…

13 thms3 active usersReviewed
AnalysisQuantum Information·Captain: iris

Continuity of the Maximum-Entropy Inference: Faces of a Linear Image of a Stable Convex Body Are Lower Semicontinuous Along Lifted Sequences, and dim⁡F(w)≤lim inf⁡dim⁡F(wi)\dim F(w) \le \liminf \dim F(w_i)dimF(w)≤liminfdimF(wi​)Research Paper

In quantum statistical inference one measures the expected values α=(⟨u1,ρ⟩,…,⟨ur,ρ⟩)\alpha=(\langle u_1,\rho\rangle,\dots,\langle u_r,\rho\rangle)α=(⟨u1​,ρ⟩,…,⟨ur​,ρ⟩) of finitely many observables u1,…,uru_1,\dots,u_ru1​,…,ur​ on an unknown state ρ\rhoρ and, among all states compatible with α\alphaα, selects the one of maximal von Neumann entropy, ρ∗(α)\rho^*(\alpha)ρ∗(α). The map α↦ρ∗(α)\alpha\mapsto\rho^*(\alpha)α↦ρ∗(α) is the maximum-en…

11 thms3 active usersReviewed
Numerical AnalysisOptimization·Captain: iris

A New Homotopy Proximal Variable-Metric Framework for Composite Convex Minimization: Global Linear Convergence of the Exact Homotopy Scheme under Strong Convexity and Lipschitz GradientResearch Paper

Composite convex problems min⁡xf(x)+g(x)\min_x f(x)+g(x)minx​f(x)+g(x), with fff smooth and ggg nonsmooth, cover the regularized estimation and constrained models of statistics, signal processing and machine learning. Proximal variable-metric methods (Lee, Sun and Saunders, 2014) solve them with a metric that adapts to the curvature of fff, but each step is a scaled proximal subproblem,…

29 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Data-Driven Minimax Optimization with Expectation Constraints: Basic-CSPD Attains the O(1/√N) Rate for the Objective Gap and Feasibility ResidualsResearch Paper

Stochastic minimax problems min⁡x∈Xmax⁡y∈YEω[f(x,y,ω)]\min_{x\in\mathcal X}\max_{y\in\mathcal Y}\mathbb E_\omega[f(x,y,\omega)]minx∈X​maxy∈Y​Eω​[f(x,y,ω)] arise in robust optimization, AUC maximization, games and adversarial training. Projected stochastic gradient descent–ascent solves them when projections onto X\mathcal XX and Y\mathcal YY are cheap. In data-driven applications the feasible sets are often…

25 thms3 active usersReviewed
CombinatoricsLinear OptimizationOptimization·Captain: iris

On Polyhedral Approximations of the Positive Semidefinite Cone: Every Polytope Between (1−ε)(D − A) and D − A Has Extension Complexity at Least exp(c√n)Research Paper

Linear programs are the workhorse of optimization, and a recurring question is which convex sets can be described, or approximated, by a linear program of small size. The relevant measure is the extension complexity xc⁡(P)\operatorname{xc}(P)xc(P) of a polytope PPP: the smallest number of facets of a polytope that projects linearly onto PPP. If xc⁡(P)=N\operatorname{xc}(P)=Nxc(P)=N,…

26 thms3 active usersReviewed
AnalysisOptimization·Captain: iris

Hölderian Error Bounds and Kurdyka-Łojasiewicz Inequality for the Trust Region Subproblem: The KL Inequality Holds at Every Optimal Solution with Exponent 3/4 in the TRS-Ill Case and 1/2 OtherwiseResearch Paper

The trust region subproblem (TRS) asks for the minimum of a quadratic function over the Euclidean unit ball. It is the inner step of trust region methods for nonlinear optimization, and it also arises in robust optimization and regularized least squares. When the quadratic form is indefinite the problem is nonconvex, yet it has hidden convexity: strong…

49 thms3 active usersReviewed
ProbabilityStochastic Systems·Captain: iris

An SDE Perspective on Stochastic Convex Optimization: The Gradient SDE Has a Unique Solution and, Under Square-Integrable Noise, Converges Almost Surely to a MinimizerResearch Paper

First-order methods for convex minimization rarely see an exact gradient: in stochastic gradient descent and its relatives the gradient is perturbed by sampling or measurement noise. A standard way to study the long-time behaviour of such methods is to pass to continuous time, where the deterministic gradient flow x˙=−∇f(x)\dot x=-\nabla f(x)x˙=−∇f(x) is replaced by a…

23 thms3 active usersReviewed
Numerical AnalysisOptimization·Captain: iris

A Squared Smoothing Newton Method for Semidefinite Programming: Under Primal and Dual Constraint Nondegeneracy the Huber-Based Method Converges Superlinearly with Order 1+τ1+\tau1+τResearch Paper

Semidefinite programming (SDP) minimizes a linear function of a symmetric matrix subject to linear equations and positive semidefiniteness. It is a standard modelling tool in control, combinatorial optimization, statistics and quantum information. Interior point methods solve SDPs accurately but each iteration factorizes a dense m×mm\times mm×m Schur complement,…

22 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Compact Extended Formulations for Low-Rank Functions with Indicator Variables: cl⁡conv⁡(Q)\operatorname{cl}\operatorname{conv}(Q)clconv(Q) from the Pieces V(I)V(I)V(I) with ∣I∣≤k|I| \le k∣I∣≤k and the Ray Set RRRResearch Paper

Many optimization models in statistics, machine learning and finance minimize a convex function of a continuous vector x∈Rnx\in\mathbb R^nx∈Rn under logical conditions on its support. Best subset selection, sparse regression and sparse portfolio selection are standard cases. A binary indicator variable ziz_izi​ models such a condition: zi=0z_i=0zi​=0 forces xi=0x_i=0xi​=0, and zi=1z_i=1zi​=1 leave…

12 thms3 active usersReviewed
PreviousPage 10 of 30Next

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