Mathematical optimization

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.

A penalty method incorporates constraint violation into the objective with a parameter controlling its cost. For an equality constraint $c(x)=0$, the quadratic penalty method adds a multiple of $\Vert c(x){\Vert }_2^2$; a power penalty uses higher even powers. The penalty can allow infeasible iterates while encouraging feasibility as the cost grows. This differs from a logarithmic barrier, whose domain itself excludes the constraint boundary and exterior. Existence of a penalized stationary point, convergence of its constraint violation and convergence of the primal points are separate questions.

For an equality-constrained optimization problem, an even integer $p\ge 2$ makes this a nonnegative penalty for constraint violation. Its derivative is $\nabla f+{\mu }^{-1}D{c}^T{c}^{p-1}$, with the power applied coordinatewise. The case $p=2$ is the quadratic penalty. Reducing $\mu$ increases the cost of infeasibility; it does not itself ensure that computed stationary points or minimizers stay bounded.

At a stationary point of the power penalty, define the displayed multiplier estimates. Its stationarity equation becomes $\nabla f-D{c}^{T}y=0$. If $\mu \downarrow 0$ and these multipliers are bounded, then each $c_i\to 0$. Along any convergent primal subsequence, a further multiplier subsequence converges and yields equality-constrained first-order KKT conditions at the limit. This is a statement about finite cluster points: bounded multipliers alone do not prove convergence or boundedness of the primal iterates.

For smooth constraints $g_i\ge 0$, minimizeapproximately in $x$, then update the nonnegative Lagrange multipliers by the displayed projected rule. Equality constraints instead contribute $-{\nu }_j{h}_j+h_j^2/(2\mu )$ and use the unprojected update ${\nu }_j^{+}={\nu }_j-h_j/\mu$. The construction combines Lagrangian duality with a quadratic penalty method.

For an inequality, the exact identity is $\min (g_i,\mu {\lambda }_i)=\mu ({\lambda }_i-{\lambda }_i^{+})$. Its unshifted negative part satisfies $\min (g_i,0)=\mu \min ({\lambda }_i-{\lambda }_i^{+},0)$. On a violated constraint, accurate new multipliers therefore give violation of the order of $\mu$ times the multiplier error. This can achieve high feasibility accuracy without a vanishingly small $\mu$, reducing condition number difficulties. The negative-part qualification is essential if an iterate approaches a binding constraint from the feasible side.

For constraints $h=0$, $g\ge 0$, minimize the displayed merit function for progressively smaller $\mu >0$, where $g_i^{-}=\min (g_i,0)$. Increasing the quadratic penalty discourages constraint violation. In a violated inequality, differentiation gives the multiplier estimate ${\lambda }_i=-g_i/\mu$; an inactive inequality has estimate zero. Thus obtaining small violations by this method alone typically requires a very small $\mu$, which may cause a large condition number in the inner minimization.

A merit function is a scalar objective function used by an iterative constrained algorithm to balance objective reduction and feasibility. It permits a line search or other acceptance test even when the original objective function alone is insufficient to judge progress. Quadratic penalty methods and the augmented Lagrangian method give two constructions with different treatments of multiplier information.

Adding an optimization constraint shrinks the admissible set, so it cannot lower the infimum of the same objective function. Every value attained on the smaller set was already available on the larger set. If both minima exist and the larger problem has a unique minimizer absent from the smaller set, the inequality is strict. This compares beam energies for free, pinned, and clamped endpoints without evaluating the energy integrals.

If a real-valued function $g$ has a zero in the feasible region, then $g^2-c\ge -c$, with equality precisely on that zero set. The minimum can therefore occur along a curve or a higher-dimensional set rather than at isolated critical points. To maximize it on a compact feasible region, maximize $|g|$: both the largest and the smallest values of $g$ must be considered, since a large negative value also has a large square.

The metric k-center problem chooses at most $k$ centers from a finite metric space to minimize the largest distance from a point to its nearest center. For $1\le k\le |V|$, exactly $k$ centers gives the same optimum: extra centers never increase the radius. The restriction that centers belong to $V$ matters; allowing centers anywhere in an ambient metric space is a different problem.

The basic packing argument is short. If a radius-$r$ solution uses $k$ centers, its $k$ closed balls cover $V$. Two points assigned to the same center have distance at most $2r$ by the triangle inequality. Thus $k+1$ points with pairwise distances greater than $2r$ certify that no radius-$r$ solution exists. Greedily selecting a new center only outside all existing radius-$2r$ closed balls therefore uses at most $k$ centers whenever a radius-$r$ solution exists, and its final covering radius is at most $2r$. The farthest-first traversal achieves the same approximation ratio without knowing $r$.

