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
Linear OptimizationOperations Research·Captain: mikedeng1

Retailer-Supplier Flexible Commitments Contracts: A Robust Optimization Approach: With Box Demand Uncertainty the Min-Max RSFC Problem Has the Same Optimal Value on the Extreme DemandsResearch Paper

In a flexible commitments contract a retailer announces, before a selling horizon starts, a vector of planned orders (commitments) to its supplier, who uses them to plan capacity. During the horizon the retailer may deviate from the commitments, but pays penalties for each deviation and for changes between successive commitments. Such contracts were studied…

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

On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization IV: The Nesterov–Todd Scaling of a Quadratic or Rotated Quadratic Cone Is W = −Q + (e₁ + w)(e₁ + w)ᵀ/(1 + w₁)Research Paper

Conic quadratic (second-order cone) programs are solved in practice by primal-dual interior-point methods. Each iteration solves a Newton system for the central-path equations, and for non-polyhedral cones that system is only guaranteed to be well posed after the problem is scaled: the primal point xxx and the dual slack sss are transformed by a matrix ΘW\Theta WΘW…

15 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

How Bad is Selfish Routing? 2: With Linear Latency Functions the Cost of a Nash Flow Is at Most 4/3 Times the Optimal CostResearch Paper

In a road or communication network, each user picks a route to minimize its own delay, without regard to the delay it imposes on others. The outcome is an equilibrium that is in general not socially optimal: Braess's paradox shows that adding a road can make every user worse off, and Pigou's two-link example shows that selfish users can incur a third more…

15 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Pegasos: Primal Estimated Sub-Gradient Solver for SVM: Mini-Batch Pegasos Has Average Instantaneous Objective Within c(1+ln T)/(2λT) of the SVM Optimum'sResearch Paper

The support vector machine (SVM) is a linear classifier trained by minimising a regularised hinge loss. For training sets with millions of examples, solving the SVM problem to high accuracy by interior-point or dual decomposition methods is too slow, and what is needed is an algorithm whose cost per iteration does not grow with the number of examples. Pegaso…

15 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion 2: With Random Objective, Z(x) = Z_D(x) = Z_DD(x) and Moment-Matching Distributions Attain Z(x) AsymptoticallyResearch Paper

Two-stage stochastic linear programming chooses a first-stage decision xxx before a random parameter is revealed and pays an optimal second-stage (recourse) cost afterwards. The classical model fixes the distribution of the random parameter. In practice it is rarely known beyond a few moments, and a decision maker who is averse to risk does not evaluate the…

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

Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion 3: With Random Right-Hand Side and Known Dual Extreme Points, the Problem Equals the Semidefinite Program (14)Research Paper

Two-stage stochastic linear programs model a decision xxx taken before uncertainty is revealed, followed by a corrective recourse action once it is. The classical model needs the full probability distribution of the uncertain data, which in practice is rarely known; often only estimates of the mean and the second moments are available, and the computed plan…

11 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion 1: With Random Objective, the Risk-Averse Minimax Problem Equals the Semidefinite Program (7)Research Paper

Two-stage stochastic linear programs choose a first-stage decision xxx before a random parameter is revealed and a recourse decision www afterwards. The classical model assumes the distribution of the random data is known. In practice it is estimated, and often only its first two moments are trusted. The minimax (distributionally robust) approach hedges against…

13 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling I: Randomized Rounding of the Convex Quadratic Relaxation (CQP′) Is Within 3/2 for R | | Σ wⱼCⱼResearch Paper

Scheduling jobs on unrelated parallel machines to minimize the total weighted completion time, the problem written R ∣ ∣∑wjCjR\,|\,|\sum w_jC_jR∣∣∑wj​Cj​ in the three-field notation, is one of the basic NP-hard models of machine scheduling. Each job may take a different time on each machine, as when heterogeneous processors, plants or crews serve the same pool of tasks, and…

12 thms4 active usersReviewed
🏆Completed
Numerical AnalysisOperations ResearchOptimization·Captain: mikedeng1

A Coordinate Gradient Descent Method for Nonsmooth Separable Minimization 3: The Local Lipschitzian Error Bound Holds for Polyhedral P with Quadratic or Composite f, and for Strongly Convex fResearch Paper

Many problems in statistics, signal processing and machine learning minimize the sum of a smooth function and a convex but nonsmooth one: ℓ1\ell_1ℓ1​-regularized least squares (the Lasso), bound-constrained problems, and group-sparse regression are standard examples. Tseng and Yun (Math. Program. Ser. B 117 (2009) 387–423) proposed the coordinate gradient…

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

