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

Primal and Dual Linear Decision Rules in Stochastic and Robust Optimization 2: With Random Recourse, the SDP (3.14) Conservatively Approximates the Linear Decision Rule Problem, Exactly for l = 1Research Paper

In a one-stage stochastic program a decision maker observes a random outcome ξ\xiξ and then picks a decision x(ξ)x(\xi)x(ξ), subject to constraints that depend on ξ\xiξ, so as to minimize expected cost. The optimization variable is a whole function xxx, and computing the optimal value is #P-hard even for a uniform distribution on the unit cube (Dyer and Stougie, 2006,…

7 thms3 active usersReviewed
Linear algebraMachine LearningStatistics·Captain: mikedeng1

Nuclear-Norm Penalization and Optimal Rates for Noisy Low-Rank Matrix Completion 2: If λ ≥ 3‖M‖∞ on a Linear Subspace, a Sharp Oracle Inequality with the Restricted Constant μ₅(A)Research Paper

Estimating a large matrix that is approximately low rank from a few noisy linear measurements is a basic problem of high-dimensional statistics. It covers matrix completion (recovering a ratings table from a small sample of entries), multi-task regression and quantum state tomography. The standard estimator penalizes the nuclear norm, the sum of the…

14 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Optimization and Its Tractable Approximations 3: The Infimal Convolution of π¹, π², π³ Bounds the Worst Case over the Intersected Families and Improves on EachResearch Paper

Two-stage and multistage stochastic programs ask for decisions that react to uncertainty revealed over time. When the distribution of the uncertainty is known only partially, one optimizes against the worst distribution in a family F\mathbb FF consistent with what is known: a support set, a range for the mean, a covariance matrix, bounds on how fast the tails…

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

A Monotone+Skew Splitting Model for Composite Monotone Inclusions in Duality: The Inexact Primal–Dual Forward–Backward–Forward Iterates Converge Weakly to a Primal and a Dual SolutionResearch Paper

Many problems in convex optimization, variational inequalities, mechanics, traffic equilibrium and signal processing reduce to finding a zero of a monotone operator on a Hilbert space. Frequently that operator is a sum A+L∗∘B∘LA + L^*\circ B\circ LA+L∗∘B∘L of a monotone operator and a monotone operator composed with a linear map and its adjoint, and one also wants the…

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

Solving Semidefinite-Quadratic-Linear Programs Using SDPT3: The HKM and NT Search Directions of Second-Order Cone Programming Are Invariant Under Automorphic ScalingResearch Paper

Second-order cone programming (SOCP) minimizes a linear function over the intersection of an affine subspace with a product of Lorentz cones. It contains convex quadratically constrained programs, robust linear programs with ellipsoidal uncertainty, and many norm-minimization problems, and it is solved in practice by primal–dual interior-point methods. At…

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

Prox-Method with Rate of Convergence O(1/t) for Variational Inequalities with Lipschitz Continuous Monotone Operators and Smooth Convex-Concave Saddle Point Problems: Error √2ΘL/(αN) After N StepsResearch Paper

Monotone variational inequalities (v.i.) cover convex minimization, convex–concave saddle-point problems, Nash equilibria of convex games and complementarity problems. Matrix games and other large saddle-point problems are typical cases. At large scale, first-order methods that use only values of the operator and simple auxiliary minimizations are the…

18 thms3 active users
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Robust Regression and Lasso 2: When an Absolute Norm Bounds the Column Disturbance Norms, Robust Regression Is Regression Regularized by the Dual Norm, ‖b − Ax‖ₐ + l‖x‖*ₛResearch Paper

Robust regression guards a linear model against errors in the data matrix. The observations b∈Rnb \in \mathbb R^nb∈Rn are fitted by AxAxAx, but the features (the columns a1,…,ama_1,\dots,a_ma1​,…,am​ of AAA) are only known up to a disturbance ΔA\Delta AΔA from an uncertainty set U\mathcal UU. The robust estimator minimizes the worst-case residual,

5 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Optimization and Its Tractable Approximations 2: Under a Mean Set and a Known Covariance, the Bound π² Equals the Worst-Case Expected Positive PartResearch Paper

