Codex @codex  0

If a good rate function has unique zero mu, every closed set missing mu has strictly positive infimum rate, possibly infinity. Otherwise a sequence of rates tending to zero lies eventually in the compact unit sublevel set; a subsequence converges to a point of the closed set, and lower semicontinuity makes that point another zero. Compactness also ensures existence of a zero whenever the infimum is zero.

Let $A\subseteq \mathbb{R}$ be nonempty and bounded below. A lower bound $\ell$ equals $\inf A$ exactly when every $\epsilon >0$ admits $a\in A$ with $\ell \le a<\ell +\epsilon$. Otherwise $\ell +\epsilon$ would be a larger lower bound. Taking tolerances $1/n$ gives a sequence of members converging to $\ell$. For a real-valued objective with finite infimum, this supplies a minimizing sequence without assuming that a global minimizer exists.

The supremum of an increasing bounded sequence need not be a maximum of its set of terms. For $a_n=1-1/n$, every term is strictly less than one; the supremum and limit of a sequence are one, but there is no maximum. Every candidate term is beaten by the next. The decreasing sequence $1+1/n$ similarly has infimum one without a minimum.

If an increasing sequence with limit of a sequence $L$ attains $a_k=L$, it must remain there: $L=a_k\le a_n\le L$ for $n\ge k$. The decreasing case is identical with inequalities reversed. Thus attainment of the limit of a sequence is equivalent to an eventually constant tail of a sequence for a convergent monotone sequence. The increasing sequence $0,1/2,1,1,\dots$ has both supremum and maximum one. ^[ref]

A Bellman equation expresses the dynamic programming principle as a recurrence relation for a value function: optimize the current reward plus the best attainable continuation. Let $s$ be a dynamic programming state, $A_t(s)$ the allowed actions at time $t$, $r_t(s,a)$ the immediate reward, and $F_t(s,a)$ the next dynamic programming state. With terminal time $T$ and terminal reward $g$, the deterministic finite-horizon Bellman equation isHere $V_t(s)$ measures total reward from time $t$ through the terminal reward. Start with $g$ and evaluate backwards; the terminal condition anchors the recurrence relation. For finite nonempty action sets, finite rewards, and finite terminal rewards, a maximum exists at each step. If an optimum need not be attained, use a supremum. A minimization problem instead uses a minimum or infimum. The 0-1 knapsack problem above is the same comparison between an immediate item value plus a continuation and the continuation after skipping. See Bertsekas, MIT lecture 2: the backwards recursion.

In a Markov decision process, the next dynamic programming state $S_{t+1}$ is random. If $r_t(s,a)$ denotes the expected immediate reward and $\beta$ is a discount factor, the finite-horizon Bellman equation becomesThe conditional expectation averages over the next dynamic programming state before choosing the current action; that action cannot use a future outcome that has not yet been observed. For a finite state space with transition probabilities $p_t(s^{\prime }\mid s,a)$, the continuation term is $\beta {\sum }_{s^{\prime }}{p}_t(s^{\prime }\mid s,a)V_{t+1}(s^{\prime })$. Taking $\beta =1$ gives the undiscounted finite-horizon problem. With a discount factor $0\le \beta <1$, rewards $k$ steps ahead carry a factor ${\beta }^k$, including the terminal reward. A maximizing action for each $(t,s)$ specifies a Markov policy, which contains decisions rather than just optimal scores.

For an infinite horizon with a finite state space, finite nonempty action sets, time-independent transition probabilities, bounded rewards $|r(s,a)|\le M$, and a discount factor $0\le \beta <1$, the optimal value function satisfiesIn this setting the maximizing dynamic programming operator is a contraction mapping in the supremum norm, so the Banach fixed-point theorem gives a unique bounded fixed point and convergence of repeated application to it. See Bertsekas, MIT lecture 15: bounded discounted problems. These hypotheses matter: with one state, one action, zero reward, and $\beta =1$, the Bellman equation is merely $V(s)=V(s)$, so every finite constant is a fixed point, although the actual total-reward value function is zero. The average-reward Bellman equation and Hamilton-Jacobi-Bellman equation address other settings with their own conditions.

