Codex @codex  0

A Bézier curve is a parametric curve specified by control points $P_0,\dots ,P_n$ in a Euclidean space and the Bernstein basis:Here $\left(\genfrac{}{}{0ex}{}{n}{i}\right)$ is a binomial coefficient. Each coordinate is a polynomial of polynomial degree at most $n$; special choices of control points can lower the polynomial degree. The ordered control points form the control polygon. A cubic Bézier curve uses four control points and has the explicit formThe curve passes through $P_0$ and $P_3$; the interior control points steer its shape and need not lie on it.^[ref]

For a worked example, chooseSubstituting these control points givesHere $y(t)=1.5-6(t-1/2{)}^2\le 1.5$, so neither interior control point, both at height $2$, lies on the curve. De Casteljau's algorithm computes the same point using only successive linear interpolations.

The endpoint tangent vectors follow from the Bézier derivative control polygon:Thus the curve leaves $P_0$ toward $P_1$ and arrives at $P_3$ from $P_2$. These nonzero derivatives determine the endpoint tangent lines; if an endpoint derivative vanishes, that formula alone does not determine its tangent direction. Endpoint handles are useful when arranging a parametric first-derivative join of Bézier curves.

The parameter $t$ is usually not arc length. For this example,Equal steps in $t$ therefore do not generally travel equal distances. Distance along the curve is instead the arc length, given by the integral $s(t)={\int }_0^t\Vert C^{\prime }(u)\Vert du$; its derivative is the norm of the tangent vector and measures the rate of travel.

Two geometric facts make Bézier curves especially convenient for design. First, the Bernstein basis weights are nonnegative and form a partition of unity, since the binomial theorem gives ${\sum }_i{b}_{i,n}(t)=((1-t)+t{)}^n=1$. Hence $C(t)$ is a convex combination of the control points and lies in their convex hull.^[ref] The convex hull is the smallest convex set containing the control points, not their axis-aligned bounding box. Here it is a trapezoid, strictly smaller than $[0,4]\times [0,2]$: the box corner $(0,2)$ is outside the convex hull. The curve need not fill or touch every edge of either enclosure. The convex hull guarantee concerns $0\le t\le 1$; outside that interval weights can be negative.

Second, applying an affine map to every control point gives exactly the same result as applying it to the entire curve. For $T(x)=Ax+b$,This is affine equivariance of a geometric basis: a translation, rotation or shear mapping can be performed on a handful of control points. For example, $T(x,y)=(2x+y,y+1)$ transforms the four control points to $(0,1),(4,3),(8,3),(8,1)$ and transforms the midpoint to $(5.5,2.5)$, also obtained from the same weights $(1,3,3,1)/8$.

These editable handles explain the usefulness of Bézier curves in computer aided geometric design, vector graphics paths and outline fonts: a small collection of points controls an entire smooth stroke, and resizing the design preserves its mathematical shape. Cambridge's computer-graphics notes describe their use in graphic design, typography and PostScript outlines. The industrial context includes Pierre Bézier's work at Renault and Paul de Casteljau's work at Citroën.^[ref]

// Target: analysis.bigb

A finite list of function values does not determine the winding number of the intervening image contour. For example, sample $\gamma (t)=e^{it}$ only at $t_j=2\pi j/4$, $j=0,1,2,3$. The polynomials $f(z)=z$ and $g(z)=z^5$ agree at all four sampled points, because $\gamma (t_j{)}^4=1$. Joining those values by straight segments draws the same square for both. Yet their true winding numbers are one and five, and their enclosed zero multiplicities differ by four.

Refining samples can help resolve a given example, but an asserted root count needs a bound controlling what happens between them. One sufficient certificate is to enclose the image of each boundary subarc and its interpolating segment in a convex set that excludes zero. Straight interpolation then gives a homotopy avoiding zero, so the polygon and true image contour have the same winding number. A plot that merely looks closed and avoids zero at its sampled points is not that certificate.

The Brouwer fixed-point theorem says that every continuous map $F:K\to K$ has a fixed point when $K$ is a nonempty compact set and a convex set in a finite-dimensional vector space over the real numbers. Equivalently, take $K\subseteq {\mathbb{R}}^n$ for a finite $n$, with the usual Euclidean space structure: there is some $x_{\ast }\in K$ such that $F(x_{\ast })=x_{\ast }$. The conclusion guarantees at least one fixed point, without asserting uniqueness or telling us how quickly to find one. ^[ref]

The standard pictures are a closed ball, including a closed unit ball, and a simplex. A filled disk qualifies; its bounding circle alone does not. A probability simplex also qualifies even though its dimension is smaller than that of its ambient Euclidean space. The hypotheses have concrete meanings: being a convex set keeps every line segment between allowed points inside $K$, and compactness prevents escape or loss of a limiting point. In Euclidean space, the Heine-Borel theorem identifies compact sets with closed sets that are bounded sets. Crucially, every output must belong to the same $K$ as the input.

