Inequality KKT duality and optimality certificates

Every $y\in K$ has a representation whose positive-coefficient vectors are linearly independent. Start with any nonnegative coefficient list and discard its zero coefficients. If its remaining vectors are dependent, take a nonzero relation ${\sum }_j{c}_j{a}_j=0$ and change its sign so some $c_j>0$. For the current positive coefficients $t_j$, put $s={\min }_{c_j>0}{t}_j\mathrm{/}{c}_j$. Replacing each $t_j$ by $t_j-s{c}_j$ preserves the represented vector, leaves every coefficient nonnegative, and makes at least one positive coefficient zero. Repeating at most $m$ times leaves an independent positive support.

Fix an independent index set $J$ and let $A_J$ have columns $a_j$, $j\in J$. Its Gram matrix $G_J=A_J^T{A}_J$ is invertible: for every nonzero $v$, $v^T{G}_{J}v=\mathrm{\parallel }{A}_{J}v{\mathrm{\parallel }}_2^2>0$ by independence. Put $B_J=G_J^{-1}{A}_J^T$, define $R_J(y)=B_{J}y$ on ${\mathbb{R}}^n$, and set $L_J=({\sum }_{r=1}^{\mathrm{\mid }J\mathrm{\mid }}{\sum }_{s=1}^n(B_J{)}_{rs}^2{)}^{1\mathrm{/}2}$. Applying [F2] to each row gives $\mathrm{\parallel }{R}_J(y)-R_J(y^{\mathrm{\prime }}){\mathrm{\parallel }}_2^2\le L_J^2\mathrm{\parallel }y-y^{\mathrm{\prime }}{\mathrm{\parallel }}_2^2$, so $R_J$ is Lipschitz with finite constant $L_J$, hence continuous. On the closed subspace $S_J=\mathrm{span}\{a_j:j\in J\}$ it satisfies $A_J{R}_J(y)=y$. Hence $A_J({\mathbb{R}}_{\ge 0}^{\mathrm{\mid }J\mathrm{\mid }})=S_J\cap R_J^{-1}({\mathbb{R}}_{\ge 0}^{\mathrm{\mid }J\mathrm{\mid }})$ is closed: $S_J$ is closed by [F1], the nonnegative orthant is closed, and $R_J$ is continuous. For $J=\mathrm{\varnothing }$ this cone is $\{0\}$, also closed.

By step 1.1, $K$ is the union of the cones in step 1.2 over independent subsets $J\subseteq \{1,\dots ,m\}$. There are only finitely many such subsets, so this union is closed. Each component is a convex cone, and directly taking nonnegative combinations shows $K$ is convex.

If $q=0$, then $H$ is the unique map into ${\mathbb{R}}^0$ and the level is all of $U$. The curve $\gamma (t)=x+td+\frac{1}{2}{t}^{2}z$ has the required value and first two derivatives.

Now suppose $q>0$ and take the graph in [F1]. Put $v=D^2\psi (0)[d,d]$. Since $H(x+td+\psi (td))=H(x)$ for small $t$, [F2] and $\psi (td)=\frac{1}{2}{t}^{2}v+o(t^2)$ give $DH(x)d=0$ and $DH(x)v+D^{2}H(x)[d,d]=0$.

The compatibility equation for $z$ and step 1.2 imply $e=z-v\in \ker DH(x)$. Define $u(t)=td+\frac{1}{2}{t}^{2}e$ and $\gamma (t)=x+u(t)+\psi (u(t))$. This curve stays on $H=H(x)$ by [F1]. Using [F2] and $D\psi (0)=0$ gives $\gamma (t)=x+td+\frac{1}{2}{t}^2(e+v)+o(t^2)=x+td+\frac{1}{2}{t}^{2}z+o(t^2)$, so its first two derivatives at $0$ are $d$ and $z$.

If $r=0$, then ${\mathbb{R}}^r=\{0\}$ and $b=0$. Alternative 1 holds with $x=0\in {\mathbb{R}}^n$, while alternative 2 is impossible because the only $y\in {\mathbb{R}}^0$ is $0$ and $b^{T}y=0$. This handles the zero-dimensional ambient case. Now assume $r\ge 1$. Let $C=\{{\sum }_{j=1}^n{x}_j{A}_j:x_j\ge 0\}$, where $A_j$ are the columns of $A$. This is a nonempty convex cone and is closed by [F1]. If $b\in C$, its nonnegative coefficients give alternative 1. If $b\mathrm{\notin }C$, let $p$ be its nearest point in $C$ by [F2] and put $z=b-p\mathrm{\ne }0$.

