Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Optimization

2,311 missions · 1,746 completed

Missions

Open565Completed1746All2311
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research·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
Operations ResearchProbability·Captain: mikedeng1

On the Value of Mix Flexibility and Dual Sourcing in Unreliable Newsvendor Networks 2: Under Perfect Reliability the Flexibility Premium Is Nonnegative for Every Nondecreasing UtilityResearch Paper

A manufacturer that makes several products must decide, before demand is known, how much capacity to buy. It can buy dedicated capacity, one resource per product, or a single flexible resource that can make every product. Flexible capacity pools demand: a surplus of one product's demand can be served by capacity that would otherwise sit idle. A common…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem III: Nearest and Cheapest Insertion Are Within a Factor of TwoResearch Paper

The traveling salesman problem (TSP) asks for a shortest closed route through a finite set of points. It is NP-hard, and in practice tours are built by fast constructive heuristics whose output is then improved or used as is. A central question in the analysis of algorithms, raised in this form by Rosenkrantz, Stearns and Lewis in 1977, is how far such a…

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

On the Value of Mix Flexibility and Dual Sourcing in Unreliable Newsvendor Networks 1: The Risk-Neutral Flexibility Premium Is Nonnegative for Every ReliabilityResearch Paper

A firm that sells several products must decide, before demand is known, how much production capacity to build and of what kind. Dedicated capacity makes one product; flexible capacity makes any of them. The classic argument for flexibility is demand pooling: capacity that can follow demand to whichever product needs it wastes less than capacity locked to…

10 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research·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
Operations Research·Captain: mikedeng1

An Interactive Weighted Tchebycheff Procedure for Multiple Objective Programming II: The Lexicographic Weighted Tchebycheff Program Characterizes the Nondominated SetResearch Paper

A multiple objective program asks to maximize kkk objectives f1(x),…,fk(x)f_1(x),\dots,f_k(x)f1​(x),…,fk​(x) simultaneously over a feasible set SSS. There is usually no point that is best in every objective, so the object of interest is the set of nondominated criterion vectors: those that cannot be improved in one objective without being worsened in another. Interactive procedures for…

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

An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs II: The Due-Date Schedule at the Least Feasible Cost Level Minimizes the Maximum Deferral CostResearch Paper

