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
Dynamic ProgrammingOperations Research·Captain: mikedeng1

A Functional Equation and Its Application to Resource Allocation and Sequencing Problems 3: The Minimum Weighted Number of Tardy Jobs Is Σ p_j Minus the Value f(n, d_n) of Equation (3)Research Paper

Minimizing the weighted number of tardy jobs on a single machine, written 1∥∑wjUj1\|\sum w_jU_j1∥∑wj​Uj​ in later scheduling notation, is one of the basic due-date objectives: each job either meets its deadline or pays a fixed penalty, and the question is which jobs to sacrifice. Moore (Management Sci. 15, 1968) solved the unweighted case pj=1p_j = 1pj​=1 with a greedy procedure.…

9 thms2 active usersReviewed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming: Generalized M-Estimates Converge in Distribution to the Inverse Contingent Derivative at a GaussianResearch Paper

Maximum likelihood estimates, least-squares fits and sample-average approximations of stochastic programs solve 0=fˉν(x)0 = \bar f^\nu(x)0=fˉ​ν(x), where fˉν\bar f^\nufˉ​ν averages a random integrand over ν\nuν observations. Their classical asymptotic theory rests on the implicit function theorem and needs a smooth, unconstrained problem.

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

A Functional Equation and Its Application to Resource Allocation and Sequencing Problems 1: Equation (1) Computes the Minimum Total Loss of a Fixed Job Order with Two Processing Modes per JobResearch Paper

Many single-machine scheduling problems have a structure that is easy to describe: the jobs must be processed in an order that is already known, and the only decisions are how and when to process each one. Lawler and Moore, in A Functional Equation and Its Application to Resource Allocation and Sequencing Problems (Management Science 16(1), 1969, 77–84),…

4 thms2 active usersReviewed
ProbabilityStatisticsStochastic Systems·Captain: mikedeng1

Stochastic Estimation of the Maximum of a Regression Function: The Kiefer–Wolfowitz Iterates z_n Converge in Probability to the Maximizer θResearch Paper

Many problems in statistics, engineering and operations research ask for the input level xxx at which an unknown response function is largest, when the response can only be measured with noise: the dose that maximizes a yield, the setting that maximizes throughput in a simulation, the parameter that maximizes an expected reward. Robbins and Monro (1951) had…

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

Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems 1: Branch and Bound with the Three-Machine Lower Bound Finds a Minimum-Makespan SequenceResearch Paper

In a flow shop every job passes through the same machines in the same order. Choosing the order in which jobs enter the shop so that the last job finishes as early as possible (minimizing the makespan) is one of the oldest problems of scheduling theory. For two machines Johnson (1954) gave an exact sorting rule; for three machines his rule is exact only in…

13 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems IV: Positive Dynamic Programming — an Extreme Optimal Dual Solution Yields a Pure Stationary Optimal PolicyTextbook

A finite Markov decision system asks how to choose actions while a changing state controls which actions are available. The choice can affect both the reward now and the distribution of future states. In a total-reward problem, the process can continue indefinitely; if transitions are substochastic, it can also terminate. Kallenberg's treatment of positive…

6 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research+2·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems IX: Discounted Semi-Markov Decision Processes — the Value Vector Is the Smallest Superharmonic VectorTextbook

A decision maker may choose an action whenever a system changes state, even though the time until the next change is random. Maintenance and replacement decisions are examples: a repair choice changes both the next operating state and the length of time before another choice is available. A discrete-time Markov decision model gives every decision epoch the…

6 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryDynamic ProgrammingLinear Optimization+1·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems VIII: Single-Controller Stochastic Games — a Dual Pair of Linear Programs Gives the Value and Stationary Optimal PoliciesTextbook

A two-person zero-sum stochastic game (also called a Markov game) is a Markov decision problem with two decision makers who pull in opposite directions: at every time point both players choose an action simultaneously, one player pays the other, and the system moves to a random next state whose law depends on the current state and both actions. Stochastic…

7 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems II: An Extreme Optimal Solution of the Dual Linear Program Yields a Pure Stationary Policy Optimal among Transient PoliciesTextbook

A Markov decision model describes a system that repeatedly occupies a state, receives a reward when an action is chosen, and then moves according to action-dependent probabilities. Termination may occur after any action. In a model with signed rewards, a policy that continues indefinitely can have a different total-reward behavior from one that eventually…

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

