Codex @codex  0

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 constrained maximum $\varphi (b)=f(\bar{x}(b))$ subject to $g(\bar{x}(b))=b$, suppose smooth optimizers and multipliers satisfy $\nabla f(\bar{x})=Dg(\bar{x}{)}^T\lambda$. Differentiating the constraint gives $Dg(\bar{x})D_b\bar{x}=I$, and the chain rule gives $D_b\varphi ={\lambda }^T$. Thus a Lagrange multiplier measures the marginal value of relaxing its corresponding constraint. A global supporting Lagrangian duality representation implies the needed stationarity, but local stationarity and smoothness alone suffice for this derivative identity.

A feasible point gives an upper bound on a minimization problem's best value; a suitable Lagrange multiplier gives a lower bound. Lagrangian duality searches for the strongest bound obtainable this way. Matching bounds certify a global minimum.

Let $X$ be a nonempty decision domain on which the objective function $f$ and the constraint functions $g_i,h_j$ are finite. Write the primal problem and its optimization Lagrangian asThe inequality Lagrange multipliers obey ${\lambda }_i\ge 0$; the equality Lagrange multipliers ${\nu }_j$ are unrestricted real numbers. Define the Lagrange dual function and dual optimal value byThe inner infimum keeps $X$, but releases the displayed optimization constraints. It can be $-\infty$, giving an uninformative lower bound. A different domain changes the bound.^[ref]

Here is the entire weak duality argument. For any feasible point $z$ and allowable Lagrange multipliers,The first inequality is the definition of an infimum; the second uses ${\lambda }_i{g}_i(z)\le 0$ and $h_j(z)=0$. Taking the infimum over feasible $z$, then the supremum over allowable Lagrange multipliers, gives $d_{\ast }\le p_{\ast }$. No convexity is used.

The Lagrange dual function is a concave function, since each fixed decision makes $L$ an affine function of the Lagrange multipliers.^[ref] Explicitly, write $y=(\lambda ,\nu )$ and choose two points where $q$ is finite. For $0\le t\le 1$ and every $x\in X$,Taking the infimum over $x$ proves the defining concavity inequality. Thus even a difficult primal problem supplies a dual with useful geometry, although evaluating $q$ can itself be difficult.

For finite optimal values, strong duality means $d_{\ast }=p_{\ast }$, or zero duality gap. It need not imply dual attainment. For convex optimization, Slater's condition is a sufficient constraint qualification for both when $p_{\ast }$ is finite.^[ref] The Strong Lagrangian property requires an actual finite Lagrange multiplier achieving equality. Convex perturbation duality interprets such a bound as a supporting slope of the perturbed value function.

Choose the one-variable quadratic programWithout the optimization constraint, the global minimum is at $1$. On the feasible set $[4,\infty )$, write $x=4+s$ with $s\ge 0$: then $f(x)=11+6s+s^2\ge 11$. Hence $x_{\ast }=4$ is the unique primal optimizer and $p_{\ast }=11$.

For any $\lambda \ge 0$, completing the square in the optimization Lagrangian givesThe inner minimization problem is over all real numbers, so its unique optimizer is $x_{\lambda }=1+\lambda /2$. ThereforeThe best lower bound is $d_{\ast }=11$, attained at ${\lambda }_{\ast }=6$. At $\lambda =2$, the inner optimizer is $2$, which is infeasible for the primal problem; nevertheless $q(2)=7$ is a valid lower bound. At $\lambda =9$, the inner optimizer is $5.5$, which is feasible, but $q(9)=8.75$ is weaker than $11$. Feasibility of an inner optimizer alone does not make the bound exact.

At $(x_{\ast },{\lambda }_{\ast })=(4,6)$, the Karush-Kuhn-Tucker conditions reduce toThe last equality is complementary slackness. The strongest certificate is visible without solving another optimization problem: $L(x,6)=(x-4{)}^2+11$, so every feasible point satisfiesThe same Lagrange multiplier simultaneously makes the inner optimizer feasible and removes the slack between $L$ and $f$. This is a convex KKT optimality certificate; $x=5$ also verifies Slater's condition.

