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

Missions

Open583Completed1728All2311
🏆Completed
Convex Optimization·Captain: mikedeng1

Error Bounds, Quadratic Growth, and Linear Convergence of Proximal Methods II: Dual Strict Complementarity and Firm Convexity of the Components Give the Error Bound for f(Ax) + g(x)Research Paper

Proximal gradient methods are used to minimize an objective with one smooth part and one convex part whose proximal map can be evaluated. A small proximal gradient step is a practical stopping signal, but it indicates proximity to an optimizer only when the objective has an appropriate error bound. Section 4 of Drusvyatskiy and Lewis gives conditions for…

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

Approximation Algorithms for Product Framing and Pricing 1: The NEST Framing Algorithm Earns at Least 6/π² of the Optimal Expected Revenue When Page Views Are NBUEResearch Paper

An online retailer does not show its catalogue at once. Products are arranged on a sequence of pages, and a consumer looks at the first few pages and then chooses among what she has seen, or leaves. Where a product is placed therefore decides whether it is considered at all. Gallego, Li, Truong and Wang (Operations Research, 2020) call the placement…

16 thms2 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

Extrapolated Proximal Subgradient Algorithms for Nonconvex and Nonsmooth Fractional Programs 3: Enhanced e-PSG Cluster Points Are Strong Lifted Stationary Points for Max-Type DenominatorsResearch Paper

Fractional programs minimize a ratio f(x)/g(x)f(x)/g(x)f(x)/g(x) over a constraint set. They arise whenever a quantity has to be normalized: the scale-invariant sparse recovery model minimizes ∥x∥1/∥x∥2\|x\|_1/\|x\|_2∥x∥1​/∥x∥2​ (Rahimi, Wang, Dong, Lou 2019), robust Sharpe-ratio portfolio selection maximizes a mean-to-worst-case-risk ratio, and generalized eigenvalue problems minimize Rayleigh…

16 thms2 active usersReviewed
🏆Completed
Convex OptimizationNumerical Analysis·Captain: mikedeng1

From Error Bounds to the Complexity of First-Order Descent Methods for Convex Functions 3: ISTA for ℓ1-Regularized Least Squares Satisfies f(x_k) − min f ≤ (f(x_0) − min f)/q^k with q = 1 + 2aγ_R/b²Research Paper

The ℓ1-regularized least squares problem (the Lasso, or basis pursuit denoising) is the model problem of compressed sensing and sparse inverse problems: given a matrix A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n, data d∈Rmd\in\mathbb R^md∈Rm and a weight μ>0\mu>0μ>0, one seeks a vector xxx that fits Ax≈dAx\approx dAx≈d while having few nonzero entries. The standard first-order method for it is the i…

14 thms2 active usersReviewed
🏆Completed
Statistics·Captain: mikedeng1

Fast Best Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms II: CD-PSI(k) Terminates Finitely at a Partial Swap Inescapable Minimum of Order kResearch Paper

Best subset selection asks for the linear model that fits a response with as few predictors as possible. It is a basic problem of statistics and a standard test case for mixed-integer optimization. The penalized form

8 thms2 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold: Every Limit Point of ManPG Is Stationary, and an ε-Stationary Point Is Reached Within ⌈2L(F(X₀)−F*)/(γᾱε²)⌉ IterationsResearch Paper

Many problems in statistics and signal processing ask for an orthonormal frame X∈Rn×rX\in\mathbb R^{n\times r}X∈Rn×r that is both a good fit to the data and sparse or otherwise structured. Sparse principal component analysis, compressed modes in physics, unsupervised feature selection and sparse blind deconvolution all take the form

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

Proximal Algorithms II: The Proximal Operator of a Norm Is v − λΠ_B(v/λ), B the Unit Ball of the Dual NormResearch Paper

Norms are the most common nonsmooth terms in convex optimization models. The ℓ1\ell_1ℓ1​ norm promotes sparsity in the lasso and in compressed sensing, the Euclidean norm of blocks of variables promotes group sparsity in the group lasso, and the nuclear norm promotes low rank. First-order methods for such models, notably the proximal gradient method, ADMM and…

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

Constrained Assortment Optimization for the Nested Logit Model 6: Under Space Constraints, the Linear Program (13) over Knapsack-Relaxation Solutions Bounds the Optimal Expected RevenueResearch Paper