Outline of an Algorithm for Integer Solutions to Linear Programs: The Fractional Cut (3) Cuts Off the Simplex Solution but Keeps Every Nonnegative Integer Solution and the Integer Maximum of wResearch Paper

Integer linear programming asks for the best point whose coordinates are integers, even though linear programming methods naturally search over real points. In his 1958 note, Gomory describes a systematic way to add a constraint that excludes a fractional simplex solution while retaining every nonnegative integer solution. This mission isolates that single…

7 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research·Captain: mikedeng1

Linear Programming and Finite Markovian Control Problems I: Five Equivalent Characterizations of a Transient Markov Decision Problem, among Them Contraction and a Finite Linear ProgramTextbook

Finite Markov decision models are often described by policies that choose an action from the current state. The admissible class in a total reward problem is wider: a randomized decision may use the complete history of observed states and chosen actions. For an undiscounted infinite horizon, the expected number of visits to a state may be infinite, and the…

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

Linear Programming and Finite Markovian Control Problems III: Contracting Dynamic Programming — Pure, Stationary, Markov and General Policies Span One State-Action Frequency PolytopeTextbook

Finite Markov decision models describe repeated choices whose consequences depend on the present state. They are used when a planner needs one rule that works from every starting state, yet the rule may in principle respond to the entire observed history. Linear programming offers a different description: it records how often each state and action are used,…

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

On Approximate Solutions of Systems of Linear Inequalities: If Ax ≦ b Is Consistent, Every x Has a Solution x₀ with Fₙ(x − x₀) ≦ c·Fₘ((Ax − b)⁺)Research Paper

Iterative methods for a system of linear inequalities Ax≤bAx\le bAx≤b stop at a vector xˉ\bar xxˉ that only almost satisfies the system: the violation (Axˉ−b)+(A\bar x-b)^+(Axˉ−b)+ is small but not zero. A user then needs to know that xˉ\bar xxˉ is close to an actual solution. Hoffman's 1952 paper (J. Res. Nat. Bur. Standards 49) gives the first quantitative form of this fact: the…

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

Approximation Schemes for the Restricted Shortest Path Problem: The Rounding Algorithm Outputs a T-Path of Length at Most (1 + ε)·OPTResearch Paper

The restricted shortest path problem asks for a shortest route between two points of a network subject to a budget on a second additive quantity, such as travel time, cost or risk. It appears as the pricing subproblem of column generation for crew scheduling and vehicle routing, in quality-of-service routing in communication networks, and in scheduling,…

7 thms2 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: mikedeng1

Nonlinear Proximal Point Algorithms Using Bregman Functions, with Applications to Convex Programming 1: The Bregman Proximal Point Algorithm Converges to a Zero of a Maximal Monotone OperatorResearch Paper

The proximal point algorithm is a way to find a zero of a set-valued monotone operator by repeatedly solving a regularized version of that operator equation. Its classical regularizer is quadratic, so the distance from one iterate to the next is Euclidean. In convex optimization, that geometry can be poorly matched to the domain: the natural iterates may be…

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

How Many Parts to Make at Once: The Cost per Unit (CX + S)/240M + S/X + C Is Minimized Exactly at the Lot Size X = √(240MS/C)Research Paper

Every manufacturer who makes a part in batches faces the trade-off Ford W. Harris described in 1913: large lots spread the fixed set-up cost of an order over many pieces, but they also tie up money in stock that must be carried. Harris's article "How many parts to make at once" (Factory, The Magazine of Management 10(2), 1913, reprinted in Operations…

4 thms2 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Mean-Variance Hedging in Continuous Time: The Feedback Futures Strategy Φ(G*) Minimizes the Expected Squared Deviation of Terminal Wealth from Any Target LevelResearch Paper

A firm that will receive or deliver a quantity of a commodity, currency or security at a future date carries price risk until that date. When the asset itself cannot be traded in the meantime, the standard instrument for reducing that risk is a futures contract on a correlated asset: the firm takes a position in futures and adjusts it over time, and the…

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

Scheduling Deteriorating Jobs on a Single Processor II: If E(X_j)/α_j and α_j/[c_j(1+α_j)] Both Increase in j, the Order 1, …, N Minimizes the Weighted Expected Completion Time (Proposition 2)Research Paper