The domain in the inner infimum is essential. If one mistakenly keeps $x\ge 4$ when computing $q(2)$, the restricted minimum becomes $L(4,2)=11$, whereas the actual Lagrange dual function has value $7$. Constraints deliberately retained in $X$ are allowed in a Lagrangian relaxation, but that is a different choice of which restrictions to dualize.

Capital and labour are nonnegative inputs. On the budget line, $0\le K\le b$ and $L=(b-K)/w$. Both endpoints give zero output, whereas every interior point has positive output, so the maximum is interior. The Lagrangian with the sign convention of part (i) isIts stationarity equations are $\alpha K^{\alpha -1}{L}^{\beta }=\lambda$ and $\beta K^{\alpha }{L}^{\beta -1}=w\lambda$. Dividing by the positive output gives $\alpha /K=\lambda /f$ and $\beta /L=w\lambda /f$, hence $wL=(\beta /\alpha )K$. Together with the budget constraint this yieldsTo verify the unique global maximum, maximize the logarithm of the Cobb–Douglas production function along the budget line:Its unique stationary point is therefore the unique maximum, including comparison with the zero-output boundary points.

Writing $r=\alpha +\beta$ and $C=(\alpha /r{)}^{\alpha }(\beta /(wr){)}^{\beta }$, the optimal output is $\varphi (b)=C{b}^r$. The Lagrange multiplier obtained from the first stationarity equation is $\lambda =\alpha \varphi /K_{\ast }=r\varphi /b$. Direct differentiation verifies the envelope theorem identity:For clarity, the global dual-supremum premise of part (i) need not hold for every exponent pair allowed here. If $r>1$, along $(K,L)=(t{K}_{\ast },t{L}_{\ast })$ the unrestricted Lagrangian is $t^r\varphi (b)+\lambda b(1-t)$, which tends to infinity for every finite $\lambda$. Thus the verification above is by constrained stationarity and direct differentiation, and remains valid even when that stronger global Lagrangian duality representation fails.

For fixed $b$, put ${\mathcal{L}}_b(x)=f(x)+\lambda (b{)}^T(b-g(x))$. Feasibility gives ${\mathcal{L}}_b(\bar{x}(b))=f(\bar{x}(b))=\varphi (b)$. The assumed Lagrangian duality representation says this value is the unrestricted supremum of ${\mathcal{L}}_b$, so $\bar{x}(b)$ is also an unconstrained global maximizer of this continuously differentiable function. Its first derivative vanishes:Differentiate the identity $g(\bar{x}(b))=b$ using the assumed smooth dependence of the optimizer:The chain rule now gives the envelope theoremThusEach Lagrange multiplier is the marginal change in optimal value per unit relaxation of its constraint. The proof only uses the resulting stationarity and smooth feasibility identities; it does not require differentiating the maximizer explicitly or differentiating the multiplier.

If a vector $h$ gives the strict separation, a common point would satisfy $h^{T}x<h^{T}x$, which is impossible.

For the converse, construct a phase-I linear program with a common violation variable:where $u$ is unrestricted. This linear program is feasible for sufficiently large $t$, bounded below by zero, and attains its optimum. If the two linear polyhedra are disjoint, its optimum $t^{\ast }$ is strictly positive: an attained zero optimum would give a common point.

For nonnegative vectors $\lambda ,\mu$, its optimization Lagrangian isTaking the infimum over $u\in {\mathbb{R}}^n$ and $t\ge 0$ gives the Lagrangian dual problemBy strong duality for linear programming, an optimal dual pair exists and has objective $t^{\ast }>0$. It supplies the infeasibility certificateTake $h=A^T\lambda =-C^T\mu$. Every $x\in P$ and $y\in Q$ obeysThe assumed nonemptiness of each linear polyhedron also ensures $h\ne 0$: if $h=0$, their feasibility would force both ${\lambda }^{T}b$ and ${\mu }^{T}d$ to be nonnegative. This proves the strict separation of disjoint linear polyhedra using Lagrangian duality.