Codex @codex  0

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$.

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.

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.

For a smooth function $f:U\to \mathbb{R}$ on an open set $U\subseteq {\mathbb{R}}^n$, a critical point is an input $x_{\ast }$ where the gradient vanishes: $\nabla f(x_{\ast })=0$. Equivalently, every first partial derivative is zero. Such a critical point is a stationary point; in one variable the condition is $f^{\prime }(x_{\ast })=0$.

There is a broader convention in elementary one-variable calculus: a "critical number" is an interior input where the derivative is zero or does not exist, provided the function itself is defined there. Thus a corner can be a critical number without being a stationary point. Here the smooth meaning of critical point is used unless the broader convention is explicitly stated. ^[ref]

For the polynomial $f(x)=x^4-2x^2$ on the real line,The stationary points at $x=\pm 1$ are strict local minima and attain the global minimum; the stationary point at $x=0$ is a strict local maximum. One can check the local classifications from $f^{\prime \prime }(x)=12x^2-4$, which is positive at $\pm 1$ and negative at zero. The identity $f(x)=(x^2-1{)}^2-1\ge -1$ proves the global minimum directly. Since $f(x)\to +\infty$ as $|x|\to \infty$, there is no global maximum on $\mathbb{R}$.

A zero derivative alone does not guarantee an extremum. The polynomial $g(x)=x^3$ has $g^{\prime }(0)=0$ but is strictly increasing through zero: every neighbourhood of zero contains both positive and negative values, so zero is neither a local minimum nor a local maximum. Conversely, the absolute value function $h(x)=|x|$ has a strict local minimum and a unique global minimum at zero, but its left and right derivatives are $-1$ and $+1$. It is not differentiable there, so zero is a critical number under the broader convention and is not a stationary point.

The usefulness of critical points is that they reduce the search for smooth interior extrema to equations. Every local minimum or local maximum of a differentiable function at an interior point has zero gradient; this condition is necessary, and $x^3$ shows that it is not sufficient. The striking feature is that all the first directional derivatives must vanish together, even though the surrounding values can form a valley, a peak, or a saddle point of a scalar function. ^[ref]

Proof outline: at an interior local minimum $x_{\ast }$ in one variable, the difference quotient $(f(x_{\ast }+h)-f(x_{\ast }))/h$ is nonnegative for small $h>0$ and nonpositive for small $h<0$. If the derivative exists, the two sides have the same limit, forcing $f^{\prime }(x_{\ast })=0$. Reverse the inequalities for a local maximum. In several variables, apply this argument along each coordinate line to obtain zero partial derivatives and hence zero gradient. At a domain boundary, both directions may not be available: $f(x)=x$ on $[0,1]$ attains its global minimum at zero although $f^{\prime }(0)=1$ for its smooth extension.

Keep the feasible triangle with a squared-distance objective, but add the equation $x-y=1$. An equality requires an exact relation, whereas an inequality allows a range. Here the equality selects a line, and intersecting that line with the original feasible region leaves just the line segment from $(1,0)$ to $(2,1)$:The lower bound comes from $y\ge 0$; the upper bound comes from $x+y=2t+1\le 3$. This is a nonempty closed set even though it has empty interior in the plane. An equality can reduce the dimension of the allowed decisions without making the feasible region empty.

The old optimum $(1.5,1.5)$ violates the added equality. On the surviving line segment, the objective function isThe derivative shows that the unique global minimum is at $t=1$, giving $(x,y)=(2,1)$ and value $1$. The nearest point on the entire equality line would be $(2.5,1.5)$, at $t=1.5$ with value $0.5$, but it violates $x+y\le 3$. Both the equality and the original inequalities must hold simultaneously.

Use $g=x+y-3$ and $h=x-y-1$ to fix the multiplier sign convention in the optimization Lagrangian $L=f+\lambda g+\nu h$; the Lagrange multipliers of $-x$ and $-y$ are again zero. At $(2,1)$, Karush-Kuhn-Tucker conditions hold with $\lambda =1$ and $\nu =-1$:The Lagrange multiplier of an equality has no nonnegativity restriction. For an independent global certificate, completing the square gives $f+g-h=(x-2{)}^2+(y-1{)}^2+1$. On the feasible set, $h=0$ and $g\le 0$, so $f\ge 1$, with equality exactly at $(2,1)$.