A retailer that sells products in several categories has to decide which products to put on display. Under the nested logit model a customer first picks a category (a nest) and then a product inside it, so offering a product changes the purchase probabilities of every other product. Choosing the assortment that maximizes expected revenue is assortment…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationMachine Learning·Captain: mikedeng1

Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization 2: For f = ‖x‖², Every k-Sparse Point of the Simplex Has Duality Gap ≥ 2/kResearch Paper

The Frank–Wolfe algorithm minimizes a smooth convex objective over a compact convex domain by choosing an atom through a linear optimization problem and moving toward it. On a domain that is the convex hull of atoms, each ordinary iteration introduces at most one new atom. That makes the method useful when a solution represented with few atoms is valuable,…

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

Constrained Assortment Optimization for the Nested Logit Model 1: The Assortment Stitched from the Linear Program (4) Is the Best Among All Combinations of the Candidate AssortmentsResearch Paper

An assortment planner chooses which products to offer to arriving customers. When products are grouped into nests, a customer's choice of nest depends on all the assortments offered at once. A planner may nevertheless be able to generate only a short list of promising assortments for each nest. The remaining task is to choose one assortment from each list…

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

Constrained Assortment Optimization for the Nested Logit Model 5: For Joint Assortment and Pricing, O(pb²) Candidate Assortments per Nest Include an Optimal Solution of Problem (7) for Every u ≥ 0Research Paper

A retailer that sells through a choice model decides two things at once: which products to put on the shelf and at what price. Under the nested logit model of discrete choice, products are grouped into nests (brands, categories, store sections); a customer first picks a nest, or leaves without buying, and then picks a product inside the nest. The price of a…

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

A Primal-Dual Interior-Point Algorithm for Nonsymmetric Exponential-Cone Optimization 2: Rank-One Recursions Factor Y₀(Y₀ᵀS₀)⁻¹Y₀ᵀ = VVᵀ and S₀(Y₀ᵀS₀)⁻¹S₀ᵀ = UUᵀResearch Paper

Quasi-Newton methods replace the Hessian of an objective by a matrix H≻0H \succ 0H≻0 that is updated from observed pairs of steps and gradient changes. The secant equation HS=YHS = YHS=Y asks the new matrix to map the observed steps SSS to the observed changes YYY. The best-known update is BFGS, which for ppp simultaneous pairs S,Y∈Rn×pS, Y \in \mathbb{R}^{n\times p}S,Y∈Rn×p reads

7 thms2 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Proximal Alternating Linearized Minimization for Nonconvex and Nonsmooth Problems II: The Proximal Map of the Nonnegative Sparsity Constraint Is Hard Thresholding of the Positive PartResearch Paper

Nonnegative matrix factorization (NMF) approximates a data matrix A∈Rm×nA\in\mathbb R^{m\times n}A∈Rm×n by a product XYXYXY of two nonnegative factors. Adding a cap on the number of nonzero entries of each factor gives sparse NMF, used in signal separation, text mining and image analysis because sparse nonnegative factors are easier to interpret. Bolte, Sabach and Teboulle…

6 thms2 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Proximal Alternating Linearized Minimization for Nonconvex and Nonsmooth Problems I: Every Bounded PALM Sequence of a KL Function Has Finite Length and Converges to a Critical PointResearch Paper

Many problems in data analysis and signal processing are posed as minimizing a sum of three terms over two blocks of variables: a nonsmooth function of the first block, a nonsmooth function of the second block, and a smooth coupling term. Nonnegative and sparse matrix factorization, blind deconvolution and dictionary learning all have this form, with…

17 thms2 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms III: Accumulation Points of the Greedy Sparse-Simplex Method Are Coordinate-Wise MinimaResearch Paper

Many estimation problems in signal processing and statistics look for a vector with few nonzero entries that fits data well. Compressed sensing (Donoho 2006) recovers a sparse xxx from linear measurements by minimizing ∥Ax−b∥2\|Ax-b\|^2∥Ax−b∥2 over sparse vectors. Sub-wavelength optical imaging and phase retrieval (Shechtman, Eldar, Szameit, Segev 2011) lead to the same…

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

An Exact Algorithm for the Two-Echelon Capacitated Vehicle Routing Problem 1: The Multiple-Choice Knapsack Relaxation Gives a Valid Lower Bound for Every Admissible Choice of PenaltiesResearch Paper

In city logistics, goods often cannot be carried by large trucks all the way to the final customers. A common design routes the goods through intermediate depots, called satellites: large first-level vehicles carry freight from a central depot to the satellites, and small second-level vehicles deliver it from the satellites to the customers. The two-echelon…