Applying [F3] with $c=0$ and $c=2p$ gives both $⟨z,p⟩\ge 0$ and $⟨z,p⟩\le 0$, hence $⟨z,p⟩=0$. Applying [F3] to arbitrary $c\in C$ then gives $⟨z,c⟩\le 0$. In particular $A_j^{T}z\le 0$ for every column, and $⟨z,b⟩=⟨z,p+z⟩=\mathrm{\parallel }z{\mathrm{\parallel }}_2^2>0$. Thus $y=-z$ satisfies $A^{T}y\ge 0$ and $b^{T}y=-\mathrm{\parallel }z{\mathrm{\parallel }}_2^2<0$, which is alternative 2.

The alternatives cannot both hold: if $Ax=b$ with $x\ge 0$ and $A^{T}y\ge 0$, then $b^{T}y=x^T{A}^{T}y\ge 0$, contradicting $b^{T}y<0$. Step 1.1 produces one alternative in every case, so exactly one holds.

Take $d\in T_C(x)$ and use its defining feasible sequence $x+t_k{d}_k$, where $t_k\downarrow 0$ and $d_k\to d$. For $h(x)=0$, Taylor expansion gives $0=h(x+t_k{d}_k)=t_{k}Dh(x)d+o(t_k)$, hence $Dh(x)d=0$. For active $i$, feasibility gives $0\ge g_i(x+t_k{d}_k)=t_{k}D{g}_i(x)d+o(t_k)$, hence $D{g}_i(x)d\le 0$. Therefore $d\in {\mathcal{L}}_C(x)$.

Now take $d\in {\mathcal{L}}_C(x)$. Let $w$ be the MFCQ direction; if no inequality is active set $w=0$. Both $d$ and $w$ lie in $\ker Dh(x)$. When there are equality constraints, [F2] supplies a local graph $x+u+\psi (u)$ over this kernel; with no equalities use $\psi =0$. For $t>0$ small, define $u(t)=td+t^{3\mathrm{/}2}w$ and $x(t)=x+u(t)+\psi (u(t))$. Then $h(x(t))=0$ and [F3] yields $x(t)-x=td+t^{3\mathrm{/}2}w+O(t^2)$, so $(x(t)-x)\mathrm{/}t\to d$.

If $i$ is active, Taylor expansion gives $g_i(x(t))=tD{g}_i(x)d+t^{3\mathrm{/}2}D{g}_i(x)w+O(t^2)+o(t^2)$. When $D{g}_i(x)d<0$, its order-$t$ term makes this negative for all sufficiently small $t>0$. When $D{g}_i(x)d=0$, MFCQ gives $D{g}_i(x)w<0$, and its order-$t^{3\mathrm{/}2}$ term dominates the remainder of order $t^2$. Inactive inequalities remain strict by continuity. Since there are finitely many inequalities, one positive $\tau$ works for all of them and every $0<t<\tau$. Thus $x(t)$ is feasible for such $t$.

Taking $t_k=\tau \mathrm{/}{2}^{k+1}$ gives feasible points with $t_k\downarrow 0$ and $(x(t_k)-x)\mathrm{/}{t}_k\to d$, so $d\in T_C(x)$. This proves ${\mathcal{L}}_C(x)\subseteq T_C(x)$; step 1.1 gives the reverse inclusion.

For $d\in {\mathcal{L}}_C(x)$, the equality term in stationarity vanishes, and inactive multipliers vanish by complementarity. Therefore $\mathrm{\nabla }f(x{)}^{T}d=-{\sum }_{i\in I(x)}{\lambda }_{i}D{g}_i(x)d$. Every summand on the right is nonnegative because ${\lambda }_i\ge 0$ and $D{g}_i(x)d\le 0$.

The sum in step 1.1 is zero exactly when each term with ${\lambda }_i>0$ is zero; because each such term is nonnegative, this is equivalent to $D{g}_i(x)d=0$ for every positively weighted active index. That is the claimed equivalence and critical-cone description.

Since $x$ is feasible, $Ax-b=0$ and $g_i(x)\le 0$. Since ${\lambda }_i\ge 0$, this gives $L(x,\lambda ,\nu )=f_0(x)+{\sum }_i{\lambda }_i{g}_i(x)\le f_0(x)$. The infimum defining $q$ is no larger than this particular Lagrangian value, so $q(\lambda ,\nu )\le f_0(x)$.