A real-valued function that is continuous on a nonempty compact space attains both a global minimum and a global maximum. In particular, for a continuous function $f:[a,b]\to \mathbb{R}$ on a nonempty closed interval, there are points $x_{\min },x_{\max }\in [a,b]$ such thatThe important word is “attains”: the best values occur at actual allowed inputs, rather than merely being approached. The interval version is ^[ref].

For a worked example, take $f(x)=(x-1{)}^2$ on $[-1,2]$. Its global minimum is $f(1)=0$, and its global maximum is $f(-1)=4$. Nonnegativity gives the first answer; $|x-1|\le 2$ on the specified closed interval gives the second. The endpoint $x=-1$ is essential: looking only for a zero derivative would find the minimum and miss the maximum.

For comparison, the continuous function $g(x)=x$ on the open interval $(0,1)$ has infimum $0$ and supremum $1$, but neither is a value of $g$. Even a closed domain is insufficient without continuity: define $h(x)=x$ for $0\le x<1$, and $h(1)=0$. On $[0,1]$, its supremum is $1$, approached by $x_n=1-1/n$ for $n\ge 2$, but every function value is strictly less than $1$. This endpoint change makes $h$ discontinuous, preventing attainment. On the unbounded real line, the continuous function $x\mapsto x$ has neither a global minimum nor a global maximum. These examples show what can fail when a hypothesis is dropped; functions outside the hypotheses may still have extrema.

The extreme value theorem is an existence tool for optimization: first establish that a continuous objective function on a nonempty compact feasible set has a best value, then investigate where it occurs. It neither locates the optimizing point nor promises uniqueness or differentiability. For example, the absolute value function $|x|$ on $[-1,2]$ has its global minimum at zero although no derivative exists there; a constant function has every input as a minimizer. This role in optimization is explained in University of Toronto MAT237 notes, section 1.4: compactness and the extreme value theorem.

A short proof outline identifies the mechanism. The continuous image of a compact space is compact; a nonempty compact subset of the real line contains its infimum and supremum. For a closed interval, one can instead choose inputs whose outputs approach the supremum, extract a convergent subsequence by the Bolzano-Weierstrass theorem, and use continuity to make its limiting output equal that supremum. The closed interval retains the limiting input. Repeating the argument for the infimum supplies the minimum.

Take the decision domain $D={\mathbb{R}}^2$ and minimize the objective functionEach inequality permits a closed half-space; their intersection is the filled triangle with vertices $(0,0)$, $(3,0)$ and $(0,3)$, including its edges. The feasible region is a compact set and a convex set. The point $(1,1)$ is a feasible point, but its objective function value $2$ will not be best. Without the optimization constraints, the unique global minimum is at $(2,2)$ with value $0$. That point is infeasible because $2+2>3$.

The objective function is the squared Euclidean distance from $(2,2)$. Its positive level sets are circles centered there. Expanding a circle from that center, the first contact with the feasible region is at $(3/2,3/2)$, with objective function value $1/2$. Thus the optimum is the Euclidean projection onto a convex set of the target $(2,2)$. Squaring a nonnegative Euclidean distance preserves which point is nearest.^[ref]

Here is a direct certificate, without relying on the picture. Put $s=x+y$ and $d=x-y$. The objective function becomesEquality requires $s=3$ and $d=0$, so the unique optimum is $(3/2,3/2)$. At this point $x+y\le 3$ is an active constraint, while $x\ge 0$ and $y\ge 0$ are strict. An active constraint identifies a tight restriction at a specified point; it alone does not establish optimality. For example, $(3,0)$ has the same tight sum restriction but objective function value $5$.

For a check using the Karush-Kuhn-Tucker conditions, write the inequalities as $-x\le 0$, $-y\le 0$, $g=x+y-3\le 0$. Their Lagrange multipliers at the optimum are $(0,0,1)$. The gradient equation isFeasibility, nonnegative Lagrange multipliers and complementary slackness also hold. With this strictly convex function and affine optimization constraints, the Karush-Kuhn-Tucker conditions certify the unique global minimum.^[ref]