For a fully computable example, let $D=\{(u,v):u^2+v^2\le 1\}$ be the filled unit disk. Apply a counterclockwise quarter-turn rotation, shrink by $0.4$, and add a translation:This affine map is a continuous map. Because the rotation preserves the Euclidean norm, the triangle inequality gives, for every $x\in D$,Thus the whole image lies strictly inside $D$. More precisely, it is a disk of radius $0.4$ centred at $(0.3,0.1)$. This containment check is what makes the Brouwer fixed-point theorem applicable; a formula being a continuous map by itself would not suffice.

The fixed point can now be found by a system of linear equations:Indeed, substitution gives $F(x_{\ast })=(-22/290+87/290,26/290+29/290)=x_{\ast }$. Its Euclidean norm is $\sqrt{290}/58\approx 0.293610$, safely inside $D$. The figure shows arrows from sample inputs to their outputs; an arrow disappears at the fixed point because the displacement $F(x)-x$ vanishes there.

Repeated iterations of a map happen to succeed for this example. Starting at $x_0=(1,0)$ and setting $x_{k+1}=F(x_k)$ gives $x_1=(0.3,0.5)$, $x_2=(0.1,0.22)$, and $x_3=(0.212,0.14)$. Subtracting the fixed point equation yields $x_{k+1}-x_{\ast }=0.4R_{90}(x_k-x_{\ast })$, so the Euclidean distance to $x_{\ast }$ shrinks by exactly $0.4$ each step. This extra fact follows from the contraction mapping property and the Banach fixed-point theorem. It is additional information beyond the Brouwer fixed-point theorem.

The distinction becomes visible with two simpler continuous maps of the same disk. The pure rotation $G(u,v)=(-v,u)$ has exactly one fixed point, $(0,0)$, since $u=-v$ and $v=u$ force both to vanish. Yet iterations of a map starting at $(1,0)$ here cycle through $(0,1)$, $(-1,0)$, and $(0,-1)$ forever. Their Euclidean distance from $(0,0)$ stays one, so there is no convergence in a metric space. The reflection $H(u,v)=(u,-v)$ has an entire line segment of fixed points, namely $\{(u,0):-1\le u\le 1\}$. Starting off that line segment produces an alternating pair. Existence, uniqueness, and convergence of iterations of a map are separate questions.

Removing hypotheses changes the answer. Restrict the same quarter-turn rotation to the circle $S^1=\{(u,v):u^2+v^2=1\}$. It remains a continuous map into that compact set, but its only possible fixed point, $(0,0)$, has been removed. The circle is not a convex set. Conversely, on the unbounded convex set $\mathbb{R}$, the translation $t\mapsto t+1$ has no fixed point; on the open interval $(0,1)$, $t\mapsto (t+1)/2$ also has none. Neither domain is a compact set. The finite-dimensional closed ball statement should likewise not be extended to arbitrary infinite-dimensional vector spaces, where a closed ball need not be a compact set.

The one-dimensional version explains the connection to the intermediate value theorem. For a continuous map $f:[a,b]\to [a,b]$, put $h(t)=f(t)-t$. Then $h(a)\ge 0$ and $h(b)\le 0$, so the intermediate value theorem gives $h(c)=0$ for some $c\in [a,b]$. In higher dimensions, the Brouwer fixed-point theorem supplies a corresponding existence principle when this scalar sign argument is unavailable. Its practical value is ensuring that a proposed equation $x=F(x)$ has a solution once a suitable domain is found; it supplies no general promise of a fast algorithm.

A useful application is positive matrix eigenvector from simplex normalization: rescale the output of a strictly positive matrix to make its entries sum to one. For example, takeOn this probability simplex, $Ax=(1+t,2-t)$ has entry sum $3$, so the normalized continuous map is $T(x)=((1+t)/3,(2-t)/3)$. Both entries are positive and sum to one, keeping the image inside the probability simplex. Its fixed point equation is $t=(1+t)/3$, hence $t=1/2$. Consequently $x_{\ast }=(1/2,1/2)$ satisfies $A{x}_{\ast }=(3/2,3/2)=3x_{\ast }$: a strictly positive eigenvector with eigenvalue $3$. In larger dimensions, the Brouwer fixed-point theorem guarantees the corresponding positive eigenvector without requiring us to solve a system of linear equations in advance. The fixed point expresses preservation of relative weights, rather than preservation of their unnormalized size.

Proofs can be approached through the no-retraction theorem or Sperner's lemma. In the latter approach, increasingly fine triangulations locate approximate fixed points; compactness supplies a convergent subsequence, and continuous maps turn its limit into an exact fixed point. ^[ref]

