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

Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case 2: The Greedy Forward Dual Solution Is Optimal and Its Value Is the Lot-Sizing CostResearch Paper

Economic lot sizing asks when to produce goods across a finite planning horizon when demand in each period is known. Producing in a period incurs a fixed setup charge and a marginal cost per unit, while goods may be produced before the period in which they are needed. Such a decision has to balance paying another setup charge against producing more units…

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

Vertical Integration and Antitrust Policy: Integrating Successive Monopolies Lowers the Final Price and Raises Output, Joint Profit and Consumer SurplusResearch Paper

In 1950 the United States Supreme Court appeared to be moving toward treating corporate integration, horizontal or vertical, as illegal per se under the antitrust laws. Joseph J. Spengler's note in the Journal of Political Economy argued that this conflates two different things: horizontal integration can suppress competition, but vertical integration, the…

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

A Dual Approach to Solving Nonlinear Programming Problems by Unconstrained Optimization 3: Under Second-Order Conditions, Tolerances αₖ ≤ q[sup g_r − g_r(yᵏ)] Give |xᵏ − x̄| ≤ s|yᵏ − ȳ|Research Paper

The method of multipliers (augmented Lagrangian method), proposed independently by Hestenes and Powell in 1969, solves a constrained optimization problem by a sequence of unconstrained minimizations of a penalized Lagrangian, updating a multiplier estimate between them. It became one of the standard algorithms of nonlinear programming and is the ancestor of…

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

Duality and Stability in Extremum Problems Involving Convex Functions 2: The Dual Supremum Equals the Lower Limit of the Perturbed Infimum, sup (P*) = lim inf_{z→0} inf (P(z))Research Paper

A convex minimization problem comes with a dual maximization problem, and the dual value never exceeds the primal value. When the two values differ, a duality gap occurs. Dual bounds, Lagrangian relaxations and optimality certificates are then weaker than hoped. Conditions that rule the gap out are constraint qualifications such as Slater's condition and…

8 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

An Iterative Method of Solving a Game: For Every Vector System, min U(t)/t and max V(t)/t Converge to the Value of the GameResearch Paper

A finite two-person zero-sum game is given by a real pay-off matrix, and its value can be computed by linear programming. In 1949 George W. Brown proposed a much simpler procedure, now called fictitious play: each player in turn plays a best pure reply to the accumulated play of the opponent so far, and the running averages are read off as estimates of the…

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

Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming: The Set-Inclusive LP Has the Same Feasible Set as the LP of Support FunctionalsResearch Paper

A linear program max⁡c⋅x\max c\cdot xmaxc⋅x subject to Ax≤bAx\le bAx≤b, x≥0x\ge 0x≥0 assumes that the constraint matrix AAA is known exactly. In practice the columns of AAA — the activity vectors, describing how much of each resource one unit of activity jjj consumes — are estimates. A. L. Soyster's 1973 technical note in Operations Research (doi:10.1287/opre.21.5.1154) asked what a…

12 thms2 active usersReviewed
🏆Completed
AnalysisFunctional AnalysisOperations Research·Captain: mikedeng1

An Implicit-Function Theorem for a Class of Nonsmooth Functions: Strong Approximation by a Function with Lipschitzian Inverse Yields a Unique Lipschitzian Implicit FunctionResearch Paper

The classical implicit-function theorem solves an equation F(x,y)=0F(x, y) = 0F(x,y)=0 for xxx as a function of a parameter yyy near a known solution (x0,y0)(x_0, y_0)(x0​,y0​), provided FFF is (strongly) Fréchet differentiable in xxx with an invertible partial derivative. Much of optimization does not meet that hypothesis. Optimality conditions of constrained problems, complementarity problems…

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

Scenarios and Policy Aggregation in Optimization Under Uncertainty 1: In the Convex Case Progressive Hedging Converges to Optimal Solutions of (P) and (D) Exactly When They ExistResearch Paper

Decisions under uncertainty are often modelled by a finite set of scenarios: possible futures s∈Ss\in Ss∈S with weights psp_sps​, each with its own optimization problem. Solving every scenario separately is easy but useless in practice, because the decision taken today cannot depend on which scenario will be revealed tomorrow. Progressive hedging, introduced by…

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