10 thms2 active usersReviewed
🏆Completed
Numerical Analysis·Captain: mikedeng1

Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms I: Every Coordinate-Wise Minimum Is an L2(f)-Stationary PointResearch Paper

Many problems in signal processing, statistics and machine learning ask for a minimizer of a smooth loss among vectors with few nonzero entries: compressed sensing with a nonlinear measurement model, sparse regression with a non-quadratic loss, sparse phase retrieval. The common abstraction is the sparsity constrained problem

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

A Hybrid Genetic Algorithm for Multidepot and Periodic Vehicle Routing Problems: Biased-Fitness Survivor Selection Never Removes an Elite Individual Outside XResearch Paper

Genetic algorithms with local search ("memetic" or hybrid genetic algorithms) are among the most effective heuristics for vehicle routing. Their recurring weakness is premature convergence: selection and local improvement both favour good individuals, so the population fills with near-copies of a few solutions and the search stalls. Vidal, Crainic,…

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

Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model 3: Robust Dynamic Assortments Grow with Remaining Capacity and over TimeResearch Paper

Single-leg capacity allocation under customer choice is the basic dynamic problem of revenue management: a firm holds a fixed stock of a perishable resource (seats on a flight leg, rooms on a night), and in every period of a finite selling horizon it decides which products (fare classes) to offer to the arriving customer. Talluri and van Ryzin (Management…

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

Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model 2: Rectangular Uncertainty Reduces the Size-Constrained Robust Problem to Known Weights (u₀, l₁, …, lₙ)Research Paper

Assortment optimization is the problem a retailer faces in deciding which subset of its products to put in front of customers. Under the multinomial logit (MNL) choice model each product carries a preference weight, and a customer facing an offered set buys each product with probability proportional to its weight, or buys nothing. The optimal assortment…

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

Hedging Inventory Risk Through Market Instruments II: A Small Fair Hedge Raises the Newsvendor's Expected UtilityResearch Paper

A retailer that orders stock months before the selling season carries inventory risk: its profit depends on a demand it cannot observe when it commits. For many goods that demand moves with a quantity traded on financial markets: sales of housing-related products with an interest-rate or construction index, sales of fashion or luxury goods with a stock…

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

Quantity Flexibility Contracts and Supply Chain Performance 2: The Minimum Commitment Policy Is Optimal for the Open-Loop Program (F-OLFC) and AdmissibleResearch Paper

Manufacturers routinely share rolling schedules with their suppliers: each period the buyer commits to a purchase for the current period and issues non-binding estimates for future periods, then revises those estimates as the horizon rolls forward. Unconstrained revisions push forecast risk upstream and are a recognized source of the bullwhip effect. A quant…

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

Robust Assortment Optimization in Revenue Management Under the Multinomial Logit Choice Model 1: The Optimal Robust Assortment Is Revenue-Ordered, S*(V) = {i : rᵢ > Z*(V)}Research Paper

Assortment optimization asks which subset of products a firm should offer when customers choose among the offered products, or leave without buying. It underlies shelf-space planning in retail, the choice of which fare classes to keep open in airline revenue management, and the selection of items shown on a web page. The multinomial logit (MNL) model is the…

9 thms2 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 5: RCDM with Adaptive Lipschitz Estimates (RACDM) Has Expected Error at Most 8nR₁²(x₀)/(16 + 3k)Research Paper

Random coordinate descent minimizes a smooth convex function f:Rn→Rf:\mathbb R^n\to\mathbb Rf:Rn→R by updating one coordinate at a time, chosen at random. Each iteration needs a single partial derivative instead of the full gradient, which is what makes the method usable on problems whose dimension is in the millions or billions ("huge-scale" problems). Nesterov's…

8 thms2 active usersReviewed
🏆Completed
AnalysisNumerical Analysis·Captain: mikedeng1

Nonsmooth Optimization via Quasi-Newton Methods II: The Bisection Armijo–Wolfe Line Search Terminates When Every Left Limit of h′ ExistsResearch Paper

Quasi-Newton methods such as BFGS were designed for smooth objectives, yet in practice they are routinely and successfully applied to nonsmooth functions. Lewis and Overton (Math. Program. 141 (2013) 135–163) study why. A quasi-Newton step needs a step length along each search direction, and on a nonsmooth function the usual line searches have to decide…

7 thms2 active usersReviewed
PreviousPage 56 of 70Next

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