Starting with an arbitrary point in a finite metric space, repeatedly select a point maximizing its distance to the selected set. Maintain each point's distance to its nearest selected center; each new center updates all those distances, giving $O(k|V|)$ distance evaluations for $k$ centers.

For the metric k-center problem, let $R$ be the final covering radius and add a point realizing $R$ to the $k$ selected centers. Every pair among these $k+1$ points has distance at least $R$: at each selection the current maximum distance is at least its final value. If the optimum radius is $r^{\ast }$, two of these points belong to the same optimal radius-$r^{\ast }$ closed ball, so the triangle inequality gives $R\le 2r^{\ast }$. The case $R=0$ is already optimal. This proves a factor-two approximation algorithm.

The set of minimizers of an objective:It is a set of inputs, whereas the minimum is an objective value. The argmin can be empty if an infimum is not attained, a singleton, or a larger set.

If $\varphi$ is strictly increasing on the range of $f$, then $f(x)\le f(y)$ if and only if $\varphi (f(x))\le \varphi (f(y))$. Quantifying over every $y$ proves that $f$ and $\varphi \circ f$ have the same argmin, whether or not a minimum is attained. Squaring therefore preserves the argmin of a nonnegative objective, while squaring a signed objective need not preserve its argmin.

A line search chooses a positive step size $\alpha$ along a search vector $s$, updating $x$ to $x+\alpha s$. For a differentiable function $f$, a descent direction makes sufficiently short steps decrease the objective function; an Armijo condition quantifies the decrease, while the Wolfe conditions also prevent accepting an unnecessarily short step.

Suppose $f$ is bounded below on its initial level set, continuously differentiable with a Lipschitz gradient nearby, and each descent direction $p_k$ uses a step satisfying fixed Wolfe conditions. If $\cos {\theta }_k=-\nabla f(x_k{)}^T{p}_k/(\Vert \nabla f(x_k)\Vert \Vert p_k\Vert )$, the displayed series converges. In particular a uniform positive lower bound on these cosines gives $\nabla f(x_k)\to 0$.

For a gradient Lipschitz constant $L$, the curvature condition gives ${\alpha }_k\ge (1-\eta )(-\nabla f^T{p}_k)/(L\Vert p_k{\Vert }^2)$. Sufficient decrease then gives $f(x_k)-f(x_{k+1})\ge \sigma (1-\eta ){\cos }^2{\theta }_k\Vert \nabla f(x_k){\Vert }^2/L$. Summing and using the lower bound on $f$ proves the assertion.

A search direction is the nonzero vector $p_j$ used in the displayed optimization update. In a line search with positive step size, its orientation matters: a descent direction has negative directional derivative of the objective function. Minimization over a full line instead permits either sign of ${\alpha }_j$.

A line search that finds a global minimizer along the chosen ray, provided one exists. For a negative gradient direction, its decrease in the objective function is at least that of any admissible fixed step size. The cost of solving this one-dimensional minimization problem must be included when comparing computation time.

Target: vector-space.bigb, under Vector subspace.

A vector $s$ is a descent direction for a differentiable function $f$ at $x$ if its directional derivative $\nabla f(x{)}^{T}s$ is negative. The first-order expansion $f(x+\alpha s)=f(x)+\alpha \nabla f(x{)}^{T}s+o(\alpha )$ then gives $f(x+\alpha s)<f(x)$ for sufficiently small positive $\alpha$. The negative gradient is a descent direction whenever the gradient is nonzero.

For a nonzero gradient, this unit direction minimizes the directional derivative among Euclidean unit directions. The Cauchy-Schwarz inequality gives $\nabla f(x{)}^{T}p\ge -\Vert \nabla f(x){\Vert }_2$, with equality for the displayed direction. The steepest descent method usually uses the equivalent unnormalized direction $-\nabla f(x)$ and chooses a separate step length. A different choice of norm can change the steepest direction.

For $0<{\beta }_1<1$ and a descent direction $s$, the Armijo condition asks for a decrease at least a fixed fraction ${\beta }_1$ of the decrease predicted by the first-order Taylor expansion. Put $d=\nabla f(x{)}^{T}s<0$. Differentiability gives $f(x+\alpha s)-f(x)-{\beta }_1\alpha d=(1-{\beta }_1)\alpha d+o(\alpha )<0$ for all sufficiently small positive $\alpha$. Thus the condition is satisfiable without a second derivative.

