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
Algorithmic Game TheoryMachine LearningOptimization·Captain: mikedeng1

Blackwell Approachability and No-Regret Learning are Equivalent 1: Any Approachability Algorithm Yields Online Linear Optimization with Regret/T at Most 2κ Times Its Approachability RateResearch Paper

Online decision makers often have to choose an action before seeing the cost assigned to it. A no-regret algorithm performs almost as well, in total, as the best single action that could have been chosen after the costs were known. In a related repeated-game problem, Blackwell approachability asks a player to keep the average of vector payoffs close to a…

6 thms2 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research+1·Captain: mikedeng1

Understanding and Using Linear Programming XI: The KKT Conditions and the Unique Smallest Enclosing BallTextbook

The smallest enclosing ball problem asks, for finitely many points p1,…,pn∈Rdp_1,\dots,p_n\in\mathbb{R}^dp1​,…,pn​∈Rd, for a ball of the smallest radius that contains all of them. It appears in clustering, in collision detection and bounding-volume hierarchies, in facility location (placing one service point so that the farthest client is as close as possible), and in the…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

On the Choice-Based Linear Programming Model for Network Revenue Management II: Only Efficient Offer Sets Carry Time in an Optimal CDLP SolutionResearch Paper

Airlines, hotels and rail operators sell many products (an itinerary combined with a fare class) that share a network of finite resources (flight legs, room-nights). When customers choose among whatever products are on offer, the firm's control is no longer "accept or reject a request for product jjj" but which set of products to offer at each moment. The…

9 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: mikedeng1

An Introduction to the Theory of Mechanism Design VI: Rochet's Theorem — Implementability Is Cyclical MonotonicityTextbook

Almost every screening, auction and regulation model asks the same preliminary question: which allocation rules can be made incentive-compatible by some choice of payments? In the one-dimensional models of auction theory and nonlinear pricing the answer is monotonicity: higher types must receive higher allocations. Many applications are not one-dimensional,…

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

Fast Projection onto the Simplex and the ℓ1 Ball: Correctness of Condat's AlgorithmResearch Paper

The Euclidean projection of a vector onto the simplex — the nonnegative vectors whose entries sum to a fixed radius — is a subroutine of first-order methods whose iterates must stay probability vectors or nonnegative budgets: portfolio optimization, multispectral unmixing, image segmentation, constrained least squares and many machine-learning models.…

13 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Linear Programming: Foundations and Extensions V: Convergence Rates of the Path-Following MethodTextbook

Interior-point methods are, together with the simplex method, the standard algorithms for linear programming, and the primal–dual path-following method is the form in which they are implemented in most solvers. Unlike the simplex method, it is a one-phase method: it can start from any point whose primal and dual variables are strictly positive, feasible or…

14 thms2 active usersReviewed
🏆Completed
Information TheoryLinear algebraOperations Research+1·Captain: naimengye

Decoding by Linear Programming: Exact Recovery by ℓ1 Minimization under the Restricted Isometry ConditionResearch Paper

Consider the classical error-correcting problem. An input vector f∈Rnf \in \mathbb{R}^nf∈Rn (the plaintext) is encoded as Af∈RmAf \in \mathbb{R}^mAf∈Rm by a coding matrix AAA with m>nm > nm>n, and an unknown, arbitrary vector of errors eee corrupts the result, so that only y=Af+ey = Af + ey=Af+e is observed. Can fff be recovered exactly, and by an algorithm whose running time is polynomial in mmm? Can…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Stochastic Programs with Fixed Recourse: The Equivalent Deterministic Program II: Stability of the Deterministic Equivalent Convex ProgramResearch Paper

A two-stage stochastic linear program with fixed recourse chooses a first-stage decision xxx before a random vector ξ\xiξ is observed, and then pays for a cheapest corrective action yyy once ξ\xiξ is known. It is the basic model of planning under uncertainty in operations research: capacity expansion, production planning with random demand, and energy dispatch are…

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

A New Projection Method for Variational Inequality Problems: The Hyperplane Projection Method Converges to a Solution Under Continuity and Generalized MonotonicityResearch Paper

