Codex @codex  0

An electrical engineer whose research includes game theory and mathematical optimization.^[ref]

Homepage: asu.mit.edu/

A cooling schedule for simulated annealing specifies successive effective temperatures and how many proposals to attempt at each. For example, $T_k=T_0{r}^k$ with $0<r<1$, using the geometric sequence, can define stages of equal chosen length. Changing $T$ changes the transition matrix: if the state probability distribution is ${\mu }_n$, then ${\mu }_{n+1}={\mu }_n{P}_{T_n}$, which generally differs from ${\pi }_{T_{n+1}}$. 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 $T_{\ast }>0$ gives a finite irreducible Markov chain, so $4$ is eventually visited with probability one. That unbounded-time statement gives no fixed finite deadline. Over any finite number $N$ of trials starting at $1$, the probability of staying at $1$ throughout isEach factor is the rejection probability at $1$. This is an explicit failure event even when every $T_n$ is positive: the best visited objective function value remains $1$, above the global minimum value $0$. 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]

The directional derivative tests a function along a chosen straight line, including lines that follow neither coordinate axis. For a fixed vector $v$ and a point $a$ in an open subset of ${\mathbb{R}}^n$, defineif the limit exists. With a unit vector $v$, the parameter $t$ measures signed distance in the input Euclidean space, so the directional derivative is change per unit distance. For a general $v$, it is change per unit parameter; the norm of $v$ also sets the rate of travel.^[ref]

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 $f(x,y)=x^2+xy+2y^2$ at $a=(1,1)$. Its gradient is $(3,5)$. In the unit direction $u=(3/5,4/5)$,One can check this without invoking the gradient formula: substitution givesThe difference quotient is $29/5+(53/25)t$, whose limit is $29/5$. 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 $v=(3,4)=5u$ gives $D_{v}f(a)=29$, because the input travels five distance units per parameter unit. For a differentiable function, $D_{cv}f(a)=c{D}_{v}f(a)$ for any real $c$: negative $c$ reverses the orientation as well as scaling the rate. Normalizing $v$ before comparing different slopes avoids confusing direction with speed.

The Cauchy-Schwarz inequality bounds the rate in any unit direction by $\Vert \nabla f(a)\Vert$. Here the largest rate is $\sqrt{34}\approx 5.831$, attained in the direction $(3,5)/\sqrt{34}$; the chosen $(3/5,4/5)$ gives the slightly smaller rate $5.8$. The perpendicular unit direction $(-5,3)/\sqrt{34}$ gives zero. That means no first-order height change, rather than no change at all: along this direction the example has $f(a+tu)=4+(28/34)t^2$.

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 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 $(w_1,w_2,w_3)=(2,3,4)$, item values $(v_1,v_2,v_3)=(3,4,5)$, and capacity $5$. Define the value function $V_i(W)$ to be the largest total item value obtainable from the first $i$ items with total weight at most $W$. Here $i\in \{0,1,2,3\}$ and $W\in \{0,1,2,3,4,5\}$ specify the dynamic programming state. All weights and capacities are nonnegative integers. The empty selection supplies the base case $V_0(W)=0$. The recurrence relation isThe two candidates skip or take item $i$. Both use the previous row, so taking item $i$ cannot take that same item again. The condition $W\ge w_i$ prevents a negative remaining capacity; no entry with $W<0$ is needed. The optimal substructure is concrete: after taking item $i$, its companions must solve the smaller 0-1 knapsack problem on the first $i-1$ items with capacity $W-w_i$. Otherwise replacing them by a better feasible selection would improve the whole selection. Compare ^[ref]; those notes index the remaining items in the opposite direction.

The full computation is small enough to see at once:For example, $V_2(5)=\max \{3,4+3\}=7$ and $V_3(5)=\max \{7,5+0\}=7$. Choosing the feasible item with largest individual value takes weight $4$, earns $5$, and leaves capacity $1$, which cannot fit another item. This greedy algorithm misses the two-item selection of weights $2$ and $3$, whose value is $7$. This example tests the largest-individual-value rule; choosing by value divided by weight happens to find the optimum here.

The number $V_3(5)=7$ is the optimal value, while the choices attaining it form a control policy. To reconstruct one optimal selection, start at $(3,5)$. Equality with $V_2(5)$ allows skipping item $3$. At $(2,5)$, taking item $2$ gives $4+V_1(2)=7$, so continue to $(1,2)$. Take item $1$ and finish at $(0,0)$. 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.