The bound in step 1.1 holds for every primal feasible $x$ and every dual feasible pair. Taking the infimum over primal feasible $x$ and the supremum over dual feasible pairs gives $d^{\ast }\le p^{\ast }$ when the primal set is nonempty.

Let $W=\mathrm{aff}(\mathrm{dom}p)$. Since $0$ belongs to the domain, $W$ is a linear subspace; relative interior gives a ball about $0$ in $W$ contained in $\mathrm{dom}p$. If $W=\{0\}$, take $\mathrm{\ell }=0$. Otherwise identify $W$ with a Euclidean coordinate space. The restriction of $p$ to that open ball is finite and convex, so [F1] makes it continuous at $0$.

In $W\times \mathbb{R}$, let $E=\{(z,t):p(z)\le t\}$ and let $\bar{E}$ be its closure. The set $E$ is convex, $(0,p(0))\in E$, and $\bar{E}$ is nonempty, closed and convex. Continuity from step 1.1 shows that $(0,p(0)-ϵ)\mathrm{\notin }\bar{E}$ for every $ϵ>0$: choose $\delta >0$ so $p(z)>p(0)-ϵ\mathrm{/}3$ whenever $\mathrm{\parallel }z\mathrm{\parallel }<\delta$, while a sufficiently small open ball about $(0,p(0)-ϵ)$ has $\mathrm{\parallel }z\mathrm{\parallel }<\delta$ and $t<p(0)-2ϵ\mathrm{/}3$, so it misses $E$. Thus $(0,p(0))$ is a boundary point of $\bar{E}$.

For each positive integer $k$, project $z_k=(0,p(0)-1\mathrm{/}k)$ onto $\bar{E}$, obtaining $y_k$. Since $(0,p(0))\in \bar{E}$, the projection distance is at most $1\mathrm{/}k$, so $y_k\to (0,p(0))$. The unit vectors $a_k=(y_k-z_k)\mathrm{/}\mathrm{\parallel }{y}_k-z_k{\mathrm{\parallel }}_2$ have a convergent subsequence by [F3], with unit limit $a=(s,\alpha )\in W\times \mathbb{R}$. For each $y\in \bar{E}$, [F2] gives $⟨a_k,y-y_k⟩\ge 0$; passing along that subsequence gives $⟨a,y-(0,p(0))⟩\ge 0$.

The epigraph contains every upward vertical ray, so the support inequality forces $\alpha \ge 0$. If $\alpha =0$, points $(z,p(z))\in E$ for all sufficiently small $z$ and $-z$ in the ball from step 1.1 force both $⟨s,z⟩\ge 0$ and $⟨s,-z⟩\ge 0$. Hence $s=0$, contradicting $\mathrm{\parallel }a{\mathrm{\parallel }}_2=1$. Therefore $\alpha >0$. Setting $\mathrm{\ell }(z)=-⟨s,z⟩\mathrm{/}\alpha$, the support inequality at $(z,p(z))$ yields $p(z)\ge p(0)+\mathrm{\ell }(z)$ for $z$ in the domain; outside the domain the inequality is automatic because $p(z)=+\mathrm{\infty }$.

Every $d\in T_C(x_{\ast })$ satisfies $\mathrm{\nabla }f(x_{\ast }{)}^{T}d\ge 0$. For $d=0$ this is immediate. Otherwise take a defining sequence $x_{\ast }+t_k{d}_k\in C$, with $t_k\downarrow 0$ and $d_k\to d$. For large $k$, local minimality gives $f(x_{\ast }+t_k{d}_k)-f(x_{\ast })\ge 0$. Differentiability gives $f(x_{\ast }+t_k{d}_k)-f(x_{\ast })=t_k\mathrm{\nabla }f(x_{\ast }{)}^T{d}_k+o(t_k)$; divide by $t_k$ and pass to the limit.

By [F1] and step 1.1, $\mathrm{\nabla }f(x_{\ast }{)}^{T}d\ge 0$ for every $d\in {\mathcal{L}}_C(x_{\ast })$. Form a matrix $B$ with columns $\mathrm{\nabla }{h}_j(x_{\ast }),-\mathrm{\nabla }{h}_j(x_{\ast })$ for each equality and $-\mathrm{\nabla }{g}_i(x_{\ast })$ for each active inequality, and set $c=\mathrm{\nabla }f(x_{\ast })$. If alternative 1 of [F2] failed, alternative 2 would give $B^{T}d\ge 0$ and $c^{T}d<0$. The paired equality columns force $Dh(x_{\ast })d=0$, while the inequality columns force $D{g}_i(x_{\ast })d\le 0$ for every active $i$, so $d\in {\mathcal{L}}_C(x_{\ast })$, contradicting step 1.1. Thus there are nonnegative coefficients representing $c$ as a combination of the columns of $B$.