Start with a trial step size ${\alpha }_0>0$ and repeatedly replace $\alpha$ by $\rho \alpha$, with $0<\rho <1$, until the Armijo condition holds. For a differentiable function and a descent direction, the short-step argument in the Armijo condition proves finite termination. This alone does not enforce the curvature part of the Wolfe conditions.

For a continuously differentiable function, a descent direction $s$ and $0<{\beta }_1<{\beta }_2<1$, the Wolfe conditions require both the Armijo condition andThis second inequality is the weak curvature condition: the slope must have become less negative. The strong variant instead requires $|\nabla f(x+\alpha s{)}^{T}s|\le {\beta }_2|\nabla f(x{)}^{T}s|$. The weak version already guarantees a positive curvature pair for the Quasi-Newton secant equation.

Suppose $f$ is continuously differentiable, $s$ is a descent direction, and $f(x+\alpha s)$ is bounded below for $\alpha \ge 0$. A positive step size satisfying the weak Wolfe conditions exists. To prove this, put $\varphi (\alpha )=f(x+\alpha s)$, $d={\varphi }^{\prime }(0)<0$, and $h(\alpha )=\varphi (\alpha )-\varphi (0)-{\beta }_1\alpha d$. The Armijo condition proof shows $h<0$ just to the right of zero. Boundedness below gives $h(\alpha )\to +\infty$. Consequently there is a first positive zero $A$, with $h\le 0$ on $[0,A]$. By the mean value theorem, some $t\in (0,A)$ satisfiesAt $t$, $h(t)\le 0$ gives the Armijo condition, and the displayed derivative gives the weak Wolfe conditions.

Run a local optimization method from multiple initial points and compare the feasible solutions it returns. This can explore different attraction regions, but a finite set of starts does not generally certify a global minimum.

Optimization of an objective given as a ratio, such as area divided by perimeter. When the denominator is positive, a trial ratio $r$ can be tested by maximizing numerator minus $r$ times denominator.

For maximizing $A(x)/B(x)$ with $B(x)>0$, repeatedly maximize $A(x)-rB(x)$ and update $r$ to the ratio at the selected maximizer. If the maximum difference is zero, $r$ is the optimal ratio. Exact convergence claims require the relevant existence and regularity assumptions.

A constraint qualification is a regularity hypothesis on optimization constraints that guarantees a specified optimality or duality conclusion. For the necessity of Karush-Kuhn-Tucker conditions, an appropriate constraint qualification ensures that a local minimum admits suitable Lagrange multipliers; linear independence of the gradients of equality optimization constraints and active constraints is one sufficient hypothesis in KKT regularity at a local minimum.^[ref] Slater's condition provides a different constraint qualification for convex optimization, yielding strong duality and dual attainment.^[ref]

At a feasible point for smooth $h=0$, $g\ge 0$, the equality gradients must be independent and there must be a direction $v$ with $Dhv=0$ and $D{g}_{i}v>0$ for every active inequality. It supplies a first-order direction strictly into all active inequality constraints while respecting the equality tangent space. This constraint qualification ensures the usual Karush-Kuhn-Tucker conditions are necessary for local optimality. For a strictly convex quadratic inequality restricted to an affine equality space, it holds at every feasible point exactly when a strictly feasible point exists; moving from a boundary point toward a strictly feasible point supplies the required direction.

For smooth equality constraints $h_j=0$ and inequality constraints $g_i\ge 0$, this condition requires linear independence of all equality gradients and active inequality gradients at the feasible point. It ensures existence of Lagrange multipliers at a local optimum and uniqueness of their values for a fixed objective gradient. It implies the Mangasarian–Fromovitz constraint qualification by solving the independent gradient equations with zero equality derivatives and positive active inequality derivatives.

Scheduling assigns jobs to processing resources and orders their execution subject to resource and precedence requirements. Objectives include completion time, lateness and throughput. In single-machine sequencing with all jobs mandatory, the total processing time is constant, but order-dependent setups can still change completion time. With parallel machines, machine allocation and sequencing jointly determine the parallel-machine makespan with sequence-dependent setups.

For single-machine jobs all available at time zero, order by nondecreasing deadline. Keep a tentative on-time list. Whenever appending a job makes its completion exceed its deadline, delete a job of largest processing time from that list and place it on a rejected list. Append all rejected jobs at the end. This minimizes the number of late jobs: at the first missed deadline at least one job of that prefix must be rejected, and rejecting a longest one frees at least as much processing time as any alternative. The exchange argument applies recursively to the remaining prefixes. The algorithm needs no ordering of the rejected jobs to determine the minimum count.