A variational inequality asks for a point of a convex set at which a vector field points "inward" against every feasible direction. The format covers the first-order optimality conditions of constrained optimization, nonlinear complementarity problems, traffic and economic equilibria (Wardrop, Walrasian, Nash–Cournot), and systems of nonlinear equations;…

16 thms2 active usersReviewed
🏆Completed
Functional AnalysisOperations ResearchOptimization·Captain: mikedeng1

Accelerated Proximal Point Method for Maximally Monotone Operators: The Fixed-Point Residual Rate of the Accelerated MethodResearch Paper

Many problems in optimization reduce to finding a zero of a maximally monotone operator: minimizing a closed proper convex function (its subdifferential is maximally monotone), finding a saddle point of a convex–concave function, and solving monotone variational inequalities. The basic algorithm for this problem is the proximal point method of Martinet…

10 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchOptimization·Captain: mikedeng1

The Traveling-Salesman Problem and Minimum Spanning Trees, Part II: Convergence of the Constant-Step Ascent to the 1-Tree BoundResearch Paper

The traveling-salesman problem (TSP) asks for a cheapest cycle through all vertices of a weighted complete graph. Exact algorithms for it are branch-and-bound searches, and their size depends almost entirely on the quality of the lower bounds used to prune the search. In 1970 Held and Karp introduced the 1-tree bound: a Lagrangian relaxation of the degree-2…

10 thms2 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XXXIII: Near-Optimality for Submodular MinimizationTextbook

