第 10 章：凸优化基础

\(\forall x,y\in C,\,\forall\theta\in[0,1]:\,\theta x+(1-\theta)y\in C\)

定义：\(f(\theta x+(1-\theta)y)\le\theta f(x)+(1-\theta)f(y)\)，\(\forall x,y\in\mathrm{dom}\,f,\,\theta\in[0,1]\)。

一阶条件（\(f\) 可微）：\(f(y)\ge f(x)+\nabla f(x)^T(y-x)\)，\(\forall x,y\)。

二阶条件（\(f\) 二阶可微）：\(\nabla^2 f(x)\succeq 0\)，\(\forall x\in\mathrm{dom}\,f\)。

非空：考虑 \(\mathbb{R}^{n+1}\) 中的集合 \(\mathrm{epi}(f)=\{(x,t):f(x)\le t\}\)（凸集）和点 \((x,f(x))\in\partial\,\mathrm{epi}(f)\)。由支撑超平面定理，存在 \((g,\mu)\neq0\) 使 \(g^T(y-x)+\mu(t-f(x))\le0\) 对所有 \((y,t)\in\mathrm{epi}(f)\)。取 \(t\to+\infty\) 得 \(\mu\le0\)；若 \(\mu=0\) 则 \(g=0\)（矛盾），故 \(\mu<0\)，令 \(s=-g/\mu\)，则 \(s\in\partial f(x)\)。

有界：因 \(x\in\mathrm{int\,dom}\,f\)，存在 \(\delta>0\) 使 \(B(x,\delta)\subset\mathrm{dom}\,f\)，\(f\) 在 \(B\) 上有上界 \(M\)。对任意 \(g\in\partial f(x)\) 和 \(\|d\|=1\)：\(f(x+\delta d)\ge f(x)+\delta g^Td\)，故 \(g^Td\le(M-f(x))/\delta\)，即 \(\|g\|\le(M-f(x))/\delta\)。

设 \(x^*=\Pi_K(z)\)，对任意 \(d\in K\) 和 \(t\in[0,1]\)，由 \(K\) 的凸性，\(x^*+t(d-x^*)\in K\)。

由 \(x^*\) 的最优性：\(\frac{1}{2}\|x^*+t(d-x^*)-z\|^2\ge\frac{1}{2}\|x^*-z\|^2\)。

展开：\(t^2\|d-x^*\|^2 + 2t\langle x^*-z,d-x^*\rangle\ge0\)，除以 \(t>0\) 后令 \(t\to0^+\)： \[\langle x^*-z,d-x^*\rangle\ge0\] 即 \(\langle z-\Pi_K(z),d-\Pi_K(z)\rangle\le0\)。

\(f(y)\ge f(x)+g^T(y-x),\quad\forall y\in\mathrm{dom}\,f\)

\((\partial\|x\|_1)_i = \begin{cases}\{1\} & x_i>0\\ \{-1\} & x_i<0\\ [-1,1] & x_i=0\end{cases}\) 即 \(\partial\|x\|_1 = \{g:\,g_i=\mathrm{sign}(x_i)\text{ 若 }x_i\neq0,\,g_i\in[-1,1]\text{ 若 }x_i=0\}\)。

问题可分离，对每个分量独立求解：\(\min_{x_i}\frac{1}{2}(x_i-y_i)^2+\lambda|x_i|\)。

最优性条件（次梯度为零）：\(x_i - y_i + \lambda\partial|x_i|\ni 0\)。

分情况：若 \(x_i>0\)：\(x_i=y_i-\lambda\)，需 \(y_i>\lambda\)；若 \(x_i<0\)：\(x_i=y_i+\lambda\)，需 \(y_i<-\lambda\)；若 \(x_i=0\)：需 \(|y_i|\le\lambda\)。

故软阈值算子：\(x_i^* = \mathcal{S}_\lambda(y_i) = \mathrm{sign}(y_i)\max(|y_i|-\lambda,0)\)。

\[L(x,\lambda,\nu) = f_0(x)+\sum_i\lambda_i f_i(x)+\sum_j\nu_j h_j(x)\] \[g(\lambda,\nu) = \inf_x L(x,\lambda,\nu)\] 对偶问题：\(\max g(\lambda,\nu)\) s.t. \(\lambda\ge0\)。

对任意可行 \(\tilde x\)（满足约束）和 \(\lambda\ge0\)： \[g(\lambda,\nu)\le L(\tilde x,\lambda,\nu) = f_0(\tilde x)+\underbrace{\sum\lambda_i f_i(\tilde x)}_{\le0}+\underbrace{\sum\nu_j h_j(\tilde x)}_{=0}\le f_0(\tilde x)\] 对 \(\tilde x\) 取下确界得 \(g(\lambda,\nu)\le p^*\)，再对 \(\lambda,\nu\) 取上确界得 \(d^*\le p^*\)。

① 原始可行性：\(f_i(x^*)\le0,\,h_j(x^*)=0\)
② 对偶可行性：\(\lambda_i^*\ge0\)
③ 互补松弛：\(\lambda_i^* f_i(x^*)=0\)
④ 稳定性（梯度条件）：\(\nabla f_0(x^*)+\sum_i\lambda_i^*\nabla f_i(x^*)+\sum_j\nu_j^*\nabla h_j(x^*)=0\)

