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,749 completed

Missions

Open562Completed1749All2311
🏆Completed
Convex OptimizationMachine LearningOperations Research+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
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems IV: Greedy Set Cover C1 Has Worst-Case Ratio H(k) on SC(k)Research Paper

Set covering asks for the fewest members of a family of sets whose union is everything the family covers. It models crew scheduling, facility siting, test-suite reduction, logic minimization and fault testing; Johnson names the last two as its practical applications. Karp showed in 1972 that the decision version is NP-complete (Karp 1972), so in practice…

8 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisTheoretical Computer Science·Captain: mikedeng1

Sparse Approximate Solutions to Linear Systems 1: The Column Bound for Greedy SelectionResearch Paper

Many problems in scientific computing and statistics ask for a solution of a linear system Ax≈bAx\approx bAx≈b that uses as few unknowns as possible. In statistics this is subset selection (Golub and Van Loan, Matrix Computations, 1983). In coding theory over binary matrices it is the minimum weight solution problem (Gallager, 1968). Natarajan's own motivation was r…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems II: The Greedy Literal Algorithm B1 Has Worst-Case Ratio (k+1)/k on MS(k)Research Paper

Maximum satisfiability asks for a truth assignment satisfying as many clauses of a propositional formula as possible. The paper notes that the restriction MS(k)MS(k)MS(k), in which every clause has at least kkk literals, is polynomial complete for every k≥1k \ge 1k≥1, so exact optimization is out of reach in general and one asks instead how close a fast algorithm is…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems I: The Subset-Sum Algorithms A_k Have Worst-Case Ratio (k+1)/kResearch Paper

David S. Johnson's 1974 paper Approximation Algorithms for Combinatorial Problems (J. Comput. System Sci. 9 (1974) 256–278) is one of the founding papers of the theory of approximation algorithms. It asks, for optimization problems whose decision versions Karp had just shown to be polynomial complete, how close a fast heuristic can be guaranteed to come to…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs I: Moore's Algorithm Yields a Schedule with the Minimum Number of Late JobsResearch Paper

A single machine must process a set of jobs, each with a processing time and a due-date, and a job that finishes after its due-date is late. Counting late jobs is the natural objective when a late order is simply lost, whatever its lateness. In the three-field notation of scheduling theory this is the problem 1 ∥ ∑Uj1\,\|\,\sum U_j1∥∑Uj​, and it is one of the few…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Scheduling with Deadlines and Loss Functions: On One Processor, Decreasing Penalty-to-Length Order Is Optimal When No Task Finishes Before Its DeadlineResearch Paper

A processor, a machine shop or a single server must work through a set of jobs one at a time, and each job is costly when it is late. Deciding the order is the single-machine sequencing problem, the simplest and most studied model of scheduling theory. Robert McNaughton's 1959 article Scheduling with Deadlines and Loss Functions (Management Science…

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

A Supply Chain Theory of Factoring and Reverse Factoring 1: The Supplier's Equilibrium Choice Among Recourse, Non-Recourse and Reverse FactoringResearch Paper

Small and medium-sized suppliers that sell to large retailers typically ship first and are paid weeks or months later. Until the invoice is paid, the supplier's cash is trapped in accounts receivable, while production has to be financed up front. Factoring (selling or pledging the receivable to a financial intermediary for immediate cash) and reverse…

8 thms2 active usersReviewed
🏆Completed
Control TheoryConvex OptimizationOperations Research·Captain: mikedeng1

Robust Solutions to Uncertain Semidefinite Programs II: An SDP Inner Approximation of the Robust Feasible Set under Structured PerturbationsResearch Paper

A semidefinite program (SDP) minimizes a linear objective cTxc^TxcTx subject to a linear matrix inequality F(x)=F0+∑i=1mxiFi⪰0F(x) = F_0 + \sum_{i=1}^m x_i F_i \succeq 0F(x)=F0​+∑i=1m​xi​Fi​⪰0. In engineering applications the coefficient matrices are rarely known exactly: they come from measurements, from a model of a physical plant, or from a finite-precision implementation. El Ghaoui, Oustry and Lebret…

5 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations Research·Captain: mikedeng1