Régularisation d'inéquations variationnelles par approximations successives I: Every Weak Cluster Point of the Regularized Iterates Solves the Monotone Variational InequalityResearch Paper

The proximal point algorithm is a basic iterative scheme of convex optimization and monotone operator theory. To solve a problem governed by a monotone operator, it replaces the problem by a sequence of better-conditioned problems, each regularized by a quadratic term centred at the previous iterate. Augmented Lagrangian methods, the Douglas–Rachford and…

10 thms2 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOperations Research·Captain: mikedeng1

Strongly Regular Generalized Equations III: Reduced-Form Criterion — a Linear Generalized Equation over a Polyhedral Set Is Strongly Regular Iff Its Reduced Form Is Uniquely Solvable on LResearch Paper

Many problems in optimization and equilibrium modelling, among them linear and nonlinear complementarity problems, variational inequalities over polyhedra, and the Karush–Kuhn–Tucker conditions of nonlinear programs, can be written as a single generalized equation

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

Strongly Regular Generalized Equations II: Schur-Complement Criterion — A₁₁ Nonsingular and (A/A₁₁) Positive Definite Make (A + ∂ψ_{ℝʳ×K})⁻¹ Lipschitz on ℝ^{r+s}; for K = ℝˢ₊, P-Matrix IffResearch Paper

A constrained system can be written as a generalized equation: a smooth or linear expression must balance the normal cone of a feasible set. This form includes variational inequalities and the first-order conditions of many optimization problems. It is useful to know whether a small change in the right-hand side determines one nearby solution and how far…

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

On the Job-Shop Scheduling Problem: The Integer Program (2)–(7) with 0–1 Variables y_jk Attains Exactly the Minimum Make-SpanResearch Paper

The job-shop scheduling problem asks how to time a set of tasks on shared machines so that every product is finished as early as possible. Around 1959 several authors proposed to solve it with Gomory's then new integer programming (Gomory 1958). The obstacle is the noninterference condition: two tasks on the same machine must not overlap, so one of them…

7 thms2 active usersReviewed
🏆Completed
Functional AnalysisOperations Research·Captain: mikedeng1

Strongly Regular Generalized Equations I: Implicit-Function Theorem — the Solution x(p) of 0 ∈ f(p, x) + ∂ψ_C(x) Is Locally Unique with ‖x(p) − x(q)‖ ≤ (λ + ε)‖f(p, x(q)) − f(q, x(q))‖Research Paper

Many problems of optimization and equilibrium can be written as one inclusion. Some examples are the Karush–Kuhn–Tucker conditions of a nonlinear program, nonlinear complementarity problems, variational inequalities and the equilibrium conditions of economic and traffic models. In each of them a point xxx has to satisfy 0∈f(x)+∂ψC(x)0 \in f(x) + \partial\psi_C(x)0∈f(x)+∂ψC​(x). In…

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

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 4: Batch List Scheduling Is Within B + 1 − 1/m of the Optimal Makespan and Has a Bounded Relative Maximum-Lateness ErrorResearch Paper

Semiconductor burn-in ovens can process several jobs at once. A group placed in one oven must remain together until the longest job has finished, so increasing batch size saves oven starts but can delay short jobs. When several ovens are available, a scheduler also has to decide which oven receives each batch. Lee, Uzsoy, and Martin-Vega studied this…

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

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 1: Dynamic Program DP1 Finds a Minimum-Makespan On-Time Batch Schedule of Equal-Length Jobs with Agreeable Release and Due DatesResearch Paper

Burn-in is the final testing stage of semiconductor manufacturing: finished integrated circuits are loaded on boards and held in an oven at high temperature for a prescribed minimum time, so that weak devices fail before shipment. An oven holds many boards at once, a load cannot be interrupted, and a board may stay in the oven longer than its specified time…

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

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 2: Dynamic Program DP2 Finds a Minimum-Makespan On-Time Batch Schedule When Processing Times and Due Dates Are AgreeableResearch Paper

In semiconductor manufacturing, finished chips go through burn-in: they are loaded on boards and held in an oven at high temperature to expose early failures. An oven holds a bounded number of boards, a load cannot be interrupted once started, and a chip may stay in the oven longer than its specified burn-in time but not shorter. Lee, Uzsoy and Martin-Vega (…

7 thms2 active usersReviewed
🏆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
🏆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
🏆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
PreviousPage 59 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