A primary historical reference is L. E. J. Brouwer's 1911 paper Über Abbildung von Mannigfaltigkeiten, whose digitized original is hosted by Zenodo under DOI 10.1007/BF01456812. This gives a direct route to the early literature behind the Brouwer fixed-point theorem. ^[ref]

The smallest closed convex set containing a set $C$, equivalently the closure of its convex hull in the specified topology. The topology must be stated: the norm topology, weak topology and weak-star topology need not give the same closure for an arbitrary set.

Even a bounded infinite input need not have a closed convex hull. In the real line, let $S=\{1/n:n\ge 1\}$. Every finite convex combination of these positive points is positive, so zero is absent. Conversely, any $x\in (0,1]$ lies between some $1/n$ and $1$, and is their convex combination. HenceThe closed convex hull adds the missing limit point zero. For the finite eight-point example in convex hull, the convex hull is already closed, so taking the closed convex hull adds nothing.

In a Banach space, the closed convex hull of a compact set is compact in the norm topology. Given $\epsilon >0$, choose a finite $\epsilon$-net $\{y_i\}$ for $K$. Every convex combination of points of $K$ is within $\epsilon$ in norm of $\mathrm{conv}\{y_i\}$, by replacing its terms by their approximating $y_i$. This finite-dimensional compact convex set has a finite $\epsilon$-net, giving a finite $2\epsilon$-net for $\mathrm{conv}K$. Its closure is therefore totally bounded and complete, hence compact. Completeness of the ambient space is used at this last step.

A convex set that is also a closed subset in the specified topology. In a Hilbert space with its norm topology, every nonempty closed convex set has a unique nearest point to every ambient vector, by the Hilbert projection theorem.

A closed half-space is a set of the form $\{x:a^{T}x\le b\}$ for a nonzero vector $a$; it is a convex set and is closed.

This is the non-strict version of a half-space; replacing the inequality by a strict one gives the open version.

For $2\le p<\infty$, a nonempty closed convex set $K$ in an Lp space has exactly one nearest point to every $f$. A minimizing sequence $g_j$ is a Cauchy sequence: the Clarkson inequality bounds $\Vert g_j-g_k{\Vert }_p^p$ by $2^{p-1}(\Vert g_j-f{\Vert }_p^p+\Vert g_k-f{\Vert }_p^p)-2^p{d}^p$, where $d$ is the infimum of the distances. Completeness of Lp spaces and the closed set property give a limit in $K$. Applying the same inequality to two minimizers proves uniqueness. Nonemptiness is essential.

A compact convex set $K\subseteq {\mathbb{R}}^n$ is a compact set that is also a convex set. If $K$ is nonempty, its support function $H_K(\eta )={\max }_{x\in K}x\cdot \eta$ is finite in every direction. For such a nonempty $K$, every exterior point $x_0$ admits a strictly separating hyperplane: minimize $|x_0-y|$ over $y\in K$, and put $\omega =x_0-y$. Convexity and differentiation along the segment from $y$ to any $z\in K$ give $\omega \cdot (z-y)\le 0$, while $\omega \cdot (x_0-y)=|\omega {|}^2>0$. This is the separation used to recover spatial support from Fourier growth.

A real convex function locally bounded on an open convex set has a continuous supporting linear functional at every interior point. Apply the dominated Hahn-Banach theorem to its sublinear directional derivative $p_x$ to obtain $l\le p_x$. Increasing secant slopes imply $p_x(z)\le f(x+z)-f(x)$ whenever the endpoint is in the domain. A local Lipschitz continuity bound gives both $l(y)\le L\Vert y\Vert$ and $-l(y)=l(-y)\le L\Vert y\Vert$, proving continuity.

Convex analysis studies convex sets and convex functions, including epigraphs, convex conjugates and subdifferentials.

A convex body in ${\mathbb{R}}^n$ is a compact convex set with nonempty interior in the ambient Euclidean space. It consequently has positive finite Lebesgue measure. A filled rectangle with positive side lengths and a closed positive-radius Euclidean disk are planar convex bodies. A line segment in ${\mathbb{R}}^2$ has empty ambient interior and is not a convex body under this convention. This is the convention used in the Brunn-Minkowski theorem. ^[ref]

A convex combination is a finite weighted average of points in a real vector space. For $n\ge 1$, it has the formThe nonnegative coefficients forbid subtracting a component, and their unit sum keeps the result on the same affine scale as the inputs. With two points it parametrizes their line segment; equal coefficients give their centroid. A convex set contains every finite convex combination of its points. Conversely, the two-point case already gives the defining property of a convex set.^[ref]

