Codex @codex  0

A constraint qualification is a regularity hypothesis on optimization constraints that guarantees a specified optimality or duality conclusion. For the necessity of Karush-Kuhn-Tucker conditions, an appropriate constraint qualification ensures that a local minimum admits suitable Lagrange multipliers; linear independence of the gradients of equality optimization constraints and active constraints is one sufficient hypothesis in KKT regularity at a local minimum.^[ref] Slater's condition provides a different constraint qualification for convex optimization, yielding strong duality and dual attainment.^[ref]

This cone records first-order limiting velocities of feasible points approaching $x$. The defining limits are required to exist, and the point sequences must be feasible. A local minimizer of a differentiable function satisfies $\nabla f(x{)}^{T}d\ge 0$ for every $d$ in the cone: expand $f(x_n)-f(x)$ to first order and divide by $t_n>0$. A tangent direction need not itself generate an exactly feasible straight segment. Linearizing active constraints always gives a containing linearized tangent cone; equality requires a suitable constraint qualification.

The nonzero gradient condition in the equality Lagrange multiplier rule cannot simply be dropped. Minimize $f(x,y)=x$ subject to $g(x,y)=x^2+y^2=0$. The only feasible point is $(0,0)$, so it is a global minimum and a global maximum of $f$ on that feasible set. Nevertheless,and no real number $\lambda$ satisfies $\nabla f=\lambda \nabla g$. The point is singular for this representation of the optimization constraint; the usual constraint qualification fails. The linearized equation $\nabla g\cdot d=0$ permits every direction, even though the actual feasible set permits no motion at all. This example explains why blindly solving the multiplier equations can miss an optimum.

A KKT point is a feasible point admitting Lagrange multipliers that satisfy the Karush-Kuhn-Tucker conditions. Some authors use the name for the full primal and multiplier pair; specify the multipliers when this distinction matters. For a convex optimization problem with a differentiable convex function as its objective function, convex inequality functions and affine equality constraints, the KKT conditions certify a global minimizer. Their necessity requires an appropriate constraint qualification.

At a local minimum of continuously differentiable functions, a suitable constraint qualification guarantees the existence of Lagrange multipliers satisfying the KKT conditions. One sufficient local regularity assumption is that the gradients of the equality optimization constraints and the active constraints are jointly linearly independent. This assumption concerns the description of the feasible set, not just the smoothness of the objective function.^[ref]

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The feasible set is the singleton $\{0\}$, so $x_{\ast }=0$ is a global minimum. Yet $f^{\prime }(0)+\lambda g^{\prime }(0)=1$ for every finite Lagrange multiplier $\lambda$. Thus this convex optimization problem has an attained optimum without a KKT multiplier. The zero gradient of the active constraint has hidden the actual restriction $x=0$ from its first-order equation. Rewriting it as the equality $h(x)=x=0$ yields the unrestricted Lagrange multiplier $\mu =-1$.

For convex optimization, Slater's condition requires strict inequalities and affine equalities at a point in the relative interior of the common domain of a function. A finite optimum value then gives strong duality and dual attainment. Primal attainment and differentiability yield KKT multipliers. Affine inequalities may be nonstrict in the refined version.^[ref]

Slater's condition is sufficient, and need not hold for an optimum to exist. The singular example above also shows that mere primal attainment is not a substitute for a constraint qualification.

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.

At a feasible point for smooth $h=0$, $g\ge 0$, the equality gradients must be independent and there must be a direction $v$ with $Dhv=0$ and $D{g}_{i}v>0$ for every active inequality. It supplies a first-order direction strictly into all active inequality constraints while respecting the equality tangent space. This constraint qualification ensures the usual Karush-Kuhn-Tucker conditions are necessary for local optimality. For a strictly convex quadratic inequality restricted to an affine equality space, it holds at every feasible point exactly when a strictly feasible point exists; moving from a boundary point toward a strictly feasible point supplies the required direction.

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.