The time at which all work in a scheduling instance has finished, equivalently the largest completion time measured from a common start. For divisible job sizes $t_i\ge 0$ and positive machine speeds $s_j$, when each machine's completion time is its total assigned size divided by its speed, the minimum makespan is ${\sum }_i{t}_i/{\sum }_j{s}_j$. The lower bound follows from total processing capacity; assigning the fraction $s_j/{\sum }_h{s}_h$ of each job to machine $j$ attains it.

On one server with all jobs initially available, nonnegative fixed durations and no sequence-dependent setup, a nondecreasing-duration order minimizes the sum of completion times. Swapping adjacent durations $a>b$ reduces their combined contribution by $a-b$ and changes no later completion time, because their total duration is unchanged. Repeated adjacent exchanges remove every inversion. The sum of pre-service waiting times has the same optimum, differing by the fixed total duration.

Partition jobs between machines and choose an ordering on each machine. Machine $r$ has load $C_r$ equal to its processing times, initial setup and internal changeovers; the completion time of all jobs is the maximum of these loads. Minimize a variable $C_{\max }$ subject to $C_r\le C_{\max }$ for every machine. Branch and bound can combine machine-assignment decisions with route bounds; heuristic moves relocate jobs between machines, swap jobs, and reorder blocks. Minimizing the sum of route costs alone does not generally minimize the makespan.

An objective function is a real-valued function assigning a score to each decision under consideration. An optimization problem seeks a feasible solution maximizing or minimizing this score. The optimizing decision and its score are different objects: in the budget constraint example, the decision is $(5,5)$ and the optimal value is $25$.

Choosing an objective function expresses what matters. With $x+y=10$ and $x,y\ge 0$, maximizing $x+y$ makes every feasible point equally good; maximizing $x$ selects $(10,0)$; maximizing $xy$ rewards balance. If $x,y$ are side lengths, $xy$ is a rectangle's area, and the budget constraint fixes its perimeter at $20$. The same mathematics then says that a square encloses the largest area among these rectangles.

For the product objective function, the positive level sets $xy=c$ are hyperbolas. Each collects decisions with identical scores. The highest attainable level set touches the feasible set at $(5,5)$; higher ones miss it entirely.

The product $xy$ is neither a convex function nor a concave function on the positive quadrant: along $(t,t)$ it is $t^2$, while along $(t,10-t)$ it is $10t-t^2$. Yet its restriction to this feasible set is a strictly concave function. Thus the geometry of the allowed decisions can make an otherwise nonconcave maximization problem tractable. Replacing $f$ by $-f$ always converts a maximization problem into an equivalent minimization problem.

// Target: mathematical-optimization.bigb

Project scheduling asks how quickly a collection of dependent activities can finish. Adding their durations usually overestimates the answer, because independent activities can run together; taking only the longest single activity usually underestimates it, because some activities must wait. The critical path method identifies the chain of dependencies that determines the finish time. Its simplest model assumes known, fixed durations, unlimited parallel processing, and precedence requirements saying that each predecessor must finish before its successor starts. These are the assumptions of the basic model in Hendrickson, Project Management for Construction, §10.2.

Represent each activity by a vertex of a finite Directed acyclic graph; an edge $i\to j$ means that activity $j$ waits for activity $i$. Activity $i$ runs without interruption for duration ${\tau }_i\ge 0$, starting at $t_i\ge 0$. The optimization constraints and project finish time areThe objective function is to minimize $T$. All durations and start times use the same time unit, and the project starts at time zero. The Directed acyclic graph assumption allows a topological order in which every predecessor is processed first.

Consider this small, abstract project:

Activities A and E may start together. After A finishes, B and C may run together, but D must wait for both. F must similarly wait for both D and E: a merge means all incoming requirements must hold. This activity-as-vertex convention keeps durations on the activities and uses arrows only to express precedence.

Unlimited parallel processing is essential to the equality between the longest graph path duration and the optimal finish time. For example, two independent chains, each containing two activities of duration 3, have longest graph path duration 6. Two processors can finish both chains in 6, but one processor needs 12 because all four activities must run sequentially. Thus with limited resources the longest graph path still gives a lower bound, but it need not be achievable. Such resource requirements belong to the broader subject of scheduling.

// Target: mathematical-optimization.bigb

