Codex @codex  0

For inequalities $c_j(x)\ge 0$, the active constraints at a feasible point are those holding with equality. Inactive constraints remain strictly satisfied in a sufficiently small neighborhood and do not restrict first-order feasible velocities there. The active gradients determine the linearized tangent cone and appear in the linear independence constraint qualification. At a KKT point, inactive constraints have zero Lagrange multipliers by complementary slackness.

These feasible potentials give the lower bound ${\sum }_i{\lambda }_i-{\sum }_j{\mu }_j$ on every assignment cost. An assignment using only equality edges attains this bound and is optimal by weak duality and complementary slackness.

Suppose strictly feasible stationary points of $f(x)-{\mu }_k{\sum }_j\log c_j(x)$ form a bounded sequence. Every cluster point satisfying the linear independence constraint qualification is a KKT point. Inactive multipliers tend to zero. The active gradients near the limit have uniformly bounded dual vectors, so pairing barrier stationarity with those vectors bounds the active multipliers. A convergent multiplier subsequence then gives stationarity, nonnegative multipliers and complementary slackness, since ${\lambda }_{k,j}{c}_j(x_k)={\mu }_k\to 0$. A stationarity residual tending to zero is also allowed.

This conclusion is stationarity, not global optimality. If the subproblems are globally minimized and strictly feasible points are dense in the feasible set, any cluster point is instead a global minimizer. Compare each barrier minimum with a fixed strictly feasible point; boundedness near the cluster point bounds $\log c_j(x_k)$ above. Taking the limit gives the objective comparison on strictly feasible points, then continuity and density extend it to all feasible points.

For finite convex total variation and a positive squared-error budget, the Slater condition supplies a multiplier $\lambda \ge 0$ such that every constrained minimizer also minimizes $\mathrm{TV}(u)+\lambda \Vert u-g{\Vert }^2$. Conversely, a minimizer of that penalized objective with $\lambda >0$ minimizes total variation under the budget equal to its own squared error. Complementary slackness proves the first implication; a comparison of objective values proves the second. This does not assert uniqueness of the multiplier or equality of all minimizer sets when $\lambda =0$.

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 dual variable is a multiplier associated with a primal constraint in a dual linear program. In a minimization linear program with equality constraints $Ax=b$ and nonnegative primal variables, the Lagrangian $c^{T}x+y^T(b-Ax)$ yields the dual objective $b^{T}y$ and inequalities $A^{T}y\le c$; the equality-constraint multipliers $y$ are unrestricted in sign. For a transportation problem, row and column dual variables give potentials $u_i,v_j$ satisfying $u_i+v_j\le c_{ij}$. Complementary slackness makes occupied routes attain equality.

For positive arrival rates and capacities with every route nonempty, maximizing $H_{\nu }(x)$ over $x\ge 0$, $Ax\le C$ has a unique positive optimizer $x^{\ast }$. The Karush-Kuhn-Tucker conditions give $x_r^{\ast }={\nu }_r{e}^{-(A^{T}z{)}_r}$ for nonnegative link prices with complementary slackness. Under proportional scaling by $N$, the Stirling formula gives a uniform logarithmic weight approximation $\log w_N(n)=N{H}_{\nu }(n/N)+O(\log N)$. Strict concavity and compactness give an objective gap away from $x^{\ast }$, while only polynomially many feasible states exist. Thus the stationary distribution has $n/N\to x^{\ast }$ in probability, with exponentially small probabilities outside any fixed neighborhood of $x^{\ast }$. In particular $\mathbb{E}[n]=N{x}^{\ast }+o(N)$.

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]

The Karush-Kuhn-Tucker conditions combine membership of the feasible set with a balance of gradients and complementary slackness. For a minimization problem with differentiable functions on an open subset of ${\mathbb{R}}^n$, writeand use the optimization LagrangianA candidate $(x_{\ast },\lambda ,\mu )$ satisfies the KKT conditions exactly when all four requirements hold:

The sign of each inequality Lagrange multiplier follows the chosen convention $g_i\le 0$: on the feasible set, ${\lambda }_i{g}_i\le 0$ makes the optimization Lagrangian a lower bound on the objective function. An equality contributes zero on the feasible set for either sign of its Lagrange multiplier. Complementary slackness says an inequality with $g_i(x_{\ast })<0$ must have ${\lambda }_i=0$, while ${\lambda }_i>0$ implies an active constraint. An active constraint can still have zero Lagrange multiplier; the quadratic minimization with a moving upper bound below gives an explicit example.