A Dual Approach to Solving Nonlinear Programming Problems by Unconstrained Optimization 2: For a Normal Convex Program and Any Dual Optimal ȳ, x̄ Is Optimal iff x̄ Minimizes L_r(·, ȳ)Research Paper

Lagrangian duality turns a constrained minimization problem into the maximization of a dual function over multipliers. For convex programs the duality is clean: under mild conditions the dual optimal value equals the primal one, and an optimal multiplier vector yˉ\bar yyˉ​ exists. Computationally, however, the ordinary Lagrangian has a well-known defect. Knowing…

8 thms4 active usersReviewed
🏆Completed
Discrete GeometryFunctional AnalysisLinear algebra·Captain: mikedeng1

The Geometry of Graphs and Some of Its Algorithmic Applications 2: Euclidean Distortion ≤ c iff Σ_{q>0} q·d² + c²·Σ_{q<0} q·d² ≤ 0 for Every PSD Q with Q·1 = 0Research Paper

Many algorithms for graphs and finite metric spaces begin by placing the points in a geometric space and then working with the geometry. Euclidean space is the most convenient target: distances there are controlled by inner products, so the question "where should the points go?" becomes a question about matrices. Linial, London and Rabinovich (Combinatorica…

6 thms4 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Primal-Dual Interior-Point Methods for Self-Scaled Cones I: After One Short Step from N(β), λ₂(x₊, s₊) ≤ (2 + δ − κ)(ϵ + κ)²/((1 − δ)²(1 − κ)³)Research Paper

Linear programming, second-order cone programming and semidefinite programming are all instances of conic linear programming: minimize a linear function over the intersection of an affine subspace with a closed convex cone. Primal-dual interior-point methods solve these problems in polynomially many iterations and are the algorithms behind most conic…

17 thms4 active usersReviewed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

An Adaptive Algorithm for Finding the Optimal Base-Stock Policy in Lost Sales Inventory Systems with Censored Demand: Adaptive(α, β) Has Per-Period Regret O(N(L)^(−1/3)) at α = β = 1/2Research Paper

Periodic-review inventory systems with lost sales and a positive replenishment lead time are a basic model of retail and spare-parts operations: demand that cannot be met from stock is lost, and an order placed today arrives τ\tauτ periods later. Even with a known demand distribution the optimal policy depends on the whole vector of outstanding orders and is…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Deterministic Equivalents for Optimizing and Satisficing under Chance Constraints 2: The Fractional P-Model Program (38) Has the Same Supremum as the Convex Program (39)Research Paper

A chance constraint limits the probability of violating a requirement rather than requiring that requirement to hold for every realization of uncertain data. Charnes and Cooper developed deterministic optimization problems for several ways of judging decisions under such constraints. Their P model gives a satisficing objective: increase the probability of…

6 thms4 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Convergence Analysis of a Proximal-Like Minimization Algorithm Using Bregman Functions: PMD Attains f(xⁿ) − f(u) ≤ σₙ⁻¹D_ψ(u, x⁰) and Its Iterates Converge to a MinimizerResearch Paper

Convex minimization often has a simple objective but no useful closed form for its minimizer. A proximal method replaces one difficult minimization by a sequence of regularized minimizations. The familiar quadratic regularizer treats all directions through a Euclidean norm. In applications with nonnegative variables, entropy-like geometry can be more…

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

Wait-and-Judge Scenario Optimization 1: For Convex Programs, Seeing s_N Support Constraints Gives P^N{V(x_N) > ε(s_N)} ≤ γ, the Value of the Variational Problem (10)Research Paper

Many decision problems in control, finance and engineering must hold against an uncertain parameter δ\deltaδ whose distribution is unknown, while samples of δ\deltaδ (measurements, historical records, simulations) are available. The scenario approach replaces the uncertain constraint by the constraints of the NNN observed samples and solves the resulting convex…

12 thms4 active usersReviewed
🏆Completed
Linear algebraMachine LearningOptimization·Captain: mikedeng1

Adaptive Subgradient Methods for Online Learning and Stochastic Optimization 2: Full-Matrix AdaGrad's Regret Is Bounded by tr(G_T^{1/2})Research Paper

Online convex optimization is the standard model for learning from a stream of data: in round ttt a learner commits to a point xtx_txt​ in a convex set X⊆Rd\mathcal X\subseteq\mathbb R^dX⊆Rd, a convex loss ftf_tft​ is revealed, and the learner pays ft(xt)+φ(xt)f_t(x_t)+\varphi(x_t)ft​(xt​)+φ(xt​), where φ\varphiφ is a fixed regularizer. Subgradient methods for this model use one fixed geometry (usually…

16 thms4 active usersReviewed
🏆Completed
Machine LearningOptimization·Captain: mikedeng1

Convex Optimization: Algorithms and Complexity V: Projected Gradient Descent on a Convex β-Smooth Function Has Rate (3β‖x₁ − x*‖² + f(x₁) − f(x*))/tTextbook

Many optimization problems in statistics, machine learning and operations research ask to minimize a smooth convex function over a simple convex set: a box, a ball, a simplex, a cone of positive semidefinite matrices. Projected gradient descent is the most basic first-order method for such problems. It takes a gradient step and then returns to the feasible…

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

Convex Optimization: Algorithms and Complexity I: The Center of Gravity Method Satisfies f(x_t) − min f ≤ 2B(1 − 1/e)^{t/n}Textbook

Black-box convex optimization asks how many queries to an oracle are needed to minimize a convex function to accuracy ε\varepsilonε. In fixed dimension nnn the answer is of order nlog⁡(1/ε)n\log(1/\varepsilon)nlog(1/ε), and the first algorithm to attain it is the center of gravity method, discovered independently by Levin (1965) and Newman (1965). It is the opening example of cutt…

9 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Data-Driven Robust Optimization VI: The Moment Set U^CS Has Support Function μ̂ᵀv + Γ₁‖v‖ + √(1/ε − 1)‖Cv‖, an Upper Bound on the Worst-Case Value at RiskResearch Paper

In robust optimization, a constraint is checked against every parameter value in an uncertainty set. This turns uncertainty into a deterministic optimization problem, but the set must be chosen carefully: a large set can make decisions unnecessarily conservative, while a small one can miss likely outcomes. Bertsimas, Gupta and Kallus use data to calibrate…

11 thms4 active users
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Data-Driven Robust Optimization IV: The Forward–Backward Deviation Set U^FB Has a Closed-Form Support Function That Bounds the Worst-Case Value at RiskResearch Paper

A robust linear constraint u⊤v≤tu^\top v \le tu⊤v≤t with uuu ranging over an uncertainty set U⊆Rd\mathcal U\subseteq\mathbb R^dU⊆Rd is tractable whenever the support function δ∗(v∣U)=sup⁡u∈Uu⊤v\delta^*(v\mid\mathcal U)=\sup_{u\in\mathcal U}u^\top vδ∗(v∣U)=supu∈U​u⊤v is. Robust optimization gains a probabilistic meaning when U\mathcal UU is chosen so that every robustly feasible decision also satisfies the…

18 thms4 active users
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Data-Driven Robust Optimization III: For Independent Marginals, the Kolmogorov–Smirnov Set U^I Has Support Function (19) and Bounds the Worst-Case Value at RiskResearch Paper

A robust linear constraint f(u,x)≤0f(\mathbf u,\mathbf x)\le 0f(u,x)≤0 for all u∈U\mathbf u\in\mathcal Uu∈U replaces an uncertain parameter u~\tilde{\mathbf u}u~ by a deterministic uncertainty set U⊆Rd\mathcal U\subseteq\mathbb R^dU⊆Rd. Bertsimas, Gupta and Kallus (arXiv:1401.0212v2; Math. Program. 167, 2018) build such sets directly from data. Their requirement is a probabilistic guarantee:…

14 thms4 active users
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Data-Driven Robust Optimization II: With Known Finite Support, the χ² and G Uncertainty Sets Bound the Worst-Case Value at Risk over Their Confidence RegionsResearch Paper

Robust optimization replaces uncertain data by a set of possible values and requires a decision to work for every value in that set. A central question is how to choose the set from data so that robust feasibility also gives a specified chance of satisfying the original constraint. Bertsimas, Gupta, and Kallus study this question for several sampling models…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Data-Driven Robust Optimization I: An Uncertainty Set Whose Support Function Dominates Value at Risk Implies a Probabilistic Guarantee for Every Concave ConstraintResearch Paper

Robust optimization replaces an uncertain constraint f(u~,x)≤0f(\tilde{\mathbf u},\mathbf x)\le 0f(u~,x)≤0, whose parameter u~∈Rd\tilde{\mathbf u}\in\mathbb R^du~∈Rd is random, by the requirement that the constraint hold for every u\mathbf uu in a chosen uncertainty set U\mathcal UU:

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

Deriving Robust Counterparts of Nonlinear Uncertain Inequalities: For a Regular Nominal Vector, a Concave Uncertain Constraint Holds Robustly iff Its Fenchel Counterpart (FRC) Is SolvableResearch Paper

In robust optimization, a decision must satisfy a constraint for every parameter value in a prescribed uncertainty set. A nonlinear uncertain constraint can be difficult to use directly because it contains a universal condition over a continuum of parameters. Ben-Tal, den Hertog, and Vial study constraints whose value is concave in the uncertain parameter.…

7 thms4 active usersReviewed
PreviousPage 7 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