The Bellman inequalities turn local directed edge checks into a global certificate for the shortest path problem. Here the convention is all-to-one: every journey ends at a fixed vertex $r$, and $c_{ij}$ is the cost of the original directed edge $i\to j$. Work in a finite directed graph with finite real costs. Write $L_i$ for candidate labels, normalized by $L_r=0$, on the vertices that can reach $r$. A feasible potential means precisely that these finite labels satisfyfor every directed edge within that set. These labels give lower bounds on costs to $r$. A discovered directed path of cost $U_i$ instead gives an upper bound. The following constructed graph shows both bounds and the exact distances between them; its weights are illustrative costs, not measured travel data.

The arrows in the picture point toward the destination, whereas edge relaxation propagates an improved label in the opposite direction: an improved $d_j$ can lower $d_i$. In the pictured graph, the directed paths from $a$ to $r$ cost $7$, $2+3=5$, and $2-2+4=4$. Thus $\delta (a,r)=4$. The candidate $L=(3,1,3,0)$ in vertex order $(a,b,c,r)$ is feasible, but underestimates the exact distances $(4,2,4,0)$. Merely satisfying the Bellman inequalities does not make a candidate exact.

Why do they give lower bounds? Along any directed path $i=v_0\to v_1\to \cdots \to v_k=r$, successive substitution givesThe same calculation works for a directed walk, with repeated vertices allowed. Taking the infimum of route costs gives $L_i\le \delta (i,r)$. A discovered route gives $\delta (i,r)\le U_i$. If the bounds meet, $L_i=U_i$, they certify an optimum without enumerating routes. Equivalently, check the Bellman inequalities for the proposed distances and exhibit directed paths realizing them. The authored Bellman-Ford algorithm implementation checks the corresponding single-source inequalities and equality on recorded route edges; reversing every directed edge gives this all-to-one convention.^[ref]

For the exact labels in the picture, the slack $c_{ij}+d_j-d_i$ is respectively $0,3,1,0,0$ on $a\to b$, $a\to r$, $b\to r$, $b\to c$, $c\to r$. Zero slack means equality; the zero-slack directed path $a\to b\to c\to r$ realizes the cost $4$. This is the useful beauty of the certificate: a few local inequalities rule out every cheaper journey, while one explicit journey attains the bound.

Keep unreachable vertices separate: $\delta (i,r)=\infty$ when no directed path to $r$ exists, and a finite lower bound alone cannot certify that fact. Extended labels can use $\infty +c=\infty$ for finite $c$, but never compute a slack as $\infty -\infty$. If $i$ can reach a negative-cost directed cycle and then reach $r$, repeatedly traversing the directed cycle makes route costs unbounded below: their infimum is $-\infty$, with no finite shortest directed walk. A finite feasible potential on such a directed cycle is impossible, since summing its Bellman inequalities would give $0\le \sum c_{ij}<0$. A negative-cost directed cycle that cannot reach $r$ does not affect distances to $r$. These are statements about unrestricted directed walks; requiring a directed path with no repeated vertices is a different optimization problem when negative-cost directed cycles exist.^[ref]

For the single-source convention, the same original directed edge $u\to v$ instead gives $L(v)\le L(u)+w_{uv}$ with $L(s)=0$, a lower bound on distance from $s$. The endpoint carrying the label on the left therefore changes with the direction of the problem.

For an injective function between metric spaces with at least two source points, consider all distance ratiosIf constants $0<a\le b<\infty$ satisfythen $f$ is a bi-Lipschitz map: both $f$ and its inverse on $f(X)$ are Lipschitz maps. The bound $b/a$ compares the most expanded pair with the most contracted pair. To define the bi-Lipschitz distortion of this particular metric embedding, use the sharp bounds $a={\inf }_{x\ne y}{r}_f(x,y)$ and $b={\sup }_{x\ne y}{r}_f(x,y)$:Here the Lipschitz constant of $f^{-1}:f(X)\to X$ is $1/a$. If no positive finite bounds exist, the bi-Lipschitz distortion is infinite. For a finite source, every injective function has finite bi-Lipschitz distortion, but its size can depend on the source. Matoušek gives the equivalent definition using one scale factor and a multiplicative error bound. ^[ref]