Integrating Replenishment Decisions with Advance Demand Information II: With Zero Set-up Cost the Myopic Base-Stock Policy Is Optimal When Myopic Levels Are NondecreasingResearch Paper

Many firms learn about demand before it has to be served: customers place orders days or weeks ahead of the date they want delivery. Gallego and Özer (Management Science 47(10), 2001) model this advance demand information in a periodic-review inventory system and ask how the optimal replenishment policy should use it. Classical inventory theory (Arrow,…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research·Captain: mikedeng1

Validation of Subgradient Optimization I: The Core Problem Built from the Subgradient Iterates Solves the Dual Linear ProgramResearch Paper

Subgradient optimization maximizes a concave function that is not differentiable by stepping along an arbitrary subgradient with a prescribed sequence of step sizes. It became a standard tool of integer programming after Held and Karp used it to compute the Lagrangian 1-tree bound for the traveling-salesman problem (Held & Karp 1971). Held, Wolfe and…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis+1·Captain: mikedeng1

Robust Solutions to Least-Squares Problems with Uncertain Data II: Robust Least Squares as Tikhonov RegularizationResearch Paper

Least squares fits a linear model Ax≃bAx \simeq bAx≃b by minimizing ∥Ax−b∥\|Ax - b\|∥Ax−b∥, and its solution can be extremely sensitive to errors in the data (A,b)(A, b)(A,b) when AAA is ill-conditioned. The standard remedy is Tikhonov regularization (ridge regression): minimize ∥Ax−b∥2+μ∥x∥2\|Ax - b\|^2 + \mu\|x\|^2∥Ax−b∥2+μ∥x∥2, whose solution x=(A⊤A+μI)−1A⊤bx = (A^\top A + \mu I)^{-1}A^\top bx=(A⊤A+μI)−1A⊤b is stable but depends on a…

9 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Linear-Time Approximation for Maximum Weight Matching: The Approximation Guarantee of the Scaling AlgorithmResearch Paper

The maximum weight matching (MWM) problem asks, for a graph with edge weights, for a set of vertex-disjoint edges of largest total weight. It is a central problem of combinatorial optimization, with applications to transportation, assignment and scheduling, and as a subroutine for shortest paths, planar max cut, Chinese postman tours and metric TSP.…

12 thms2 active usersReviewed
Control TheoryOperations Research·Captain: mikedeng1

Optimizing Static Linear Feedback: Gradient Method II: The Gradient Flow Stays in the Sublevel Set and Converges Exponentially under State FeedbackResearch Paper

The linear-quadratic regulator (LQR) is the basic problem of optimal control: steer a linear system x˙=Ax+Bu\dot x = Ax + Bux˙=Ax+Bu so as to minimize an integrated quadratic cost of state and input. When the full state is measured, the optimal law is a static linear feedback u=−Kxu = -Kxu=−Kx obtained from an algebraic Riccati equation. When only an output y=Cxy = Cxy=Cx is measured, the…

13 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebra·Captain: mikedeng1

A Singular Value Thresholding Algorithm for Matrix Completion 3: Convergence to the Minimum Nuclear Norm SolutionResearch Paper

Nuclear norm minimization is the standard convex surrogate for rank minimization: to recover a low-rank matrix from a few linear measurements, or from a subset of its entries, one minimizes the sum of the singular values subject to the data constraints. For matrix completion, Candès and Recht (Found. Comput. Math. 2009) showed that this convex program…

8 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis·Captain: mikedeng1

A Singular Value Thresholding Algorithm for Matrix Completion 2: Convergence of the SVT Iteration under General Convex ConstraintsResearch Paper

Singular value thresholding (SVT) is a first-order method introduced by Cai, Candès and Shen (SIAM J. Optim. 20 (2010)) for recovering a low-rank matrix from incomplete or indirect information. Its basic form, for matrix completion, alternates a soft-thresholding of singular values with a gradient step on a dual variable, and needs only one sparse singular…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis·Captain: mikedeng1

A Singular Value Thresholding Algorithm for Matrix Completion 1: The SVT Iteration Converges to the Unique Solution of the Proximal ProblemResearch Paper

Matrix completion asks to recover an n1×n2n_1\times n_2n1​×n2​ matrix MMM from a subset Ω\OmegaΩ of its entries. When MMM has low rank, a standard convex surrogate is to minimize the nuclear norm ∥X∥∗\|X\|_*∥X∥∗​ (the sum of the singular values) subject to agreeing with MMM on Ω\OmegaΩ; Candès and Recht showed that this recovers MMM exactly under incoherence and sampling conditions (Candès–…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems 1: The Augmentation Bound for Shortest Augmenting PathsResearch Paper

The maximum flow problem asks how much of a commodity can be sent from a source to a sink through a network whose arcs have capacities. It is a basic model in operations research, underlies bipartite matching, transportation and scheduling problems, and is a standard subroutine inside larger combinatorial algorithms.

24 thms2 active usersReviewed
🏆Completed
Convex OptimizationFunctional AnalysisOperations Research·Captain: mikedeng1

A Three-Operator Splitting Scheme and its Optimization Applications 1: Weak and Strong Convergence of the Three-Operator Splitting IterationResearch Paper

Many problems in convex optimization, variational inequalities and signal processing reduce to a monotone inclusion: find a point xxx at which the sum of several monotone operators contains 000. When the sum has two terms, the classical operator-splitting methods (Douglas–Rachford, forward–backward, forward–backward–forward) solve it by iterating a fixed-point…

14 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research·Captain: mikedeng1

On Minimizing a Convex Function Subject to Linear Inequalities II: Optimality Conditions for the Sum of the Largest Linear FormsResearch Paper

In 1955 E. M. L. Beale showed how Dantzig's simplex method, which was built for linear objectives, can be carried over to certain nonlinear convex objectives that are minimized subject to linear inequalities (Beale 1955). Section 4 of that paper treats one such objective: the sum of the ttt largest of a set of ggg linear forms. Beale's motivation comes from the…

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

Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 3: Optimal Contingent-Pricing Revenue with Myopic Customers and Exponential ValuationsResearch Paper

Retailers of seasonal goods (fashion, electronics, holiday items) sell a fixed stock over a short season and routinely cut prices toward its end. A markdown of this kind segments the market over time: customers with high valuations buy early at a premium price, and customers with lower valuations are served later at a discount price. Aviv and Pazgal (MSOM…

6 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Optimal Pricing of Seasonal Products in the Presence of Forward-Looking Consumers 1: Threshold Purchasing Policies under Contingent PricingResearch Paper

Retailers of fashion and seasonal goods sell at a premium price early in the season and mark the remaining stock down later. When customers anticipate the markdown, some of them who would buy at the premium price instead wait, trading a lower price against the risk that the item sells out and against the decline of their own valuation over the season. How…

5 thms2 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits II: The Iteration Bound of Coordinate DescentResearch Paper

In the contextual bandit problem a learner repeatedly observes a context, picks one of KKK actions, and sees the reward of that action only. Against a finite class Π\PiΠ of policies, statistically optimal regret of order KTln⁡∣Π∣\sqrt{KT\ln|\Pi|}KTln∣Π∣​ has been known since EXP4 (Auer et al., 2002), but EXP4 maintains a weight per policy and costs Ω(∣Π∣)\Omega(|\Pi|)Ω(∣Π∣) time per…

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

Elementare Theorie der konvexen Polyeder I: A Point on All Extreme Supports of a Finite Cone Is a Nonnegative Combination of at Most n GeneratorsResearch Paper

A polyhedral cone can be described in two ways: as the set of nonnegative combinations of finitely many vectors (a finitely generated cone), or as the intersection of finitely many closed half-spaces through the origin. That the two descriptions give the same class of sets is the Minkowski–Weyl theorem. It is the structural basis of linear programming: the…

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

An Analysis of Several Heuristics for the Traveling Salesman Problem II: Every Insertion Method Is Within ⌈lg n⌉ + 1 of the Optimal TourResearch Paper

The traveling salesman problem asks for a shortest closed route visiting every node of a weighted complete graph exactly once. It is NP-hard, so practitioners use fast heuristics, and the basic question about a heuristic is how far from optimal its tour can be. Rosenkrantz, Stearns and Lewis (SIAM J. Comput. 6(3), 1977) gave the first systematic worst-case…

10 thms2 active usersReviewed
PreviousPage 86 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