Aaron Courville 2026-11-05
Aaron Courville coauthored Deep Learning by Ian Goodfellow and others with Ian Goodfellow and Yoshua Bengio. The book develops the mathematical and statistical foundations of learning with multilayer representations, including optimization, regularization and generative models.[ref]
Deep Learning by Ian Goodfellow and others. Chapters5–8 and PartIII
He also coauthored the 2014 generative adversarial network paper. Its generator and discriminator are trained against one another, connecting generative modelling with a two-player optimization problem.[ref] The construction specifies a training objective; stable optimization and useful generated samples require additional analysis and empirical evaluation.
Asuman Özdağlar 2026-10-24
An electrical engineer whose research includes game theory and mathematical optimization.[ref]
https://computing.mit.edu/about/people/leadership/asu-ozdaglar/. MIT institutional profile, education and research expertise
Homepage: asu.mit.edu/
Portrait of Asu Ozdaglar
. Portrait linked by the MIT Schwarzman College of Computing profile. Cooling schedule for simulated annealing 2026-10-18
A cooling schedule for simulated annealing specifies successive effective temperatures and how many proposals to attempt at each. For example, with , using the geometric sequence, can define stages of equal chosen length. Changing changes the transition matrix: if the state probability distribution is , then , which generally differs from . Time spent at one temperature must be compared with its mixing time before equilibrium intuition is justified.
In the five-state barrier example for simulated annealing, fixed gives a finite irreducible Markov chain, so is eventually visited with probability one. That unbounded-time statement gives no fixed finite deadline. Over any finite number of trials starting at , the probability of staying at throughout isEach factor is the rejection probability at . This is an explicit failure event even when every is positive: the best visited objective function value remains , above the global minimum value . More exploratory proposals can help cross a barrier; cooling before those moves occur can preserve a poor local minimum. Successful asymptotic schedules need additional analysis of the allowed moves and barriers.
Historically, Scott Kirkpatrick, Charles Daniel Gelatt Jr. and Mario P. Vecchi connected statistical mechanics with mathematical optimization in 1983. They adapted the Metropolis–Hastings algorithm to cooling searches with symmetric proposals and illustrated computer-design problems.[ref]
Optimization by Simulated Annealing by Scott Kirkpatrick and others. Printed pp. 672–673 and 675: Metropolis procedure, cooling schedule, logic partitioning
C. T. Kelley Created 2026-10-14 Updated 2026-11-05
C. T. Kelley studies numerical analysis, including iterative methods for nonlinear equations, mathematical optimization and linear systems. His research connects solver design with numerical stability and computational cost, including methods that perform different stages at different arithmetic precisions.[ref]
https://ctkelley.github.io/. Author homepage, professional research activities and nonlinear-equation books
Homepage: ctkelley.github.io/
Daniel Dadush Created 2026-10-14 Updated 2026-11-05
Daniel Dadush studies mathematical optimization, including linear programming, integer programming, geometry of numbers and discrepancy theory. His work connects the geometry of high-dimensional convex sets with algorithms for mathematical optimization.[ref]
Homepage: homepages.cwi.nl/~dadush/
Portrait of Daniel Dadush
. Photograph linked on the CWI personal homepage. Directional derivative Created 2026-09-24 Updated 2026-10-14
The directional derivative tests a function along a chosen straight line, including lines that follow neither coordinate axis. For a fixed vector and a point in an open subset of , defineif the limit exists. With a unit vector , the parameter measures signed distance in the input Euclidean space, so the directional derivative is change per unit distance. For a general , it is change per unit parameter; the norm of also sets the rate of travel.[ref]
4.6 Directional Derivatives and the Gradient. Calculus Volume 3, §4.6, definition (4.36), unit-direction convention
For a differentiable real-valued function, the multivariable chain rule givesThus one gradient predicts the local response in every direction. This formula requires differentiability, rather than merely separate partial derivatives.[ref]
Return to at . Its gradient is . In the unit direction ,One can check this without invoking the gradient formula: substitution givesThe difference quotient is , whose limit is . This calculation separates the exact change along a finite path from its first-order rate at the starting point.
Changing the travel speed changes the parameter rate. Taking gives , because the input travels five distance units per parameter unit. For a differentiable function, for any real : negative reverses the orientation as well as scaling the rate. Normalizing before comparing different slopes avoids confusing direction with speed.
The Cauchy-Schwarz inequality bounds the rate in any unit direction by . Here the largest rate is , attained in the direction ; the chosen gives the slightly smaller rate . The perpendicular unit direction gives zero. That means no first-order height change, rather than no change at all: along this direction the example has .
This is useful for following a height or temperature scalar field, choosing a local search direction in mathematical optimization, and distinguishing a coordinate sensitivity from a response along an actual path. For a curved path, derivative along a curve uses its instantaneous tangent vector. Even existence of all directional derivatives does not guarantee one common linear approximation; directional derivatives do not imply differentiability gives a concrete counterexample.
Dynamic programming Created 2026-09-24 Updated 2026-11-05
Dynamic programming solves a mathematical optimization problem by choosing reusable subproblems, recording their value functions, and combining already solved cases through a recurrence relation. Its attraction is that many possible decision histories can share one continuation calculation. A dynamic programming state must retain everything needed to determine the allowed future choices and their rewards. The 0-1 knapsack problem, for example, needs both the available capacity and which items remain available; capacity alone would lose the restriction that each item can be used at most once.
Two ideas explain when this works. Optimal substructure makes an optimal continuation valid inside a larger optimal solution. When subproblems overlap, storing each answer avoids repeated work: memoization computes entries as needed, while a table fills them in dependency order. Start from known base cases. For a problem indexed by increasing size, compute smaller cases first; for a finite sequence of future decisions, work backwards from the terminal reward, as in the Bellman equation. See Bertsekas, MIT lecture 2: optimality and state augmentation.
Consider a 0-1 knapsack problem with item weights , item values , and capacity . Define the value function to be the largest total item value obtainable from the first items with total weight at most . Here and specify the dynamic programming state. All weights and capacities are nonnegative integers. The empty selection supplies the base case . The recurrence relation isThe two candidates skip or take item . Both use the previous row, so taking item cannot take that same item again. The condition prevents a negative remaining capacity; no entry with is needed. The optimal substructure is concrete: after taking item , its companions must solve the smaller 0-1 knapsack problem on the first items with capacity . Otherwise replacing them by a better feasible selection would improve the whole selection. Compare [ref]
https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/95e744ee64464cb6bc8f8264faeea080_MIT6_006F11_rec21.pdf. MIT 6.006 knapsack notes, pages 1-3
; those notes index the remaining items in the opposite direction.The full computation is small enough to see at once:For example, and . Choosing the feasible item with largest individual value takes weight , earns , and leaves capacity , which cannot fit another item. This greedy algorithm misses the two-item selection of weights and , whose value is . This example tests the largest-individual-value rule; choosing by value divided by weight happens to find the optimum here.
A knapsack table builds the optimal value from smaller subproblems
. The value function of this 0-1 knapsack problem is computed row by row. Outlined entries show the reconstruction of an optimal selection: skip weight 4, take weight 3, then take weight 2. The total weight is 5 and total value is 7. Details.The number is the optimal value, while the choices attaining it form a control policy. To reconstruct one optimal selection, start at . Equality with allows skipping item . At , taking item gives , so continue to . Take item and finish at . In a tie, either maximizing choice suffices to recover one optimum. Recording choices during the calculation or comparing stored entries afterwards recovers the control policy; a final optimal value alone does not describe the selection.
Knapsack dependencies and one optimal reconstruction
. Each node is a dynamic programming state labeled by its value function. Arrows point to the earlier-row entries used in the recurrence relation, forming a directed acyclic graph. Dashed arrows skip an item; blue arrows take it. The orange graph path reconstructs the optimal selection with value 7. Compute in the opposite direction to the arrows, beginning at the zero base row. Details.For items and integer capacity , the table uses time complexity and space complexity , counting arithmetic operations and stored numbers using Big O notation. This is pseudo-polynomial time: when weights and capacity use the binary numeral system, the capacity needs only digits. A capacity near creates about columns despite needing only about digits. Thus this algorithm is practical for moderate capacities but does not establish polynomial time in the encoded input length. See MIT 6.006 recitation 19: knapsack and input size. For the optimal value alone, one array reduces space complexity to : for each item, update capacities in descending order, from down to . Ascending order would read entries already updated for that item and could reuse it. Reconstruction then requires extra information or recomputation.
The link between the knapsack problem and dynamic programming is already explicit in a 1957 paper by Richard Bellman at RAND: its abstract discusses an exact knapsack problem solution using functional equations and cites his 1957 book. See Bellman, Comment on Dantzig's Paper on Discrete Variable Extremum Problems (1957).
Dynamic programming state Created 2026-10-14 Updated 2026-10-20
A dynamic programming state is an element of a state space that summarizes all information needed for a remaining mathematical optimization problem. Histories can share a value function entry only when their allowed continuations and future rewards agree, or have the same conditional laws in a stochastic control problem. Time or the remaining item index may be part of the summary. If past decisions still affect feasibility or rewards, enlarge the dynamic programming state; forgetting those effects invalidates the Bellman equation.
Feasibility problem 2026-11-05
A feasibility problem asks whether any point satisfies a specified collection of optimization constraints, and seeks such a point when one exists. There need not be a preference among satisfying points. If the feasible set is , the mathematical questions are whether is empty and, if not, how to produce a feasible point. A feasibility problem can be represented as mathematical optimization with a constant zero objective function.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. Section4.1.1, printed pp128–129, feasibility problems
For an original linear example, considerThe pair is a directly checkable witness. Replacing the last bound by makes the constraints inconsistent: adding , and gives . This short contradiction certifies infeasibility without enumerating candidate points.
More generally, for a real linear system , a vector satisfyingis an infeasibility certificate: multiplying and adding the assumed inequalities would force . This is the certificate side of Farkas' lemma. A failed numerical search or a timeout is different from such a proof; it need not imply that the feasible set is empty.
The allowed variable set is part of the question. The equation is feasible over the real numbers, with , but infeasible when must be an integer. Thus replacing integer programming constraints by a real relaxation changes the feasibility problem.
Quasiconvex optimization supplies a useful connection: for each threshold , test whether the original constraints and admit a feasible point. Such decisions can bracket the optimal value, while a retained witness gives an actual decision attaining the tested bound.[ref]
Convex Optimization by Stephen Boyd and Lieven Vandenberghe. Section4.2.5, printed pp145–146, Algorithm4.1
Numerical tolerances should be stated: a small constraint residual can support approximate feasibility without proving exact satisfaction. Greedy algorithm Created 2026-10-13 Updated 2026-10-20
A greedy algorithm builds a feasible solution by repeatedly committing to a locally preferred next choice. Each commitment is final: the algorithm does not revisit it when later choices become available. In mathematical optimization, the important question is whether those commitments can still attain the best objective function value.
For example, a shared telescope can accept several observation requests with fixed time slots. In interval scheduling, every completed request counts equally, and overlapping requests cannot both be accepted. Choosing the request that finishes earliest leaves the resource available sooner. The example below turns that intuition into a precise rule, then shows why choosing the earliest start or shortest duration can lose jobs.
Greedy algorithms are attractive because a single pass can replace a search through many candidate subsets. However, "locally best" is only a design proposal. A problem-specific greedy-choice property, often established by an exchange argument, must connect the local decision to the actual objective function. The largest-individual-value rule in the 0-1 knapsack problem fails; Dijkstra's algorithm needs its nonnegative-edge assumptions. A rule's success in one optimization task does not justify it in another.
Hall allocation model 2026-10-14
In a unit-capacity assignment problem, left vertices represent demands and right vertices represent individually usable resources; an edge records compatibility. All constraints must be encoded by those allowed pairs and by using each resource at most once. Hall's marriage theorem decides feasibility. Costs belong to an additional mathematical optimization problem; precedence between jobs or requirements for consecutive slots need additional modelling.
The authored Notes on the design of a conference scheduler by David R. MacIver (Implementation, 7 August 2022) illustrates a Hall obstruction with four talks confined to three slots. With one talk per slot, that subset has size four and a graph neighbourhood of size three. An unused slot outside its graph neighbourhood does not remove the bottleneck. In the three-job example above, the same scheduling model instead has two complete assignments.
The allocation exercise in Graph Theory by Reinhard Diestel (Matching, Covering and Packing, printed p. 20, Exercise 9) asks for disjoint subsets of prescribed nonnegative integer sizes . Replace demand by left vertices with allowed resource set . Hall's marriage theorem gives exactly the conditionFor a numerical instance, let , , and . The separate demands and their combined demand fit, and works. Raising to two leaves both individual tests valid but demands four distinct resources from a set union of size three. This is the same collective obstruction with repeated demand vertices.
Infimum and supremum Created 2026-10-14 Updated 2026-10-18
For a subset of a partially ordered set, its infimum is its greatest lower bound and its supremum is its least upper bound. An upper bound only has to lie above every member; the supremum is the smallest such bound. A lower bound lies below every member; the infimum is the largest such bound. These definitions identify the exact edges of a set even when neither edge belongs to it.
For example, and both have infimum zero and supremum one. Only has a minimum and a maximum: those must be actual members of the set. The set has infimum zero without a minimum, but its supremum one is also its maximum. Such examples distinguish a bound from an attained extremal value. [ref].
For a nonempty subset of the real numbers, completeness of the real numbers guarantees a real supremum when it is bounded above, and a real infimum when it is bounded below. The bound and the ambient partially ordered set both matter: has supremum in the real numbers, but no supremum in the rational numbers. The detailed explanation belongs to completeness of the real numbers.
Why are unattained bounds useful? They specify a precise limiting target. In mathematical optimization, on has infimum zero but no global minimizer. The inputs for give a minimizing sequence: their objective values approach zero without ever reaching it. Bounds therefore describe what approximation can achieve even when no feasible input is best. The approximation property of an infimum and approximation property of a supremum express this idea quantitatively.
Interior-point method Created 2026-10-06 Updated 2026-10-07
An interior-point method solves constrained mathematical optimization problems by maintaining variables in the interiors of their feasible cones or inequality domains. Barrier derivatives are defined there, and damped Newton methods keep subsequent iterates in their domains. A central path gives a family of barrier-regularized optima whose duality gap approaches zero; a conic phase-I problem can supply a strict feasible starting point.
Interval arithmetic 2026-10-14
Interval arithmetic calculates with closed intervals that contain the possible values of a quantity. If all we know is , an interval enclosure for a function must contain for every allowed . The result says what is guaranteed, including uncertainty in the input and, with outward rounding, roundoff error in the calculation. A wide answer can still be correct; a narrow answer is useful only if it contains every possible value.
The attraction is that a finite calculation can make a statement about infinitely many real numbers at once. An interval enclosure can certify that a function stays positive throughout a whole closed interval, or bound its maximum for mathematical optimization. For example, on , the actual image of a function for is , but direct interval arithmetic gives the wider . Interval subdivision and the interval square range improve this answer in different ways.
Historically, Ramon E. Moore's 1962 Stanford dissertation studied interval arithmetic and automatic error analysis in digital computing; his book Interval Analysis followed in 1966. Eldon Hansen's account documents earlier reports as well: these dates describe important steps in developing and disseminating the subject, rather than a claim of sole invention in a particular year.[ref]
https://interval.louisiana.edu/Moores_early_papers/bibliography.html. Eldon R. Hansen, Publications Related to Early Interval Work of R. E. Moore, 2001, references 5 and 8
Moore, R. Baker Kearfott and Michael J. Cloud later wrote Introduction to Interval Analysis (2009).[ref]https://interval.louisiana.edu/books.html. R. Baker Kearfott, Books written or edited, entry for Introduction to Interval Analysis
John E. Dennis 2026-10-31
A mathematician whose research includes mathematical optimization. The Dennis-Moré condition concerns superlinear convergence of quasi-Newton methods.
Homepage: www.cmor-faculty.rice.edu/~dennis/
Jorge Moré Created 2026-10-31 Updated 2026-11-05
A mathematician working on mathematical optimization algorithms and software. The Dennis-Moré condition concerns superlinear convergence of quasi-Newton methods.
Homepage: www.mcs.anl.gov/~more/
Line breaking with squared slack cost 2026-11-05
Line breaking with squared slack cost is a simplified mathematical optimization model for paragraph layout. Treat the input as indivisible typesetting boxes with nonnegative widths , keep their order, use fixed word spacing , and require each line to fit a common typesetting line width . This model isolates the choice of breaks from adjustable spacing and hyphenation.
Let be the prefix sum, with . Placing items through on one line usesA line is feasible when . Charge for a nonfinal line and zero for the final line. If are the breaks, the objective isThe free final line is an explicit modelling choice. The convex function makes a doubled slack cost four times as much. For two slacks with fixed total,so greater imbalance increases their sum of squares. Actual break choices can also alter the line count and total slack; the whole paragraph still needs to be optimized.
Apply dynamic programming with andAn endpoint with no feasible predecessor has cost . The same recurrence finds a shortest path through the directed acyclic graph of feasible line choices. The principle of optimality explains the recurrence. Once the final breakpoint of a prefix is chosen, replacing its preceding layout by a cheaper layout with the same endpoint would improve the whole candidate. Conversely, each feasible predecessor and final line produces a valid candidate. Induction over therefore gives the optimum. Prefix states with charge their last line; only the final state gets the paragraph's free-last-line convention.
For widths , spacing 1 and capacity 7, the states areFollowing minimizing predecessors gives line lengths and cost 20. The line breaking diagram compares this with the cost 26 of greedy line breaking. With prefix sums, each candidate length takes constant time; at most candidates give time complexity and space complexity for costs and predecessors. The big O notation describes this fixed-space model; the Knuth-Plass line-breaking algorithm includes additional typography-specific choices.
Local minimum Created 2026-09-24 Updated 2026-10-14
A real-valued function , with , has a local minimum at if some satisfiesEquality is allowed; a strict local minimum excludes equality at every other sufficiently nearby point. The comparison uses a neighbourhood relative to the domain of a function. On an open set, this is an ordinary small ball around . At an endpoint, only points belonging to the domain of a function are tested. Some elementary texts reserve "local" for interior points; here endpoints are allowed under the relative convention, but the zero-gradient condition still requires an interior point.
For , each of and is a strict local minimum, although both attain the same global minimum. For , zero is a strict local minimum despite the missing derivative. Thus the definition compares values and does not require differentiability.
A local minimum describes a valley that cannot be improved by a sufficiently small move; mathematical optimization also asks whether a better value lies farther away. At a smooth interior local minimum, the gradient is zero. If the function is twice continuously differentiable nearby, its Hessian matrix is positive semidefinite: restrict to a line through the point and its second derivative is nonnegative. The converse fails for a degenerate Hessian matrix, as at zero shows.
Mathematical economics Created 2026-10-13 Updated 2026-10-20
Mathematical economics uses mathematical optimization, game theory and analysis to study allocation, choice and market coordination.
Mathematical finance Created 2026-09-24 Updated 2026-10-18
Mathematical finance uses probability theory, linear algebra and mathematical optimization to study financial markets, portfolio decisions and contingent claim prices. One question asks which portfolio best serves a specified objective; another asks what price a contingent claim must have to exclude arbitrage. The latter can have an exact answer even when future stock prices are uncertain.
The central idea is claim replication: construct a self-financing portfolio delivering the same financial payoff as a contract in every possible state. The law of one price then identifies the contract's price with the portfolio's initial cost. The binomial market makes this beautiful connection between uncertainty and linear algebra visible using just two equations. Risk-neutral pricing expresses the same cost as a discounted expectation.
The one-step example below fixes today's stock price at 100, terminal prices at 120 or 80, and the bank account's gross growth factor at 1.05. A European call option with strike price 100 pays 20 or zero. Its replicating portfolio in a binomial market costs , independently of the physical up probability, provided both states remain possible. These are conclusions within the specified financial market model.