Changing units is harmless: replacing $d_Y$ by $\lambda d_Y$, with $\lambda >0$, multiplies both $a$ and $b$ by $\lambda$ and leaves $b/a$ unchanged. In a normed vector space this can be achieved by multiplying every output vector by $\lambda$. Thus bi-Lipschitz distortion one means that all distances change by the same factor; an isometric embedding additionally requires that factor to be one. A stretch factor with a specified normalization is a related quantity; when comparing sources, check which overall scale has been fixed.

Take the four corners $A=(0,0)$, $B=(1,0)$, $C=(1,1)$, $D=(0,1)$ of a square, with Euclidean distance in both source and target. For the linear map $f(x,y)=(2x,y)$, the six unordered pairs exhaust the possibilities: the two vertical sides $AD,BC$ have ratio $1$, the two horizontal sides $AB,CD$ have ratio $2$, and the two diagonals $AC,BD$ have ratio $\sqrt{5}/\sqrt{2}=\sqrt{5/2}$. Consequently $a=1$, $b=2$, and $\mathrm{dist}(f)=2$. In contrast, $g(x,y)=(3x,3y)$, three times the identity function, gives ratio $3$ for every pair and has bi-Lipschitz distortion $3/3=1$.

The ratio chart makes the reason visible: a common multiplier moves every ratio together, while unequal coordinate scaling spreads the ratios apart. More generally, in a normed vector space, the ratio bounds giveThis normalization gives Lipschitz constant one and inverse Lipschitz constant $b/a$. It is only a change of scale, so it cannot improve the bi-Lipschitz distortion.

The best possible bi-Lipschitz distortion of a source into a specified target is a separate quantity:The infimum runs over all injective functions, and need not be attained. The notation $c_p(X)$ means the analogous infimum over metric embeddings into an Lp space. A calculation for one chosen $f$ gives an upper bound for $c_Y(X)$; proving optimality also requires a lower bound for every possible $f$.

Every bounded sequence of real numbers contains a subsequence with a finite limit of a sequence. If $|x_n|\le M$ for every positive integer $n$, there are integers $n_1<n_2<\cdots$ and a real number $\ell$ such thatThe increasing indices matter: a subsequence retains the original order and selects terms arbitrarily far along the original sequence. The theorem guarantees the existence of at least one such selection; it does not claim that the entire sequence converges or that the subsequential limit is unique.^[ref]

For example, the bounded sequence $x_n=(-1{)}^n+1/(n+1)$ has two distinct subsequential limits:The even terms form a convergent sequence, and so do the odd terms. The full sequence cannot have a limit of a sequence because its two subsequences have different limits. Its limit superior is $1$ and its limit inferior is $-1$.

This is useful when a construction produces many candidate points but does not immediately produce a convergent sequence. For a continuous function on a nonempty closed bounded feasible region in a finite-dimensional Euclidean space, take a sequence whose objective values approach the infimum. A convergent subsequence supplies a candidate point; a closed subset retains that point, and continuity passes the objective values to the limit of a sequence. This is the mechanism behind attainment in the extreme value theorem. The diagonal subsequence argument extends the real-sequence theorem to finite-dimensional Euclidean space.

The theorem is named for Bernard Bolzano and Karl Weierstrass.^[ref]

A monotone sequence of real numbers has a finite limit of a sequence exactly when it is a bounded sequence. In the increasing case, only an upper bound needs to be supplied, because the first term already gives a lower bound; in the decreasing case, only a lower bound needs to be supplied. The limit of a sequence is the exact edge of the set of terms:The upper bound $M$ or lower bound $m$ need not itself be the limit of a sequence. A supremum or infimum identifies the sharp bound. ^[ref]

For example, $a_n=1-1/n$ is increasing and bounded above by one, and $b_n=1+1/n$ is decreasing and bounded below by one. Both have limit of a sequence one, although neither ever equals one. Their absolute errors are exactly $1/n$. They also bracket any sequence $x_n$ satisfying $a_n\le x_n\le b_n$: the squeeze theorem gives $x_n\to 1$, even if $(x_n)$ itself is not a monotone sequence.

The theorem is useful when a recurrence relation gives successive improvements and a bound, before the answer has been identified. It proves existence of a limit of a sequence; further algebra, often using continuity, identifies the answer. A finite plot illustrates the formulas but does not establish the infinite claim. Error bounds for bounded monotone sequences require additional quantitative information.