由凸性，对 \(t\in(0,1]\)：\(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)\)。
令 \(t\to0^+\)，左边趋于 \(\nabla f(x)^T(y-x)\)，故 \(\nabla f(x)^T(y-x)\le f(y)-f(x)\)。

\(\Rightarrow\)：由一阶条件，\(f(x+td)\ge f(x)+t\nabla f(x)^Td\) 和 \(f(x)\ge f(x+td)+(-t)\nabla f(x+td)^Td\)，两式相加除以 \(t^2\) 令 \(t\to0\) 得 \(d^T\nabla^2f(x)d\ge0\)。

\(\Leftarrow\)：由 Taylor 展开，\(f(y)=f(x)+\nabla f(x)^T(y-x)+\frac{1}{2}(y-x)^T\nabla^2f(\xi)(y-x)\ge f(x)+\nabla f(x)^T(y-x)\)（因 \(\nabla^2f\succeq0\)），由一阶条件等价性得 \(f\) 凸。

反设存在 \(y\) 使 \(f(y) < f(x^*)\)。对 \(t\in(0,1)\)，令 \(z=x^*+t(y-x^*)\)，由凸性：
\(f(z)\le(1-t)f(x^*)+tf(y) < f(x^*)\)。
当 \(t\to0\) 时 \(z\to x^*\)，故在 \(x^*\) 的任意邻域内存在函数值更小的点，与 \(x^*\) 是局部极小矛盾。

梯度：对 \(z\) 的扰动 \(\delta z\)，令 \(p=\Pi_K(z)\)，\(p'=\Pi_K(z+\delta z)\)：
\(\Theta(z+\delta z)-\Theta(z)=\frac{1}{2}\|z+\delta z-p'\|^2-\frac{1}{2}\|z-p\|^2\)
\(\ge\frac{1}{2}\|z+\delta z-p\|^2-\frac{1}{2}\|z-p\|^2\)（\(p'\) 是最优点）
\(=\langle z-p,\delta z\rangle+O(\|\delta z\|^2)\)
类似地 \(\Theta(z+\delta z)-\Theta(z)\le\langle z+\delta z-p',\delta z\rangle+O(\|\delta z\|^2)=\langle z-p,\delta z\rangle+O(\|\delta z\|^2)\)（利用投影的非扩张性 \(\|p'-p\|\le\|\delta z\|\)）。
故 \(\nabla\Theta(z)=z-\Pi_K(z)\)。

凸性：\(\Theta(z)=\min_{y\in K}\frac{1}{2}\|z-y\|^2\) 的补函数 \(\frac{1}{2}\|z\|^2-\Theta(z)=\max_{y\in K}[\langle z,y\rangle-\frac{1}{2}\|y\|^2]\) 是凸函数（逐点上确界），故 \(\Theta\) 是凸函数（\(\frac{1}{2}\|z\|^2\) 减去凸函数不一定凸，但可直接用 \(\nabla^2\Theta\succeq0\) 验证，或用 \(\Pi_K\) 的非扩张性证明 \(\nabla\Theta\) 单调）。

Lagrange 函数：\(L=\|y\|_2+\gamma\|x\|_1+\lambda^T(Ax-b-y)\)。

KKT 稳定性条件：
对 \(y\)：\(\partial_y L\ni0\Rightarrow\frac{y^*}{\|y^*\|_2}-\lambda=0\Rightarrow\lambda=r\)。
对 \(x\)：\(\partial_x L\ni0\Rightarrow A^T\lambda\in\gamma\partial\|x^*\|_1\Rightarrow A^Tr\in\gamma\partial\|x^*\|_1\)。

由次梯度定义，\(\partial\|x\|_1\) 的每个分量在 \([-1,1]\) 内，故 \(\|A^Tr\|_\infty=\|A^Tr\|_\infty\le\gamma\cdot1=\gamma\)。

(a) Lagrange 函数：\(L(x,y,\lambda)=\|y\|_2^2+\mu\|x\|_2^2+\lambda^T(Cx-d-y)\)。
对 \(x\) 最小化：\(\nabla_x L=2\mu x+C^T\lambda=0\Rightarrow x=-\frac{1}{2\mu}C^T\lambda\)。
对 \(y\) 最小化：\(\nabla_y L=2y-\lambda=0\Rightarrow y=\frac{\lambda}{2}\)。
代入：\(g(\lambda)=-\frac{1}{4\mu}\|C^T\lambda\|_2^2-\frac{1}{4}\|\lambda\|_2^2-\lambda^Td\)。

(b) 对偶问题：\(\max_\lambda g(\lambda)\)（无约束，因原变量无约束）。
原问题为凸问题且无约束（Slater 条件自动满足），故强对偶成立。

(c) KKT 稳定性条件：\(2\mu x^*+C^T\lambda^*=0\)，\(2y^*-\lambda^*=0\)，原始可行：\(Cx^*-d=y^*\)。
由前两式：\(\lambda^*=2y^*=2(Cx^*-d)\)，代入第一式：\(2\mu x^*+2C^T(Cx^*-d)=0\)，
即 \((C^TC+\mu I)x^*=C^Td\)，故 \(x^*=(C^TC+\mu I)^{-1}C^Td\)（\(C^TC+\mu I\) 正定，可逆）。