Write the equality-column coefficients as ${\alpha }_j,{\beta }_j\ge 0$ and the active inequality coefficients as ${\lambda }_i\ge 0$. The representation from step 2.1 is $\mathrm{\nabla }f(x_{\ast })=Dh(x_{\ast }{)}^T(\alpha -\beta )-D{g}_{I(x_{\ast })}(x_{\ast }{)}^T{\lambda }_I$. Set $\nu =-(\alpha -\beta )$ and set ${\lambda }_i=0$ for inactive $i$. Then stationarity holds. Feasibility holds because $x_{\ast }\in C$; dual feasibility holds by construction; and complementarity holds because active constraints vanish while inactive multipliers are zero. These are exactly the KKT conditions.

Fix any feasible $y$ and put $d=y-x_{\ast }$. Then $Ad=0$. KKT stationarity gives $\mathrm{\nabla }f(x_{\ast }{)}^{T}d=-{\sum }_i{\lambda }_i\mathrm{\nabla }{g}_i(x_{\ast }{)}^{T}d$. If ${\lambda }_i=0$ its term is zero. If ${\lambda }_i>0$, complementarity gives $g_i(x_{\ast })=0$, and [F1] applied to $g_i$ gives $\mathrm{\nabla }{g}_i(x_{\ast }{)}^{T}d\le g_i(y)\le 0$. Hence $\mathrm{\nabla }f(x_{\ast }{)}^{T}d\ge 0$.

Applying [F1] to $f$ yields $f(y)\ge f(x_{\ast })+\mathrm{\nabla }f(x_{\ast }{)}^{T}d\ge f(x_{\ast })$. Since $y$ was arbitrary, $x_{\ast }$ is globally minimizing. Step 1.1 also gives $⟨-\mathrm{\nabla }f(x_{\ast }),y-x_{\ast }⟩\le 0$ for every feasible $y$, which is exactly $-\mathrm{\nabla }f(x_{\ast })\in N_C(x_{\ast })$ by [F2].

If the residual is zero, each summand in [F1] is nonnegative and their sum is zero, so each norm is zero. The stationarity and equality terms then give stationarity and $h(x)=0$. The positive-part term is zero exactly when $g_i(x)\le 0$ for every $i$, and the negative-multiplier term is zero exactly when ${\lambda }_i\ge 0$ for every $i$. The last term gives ${\lambda }_i{g}_i(x)=0$ coordinatewise. These are all conditions in [F2].

Conversely, if the KKT conditions hold, every vector inside each norm in [F1] is zero: feasibility makes $h=0$ and $[g{]}^{+}=0$, dual feasibility makes $[-\lambda {]}^{+}=0$, complementarity makes $\lambda \circ g=0$, and stationarity makes the first vector zero. Thus the residual is zero.

Write $Q(d)=d^T{\mathrm{\nabla }}_{xx}^{2}L(x_{\ast },\nu ,\lambda )d$ and $S=\{d:\mathrm{\parallel }d{\mathrm{\parallel }}_2=1\}$. The critical cone intersected with $S$ is closed in $S$ by its linear equalities and inequalities. If this intersection is nonempty, it is compact by [F2], and [F2] gives a minimum $\gamma =\min Q(d)>0$ there. The relatively open set $N=\{u\in S:Q(u)>\gamma \mathrm{/}2\}$ contains that intersection. If the intersection is empty, put $N=\mathrm{\varnothing }$.

For $k\ge 1$, let $D_k$ be the set of unit directions $u=(x-x_{\ast })\mathrm{/}\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2$ for feasible $x\mathrm{\ne }{x}_{\ast }$ with $\mathrm{\parallel }x-x_{\ast }{\mathrm{\parallel }}_2<1\mathrm{/}k$ and $f(x)\le f(x_{\ast })$. If $D_k$ is empty for some $k$, there is no such point in that neighborhood and strict local minimality holds. Otherwise, if bad points occur arbitrarily close with directions outside $N$, the nonempty nested closed sets $\overline{D_k\setminus N}$ have the finite-intersection property in the compact sphere $S$. By [F3] choose $d\in {\bigcap }_k\overline{D_k\setminus N}$; since $N$ is relatively open, $d\mathrm{\notin }N$ and $\mathrm{\parallel }d{\mathrm{\parallel }}_2=1$.