Inequality constrained programs, tangent cones, constraint qualifications, and KKT

Let $n\ge 1$, let $U\subseteq {\mathbb{R}}^n$ be open, and let $f:U\to \mathbb{R}$ be $C^2$. Let $p,m\in \mathbb{N}$ with zero allowed; when the target dimension is positive, let $h:U\to {\mathbb{R}}^p$ and $g=(g_1,\dots ,g_m):U\to {\mathbb{R}}^m$ be componentwise $C^2$, and when it is zero use the unique empty map. The $C^2$ convention for positive dimensions is $C^k$ Euclidean maps and diffeomorphisms. The $C^2$ inequality program is to minimize $f(x)$ subject to $h(x)=0$ and $g_i(x)\le 0$ for every $i$. Its feasible set is $C=\{x\in U:h(x)=0,g_i(x)\le 0(1\le i\le m)\}$. A feasible point $x_{\ast }$ is a local minimizer if some open neighborhood $V$ of $x_{\ast }$ satisfies $f(x_{\ast })\le f(y)$ for every $y\in C\cap V$.

At a feasible $x$, the active set is $I(x)=\{i:g_i(x)=0\}$. The Bouligand tangent cone and linearized cone are, respectively,

and

Gradients are column vectors and $D{g}_i(x)d=\mathrm{\nabla }{g}_i(x{)}^{T}d$.

The linear independence constraint qualification (LICQ) holds at $x$ when the rows of $Dh(x)$ together with $\{\mathrm{\nabla }{g}_i(x{)}^T:i\in I(x)\}$ are linearly independent. MFCQ holds at $x$ when $Dh(x)$ has full row rank (its rows are linearly independent) and there is $w\in \ker Dh(x)$ with $D{g}_i(x)w<0$ for every active $i$; the latter condition is vacuous if $I(x)=\mathrm{\varnothing }$. Here full row rank for a matrix with zero rows is understood vacuously.

The Mangasarian–Fromovitz constraint qualification (MFCQ) is the condition just stated. The Karush–Kuhn–Tucker (KKT) system is the stationarity, feasibility, dual-feasibility, and complementarity system below.

For $\nu \in {\mathbb{R}}^p$ and $\lambda \in {\mathbb{R}}^m$, the Lagrangian and KKT system are

The critical cone for a KKT tuple is $\mathcal{K}(x,\nu ,\lambda )={\mathcal{L}}_C(x)\cap \{d:\mathrm{\nabla }f(x{)}^{T}d=0\}$. These definitions use the differentiability and gradient conventions of $C^k$ Euclidean maps and diffeomorphisms, The Euclidean inner product $⟨x,y⟩={\sum }_{k<n}{x}_k{y}_k$ on ${\mathbb{R}}^n$, and The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case.

This page uses $g_i\le 0$ and nonnegative inequality multipliers throughout. The equality-only Lagrange multiplier rule does not supply any inequality multiplier assertion.