The critical path method calculates an earliest schedule, a latest schedule for a chosen finish time, and each activity's task float. A critical path is a start-to-finish graph path whose total duration is greatest. There can be several such graph paths, and every one constrains completion. In the six-activity project scheduling example, the critical graph path is A-C-D-F, of duration $3+4+2+1=10$.

Add a zero-duration source $s$ before every initial activity and a zero-duration sink $z$ after every terminal activity. Give each edge $i\to j$ weight ${\tau }_i$, including zero weight on edges leaving $s$. This produces a weighted graph in which a graph path's weight counts every activity on it exactly once. The possible source-to-sink graph paths in our example, omitting the dummy endpoints, are A-B-D-F with weight 8, A-C-D-F with weight 10, and E-F with weight 4.

Every feasible schedule must accommodate each of these sequential chains. Consequently,This bound applies to all source-to-sink graph paths, not just the one we happen to inspect. The critical path method attains the bound by setting each activity's earliest start $E_i$ to the maximum of its predecessors' earliest finish times:Evaluate this recurrence in a topological order, obtained by topological sorting. Each $E_j$ satisfies every incoming optimization constraint, so these times form a feasible solution. The same recurrence calculates the greatest weight of a graph path from $s$ to $j$; hence the feasible finish $E_z$ matches the lower bound. This is dynamic programming on a Directed acyclic graph, rather than an enumeration of all graph paths. See Paul Johnson, Scheduling and longest paths, longest-path algorithm. The linear programming formulation and its certificate are developed in project scheduling duality and unit-flow certificate for project duration.

For our project scheduling example, $E_A=E_E=0$, $E_B=E_C=3$, and the two merges giveF finishes at 10. All six activities are completed, even though E is absent from the critical graph path. Recording which predecessor attains each maximum lets us trace a critical graph path backward from the sink; retaining tied choices exposes multiple critical graph paths.

Now fix the project start at zero and the finish at $T_{\ast }=10$. The latest starts $L_i$ come from a backward pass in reverse topological order:Every activity must finish by the earliest of its successors' latest starts, explaining the minimum here. This gives $L_F=9$, $L_D=7$, $L_E=6$, $L_B=5$, $L_C=3$, and $L_A=\min (5-3,3-3)=0$. These latest times themselves form a feasible solution finishing at 10. The backward calculation depends on the chosen finish time; a later deadline would give different latest times and task floats. The forward and backward passes are described in Olivier de Weck, MIT ESD.36 Lecture 2, slides 22–29.

Changing a duration can change which graph paths are critical. If B's duration becomes 4, A-B-D-F and A-C-D-F both take 10: there are two critical graph paths. Shortening C alone then cannot reduce the finish time, because the chain through B still takes 10. If B's duration instead becomes 5, the earliest starts of D and F become 8 and 10, and the finish becomes 11. A-B-D-F is now the unique critical graph path; C has task float 1 relative to that new optimal finish. These calculations show why the critical path method is useful for understanding where a duration change matters, even in a project containing many parallel activities.

Task float, also called total float or task slack, measures an activity's available start-time delay relative to its earliest start, while allowing a feasible schedule that meets the fixed project finish. For earliest start $E_i$, latest start $L_i$, and fixed duration ${\tau }_i$, it isIn the six-activity project scheduling example with start zero and finish 10, B has task float 2 and E has task float 6. B can move from the interval $[3,5]$ to $[5,7]$, and E from $[0,3]$ to $[6,9]$, without changing D's or F's earliest starts. A, C, D, and F have zero task float. With the finish fixed to the optimal duration and the basic critical path method assumptions, zero task float identifies exactly the activities lying on at least one critical graph path. See Hendrickson, §10.4, Activity Float and Schedules.

Task float is not generally an independent allowance that can be spent separately on every activity. For a small example, let two duration-1 activities X then Y form one chain, running in parallel with a separate duration-4 activity. The optimal finish is 4. X has earliest/latest starts 0/2 and Y has earliest/latest starts 1/3, so each has task float 2. Delaying X to 2 forces Y to start at 3, using Y's allowance too. Choosing X at its latest start 2 and Y at its earliest start 1 violates precedence, although both chosen times lie inside their individual ranges. The optimization constraints still couple the decisions. Here B and E can both use their full task floats together because they lie on separate branches; that freedom must be checked from the Directed acyclic graph.

// Target: mathematical-optimization.bigb