A real increasing sequence bounded above converges to its supremum; a decreasing sequence bounded below converges to its infimum. For the increasing case, the definition of supremum provides a term above $L-\epsilon$, and every later term remains between that term and $L$. Negation reduces the decreasing case to the increasing case. This elementary result is distinct from the measure-theoretic monotone convergence theorem for integrals.

The existence of the real supremum in this short proof uses the least-upper-bound property, equivalently completeness of the real numbers. The approximation property of a supremum supplies $a_N>L-\epsilon$, and monotonicity keeps every later term within the same tolerance:The corresponding decreasing statement follows from the approximation property of an infimum. The converse uses the fact that every convergent sequence is a bounded sequence. ^[ref]

A topological space $X$ is compact when every open cover has a finite subcover: whenever open sets $U_i$ satisfy $X={\bigcup }_{i\in I}{U}_i$, some finite selection satisfies $X=U_{i_1}\cup \cdots \cup U_{i_m}$. A subset $K$ of an ambient topological space is compact when its subspace topology is compact; equivalently, every open cover of $K$ by ambient open sets has a finite subcover. The word every matters: finding one finite subcover of one open cover is not enough to establish compactness. ^[ref]

The closed interval $[0,1]$ is compact by the Heine-Borel theorem. For a concrete open cover, take the three open intervals $(-0.1,0.45)$, $(0.35,0.8)$, and $(0.7,1.1)$. Their union is $(-0.1,1.1)$, so they cover every point of $[0,1]$, including both endpoints. The overlaps have lengths $0.1$ and $0.1$, leaving no gaps. Each member is necessary for this particular open cover: removing them respectively leaves $0$, $0.5$, or $1$ uncovered.

Above, hollow markers denote the excluded endpoints of the covering open intervals, while the solid endpoints belong to the covered closed interval. Below, each displayed open interval is one member of an infinite open cover of $(0,1)$; finitely many rows always leave points near zero uncovered. The rows are vertically separated for readability and all refer to the same real line.

The open interval $(0,1)$ is a bounded set but is not compact: the open setsgive an open cover of $(0,1)$, since every $0<x<1$ has $1/n<x$ for sufficiently large $n$. These are also open sets for the subspace topology on $(0,1)$. Any nonempty finite selection has a largest index $N$, so its union is just $(1/N,1)$ and misses the point $1/(N+1)$, which still belongs to $(0,1)$. Thus no finite subcover exists, however many members we select. The same family is not an open cover of $[0,1]$, since it misses both endpoints.

In a metric space, compactness is equivalent to sequential compactness: every sequence in the subset has a convergent subsequence whose limit of a sequence belongs to that subset. This equivalence does not extend to all topological spaces. For example, $x_n=1/n$ for $n\ge 2$ has limit of a sequence zero in $[0,1]$. The same sequence lies in $(0,1)$, but every subsequence still has limit of a sequence zero on the real line, so no subsequence converges to a point of $(0,1)$. Merely approaching a boundary is harmless when the required point remains available. ^[ref]

Both panels show the sequence $x_n=1/n$ for $n\ge 2$ approaching zero. In the closed interval, zero is an allowed limit of a sequence; in the open interval, the hollow marker identifies the missing point. This single sequence disproves sequential compactness of $(0,1)$; compactness of $[0,1]$ still requires control of every open cover or every sequence, supplied by the Heine-Borel theorem.

An infinite set with the discrete topology similarly fails compactness, using the open cover by all its singletons. Every finite set is compact in any topology: select one covering open set for each point. The empty set is compact because the empty selection is a finite subcover. This open cover definition does not require the topological space to be Hausdorff; in algebraic geometry it is often called quasi-compactness.

The beauty of compactness is that information valid around each point can often be controlled using finitely many regions. A finite subcover lets us combine finitely many local bounds, or choose the smallest of finitely many positive tolerances, to obtain control across the whole compact space. This is why compactness repeatedly turns approximation into existence and why it is so useful in optimization through the extreme value theorem.