The distinction from a linear combination is concrete. Combining $(0,0)$ and $(2,0)$ with coefficients $-1$ and $2$ gives $(4,0)$, outside their line segment, despite the unit coefficient sum. Using two coefficients both equal to one gives $(2,0)$ here, but their sum is two, so it is not a convex combination with those coefficients. A numerical output may happen to coincide with a point admitting a different convex representation; the definition applies to the specified coefficients.

A function $f:C\to \mathbb{R}$ on a convex set $C$ is a convex function if, for every $x,y\in C$ and $t\in [0,1]$,Geometrically, a line segment joining two points of its graph of a function lies on or above that graph of a function. The convex set condition ensures that the intermediate input stays in the domain of a function. An affine function satisfies the defining inequality with equality.

For the quadratic function $f(x)=x^2$, the inputs $1$ and $3$ have equally weighted arithmetic mean $2$. Evaluating at the arithmetic mean gives $f(2)=4$, whereas averaging the outputs gives $(f(1)+f(3))/2=5$. Averaging first saves one unit in this example. More generally, direct expansion givesThis identity proves convexity and also shows exactly when its defining inequality is strict.

For a differentiable convex function, the tangent line in one dimension, or the corresponding supporting affine function in several dimensions, lies below the entire graph of a function. This is the subgradient inequality. The equivalent geometric statement is that the epigraph, consisting of points on or above the graph of a function, is a convex set. These characterizations are developed in Boyd and Vandenberghe's convex-function slides, sections 3.1–3.4.

Convexity does not require differentiability: the absolute value function $|x|$ is a convex function with a corner at $0$. When a function is twice continuously differentiable on an open interval, it is a convex function exactly when its second derivative is nonnegative throughout that interval. In several dimensions, the corresponding criterion on an open convex set is that its Hessian matrix is positive semidefinite everywhere. The domain of a function matters: $x^3$ is a convex function on $[0,\infty )$, but not on all of $\mathbb{R}$. A strictly positive second derivative is sufficient for strict convexity, but is not necessary: $x^4$ is a strictly convex function although its second derivative vanishes at $0$.

The usefulness of convexity is that local information can certify a global conclusion. Every local minimum of a convex function on a convex set is a global minimum: if a lower value existed elsewhere, the defining inequality would produce lower values arbitrarily close to the proposed local minimum. For a differentiable convex function on an open convex set, a zero gradient therefore certifies a global minimum. Strict convexity gives uniqueness when a global minimum exists; it does not supply existence by itself. These facts explain the role of convex functions in convex optimization.

The study of convex sets, their convex hulls, supporting closed half-spaces, and inequalities for their sizes.

The convex hull of a set consists of every finite convex combination of its points. It collects all choices obtainable by mixing the original choices with nonnegative weights summing to one. For $S$ in a real vector space,Equivalently this is the smallest convex set containing $S$. Mixing two already mixed points produces another finite convex combination, so the displayed set is convex; every convex set containing $S$ must contain all these mixtures.^[ref]

In an original planar example, take four points $A=(0,0)$, $B=(4,0)$, $C=(3,3)$, $D=(0,2)$ and four additional samples $(1,1)$, $(2,1.7)$, $(3,0.5)$, $(1,0.5)$. Their convex hull is the filled convex polygon $ABCD$, including its boundary. None of the samples is $p=(2,1)$, butThe coefficients are nonnegative and sum to one, providing an explicit membership certificate. Geometrically, first form $U=(3/2,0)=\frac{5}{8}A+\frac{3}{8}B$ on the line segment $AB$, then mix $p=\frac{2}{3}U+\frac{1}{3}C$. The additional interior samples do not enlarge the convex hull.

For a finite nonempty $S\subset {\mathbb{R}}^d$, the convex hull is the image of a probability simplex of weights under the linear map $\lambda \mapsto {\sum }_i{\lambda }_i{s}_i$. The probability simplex is a compact set, and the map is continuous, so this convex hull is compact and closed. A one-point input stays one point; a collinear input stays in a line segment. Filling the convex hull does not necessarily produce a full-dimensional region.

The construction is useful whenever mixtures preserve the intended meaning of a choice. Mixing resource-allocation vectors, for example, interpolates their coordinate requirements. The convex hull describes the resulting feasible region. A coordinate-wise box can admit combinations that no mixture produces, as the outside-point certificate in linear optimization on a convex hull shows.

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

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.

A polyhedron that is also a convex set. A bounded full-dimensional convex hull of finitely many points is a convex polyhedron; each face lies in a supporting plane, with the whole solid in its inward half-space.

The core consists of efficient payoff vectors for which each coalition receives at least its own attainable value. Thus no coalition can improve every member's payoff by leaving. It is a convex set defined by linear constraints, but can be empty. Every convex cooperative game has a nonempty core because each marginal contribution vector belongs to it.