On the augmented precedence graph, the linear programming problemhas dual $\max {\sum }_{i\to j}{\tau }_i{f}_{ij}$, with $f\ge 0$ a unit source-to-sink flow. Equivalently, the dual is the negative of the optimal uncapacitated minimum-cost flow value with arc costs $-{\tau }_i$. The flow selects a longest path, while the time variables provide a matching weak duality bound.

// Target: mathematical-optimization.bigb

A feasible timetable with finish time $T$ and a unit flow carried on a precedence path of total duration $T$ certify optimality. Summing the inequalities $t_j-t_i\ge {\tau }_i$ along that path proves every schedule needs at least $T$, while the timetable attains it.

// Target: computer-science.bigb

Maxima and minima are extrema of a real-valued function. A global maximum of $f$ on its domain $D$ is a point $x_{\ast }$ with $f(x)\le f(x_{\ast })$ for every $x\in D$; a global minimum reverses the inequality. A local extremum requires the inequality only in a neighbourhood of the point within $D$. In constrained optimization, $D$ is the feasible set, so an extremum is tested relative to the constraints rather than in every ambient direction. Thus a constrained local maximum or local minimum can occur at a boundary point without being an interior critical point.

A local extremum of a real-valued function is either a local maximum or a local minimum, with comparisons restricted to a neighbourhood in its domain. A differentiable interior local extremum is a stationary point, but the converse can fail, as $f(x)=x^3$ at zero shows.

For positive constants $A,\alpha ,\beta$, a Cobb–Douglas production function describes output in terms of capital $K$ and labour $L$. It is homogeneous of degree $\alpha +\beta$. Under $K+wL=b$ with $b,w>0$, its unique nonnegative-input optimum is $K=\alpha b/(\alpha +\beta )$ and $L=\beta b/[w(\alpha +\beta )]$, obtained by maximizing the strictly concave logarithm along the budget line. The optimized output has derivative $(\alpha +\beta )\varphi (b)/b$, equal to its budget Lagrange multiplier. When $\alpha +\beta >1$, the unconstrained Lagrangian supremum over the positive orthant is infinite for every finite multiplier, despite the finite constrained optimum; the global dual representation must not be presumed in this case.

Heuristic optimization seeks useful feasible solutions without necessarily providing a universal approximation ratio or a polynomial worst-case guarantee. Examples are local search, simulated annealing and tabu search. A claimed approximation algorithm needs a separate proved performance guarantee.

Tabu search keeps a short-term memory of recently reversed moves or visited attributes and prohibits them temporarily, reducing cycling in local search. It can select the best admissible neighbor even when that neighbor worsens the objective; an aspiration rule permits a tabu move when it improves the best known solution. For allocations, transfers and exchanges maintain feasibility and recent reverse transfers can be tabu.

Simulated annealing accepts worse feasible solutions to escape a local minimum. Minimize an objective function $E(x)$, analogous to energy. Effective temperature $T>0$ has the same units as $E$, absorbing the Boltzmann constant; it controls exploration, rather than a material's thermodynamic temperature.^[ref]

Given current feasible point $x$, draw $y$ from a proposal distribution $q(x,y)$. For a symmetric proposal distribution, $q(x,y)=q(y,x)$, use the Metropolis–Hastings acceptance probabilityAccept with this conditional probability; on rejection retain $x$. Every downhill or equal-cost proposal is accepted. Draw a fresh uniform random variable $U$ on $(0,1)$ and accept if $U<a_T(x,y)$. The off-diagonal transition probability $P_T(x,y)=q(x,y)a_T(x,y)$ includes proposing $y$.^[ref]

For a maximization problem with objective function $f$, set $E=-f$: every improving proposed neighbor is accepted, and a worsening move of loss $\Delta =f(x)-f(y)>0$ has conditional probability $\exp (-\Delta /T)$ of acceptance, under the same symmetry assumption. Likelihood-power annealing uses precisely this sign convention for a log-likelihood. Retain the best feasible solution seen, since the current state can worsen even after a global minimum has been visited.

If the proposal distribution is asymmetric, use the full Metropolis–Hastings acceptance probability, for $q(x,y)>0$,A missing reverse proposal gives zero acceptance. Even a downhill proposal need not be accepted with probability one in this case. Choosing uniformly among a variable number of neighbors is generally asymmetric: $q(x,y)=1/d(x)$ and $q(y,x)=1/d(y)$ give the correction $d(x)/d(y)$, where $d$ is vertex degree.^[ref]

The useful idea is to separate exploring from insisting on improvement: an uphill move can open a route to a better feasible solution. Its usefulness depends on the proposal distribution, the scale of the objective function, and the cooling schedule for simulated annealing. Finite practical schedules carry no general guarantee of finding a global minimum.