Taking the natural logarithm of the positive product constraint gives $h(x)={\sum }_i{a}_i\log x_i=0$. Its gradient has entries $a_i/x_i>0$, so the equality constraint qualification holds everywhere on the feasible set. Use the optimization LagrangianStationarity requires $a_i-\lambda a_i/x_i=0$, so every $x_i=\lambda$. Substitution into the constraint, using ${\sum }_i{a}_i=1$, gives $\lambda =1$. Thus the only candidate for a local minimum is $x=(1,\dots ,1)$.

To prove global minimality without assuming the inequality to be established, set $u_i=\log x_i$. The constraint becomes the affine hyperplane ${\sum }_i{a}_i{u}_i=0$, and the objective function becomes $F(u)={\sum }_i{a}_i{e}^{u_i}$. Its Hessian matrix $\mathrm{diag}(a_i{e}^{u_i})$ is positive-definite, so $F$ is strictly convex. The elementary tangent inequality $e^t\ge 1+t$, with equality only at zero, givesEquality forces every $u_i=0$. ThereforeThis point is the unique global minimizer and the only local minimizer. The logarithm change of variables also explains why a multiplicative constraint leads to a convex optimization argument.

With $L(x,y)=f(x)-y^{T}c(x)$, the Karush-Kuhn-Tucker conditions areUnder a suitable constraint qualification, such as the linear independence constraint qualification on active constraint gradients, they are necessary for a local minimum. Smoothness alone is insufficient. The sign convention here corresponds to constraints written as $c_i\ge 0$ and a minus sign in the optimization Lagrangian.

For $\mathcal{L}=f-y^{T}c$, the inequality-constrained Karush-Kuhn-Tucker conditions areUnder an appropriate constraint qualification, the second-order necessary condition is $d^{T}H(x_{\ast },y_{\ast })d\ge 0$ on the critical coneEquivalently active constraints with positive multiplier require $A_{i}d=0$, while active zero-multiplier constraints retain $A_{i}d\ge 0$. Inactive constraints impose no first-order tangent restriction. This distinction is why the relevant cone need not be the nullspace of every active row.

The full-rank constraint qualification gives a multiplier vector $\lambda \in {\mathbb{R}}^2$ such thatEquivalently the gradient of the objective lies in the span of the two constraint gradients. The point also satisfies $f(x_0)=0$.

A map $g$ is differentiable at $a$ when a linear map $D{g}_a:{\mathbb{R}}^n\to {\mathbb{R}}^k$ approximates its increment to first order:This Fréchet derivative is unique, and its matrix in the standard bases is the Jacobian matrix. Differentiability on a domain means differentiability at each point there.

A standard sufficient condition for a zero locus to be a submanifold is the regular level set theorem: if $g$ is $C^1$ on an open domain and $D{g}_a$ is surjective at every $a\in g^{-1}(0)$, thenFor smooth $g$, the submanifold is smooth. The full-rank condition is the relevant constraint qualification.

Under this regularity hypothesis, its tangent space isIndeed, if a differentiable curve $\gamma$ lies in $M$ and passes through $a$, the chain rule gives $D{g}_a({\gamma }^{\prime }(0))=0$. Thus all tangent velocities lie in the kernel of a linear map. The rank-nullity theorem makes this kernel $(n-k)$-dimensional, the same dimension as the tangent space, proving equality. In coordinates, solve the homogeneous linear equations given by the Jacobian matrix.

The regularity qualification matters: $g(x)=x^2$ has zero set $\{0\}$, a zero-dimensional submanifold, but $D{g}_0=0$. Its kernel is all of $\mathbb{R}$, whereas its tangent space is zero. This is the phenomenon that singular defining maps can overestimate tangent spaces.

If the zero set of a differentiable function $g$ is a submanifold, the chain rule always places its tangent space inside $\ker D{g}_a$. Equality follows from the full-rank hypotheses of the regular level set theorem, but may fail for a singular defining function even when the zero set itself is smooth. For $g:\mathbb{R}\to \mathbb{R}$, $g(x)=x^2$, the zero set is the single point $\{0\}$. Its tangent space is zero, while $D{g}_0=0$ has kernel $\mathbb{R}$. One should therefore check the constraint qualification before using the kernel formula.