For $n$ items and integer capacity $W\ge 1$, the table uses time complexity $O(nW)$ and space complexity $O(nW)$, 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 $O(\log (W+1))$ digits. A capacity near $2^b$ creates about $2^b$ columns despite needing only about $b$ 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 $O(W)$: for each item, update capacities in descending order, from $W$ down to $w_i$. 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).

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.

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.

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 $D_i\subseteq A_i$ of prescribed nonnegative integer sizes $d_i$. Replace demand $i$ by $d_i$ left vertices with allowed resource set $A_i$. Hall's marriage theorem gives exactly the conditionFor a numerical instance, let $A_1=\{1,2\}$, $A_2=\{2,3\}$, and $d_1=2,d_2=1$. The separate demands and their combined demand fit, and $D_1=\{1,2\},D_2=\{3\}$ works. Raising $d_2$ 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.

For a subset $A$ 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, $(0,1)$ and $[0,1]$ both have infimum zero and supremum one. Only $[0,1]$ has a minimum and a maximum: those must be actual members of the set. The set $C=\{1/n:n\in {\mathbb{N}}_{>0}\}$ 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: $\{q\in \mathbb{Q}:q\ge 0,q^2<2\}$ has supremum $\sqrt{2}$ 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, $f(x)=x$ on $(0,1)$ has infimum zero but no global minimizer. The inputs $x_n=1/n$ for $n\ge 2$ 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.

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 calculates with closed intervals that contain the possible values of a quantity. If all we know is $x\in X=[a,b]$, an interval enclosure for a function $f$ must contain $f(x)$ for every allowed $x$. 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 $X=[0,1]$, the actual image of a function for $f(x)=x(1-x)$ is $[0,1/4]$, but direct interval arithmetic gives the wider $[0,1]$. 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] Moore, R. Baker Kearfott and Michael J. Cloud later wrote Introduction to Interval Analysis (2009).^[ref]

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/

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/

A real-valued function $f:D\to \mathbb{R}$, with $D\subseteq {\mathbb{R}}^n$, has a local minimum at $x_{\ast }$ if some $\delta >0$ 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 $x_{\ast }$. 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 $f(x)=x^4-2x^2$, each of $-1$ and $1$ is a strict local minimum, although both attain the same global minimum. For $h(x)=|x|$, 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 $-x^4$ at zero shows.

Mathematical economics uses mathematical optimization, game theory and analysis to study allocation, choice and market coordination.

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 $250/21$, independently of the physical up probability, provided both states remain possible. These are conclusions within the specified financial market model.

Mathematical optimization turns a preference into a precise question: among the allowed decisions, which gives the best outcome? A model separates the objective function, which measures quality, from the optimization constraints, which determine the feasible set. This language unifies finding a cheap plan for a transportation problem, efficient scheduling, or an accurate model in linear regression. The separation is useful because changing a preference and changing what is possible are different modeling decisions. See Boyd and Vandenberghe, introductory optimization models.

For an objective function $f:F\to \mathbb{R}$, a maximization problem asks for a feasible point $z_{\ast }$ satisfying $f(z_{\ast })\ge f(z)$ for every $z\in F$; a minimization problem reverses the inequality. This is a global extremum. A local maximum or local minimum compares only nearby feasible points, so finding one does not settle the global question.

Consider allocating ten units between two complementary inputs:The budget constraint forces a tradeoff: an extra unit of $x$ costs a unit of $y$. The best allocation is $(5,5)$, with objective function value $25$. Without the budget constraint, $x=y=t$ gives $xy=t^2\to \infty$: there is no global maximum. Constrained optimization can therefore have a finite answer even when the corresponding problem with fewer optimization constraints does not. Its beauty is that geometry, calculus, and an arithmetic-geometric mean inequality can certify the same answer.

Optimal substructure means that the relevant parts of an optimal solution solve their own subproblems optimally. For a 0-1 knapsack problem, removing a chosen item leaves an optimal selection among the other allowed items at the reduced capacity. For sequential mathematical optimization, this becomes the dynamic programming principle: after fixing the next decision and resulting dynamic programming state, use an optimal continuation. Optimal substructure justifies the recurrence relation; overlap between subproblems explains why storing a value function can save work.