To maximize a log-likelihood, use energy $-\ell$ and Boltzmann distribution proportional to $e^{\ell /T}=L^{1/T}$ at temperature $T>0$. Reversing this sign favors likelihood minima and can make the probability density function nonnormalizable. For Poisson observations with total $s$ and sample size $m$, with respect to $d\lambda$ the normalized probability density function isIts mean is $(s+T)/m$ and variance $(sT+T^2)/m^2$, so it concentrates at the maximum-likelihood estimate $s/m$ as $T\downarrow 0$. Cooling of equilibrium laws and convergence of a particular changing-temperature chain are different statements; the latter requires mixing or a direct chain argument.

For $m$ independent binomial distribution observations with fixed trial count $n$ and total successes $s$, the likelihood-power probability density function relative to $dp$ is $p^{s/T}(1-p{)}^{(mn-s)/T}$. Its normalized law is the displayed beta distribution. Its mean tends to $s/(mn)$ and its variance tends to zero as $T\downarrow 0$, including endpoint maxima. Energy for maximizing a log-likelihood is its negative; the opposite sign reverses the optimization.

Let $\bar{x}=m^{-1}{\sum }_i{x}_i$ and $S={\sum }_i(x_i-\bar{x}{)}^2>0$. With Lebesgue base measure $d\mu dv$ for $v={\sigma }^2$, the likelihood-power law has conditionalsThe joint law is proper for $T<m/3$, since its marginal $v$ is inverse-gamma distribution with shape $m/(2T)-3/2$ and scale $S/(2T)$. There is also a direct convergence proof for successive Gibbs sampling updates with deterministic $0<T_n\le m/10$ and $T_n\to 0$. Update ${\mu }_n$ from $v_{n-1}$, then $v_n$ from ${\mu }_n$. Inverse-gamma distribution moments and conditional normal moments giveThe coefficients of the preceding moments are bounded by $1/6$ and $1/8$, so these moments stay bounded from a finite deterministic initial variance. Letting $T_n\to 0$ gives $\mathbb{E}{v}_n\to S/m$ and $\mathbb{E}{v}_n^2\to (S/m{)}^2$. Also $\mathbb{E}({\mu }_n-\bar{x}{)}^2=T_n\mathbb{E}{v}_{n-1}/m\to 0$. Thus the iterates converge in mean square to the normal maximum-likelihood estimate.

Consider the chosen finite minimization problemOnly adjacent integers are neighbors. At each interior state propose left or right with probability $1/2$ each; at an endpoint propose its sole neighbor with probability $1/2$ and itself with probability $1/2$. This proposal distribution is symmetric, including at the endpoints. The local minimum at $1$ is relative to these allowed moves; $4$ is the unique global minimum.

At $1$, improving-only local search rejects both neighbors because $E(0)=2$ and $E(2)=4$ exceed $E(1)=1$. For simulated annealing, choose $T_{\ast }=1/\ln 2$, using the natural logarithm. Conditional on proposing $2$ from $1$, the acceptance probability isThe one-step transition probability is instead $P_{T_{\ast }}(1,2)=(1/2)(1/8)=1/16$. Both subsequent rightward proposals are downhill, so the conditional probability of the precise next three states being $2,3,4$, given $X_0=1$ and fixed $T_{\ast }$, isThis is one possible escape route, not the probability of eventually reaching $4$. Rejections, excursions toward $0$, and repeated attempts give many other sample paths. The calculation establishes possibility, without claiming a general performance advantage from a selected sample path.

For comparison, halving $T_{\ast }$ makes the uphill acceptance probability $1/64$; doubling it makes that probability $1/(2\sqrt{2})$. Cooling makes it harder to leave this local minimum, even though the stationary distribution increasingly favors the global minimum. That tension is the central scheduling problem.

On a finite state space $F$ with finite objective function values, the fixed-$T$ target is a Boltzmann distribution:The partition function $Z_T$ normalizes the weights but cancels from the Metropolis–Hastings acceptance probability. A short detailed balance proof explains the target. With symmetric $q$ and $x\ne y$,Summing over $x$ gives ${\pi }_T{P}_T={\pi }_T$, so this is a stationary distribution. On a finite state space, a connected graph of positive symmetric proposals makes the accepted Markov chain an irreducible Markov chain. Convergence from any starting state additionally requires an aperiodic Markov chain; one positive self-transition suffices under irreducibility. Replacing $q$ by $(I+q)/2$ ensures this. For asymmetric $q$, require connectivity through bidirectional proposals: one-way proposals are rejected.^[ref]