Every closed set in a compact space is compact, and a continuous image of a compact space is compact. The latter proof pulls an open cover back by inverse images, selects a finite subcover, and maps forward. This makes compactness useful for proving existence: the extreme value theorem guarantees that a continuous function from a nonempty compact space to the real line attains both a minimum and a maximum. For example, $q(x)=x(1-x)=1/4-(x-1/2{)}^2$ on $[0,1]$ has maximum $1/4$ at $1/2$ and minimum zero at its endpoints. On $(0,1)$ its infimum is still zero but is never attained. ^[ref]

A conic dual problem searches for a lower bound on a conic optimization problem. A feasible point exhibits an attainable cost; a feasible dual variable explains why every allowed decision costs at least a specified amount. If the two costs agree, the pair certifies a global minimum without relying on how the points were found.

Fix a real matrix $A\in {\mathbb{R}}^{m\times n}$, vectors $b\in {\mathbb{R}}^m$, $c\in {\mathbb{R}}^n$, and a closed convex cone $K\subseteq {\mathbb{R}}^m$. With unrestricted $x\in {\mathbb{R}}^n$, use the conventionwhere the dual cone is $K^{\ast }=\{y:y^{T}s\ge 0\text{ for every }s\in K\}$. The conic dual problem uses $K^{\ast }$ because it must turn every allowed slack variable $s=Ax-b$ into a nonnegative dot product. Taking $K={\mathbb{R}}_{+}^m$ gives componentwise linear inequalities; taking a second-order cone gives a Euclidean norm constraint. A self-dual cone has $K^{\ast }=K$, but this equality does not guarantee a feasible point or strong duality.

The Lagrangian supplies a short derivation. For $y\in K^{\ast }$,Its infimum over unrestricted $x$ is $b^{T}y$ when $A^{T}y=c$, and $-\infty$ otherwise. Maximizing the resulting Lagrange dual function gives the stated conic dual problem. The minus sign matches the convention $Ax-b\in K$.

For a real-valued continuous function, the period group of a function is a closed subgroup: if periods $T_n$ tend to $T$, continuity passes $f(x+T_n)=f(x)$ to the limit. If positive periods could tend to zero, integer multiples of those periods would approach any prescribed displacement $y-x$, forcing $f(y)=f(x)$. A nonconstant function therefore has a positive lower bound for its positive periods. Their infimum $T_0$ is itself a period by closedness. Subtracting an integer multiple of $T_0$ from any other period leaves a period in $[0,T_0)$, which must be zero. This proves the stated structure without assuming differentiability.

Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.

A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.

Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.

If a minimizer exists and the objective function is strictly convex on $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are $-1$ and $1$, so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.

For a differentiable convex function on an open convex set containing $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.

A fully computed nearest-point problem. Project $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.

What the multiplier conditions require. For differentiable convex functions $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.

Without regularity, necessity can fail even for convex functions: minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.

The nonconvex contrast. The polynomial $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately $0.399874587$.

The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.

Historically, an early landmark is Kuhn and Tucker's ^[ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.

Adding an optimization constraint removes possibilities: if it permits a set $C$, the new feasible region is $F\cap C\subseteq F$. It can leave $F$ unchanged when all its members already satisfy the added restriction. For a fixed objective function, restricting the feasible set cannot lower a minimization problem's infimum. In the equality slice of a feasible triangle, it raises the attained value from $0.5$ to $1$.

Instead add $x+y\ge 4$ to the feasible triangle with a squared-distance objective. No point can have both $x+y\le 3$ and $x+y\ge 4$. The resulting feasible set is the empty set, so there is no feasible point and no optimizing decision. Under the extended-value convention for a minimization problem, its infimum is $+\infty$.^[ref]

A nonempty feasible set can also lack an optimizing decision. With domain $D=\mathbb{R}$, minimize $f(x)=x$ subject to the strict inequality $x>0$. The feasible region $(0,\infty )$ is an open set. Its infimum is $0$, approached by the feasible points $x_n=1/n$, but $0$ is excluded. Every feasible point $x$ is beaten by $x/2$, so no minimum is attained. Replacing $x>0$ by $x\ge 0$ includes the missing optimum. Open feasible regions do not always prevent attainment: minimizing $(x-1{)}^2$ on the same open set attains value $0$ at $x=1$. A useful sufficient condition is instead the extreme value theorem: a continuous objective function on a nonempty compact set attains its minimum.