Chapter 10 turns from structure theory to algorithms: efficient methods for minimizing M-convex functions (via domain reduction) and submodular set functions (via Schrijver's and the Iwata-Fleischer-Fujishige scaling algorithms). Most of chapter 10's numbered results are asymptotic running-time bounds for specific procedural algorithms — a genuinely…

41 thms2 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis VII: The L-Optimality Criterion and the Proximity TheoremTextbook

Submodularity — the diminishing-returns property g(p)+g(q)≥g(p∨q)+g(p∧q)g(p) + g(q) \ge g(p \vee q) + g(p \wedge q)g(p)+g(q)≥g(p∨q)+g(p∧q) on a lattice — is one of the most useful structural hypotheses in combinatorial optimization, underlying efficient algorithms for network flows, matroid theory, and set-function minimization. Chapter 7 studies L-convex functions: functions on the integer lattice …

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

The Relaxation Method for Linear Inequalities III: Reflexion in a Closed Bounded Convex Set Terminates or Ends in OscillationResearch Paper

The relaxation method for a system of linear inequalities, introduced by Agmon and by Motzkin and Schoenberg in back-to-back papers of the Canadian Journal of Mathematics (1954), solves ∑jaijxj+bi≥0\sum_j a_{ij}x_j + b_i \ge 0∑j​aij​xj​+bi​≥0 by repeatedly moving a point towards, or across, the most violated half-space. It is the ancestor of the perceptron algorithm, of Kaczmarz-type…

11 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimization·Captain: mikedeng1

A Stochastic Quasi-Newton Method for Large-Scale Optimization: The Expected Suboptimality Bound of the SQN MethodResearch Paper

Training a statistical model by empirical risk minimization means minimizing an average of NNN losses over a parameter vector w∈Rnw\in\mathbb R^nw∈Rn, where both NNN and nnn can be in the millions. Stochastic gradient descent (SGD) is the standard method: each step uses the gradient of a small random batch of losses. It is cheap per step but sensitive to the scaling of…

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

Globally Convergent Type-I Anderson Acceleration for Nonsmooth Fixed-Point Iterations: The Stabilized Type-I Anderson Acceleration Converges to a Fixed Point of Every Nonexpansive MapResearch Paper

Many first-order methods in optimization are fixed-point iterations xk+1=f(xk)x^{k+1}=f(x^k)xk+1=f(xk) of a nonexpansive map f:Rn→Rnf:\mathbb R^n\to\mathbb R^nf:Rn→Rn: proximal gradient descent, projected gradient descent, alternating projections, ISTA and Douglas–Rachford splitting (with the conic solver SCS as an instance) all have this form (Zhang, O'Donoghue, Boyd 2020, §4.2). The…

12 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis II: Local Optimality for Integrally Convex FunctionsTextbook

For a convex function on Rn\mathbb R^nRn, a point is a global minimizer as soon as it is a local minimizer — this is one of the earliest and most consequential facts of convex analysis, and it underlies why local-search and gradient methods can certify global optimality in convex programs. The discrete analogue is not automatic: a function on the integer…

14 thms2 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: Shuze Chen

Discrete Convex Analysis XV: Conjugacy of Quadratic Forms and Symmetric M-MatricesTextbook

Quadratic minimization problems with a combinatorial sign pattern in their Hessian arise throughout applied mathematics: discretizations of elliptic boundary-value problems such as the Poisson equation, resistor-network energy functionals, and the Dirichlet forms of Markov-process potential theory all produce a symmetric matrix whose off-diagonal entries…

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

Cubic Regularization of Newton Method and Its Global Performance II: The Global Rate on Star-Convex FunctionsResearch Paper

Newton's method converges quadratically near a non-degenerate minimizer, but classical theory says little about its behaviour far from one: the pure Newton step can move uphill, diverge, or be undefined when the Hessian is singular. For decades the global analysis of Newton-type methods consisted of convergence statements without rates. Nesterov and Polyak (…

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

The Generalized Quasi-Variational Inequality Problem III: The Projection Map Is a Contraction and Its Iterates Converge to a SolutionResearch Paper

A variational inequality asks for a point xxx of a set K⊆RnK\subseteq\mathbb R^nK⊆Rn at which a vector field fff points "into" KKK: (x′−x)Tf(x)≥0(x'-x)^T f(x)\ge 0(x′−x)Tf(x)≥0 for every x′∈Kx'\in Kx′∈K. It is the common form of the first-order optimality conditions of constrained optimization, of complementarity problems, and of equilibrium models in economics and traffic networks. In many of these…

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

Projected Gradient Methods for Linearly Constrained Problems II: Finite Identification of the Active Constraints at a Nondegenerate PointResearch Paper

Minimizing a smooth function subject to linear inequality constraints is the core subproblem of much of nonlinear optimization: bound-constrained problems, quadratic programs, and the subproblems of sequential quadratic programming and augmented Lagrangian methods all have this form. Methods for these problems are usually built from two parts, one that…

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

Nonmonotone Spectral Projected Gradient Methods on Convex Sets II: SPG1 Is Well Defined and Its Accumulation Points Are StationaryResearch Paper

Minimizing a smooth function over a closed convex set Ω⊆Rn\Omega\subseteq\mathbb R^nΩ⊆Rn on which projection is cheap (a box, a ball, a simplex) is a routine subproblem in large-scale optimization. Box-constrained minimization is the inner solver of augmented Lagrangian methods, and bound-constrained least squares, image restoration and density estimation all have…

11 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Generalization Bounds in the Predict-then-Optimize Framework IV: Distance to Degeneracy and the Strength Property for PolytopesResearch Paper

Many decision problems in operations research are solved in two stages: a model predicts the unknown cost vector of a linear optimization problem from features, and the predicted costs are then passed to a solver. The smart predict-then-optimize (SPO) loss of Elmachtoub and Grigas measures the quality of a prediction by the excess true cost of the decision…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

Existence of an Equilibrium for a Competitive Economy I: Equilibrium Exists When Every Consumer Can Trade Every GoodResearch Paper

Walras (1874) described an economy as a system of simultaneous equations, one per market, and argued that a set of prices clearing all markets exists because the number of equations equals the number of unknowns. Counting equations proves nothing, and the question of whether competitive equilibrium exists at all remained open for eighty years. Wald…

16 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchOptimal Transport+1·Captain: mikedeng1

Distributionally Robust Logistic Regression I: The Worst-Case Expected Logloss over a Wasserstein Ball Is a Tractable Convex ProgramResearch Paper

Logistic regression is among the most widely used classification methods in statistics and machine learning. Its maximum-likelihood estimator minimizes the average logloss on the training data and is known to overfit when data are scarce; practitioners respond with ad hoc regularization, typically a norm penalty on the weight vector. Shafieezadeh-Abadeh,…

9 thms2 active usersReviewed
PreviousPage 22 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