凸最適化

$x,y\in X$、$0\le t\le1$ なら $f_i((1-t)x+ty)\le(1-t)f_i(x)+tf_i(y)\le0$ なので $(1-t)x+ty\in X$ である。最適解 $x,y$ について $f_0((1-t)x+ty)\le(1-t)p^*+tp^*=p^*$ であり、$X$ の点なので値は $p^*$ 以上、よって $p^*$ に等しい。$f_0$ が狭義凸で最適解 $x\ne y$ があれば、$f_0(\frac12x+\frac12y)< p^*$ となって $p^*$ の定義に反する。$\square$

$x$ を半径 $R$ の局所最適解とし、$f_0(y)< f_0(x)$ となる $y\in X$ があったとする。$\|y-x\|>R$ である（そうでなければ $f_0(x)\le f_0(y)$）。$\theta:=R/\|y-x\|\in(0,1)$、$z:=(1-\theta)x+\theta y$ とおくと $\|z-x\|=R$ で、$X$ は凸なので（prop-cvxopt-sets）$z\in X$ である。$f_0$ の凸性から
$$ f_0(z)\le(1-\theta)f_0(x)+\theta f_0(y)< f_0(x) $$
となり、$x$ が局所最適解であることに反する。$\square$

$0< t\le1$ について、凸性から $f(x+t(y-x))\le(1-t)f(x)+tf(y)$、すなわち
$$ \frac{f(x+t(y-x))-f(x)}{t}\le f(y)-f(x) $$
である。$f$ は $x$ で微分可能なので、$t\to+0$ のとき左辺は方向微分 $\nabla f(x)\cdot(y-x)$ に収束する。$\square$

十分性：lem-cvxopt-first-order により $f_0(y)\ge f_0(x)+\nabla f_0(x)\cdot(y-x)\ge f_0(x)$ である。
必要性：ある $y\in X$ で $\nabla f_0(x)\cdot(y-x)<0$ とする。$\varphi(t):=f_0(x+t(y-x))$ は $\varphi'(0)=\nabla f_0(x)\cdot(y-x)<0$ を満たすので、十分小さい $t\in(0,1]$ で $\varphi(t)< \varphi(0)$ である。$X$ は凸なので $x+t(y-x)\in X$ であり、$x$ が最小値を与えることに反する。
$X=\mathbb{R}^n$ のとき：$\nabla f_0(x)=0$ なら条件は成り立つ。逆に条件が成り立てば、$y=x-\nabla f_0(x)$ として $-\|\nabla f_0(x)\|^2\ge0$、すなわち $\nabla f_0(x)=0$ である。$\square$

$x\in X$ なら $\lambda_if_i(x)\le0$ なので $g(\lambda)\le L(x,\lambda)\le f_0(x)$ である。$\lambda$ について上限、$x$ について下限をとればよい。$\square$