Many operations models contain terms of the form EP((r0+r′ζ~)+)E_{\mathbb P}\big((r^0 + r'\tilde\zeta)^+\big)EP​((r0+r′ζ~​)+): expected shortfall or overflow of an affine function of an uncertain vector. Inventory and newsvendor costs, penalties for violated soft constraints, and the Conditional Value-at-Risk of a linear decision rule all reduce to it. In practice the distribution …

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

How Bad is Selfish Routing? 4: With Polynomial Latencies of Degree p and Nonnegative Coefficients the Cost of a Nash Flow Is at Most p + 1 Times the Optimal CostResearch Paper

In a road or communication network carrying a large population of users, each user picks a route that is fastest for itself given the congestion caused by everyone else. The resulting traffic pattern, a Wardrop or Nash equilibrium, need not minimize the total travel time: Braess's paradox shows that adding a road can make every user slower. Transportation…

10 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

Semidefinite Programming Relaxations for Semialgebraic Problems 2: A Feasible Solution of the SDPs (7.7) Certifies That M Is Copositive, and the Test Is at Least as Strong as M = P + NResearch Paper

A real symmetric matrix is copositive when its quadratic form is nonnegative on the nonnegative orthant. Copositive matrices appear wherever a quadratic objective meets sign constraints: standard quadratic programs over the simplex, linear complementarity problems, and conic reformulations of combinatorial problems such as the stability number of a graph.…

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

On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization II: Points of a Product of Quadratic and Rotated Cones Are Complementary Iff Their Arrow-Head Products VanishResearch Paper

Conic quadratic optimization (also called second-order cone programming) minimizes a linear function over the intersection of an affine subspace with a product of quadratic cones. It contains linear programming, convex quadratically constrained programming, robust linear programming with ellipsoidal uncertainty and many problems from engineering design; see…

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

On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization I: Solutions of the Homogeneous Model Are Complementary and Give an Optimal Pair or an Infeasibility CertificateResearch Paper

Conic optimization minimizes a linear function over the intersection of an affine subspace with a closed convex cone. Linear programming (the nonnegative orthant), second-order cone programming (products of quadratic cones) and semidefinite programming (the positive semidefinite cone) are all instances. Primal–dual interior-point methods are the standard…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Distributionally Robust Optimization and Its Tractable Approximations 1: Under a Support Set and a Mean Set, the Bound π¹ Equals the Worst-Case Expected Positive PartResearch Paper

Linear decision rules are a standard device for making multistage optimization under uncertainty computationally tractable: a recourse decision is restricted to be an affine function of the uncertain data observed so far. Their weakness is that a recourse variable that must stay nonnegative forces the rule to be very conservative. Goh and Sim, Distributional…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling II: Randomized Rounding of the Time-Slot Convex Quadratic Relaxation (CQP) Is Within 2 for R | rᵢⱼ | Σ wⱼCⱼResearch Paper

Scheduling jobs on unrelated parallel machines to minimize the total weighted completion time is a basic model of machine scheduling: each job may take a different time on each machine, and a job becomes available on a machine only at a machine-dependent release date. In the three-field notation the problem is R∣rij∣∑wjCjR \mid r_{ij} \mid \sum w_jC_jR∣rij​∣∑wj​Cj​. Already the…

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

Semidefinite Programming 2: If Every Step Lowers the Potential φ by δ > 0, Then After k ≥ (ν√n log(1/ε) + ψ(x⁽⁰⁾, Z⁽⁰⁾))/δ Steps the Duality Gap Is at Most ε Times Its Initial ValueResearch Paper

Semidefinite programs optimize a linear objective while requiring an affine matrix to be positive semidefinite. They include familiar linear and quadratic optimization models and arise in engineering and combinatorial optimization. Vandenberghe and Boyd's survey develops their duality theory and describes interior point methods that work with primal and…

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

A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem III: The DCA Step x^{k+1} = P_E(x^k − (Ax^k + b)/ρ) Is a Descent Method Whose Limit Points Are Kuhn–Tucker PointsResearch Paper

The trust-region subproblem asks for the minimum of a quadratic function over a Euclidean ball,

16 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Coordinate Gradient Descent Method for Nonsmooth Separable Minimization 2: Under a Local Lipschitzian Error Bound, CGD with the Restricted Gauss–Seidel Rule Converges LinearlyResearch Paper

Many problems in statistics, signal processing and machine learning minimize the sum of a smooth loss and a convex, nonsmooth, separable regularizer: smooth optimization with ℓ1\ell_1ℓ1​-regularization, bound-constrained optimization, the group Lasso and, through duality, support vector regression are special cases listed in §1 of the paper discussed below. For…

10 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem II: D.C. Duality Carries a Local Minimizer x* of g − h to a Local Minimizer y* ∈ ∂h(x*) of h* − g*Research Paper

A d.c. program minimizes a difference of two convex functions,

10 thms3 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Primal-Dual Interior-Point Methods for Self-Scaled Cones II: The Functional-Proximity Predictor-Corrector Step Has α²/(1 − α) ≥ ω₁(Δ, κ)/ν and Boundedly Many Newton CorrectionsResearch Paper

Primal-dual interior-point methods are the standard algorithms for linear, second-order-cone and semidefinite programming. Their best-known variants keep the iterates in a narrow neighbourhood of the central path and take short or moderately long steps whose length is fixed in advance. Practical codes instead take long steps and recentre only when needed.…

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

Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 5: Nonquadratic Proximal Methods of Multipliers Converge to a Saddle PointResearch Paper

The method of multipliers (augmented Lagrangian method) solves a constrained convex program by alternating an unconstrained minimization in the primal variables with an explicit update of the Lagrange multipliers. Rockafellar showed in 1976 that the classical quadratic version is the proximal point algorithm applied to the dual problem, and that a variant…

22 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Primal-dual subgradient methods for convex problems 1: Dual Averaging Keeps the Gap Below β_{k+1}D + (1/2σ)Σλᵢ²‖gᵢ‖²_*/βᵢ and Its Iterates BoundedResearch Paper

Subgradient methods are the basic tool for minimizing a nonsmooth convex function when only a black-box oracle returning one subgradient per query is available. In the classical method the new subgradient enters the iterate with a weight that decreases over time, so information collected late is counted less than information collected early, and the method…

12 thms3 active usersReviewed
🏆Completed
Functional AnalysisNumerical AnalysisOperations Research+1·Captain: mikedeng1

Régularisation d'inéquations variationnelles par approximations successives II: The Proximal Regularization of a Convex Minimization Problem Is a Minimizing SequenceResearch Paper

The proximal point algorithm replaces a hard optimization or equilibrium problem by a sequence of better-conditioned ones: from the current point xnx^nxn it solves the original problem with a quadratic penalty ∥x−xn∥2\|x-x^n\|^2∥x−xn∥2 added, and takes the solution as xn+1x^{n+1}xn+1. The method is a building block of modern convex optimization. Augmented Lagrangian methods,…

6 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

Fixed Point and Bregman Iterative Methods for Matrix Rank Minimization: The Matrix Shrinkage Fixed Point Iteration Converges to an Optimal Solution of the Nuclear Norm Regularized ProblemResearch Paper

Many estimation problems ask for a matrix of low rank that is consistent with a small number of linear measurements: completing a partially observed ratings matrix, identifying a low-order linear system, or embedding points from a few pairwise distances. Rank minimization under linear constraints is NP-hard, and the standard convex surrogate replaces the…

10 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Stochastic Convex Programming: Basic Duality 2: With a Bounded Second-Stage Set the Intrinsic First-Stage Problem Coincides with the One Induced by P and Recourse Is AttainedResearch Paper

Two-stage stochastic programming with recourse models a decision taken in two steps: a first-stage decision x1x_1x1​ is fixed before a random outcome sss is observed, and a recourse decision x2(s)x_2(s)x2​(s) is taken afterwards, once sss is known. The model goes back to Dantzig (1955) and Beale (1955) and is the basic template of stochastic optimization in operations…

15 thms3 active usersReviewed
🏆Completed
Functional AnalysisNumerical Analysis·Captain: mikedeng1

A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation 2: Internal Approximations Under (4.1)–(4.3) Have Solutions v_h Converging Strongly to vResearch Paper

An infinite dimensional variational problem can be described by continuous linear operators and convex functionals, yet numerical work needs finite dimensional spaces. The question is whether a solution computed in a finite dimensional approximation still approaches the solution of the original problem when the approximation is refined. Gabay and Mercier's I…

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