Single-machine sequencing with deferral costs asks how to order jobs when the price of finishing a job depends on when it finishes. A job completed at time sss incurs the cost Pi(s)P_i(s)Pi​(s); lateness penalties, holding costs and service-level penalties are special cases. Two objectives are standard: the sum of the costs, studied by McNaughton (Management Science…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationDiscrete GeometryOperations Research·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 Research·Captain: mikedeng1

Cubic Regularization of Newton Method and Its Global Performance III: Linear-Then-Superlinear Rate on Gradient-Dominated Functions of Degree TwoResearch Paper

Newton's method converges quadratically near a non-degenerate minimum, but on its own it has no global guarantee: far from a minimizer the Newton step may increase the objective, and at points where the Hessian is indefinite it may not even be a descent direction. For most of the method's history, the global behaviour of second-order methods was controlled…

15 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·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
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions III: Guarantees of Deterministic Local SearchResearch Paper

Many optimization problems ask for a subset of a finite ground set that maximizes a function with diminishing returns: the cut of a graph or a directed graph, the value of a facility-location configuration, the entropy of a set of random variables, or a welfare function in combinatorial auctions. These functions are submodular but typically non-monotone:…

14 thms2 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research·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
Numerical AnalysisOperations Research·Captain: mikedeng1

Projected Gradient Methods for Linearly Constrained Problems III: Finite Termination of a Gradient Projection Algorithm for Quadratic ProgrammingResearch Paper

Quadratic programming, the minimisation of a quadratic function subject to linear inequality constraints, is a basic subproblem of nonlinear optimisation (sequential quadratic programming, trust-region methods) and a model in its own right in portfolio selection, least-squares estimation and control. The classical solution methods are active-set methods:…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationOperations Research·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
Convex OptimizationOperations Research·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
Convex OptimizationLinear OptimizationOperations Research·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
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems II: p-Swap Local Search for k-Median Has Locality Gap 3 + 2/pResearch Paper

The k-median problem asks to open kkk facilities among a set of candidate sites so that the total distance from clients to their nearest open facility is as small as possible. It is a basic model of facility location and of clustering, and it is NP-hard, so the question studied in approximation algorithms is how close a polynomial-time method can get to the…

8 thms2 active usersReviewed
🏆Completed
Numerical AnalysisOperations Research·Captain: mikedeng1

A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization I: Global Convergence to Stationary PointsResearch Paper

Line searches are the step-size rules inside most methods for smooth unconstrained minimization min⁡x∈Rnf(x)\min_{x \in \mathbb{R}^n} f(x)minx∈Rn​f(x): steepest descent, conjugate gradient, quasi-Newton and limited-memory methods all choose a direction dkd_kdk​ and then a step αk\alpha_kαk​ along it. Classical Armijo and Wolfe rules are monotone: they require f(xk+1)<f(xk)f(x_{k+1}) < f(x_k)f(xk+1​)<f(xk​). Grippo,…

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

Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 4: Optimal Prices and Discount Time with Myopic Customers and Identical Declining ValuationsResearch Paper

Retailers of fashion and seasonal goods sell a fixed stock over a short season and routinely cut the price part-way through it. The markdown trades off two effects: a late discount keeps early, high-valuation customers paying the full price, while an early discount reaches customers whose interest in the product fades as the season goes on. Aviv and Pazgal (…

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

A Distributional Interpretation of Robust Optimization III: Uncertainty Set Shrinkage Approximates a Two-Scenario Distributionally Robust ProblemResearch Paper

Robust optimization (RO) protects a decision against every parameter value in an uncertainty set. For a decision vvv and a parameter x∈Rmx \in \mathbb{R}^mx∈Rm with objective f(v,x)f(v, x)f(v,x) to be maximized, the robust problem around a nominal parameter x0x_0x0​ with a deviation set Δ\DeltaΔ is

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

A Distributional Interpretation of Robust Optimization I: Robust Optimization over Overlapping Uncertainty Sets Equals a Distributionally Robust Stochastic ProgramResearch Paper

Robust optimization (RO) protects a decision against every realisation of an uncertain parameter in a prescribed uncertainty set; distributionally robust stochastic programming (DRSP) protects it against every probability distribution in a prescribed distribution set. The two paradigms are usually treated separately. When the n uncertain parameters live in…

5 thms2 active usersReviewed
🏆Completed
Discrete GeometryLinear OptimizationOperations Research·Captain: mikedeng1

Maximal Lattice-Free Convex Sets in Linear Subspaces II: Minimal Valid Inequalities Come from Maximal Lattice-Free Convex SetsResearch Paper

Cutting planes for mixed-integer linear programs are often derived from a few rows of an optimal simplex tableau. Keeping qqq rows for basic integer variables x1,…,xqx_1,\dots,x_qx1​,…,xq​, dropping the nonnegativity of xxx (Gomory's corner polyhedron, Gomory 1969) and then the integrality of the nonbasic variables leaves the set of s≥0s\ge0s≥0 with f+∑jrjsj∈Zqf+\sum_j r^js_j\in\mathbb Z^qf+∑j​rjsj​∈Zq.…

16 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·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
Operations Research·Captain: mikedeng1

An Interactive Weighted Tchebycheff Procedure for Multiple Objective Programming I: In the Finite Case the Augmented Weighted Tchebycheff Program Characterizes the Nondominated SetResearch Paper

A decision problem with several conflicting objectives, such as cost, risk and service level, has no single optimum. What it has is a set of nondominated outcomes: those that cannot be improved in one objective without being worsened in another. Interactive methods of multiple objective programming search this set with a decision-maker, and at each step…

11 thms2 active usersReviewed
🏆Completed
Linear OptimizationMachine LearningOperations Research+2·Captain: mikedeng1

Distributionally Robust Logistic Regression II: Worst- and Best-Case Misclassification Risks over a Wasserstein Ball Are Linear ProgramsResearch Paper

A logistic regression model is fitted on finitely many samples, and the quantity a practitioner cares about is the misclassification risk of the fitted classifier on new data. Its empirical counterpart, the training error, is biased downwards, and classical generalization bounds give it an additive margin that depends on a complexity measure of the model…

8 thms2 active usersReviewed
PreviousPage 85 of 93Next

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