The name records William Karush's 1939 master's thesis and the 1951 work of Harold W. Kuhn and Albert W. Tucker.^[ref]

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.

For optimization constraints $c_i(x)\ge 0$ and $\mu >0$, the logarithmic barrier objective is $f_{\mu }(x)=f(x)-\mu {\sum }_i\log c_i(x)$ on $D=\{x:c_i(x)>0\forall i\}$. Its derivatives are defined only on this strictly feasible open subset. One may extend its value to $+\infty$ off $D$ to formulate an extended-real convex function. The penalty alone is $-{\sum }_i\log c_i$, while $f_{\mu }$ includes the original objective function.

When $f$ is convex and each $c_i$ is concave, $D$ is a convex set andEvery term of this Hessian matrix is a positive semidefinite matrix, so $f_{\mu }$ is convex. Its critical point satisfies the stationarity part of the Karush-Kuhn-Tucker conditions with estimates ${\lambda }_i=\mu /c_i(x)>0$ and perturbed complementary slackness ${\lambda }_i{c}_i(x)=\mu$.

With the tail-positive incidence convention, a network edge's reduced cost is $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$. For uncapacitated minimum-cost flow, dual feasibility requires $r_{ij}\ge 0$ and complementary slackness requires $f_{ij}{r}_{ij}=0$. A negative non-tree reduced cost identifies an improving graph cycle pivot in the network simplex algorithm. This sign convention differs from the row-column potentials of a transportation problem.

Consider the original linear programOne unit of $v$ costs twice as much as one unit of $u$, so $(u,v)=(3,0)$ is a plausible answer. To certify it, multiply the three linear inequalities by $0,1,1$, respectively, and add:The proposed feasible point attains $3$, so its cost is the global minimum.

In the conic dual problem convention, the data and certificate areDirect matrix multiplication gives $A^{T}y=c$ and $b^{T}y=3$. At $x=(3,0{)}^T$, the slack variable is $s=(3,0,0{)}^T$, so $s^{T}y=0$. The first linear inequality has positive slack and zero multiplier; the two positively weighted linear inequalities are tight. This is complementary slackness.

The entire dual feasible set can also be read off: write $y=(1-r,2-r,r{)}^T$ with $0\le r\le 1$. Then $A^{T}y=c$ and $b^{T}y=3r$. Maximizing this lower bound gives $r=1$. A point such as $r=1/2$ is still a valid certificate of the weaker bound $u+2v\ge 3/2$.

For a minimization problem with $g_i(u)\le 0$ and $h_j(u)=0$, the optimization Lagrangian is $L=f+{\sum }_i{\lambda }_i{g}_i+{\sum }_j{\mu }_j{h}_j$ with ${\lambda }_i\ge 0$ and unrestricted equality Lagrange multipliers. Its infimum over the original variable domain gives a dual lower bound. For a maximization problem, use $L=f-{\sum }_i{\lambda }_i{g}_i-{\sum }_j{\mu }_j{h}_j$ to obtain upper bounds. The Lagrangian sufficiency theorem combines a global extremum of this function with feasibility and complementary slackness. This is distinct from a Lagrangian density in variational physics.

Write $x_1=t$, $x_2=t^2$. The two inactive constraints are strict exactly for $-2<t<2$. Complementary slackness gives ${\lambda }_1={\lambda }_2=0$. The KKT conditions reduce toIf $t=0$ these give ${\lambda }_3=0$. Otherwise ${\lambda }_3=2t$ and $t=-3/2$, which gives a negative multiplier and is inadmissible. Thereforeis the only KKT point with this active set. Its active gradient $(0,1)$ is nonzero, so the linear independence constraint qualification, and hence the Mangasarian–Fromovitz constraint qualification, holds.

It is not a local maximizer: $(0,\epsilon )$ is feasible for small $\epsilon >0$ and has objective ${\epsilon }^2>0=F(0,0)$. The feasible boundary path $(t,t^2)$ for small negative $t$ has objective $2t^3+t^4<0$, so it is not a local minimizer either.