In the five-state barrier example for simulated annealing, $T_{\ast }=1/\ln 2$ gives exact Boltzmann weights $2^{-E(x)}$. Multiplying by $16$ givesFor the uphill edge, detailed balance is visible numerically:Thus the global minimum has the largest individual stationary probability, $16/33$, but is far from certain at this positive $T_{\ast }$. At $T_{\ast }/2$ the exact stationary distribution is $(16,64,1,16,256)/353$.

For any finite $F$, let $M$ be the set of global minima and $E_{\min }$ the smallest objective function value. Cancelling $e^{-E_{\min }/T}$ from numerator and denominator shows that each nonminimal state's weight tends to zero as $T\downarrow 0$, while every state in $M$ has equal weight. Therefore ${\pi }_T$ tends to the uniform distribution on $M$. This is a statement about a family of equilibrium probability distributions; it does not prove that a cooling Markov chain follows that family.

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]

Local search repeatedly improves a feasible solution within a specified neighborhood until no improving move remains. For an allocation, neighbors can transfer an item or exchange items between bidders while preserving the partition. A local optimum need not be a global optimum; restarting from several initial solutions can explore different basins.

A local search method that retains one current candidate and repeatedly chooses an improving neighbor of its objective. For a conflict-minimization constraint satisfaction problem, a candidate can assign all variables within their constraint domains while violating some inter-variable constraints; the objective counts those violations. Zero conflicts certifies a solution, while a positive-conflict local minimum need not certify impossibility. Plateaus and local minima motivate sideways moves, randomized choices and restarting. Prescribed variables must remain fixed in every initialization and move.

A repair method for a constraint satisfaction problem: choose a currently conflicted, movable variable, and assign a permitted value minimizing its number of violated constraints with the other variables held fixed. Tie handling can permit sideways moves. For the queens completion problem, keep prescribed rows fixed, select a conflicted unfixed row, and choose a column minimizing attacks. Never interpret failure to improve as proof that no solution exists.

A feasible point satisfies every optimization constraint of an optimization problem. For the budget constraint example, the feasible set is exactlyIt is the line segment from $(0,10)$ to $(10,0)$, a compact set and a convex set. The point $(2,8)$ is feasible, with product $16$; $(6,6)$ has a larger product $36$ but violates the budget constraint. Feasibility answers whether a decision is allowed; optimality asks whether any allowed decision is better. The extreme value theorem guarantees that this continuous objective function attains its maximum on this nonempty compact set.

Eliminating $y$ gives a one-variable objective function:By completing the square, $q(x)\le 25$, with equality exactly at $x=5$. Alternatively its derivative is $q^{\prime }(x)=10-2x$, which vanishes at $5$; the endpoint values are both zero. Completing the square proves global optimality directly, whereas the first-order optimality condition only identifies a candidate. It also quantifies the cost of imbalance: moving to $(5+\delta ,5-\delta )$ with $|\delta |\le 5$ loses exactly ${\delta }^2$ units of product. The arithmetic-geometric mean inequality gives another short certificate: $\sqrt{xy}\le (x+y)/2=5$, with equality exactly when $x=y$.

For a transportation problem with capacity inequalities, feasibility requires nonnegative shipments, row totals no greater than factory capacities and column totals equal to shop demands. Feasibility alone does not prove minimal cost: a matching transportation dual certificate with capacity inequalities provides an optimality proof. The feasible set can be empty, and a finite infimum need not be attained even when the set is nonempty.

The set of all feasible points of an optimization problem. It depends on the optimization constraints and the decision domain; the objective function ranks its members.

Think of three successive questions. Which decisions can be represented in the model? Which satisfy every optimization constraint? Which of those receive the best objective function value? For decisions $z$ in a domain $D$, inequalities $g_i(z)\le 0$ and equations $h_j(z)=0$ define the feasible regionThe domain must be contained in the domain of a function for every function being evaluated; choosing integers rather than real numbers as decisions can also change the feasible set. Constraint satisfaction determines membership of $F$. Minimizing an objective function $f$ then compares its members by $f(z)$, with optimal value ${\inf }_{z\in F}f(z)$. Changing the scores while keeping $D$ and the optimization constraints fixed leaves $F$ unchanged, provided the new objective function is defined throughout $D$. These distinctions separate an allowed decision from a best decision.^[ref]