A reduction must encode primal solutions and infeasibility or unboundedness information; merely declaring a known optimum or subtracting an unknown optimum from the objective function is not a construction. The following homogeneous self-dual embedding of a linear program works without assuming the input problem has an optimum.

First remove linearly dependent equality rows by Gaussian elimination. If an eliminated row has an inconsistent right-hand side, the original problem is already certified infeasible. Return the one-variable special-form program $\min 0$ with $A^{\ast }=0$, $y=1$, and retain that certificate; no original mathematical optimization remains. Otherwise the remaining matrix has full row rank; write it as $A$ again. Put $e=1\in {\mathbb{R}}^n$ andUse nonnegative variables $x,s\in {\mathbb{R}}^n$ and $\tau ,\kappa ,\theta ,\rho \in \mathbb{R}$, with a temporary unrestricted multiplier $\lambda \in {\mathbb{R}}^m$. Impose the homogeneous linear systemAll coefficients are computable from the input. The temporary free multiplier can be eliminated without introducing cancelling positive/negative variables. DefineReplace the second equation by $(I-A^{T}H)q=0$, and substitute $Hq$ in the other equations. Because $A$ has full row rank, $A^T\lambda =q$ is equivalent to these conditions. For no remaining equality rows, simply omit $\lambda$ and its empty equations.

Let $y=(x,s,\tau ,\kappa ,\theta ,\rho )$ and $n^{\ast }=2n+4$. Collect these substituted equations into $A^{\ast }y=0$, impose $1^{T}y=1$, and let $c^{\ast }$ select the coordinate $\theta$. The resulting Karmarkar standard form isThe next two parts prove its known positive starting point and zero optimal value. Notice that normalization is legitimate for any nonzero nonnegative embedding vector because all the equations are homogeneous; it does not require a prior bound on the original optimizer.

For any $s\ge 0$, on the event $Y\ge 0$ one has $e^{sY}\ge 1$. The Markov inequality therefore gives $P(Y\ge 0)\le \mathbb{E}{e}^{sY}$, including the trivial value one at $s=0$. Taking the infimum proves the Chernoff bound.

For $s>0$ with finite moment-generating functions, independence givesConsequentlyAn effective bandwidth is an exponential-moment measure of demand at a chosen tail parameter $s$: independence makes these quantities additive. The spare capacity $\gamma /s$ pays for the desired exponential tail bound. For a cumulative-demand process over time $t$, the corresponding bandwidth would be $\log \mathbb{E}{e}^{sX(t)}/(st)$; here the time horizon is one. It is generally larger than mean demand because it charges for fluctuations, and mathematical optimization over $s$ selects the useful tradeoff.

For independent normal distributions, putThe Gaussian effective bandwidth is ${\alpha }_j(s)={\lambda }_j+s{\sigma }_j^2/2$. For $\gamma >0$ and $v>0$, the sufficient condition becomes $m+sv/2+\gamma /s\le C$. Its left side is minimized at $s_{\ast }=(2\gamma /v{)}^{1/2}$, givingThis is a sufficient Chernoff safety margin, not the exact normal tail quantile.

Indeed $X\sim N(m,v)$, so, writing $\Phi$ for the standard normal distribution function,The exact Gaussian chance constraint is thereforeThis is necessary and sufficient when $v>0$, even when $\varphi$ is negative. The Chernoff coefficient $\sqrt{2\gamma }$ is more conservative.

There is an important boundary qualification. If $v=0$, then $X=m$ deterministically, and for $\gamma >0$ the exact requirement is $C>m$, not $C\ge m$. For example, $X\equiv 0$, $C=0$, $\gamma =1$ satisfies the printed square-root condition but has $P(X\ge C)=1>e^{-1}$. Thus both Gaussian non-strict displayed forms require positive total variance, which follows if at least one flow is present and its variance is positive. With no positive variance, the deterministic boundary in an upper-tail chance constraint must be treated separately. If $\gamma \le 0$, the target upper bound is at least one and imposes no restriction; the displayed square-root discussion naturally assumes $\gamma >0$.

The original mathematical optimization problem relative to a chosen Lagrangian dual problem. In convex perturbation duality, its objective is $\phi (x)=f(x,0)$ and its value is $p(0)$. Strong duality concerns optimal values; primal attainment additionally requires an actual minimizing point.