Inequality KKT duality and optimality certificates — Examples

If $g(x,y)\le 0$, then $y^2\le x^3$. Since $y^2\ge 0$, this forces $x^3\ge 0$, hence $x\ge 0$. The origin is feasible and has objective $0$, so it is a global minimizer.

At $(0,0)$ the constraint is active, $\mathrm{\nabla }f(0,0)=(1,0)$, and $\mathrm{\nabla }g(0,0)=(-3x^2,2y){\mathrm{\mid }}_{(0,0)}=(0,0)$. Thus $\mathrm{\nabla }f+\lambda \mathrm{\nabla }g=(1,0)\mathrm{\ne }0$ for every $\lambda \ge 0$; no KKT multiplier exists. MFCQ also fails because $Dg(0,0)w=0$ for every direction $w$, so no direction strictly decreases the active constraint.

This does not contradict [F2]: the origin is a local and global minimizer, but the MFCQ hypothesis fails, and the direct stationarity calculation proves multiplier existence cannot be inferred here.

The epigraph of $\varphi$ is exactly $E=\{(x,y,t):y\ge 0,t\ge 0,x^2\le yt\}$. For $y>0$ this is the inequality $t\ge x^2\mathrm{/}y$; when $y=0$ it forces $x=0$ and $t\ge 0$; for $y<0$ it is empty. Thus $E$ is closed, being defined by continuous non-strict inequalities. It is convex: if $\mathrm{\mid }{x}_j\mathrm{\mid }\le \sqrt{y_j{t}_j}$ for $j=1,2$, then for $0\le \theta \le 1$, $\mathrm{\mid }\theta x_1+(1-\theta )x_2\mathrm{\mid }\le \theta \sqrt{y_1{t}_1}+(1-\theta )\sqrt{y_2{t}_2}\le \sqrt{(\theta y_1+(1-\theta )y_2)(\theta t_1+(1-\theta )t_2)}$ by Cauchy–Schwarz. Therefore $\varphi$ is closed convex. The objective is continuous and has second derivative $e^{-x}>0$ in $x$, so it is closed convex and proper as well.

On its domain $\varphi \ge 0$. If $y>0$, $\varphi (x,y)\le 0$ forces $x=0$; if $y=0$, finiteness already forces $x=0$. Hence the feasible set is $\{(0,y):y\ge 0\}$ and $f_0=1$ throughout it, so $p^{\ast }=1$ and the primal minimum is attained, for example at $(0,0)$. No point has $\varphi (x,y)<0$, so Slater fails.

For $\lambda \ge 0$, every point in the Lagrangian domain has $e^{-x}+\lambda \varphi (x,y)\ge 0$, so $q(\lambda )\ge 0$. At $\lambda =0$, taking $x\to +\mathrm{\infty }$ gives $q(0)=0$. For $\lambda >0$, take $(x_k,y_k)=(k,k^3)$; then $e^{-x_k}+\lambda \varphi (x_k,y_k)=e^{-k}+\lambda \mathrm{/}k\to 0$, so again $q(\lambda )=0$. Therefore $d^{\ast }={\sup }_{\lambda \ge 0}q(\lambda )=0$ and the positive duality gap is $p^{\ast }-d^{\ast }=1$. This does not contradict [F2], because its Slater hypothesis fails.

The calculation gives a closed convex primal problem with attained finite optimum and a strict gap; the missing strict-feasibility condition is exactly the boundary that blocks the Slater theorem's certificate.

The constraint is feasible exactly when $x_1\ge 0$. At $x_{\ast }=(0,2)$ it is active, and $\mathrm{\nabla }f(x_{\ast })=(1,0)$ while $\mathrm{\nabla }g(x_{\ast })=(-1,0)$. Therefore $\mathrm{\nabla }f(x_{\ast })+{\lambda }_{\ast }\mathrm{\nabla }g(x_{\ast })=0$ for ${\lambda }_{\ast }=1\ge 0$, and ${\lambda }_{\ast }g(x_{\ast })=0$. The active gradient is nonzero, so the one-row LICQ holds.

The quadratic is convex and differentiable. Primal feasibility and the multiplier checks in step 1.1 satisfy the hypotheses of [F2], so $x_{\ast }$ is a global minimizer. Directly, for every feasible $x$, $f(x)-f(x_{\ast })=x_1+\frac{1}{2}{x}_1^2+\frac{1}{2}(x_2-2{)}^2\ge 0,$ with equality only when $x_1=0$ and $x_2=2$. Thus the minimizer is unique, and [F1] makes ${\lambda }_{\ast }=1$ the unique multiplier.

The active-set KKT certificate is exact: it proves the unique global minimizer $x_{\ast }=(0,2)$ and its unique nonnegative multiplier ${\lambda }_{\ast }=1$.

The gradient is $\mathrm{\nabla }f(x_1,x_2)=(2x_1,-2x_2)$, so $\mathrm{\nabla }f(0,0)=0$ and the origin is KKT. With no constraints, ${\mathcal{L}}_C(0)={\mathbb{R}}^2$ and $\mathcal{K}(0)={\mathbb{R}}^2$. The Hessian is $\left(\begin{array}{cc}2& 0\\ 0& -2\end{array}\right)$, whose quadratic form at $d=(0,1)$ is $-2$.

For every $t\mathrm{\ne }0$, $f(t,0)=t^2>0=f(0,0)$, while $f(0,t)=-t^2<0=f(0,0)$. Both points approach the origin as $t\to 0$, so the origin is neither a local minimum nor a local maximum. The negative critical curvature also violates the necessary condition in [F2], and strict positivity required by its sufficient condition fails.

Thus stationarity alone is not an optimality certificate: this KKT point is a saddle.