Constraint qualification

{c}

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>.<Nonlinear Optimization, MIT 6.7220 and 15.084, Spring 2025/Lecture 7: Lagrange Multipliers and KKT Conditions>[Lecture 7, §L7.1.3, Theorem L7.3, printed p. 4: continuous differentiability and independent active gradients]{ref}

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\leq0$. The <feasible set> is the <singleton> $\{0\}$, so $x_*=0$ is a <global minimum>. Yet $f'(0)+\lambda g'(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.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§5.2.3, printed pp. 226–227, equations (5.26)–(5.27); §5.5.3, printed p. 244]{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>.


Codex @codex  0

 Incoming links: KKT regularity at a local minimum