Take the usual symmetric meaning of positive definite $Q$. To include all data allowed by the source, first check feasibility. PutFull row rank makes $B$ positive definite. Every $x$ satisfying $Ax=b$ is uniquely $x_0+z$ with $Az=0$, and $z^{T}Q{x}_0=0$. ThusIf ${\rho }^2>1$, there is no feasible point. If ${\rho }^2=1$, the only feasible point is $x_0$, and $x_0$ is optimal for every $c$. If ${\rho }^2<1$, the Slater condition holds, and the following KKT conditions are necessary and sufficient:Necessity follows from the constraint qualification proved in (ii). Sufficiency follows from convexity: the stationary optimization Lagrangian $c^{T}x+y^T(b-Ax)+\gamma (x^{T}Qx-1)$ is minimized at $x$, while its feasible values never exceed the objective, and complementary slackness makes its value at $x$ equal the objective.

The singleton case cannot be silently covered by ordinary KKT necessity. For example, let $Q=I$, $A=(10)$, $b=1$, $c=(0,1{)}^T$. The sole feasible point $(1,0)$ is optimal, but stationarity would require $(0,1)$ to lie in the span of $(1,0)$, which is impossible. The feasibility split above supplies genuinely necessary and sufficient conditions without assuming an unprinted regularity hypothesis.

With inequalities written as $c_i\ge 0$, use the optimization Lagrangian $L(x,\lambda )=f(x)-{\sum }_i{\lambda }_i{c}_i(x)$. The Karush-Kuhn-Tucker conditions at $(x_{\ast },{\lambda }_{\ast })$ areFor any feasible point $z$, the first-order inequalities for a convex function and a concave function giveThe last equality uses complementary slackness. Thus $x_{\ast }$ is a global minimizer. Slater's condition is useful for necessity and existence of Lagrange multipliers, but is not required for this sufficiency argument once a KKT point is supplied.

For an active constraint with ${\lambda }_i^{\ast }>0$, the perturbed complementary slackness equation gives $c_i(x^k)\sim {\mu }_k/{\lambda }_i^{\ast }$. The Hessian matrix from part (c) therefore includesIf $\nabla c_i(x_{\ast })\ne 0$, curvature normal to that boundary grows like $1/{\mu }_k$. By contrast, a direction tangent to every active constraint annihilates these large normal outer products at the limiting point, and its curvature may remain of order one. A large spread of eigenvalues then makes the Newton linear system poorly conditioned. Under bounded remaining curvature and a positive bounded tangential curvature, the condition number typically grows like $1/{\mu }_k$; this is the usual ill-conditioning of a logarithmic barrier.

It is not a universal rate: there may be no nonzero common tangent direction, some limiting Lagrange multipliers may vanish, or all curvatures may grow together. The Hessian formula identifies the source of the difficulty without assuming these extra nondegeneracy conditions.

A precise conditional convergence statement is: with the smoothness and convexity assumptions of the question, a strict feasible point, ${\mu }_k\downarrow 0$, and barrier stationarity residualsevery convergent sequence of strictly feasible points $x^k\to x_{\ast }$ has a global minimizer as its limit. The Lagrange multiplier estimates are bounded and have a subsequence converging to multipliers satisfying the KKT conditions. The theorem does not assert convergence of the primal sequence without further assumptions.

First, continuity gives $c_i(x_{\ast })\ge 0$. For an inactive optimization constraint, $c_i(x_{\ast })>0$, soFor the active constraints, the hint permits assuming ${\lambda }_i^k\to {\lambda }_i^{\ast }$. Combining this with the inactive limits gives ${\lambda }_{\ast }\ge 0$, and passage to the limit in the residual equation proves stationarity. Since ${\lambda }_i^k{c}_i(x^k)={\mu }_k\to 0$, complementary slackness also holds. All KKT conditions follow, and part (b) proves global optimality.

The hint's multiplier assumption can in fact be weakened to selecting a subsequence. To see why the estimates are bounded, choose a strict feasible point $z$ and put $\delta ={\min }_i{c}_i(z)>0$. Concavity givesThe right side is bounded because $x^k\to x_{\ast }$ and $r_k\to 0$. This is the bounded barrier multipliers under Slater's condition argument. A convergent multiplier subsequence then gives the same KKT point, which suffices to prove that the assumed primal limit is globally optimal.