$\mathbb{R}^{m+1}$ の部分集合
$$ \mathcal{C}:=\{(u,t)\in\mathbb{R}^m\times\mathbb{R}\mid\text{ある }x\text{ で }f_i(x)< u_i\ (i=1,\dots,m),\ f_0(x)< t\} $$
を考える。
段 1（$\mathcal{C}$ は空でない開凸集合）。$(u,t)\in\mathcal{C}$ を与える $x$ は、$(u,t)$ の近くの点にも同じく使えるので $\mathcal{C}$ は開集合である。$(u,t),(u',t')$ を $x,x'$ が与えるとき、$0\le s\le1$ について $x_s:=(1-s)x+sx'$ は凸性により $f_i(x_s)\le(1-s)f_i(x)+sf_i(x')<(1-s)u_i+su_i'$（$f_0$ も同様）を満たすので、$\mathcal{C}$ は凸である。
段 2（分離）。$(0,p^*)\notin\mathcal{C}$ である。実際、$f_i(x)<0$（すべての $i$）かつ $f_0(x)< p^*$ となる $x$ は、実行可能で $f_0(x)< p^*$ となり、$p^*$ の定義に反する。Hahn–Banachの定理 の補題「点と開凸集合の分離」を $\mathbb{R}^{m+1}$ に用いると、$(0,0)$ でない $(\lambda,\mu)\in\mathbb{R}^m\times\mathbb{R}$ で
$$ \lambda\cdot u+\mu t>\mu p^*\qquad((u,t)\in\mathcal{C}) $$
となるものがある（$\mathbb{R}^{m+1}$ の線形汎関数は内積で表せる。補題の不等式の向きは $(\lambda,\mu)$ の符号を変えて合わせた）。
段 3（$\lambda\ge0$、$\mu\ge0$）。$(u,t)\in\mathcal{C}$ なら、$u$ のある成分や $t$ を大きくしても $\mathcal{C}$ に属する。$\lambda_i<0$ なら $u_i\to+\infty$ で左辺が $-\infty$ に近づき、不等式に反する。$\mu<0$ でも同様である。
段 4（$\mu>0$）。$\mu=0$ とすると $\lambda\ne0$、$\lambda\ge0$ で、$\lambda\cdot u>0$（$(u,t)\in\mathcal{C}$）である。Slater 条件の点 $\tilde x$ について $u:=\frac12(f_1(\tilde x),\dots,f_m(\tilde x))$ とすると、$f_i(\tilde x)< u_i<0$ なので、十分大きい $t$ で $(u,t)\in\mathcal{C}$ である。ところが $u$ の成分はすべて負なので $\lambda\cdot u<0$ となり、矛盾する。
段 5（結論）。$\mu>0$ で割り、$\lambda^*:=\lambda/\mu\ge0$ とおくと $\lambda^*\cdot u+t>p^*$（$(u,t)\in\mathcal{C}$）である。任意の $x$ と $\varepsilon>0$ について $(f_1(x)+\varepsilon,\dots,f_m(x)+\varepsilon,f_0(x)+\varepsilon)\in\mathcal{C}$ なので
$$ L(x,\lambda^*)+\varepsilon\Bigl(1+\sum_i\lambda_i^*\Bigr)>p^* $$
であり、$\varepsilon\to0$ として $L(x,\lambda^*)\ge p^*$ を得る。$x$ について下限をとって $g(\lambda^*)\ge p^*$ であり、prop-cvxopt-weak と合わせて $g(\lambda^*)=d^*=p^*$ である。$\square$

1：$L(\cdot,\lambda^*)=f_0+\sum_i\lambda_i^*f_i$ は凸関数の $0$ 以上の係数の和なので凸で、微分可能であり、停留性によりその勾配は $x^*$ で $0$ である。thm-cvxopt-optimality（$X=\mathbb{R}^n$）により $x^*$ は $L(\cdot,\lambda^*)$ の最小値を与えるので、相補性と合わせて
$$ g(\lambda^*)=L(x^*,\lambda^*)=f_0(x^*) $$
である。prop-cvxopt-weak により $f_0(x^*)=g(\lambda^*)\le d^*\le p^*\le f_0(x^*)$ なので、すべて等しい。
2：$p^*=f_0(x^*)$ は有限なので、thm-cvxopt-slater により $g(\lambda^*)=p^*$ となる $\lambda^*\ge0$ がある。$x^*$ は実行可能なので $\lambda_i^*f_i(x^*)\le0$ であり、
$$ f_0(x^*)=g(\lambda^*)\le L(x^*,\lambda^*)=f_0(x^*)+\sum_i\lambda_i^*f_i(x^*)\le f_0(x^*) $$
である。よって $\sum_i\lambda_i^*f_i(x^*)=0$ で、各項は $0$ 以下なのですべて $0$ であり、相補性が成り立つ。また $L(x^*,\lambda^*)=g(\lambda^*)=\inf_xL(x,\lambda^*)$ なので、$x^*$ は微分可能な関数 $L(\cdot,\lambda^*)$ の $\mathbb{R}^n$ 上の最小値を与え、thm-cvxopt-optimality によりその勾配は $0$ である。これが停留性である。$\square$