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

Efficient Algorithms for Scheduling Semiconductor Burn-In Operations 3: Dynamic Program DP3 Minimizes the Number of Tardy Equal-Length Jobs on a Batch Machine with Agreeable Release and Due DatesResearch Paper

Semiconductor burn-in tests hold several jobs in an oven at once. A production planner must decide which jobs share each oven run and in what order those runs take place. A job may become available only after earlier manufacturing steps, and a due date marks when its test should finish. The planning objective here is to minimize how many jobs finish after…

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

Application of the Branch and Bound Technique to Some Flow-Shop Scheduling Problems 2: Branch and Bound with the Two-Machine Lower Bound Finds a Sequence of Least Mean Completion TimeResearch Paper

In a two-machine flow shop, each of nnn jobs is processed first on machine AAA and then on machine BBB, and the order of the jobs is to be chosen. For the makespan (the finishing time of the last job), Johnson (1954) gave an exact sorting rule. For the sum (equivalently, the mean) of the completion times, no such rule is known: the problem is NP-hard in the…

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

Monotone Comparative Statics I: The Argmax Is Monotone Nondecreasing in (t, S) If and Only If f Is Quasisupermodular in x and Has the Single Crossing Property in (x; t)Research Paper

An optimization problem often changes when a parameter changes: a price rises, a constraint expands, or a strategic environment shifts. Comparative statics asks whether the optimal choice moves in a predictable direction. The usual numerical tools, such as derivatives, can be unavailable when choices form a discrete set or the objective is neither smooth…

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

Monte Carlo Bounding Techniques for Determining Solution Quality in Stochastic Programs: The Expected Sample-Average Optimal Value Is a Lower Bound on z* That Improves with Sample SizeResearch Paper

Most stochastic programs that arise in practice, such as two-stage stochastic linear programs with recourse, have far too many scenarios to be solved exactly. The standard remedy is sample-average approximation: draw nnn independent observations of the random data, replace the expectation by the sample mean, and solve the resulting deterministic problem. A…

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

Globally Convergent Inexact Newton Methods II: Trust Region Limit Points Are Stationary Points of ‖F‖, and Near a Zero Where F′ Is Invertible the Full Newton Step Is Eventually TakenResearch Paper

Solving a system of nonlinear equations F(x)=0F(x)=0F(x)=0, with F:Rn→RnF:\mathbf R^n\to\mathbf R^nF:Rn→Rn continuously differentiable, is a basic task in numerical analysis and optimization: it is the inner step of interior-point and sequential quadratic programming methods, of implicit time-stepping for differential equations, and of equilibrium computations in operations…

7 thms2 active usersReviewed
Control TheoryDynamical SystemsOperations Research·Captain: mikedeng1

Homogeneous Approximation, Recursive Observer Design, and Output Feedback: Global Asymptotic Stabilization of a Chain of Integrators by a Homogeneous-in-the-Bi-Limit Output FeedbackResearch Paper

Many nonlinear control systems behave like a chain of integrators, x˙1=x2,…,x˙n=u\dot x_1=x_2,\dots,\dot x_n=ux˙1​=x2​,…,x˙n​=u, with additional terms that are small either near the origin or far from it. Designs based on weighted homogeneity handle such systems by making the closed loop invariant under a dilation, which gives robustness to perturbations that are dominated by the…

13 thms2 active usersReviewed
Numerical Analysis·Captain: mikedeng1

A Trust Region Method Based on Interior Point Techniques for Nonlinear Programming: Limit Points Are KKT Points Under LICQ, Unless Infeasibility or LICQ Failure Is DetectedResearch Paper

Interior-point methods transformed linear programming in the 1980s and 1990s. A natural question was whether the same ideas carry over to nonlinear programming, where the objective and the constraints are general smooth functions. Sequential quadratic programming (SQP) methods were then the method of choice for small and medium nonlinear problems, but each…

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

On the Convergence of Interior-Reflective Newton Methods for Nonlinear Minimization Subject to Bounds 2: Local Interior-Reflective Newton Steps Converge Quadratically near a Nondegenerate MinimizerResearch Paper

Bound constrained minimization asks for a low value of a smooth objective while each variable stays between prescribed lower and upper limits. Such limits occur in nonlinear optimization models even when the objective itself has no special convexity. Coleman and Li's interior reflective method was designed to approach a solution from inside those limits…

9 thms2 active usersReviewed
🏆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
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 4: For a Random Subspace, ‖Pq‖⁻∞ ≤ (log n/n)‖r‖² with Probability Tending to OneResearch Paper

Primal–dual interior point methods follow a path of strictly feasible solutions to a linear program. Their worst case iteration bounds come from controlling a term that is quadratic in each search step. Mizuno, Todd, and Ye asked whether that term is typically much smaller than its worst case bound under a model in which a certain subspace is randomly…

7 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
PreviousPage 77 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