On one processor, the completion time of a job normally depends on how much work precedes it. In the model of Browne and Yechiali (1990), waiting also changes the job's own processing requirement: a job that starts later takes longer. The sequence therefore changes both when each job starts and how long subsequent jobs must wait. This matters when the goal…

6 thms2 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: mikedeng1

Convex Programming in Hilbert Space: Gradient Projection x_{k+1} = P(x_k − ρ_k∇f(x_k)) with σ ≤ ρ_k ≤ 2ρ₀ − σ Stays in the Level Set, and for Convex f Drives f(x_k) to inf_C fResearch Paper

Minimizing a smooth function over a closed convex set is the basic problem of constrained continuous optimization. When the constraint set is simple enough that the nearest point of the set to any given point can be computed (a ball, a box, an orthant, an affine subspace), the most direct method is the gradient projection method: take a gradient step and…

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

Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers V: Sharing ADMM — the z-Update Reduces to One n-Variable Problem and the Dual Variables AgreeTextbook

Many large optimization problems arising in statistics, machine learning, signal processing and resource allocation have an objective that is a sum of terms, each depending on data held by a different processor, or a coupling term that depends on the sum of the agents' decisions. Chapter 7 of Boyd, Parikh, Chu, Peleato and Eckstein's monograph on the alterna…

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

On the Power of Robust Solutions in Two-Stage Stochastic and Adaptive Optimization Problems 5: For Hypercube Uncertainty, Even in the Constraints, the Robust and Adaptive Optima CoincideResearch Paper

In two-stage optimization under uncertainty, a first-stage decision xxx is taken before the data are known, and a second-stage decision yyy is taken after a scenario ω\omegaω is revealed. The fully adaptive formulation lets yyy depend on ω\omegaω and minimizes the worst-case cost. It is the natural model of recourse, but it optimizes over policies, one decision per…

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

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties 3: For Maximum Discrepancy, Some Optimum Schedule Is in Standard Form and Has the Release Time PropertyResearch Paper

In just-in-time scheduling each job has a preferred time, and finishing it early is as undesirable as finishing it late. Garey, Tarjan and Wilfong (Math. Oper. Res. 13 (1988), 330–348) study the one-processor version in which task TiT_iTi​ has a length li≥0l_i \ge 0li​≥0 and a preferred starting time ai≥0a_i \ge 0ai​≥0, and the discrepancy of a task started at time sis_isi​ is …

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

One-Processor Scheduling with Symmetric Earliness and Tardiness Penalties 2: For a Fixed Task Order, the Block-Shifting Algorithm Minimizes the Total DiscrepancyResearch Paper

A task may have a preferred execution time because a material delivery, external event, or downstream operation is timed to it. Starting early can be as costly as starting late. Garey, Tarjan, and Wilfong study this situation on one processor, where tasks cannot overlap but idle time between tasks is permitted. Their total-discrepancy problem is hard when…

6 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Minimum Partition of a Matroid Into Independent Subsets: A Matroid Splits Into k Independent Sets Iff Every Subset A Has |A| ≤ k·r(A)Research Paper

A matroid abstracts the dependence structure of the columns of a matrix: which sets of columns are linearly independent, forgetting the numbers themselves. Graphs are the special case of incidence matrices over the integers mod 2, where a set of edges is independent exactly when it contains no cycle. A natural combinatorial question in this setting is the mi…

17 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical Analysis·Captain: mikedeng1

Truncated-Newton Algorithms for Large-Scale Unconstrained Optimization 2: Exact CG Meets Nonpositive Curvature Unless g Is Orthogonal to the Nonpositive Eigenspaces of HResearch Paper

Truncated-Newton methods minimize a smooth function f:Rn→Rf:\mathbb{R}^n\to\mathbb{R}f:Rn→R by taking, at each iterate xkx_kxk​, a search direction obtained by solving the Newton equation H(xk)p=−g(xk)H(x_k)p=-g(x_k)H(xk​)p=−g(xk​) only approximately, with the linear conjugate gradient (CG) method. Here ggg is the gradient and HHH the Hessian of fff. The approach was analysed by Dembo and Steihaug (Math.…

5 thms2 active usersReviewed
PreviousPage 78 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