1) 凸集投影是非扩张（实际上更强：firmly nonexpansive）
设闭凸集 $\mathcal C\subset \mathbb R^n$，投影记为 $P(x)=\Pi_{\mathcal C}(x)$。
投影的一阶最优性：对任意 $z\in\mathcal C$，有
$$ \langle x-P(x), z-P(x)\rangle \le 0. $$
取 $z=P(y)$ 得 $\langle x-P(x), P(y)-P(x)\rangle\le 0$。
同理交换 $x,y$ 得 $\langle y-P(y), P(x)-P(y)\rangle\le 0$。
二式相加：
$$ \langle x-y, P(x)-P(y)\rangle \ge \|P(x)-P(y)\|^2. $$
这就是"单边内积"版的坚定非扩张不等式。由 Cauchy–Schwarz：
$$ \|P(x)-P(y)\|^2 \le \|x-y\|\,\|P(x)-P(y)\| \Rightarrow \|P(x)-P(y)\|\le \|x-y\|. $$
证毕。
2) $\ell_1$ 范数的近端算子是软阈值
求
$$ \operatorname{prox}_{\lambda\|\cdot\|_1}(v) =\arg\min_x \frac12\|x-v\|_2^2+\lambda\|x\|_1. $$
目标按坐标可分：对每个标量 $x_i$ 解
$$ \min_{x_i}\ \frac12(x_i-v_i)^2+\lambda|x_i|. $$
分段求导：
- 若 $x_i>0$：$x_i-v_i+\lambda=0\Rightarrow x_i=v_i-\lambda$（需满足 $v_i>\lambda$ 才为正）。
- 若 $x_i<0$：$x_i-v_i-\lambda=0\Rightarrow x_i=v_i+\lambda$（需 $v_i<-\lambda$）。
- 若 $|v_i|\le\lambda$：两侧候选都跨不过 0，最优在 $x_i=0$。
合并成软阈值：
$$ \boxed{\ x_i^*=\operatorname{sign}(v_i)\cdot\max(|v_i|-\lambda, 0) \ } $$
向量形式就是逐坐标施加该算子。
3) 岭回归的对偶与 KKT
原问题（Tikhonov）：
$$ \min_x\ \frac12\|Ax-b\|^2+\frac\lambda2\|x\|^2\qquad (\lambda>0). $$
引入恒等式 $\frac12\|y\|^2=\max_u\big(u^\top y-\frac12\|u\|^2\big)$，令 $y=Ax-b$：
$$ \min_x\max_u\ \Big[u^\top(Ax-b)-\frac12\|u\|^2+\frac\lambda2\|x\|^2\Big]. $$
交换 $\min\leftrightarrow\max$（凸-凹且强对偶成立）并先对 $x$ 极小化：
$$ \min_x\ \frac\lambda2\|x\|^2+u^\top A x \ \Rightarrow\ x^*=-\frac1\lambda A^\top u,\quad \text{min值}=-\frac1{2\lambda}\|A^\top u\|^2. $$
于是对偶问题为
$$ \boxed{\ \max_u\; -\frac12\|u\|^2-\frac1{2\lambda}\|A^\top u\|^2 - b^\top u\ } $$
等价地，写成最小化：
$$ \min_u\ \frac12 u^\top\Big(I+\frac1\lambda AA^\top\Big)u + b^\top u. $$
KKT（用辅助变量 $y=Ax-b$ 与乘子 $u$ 写拉格朗日）：
$$ L(x,y,u)=\frac12\|y\|^2+\frac\lambda2\|x\|^2 + u^\top(Ax-b-y). $$
站立性与可行性：
$$ \begin{cases} \nabla_y L= y-u=0 &\Rightarrow\ y=u,\\ \nabla_x L= \lambda x + A^\top u=0 &\Rightarrow\ x=-\frac1\lambda A^\top u,\\ \text{原可行： } y=Ax-b. & \end{cases} $$
消去 $x,y$ 得对偶一阶条件：
$$ \Big(I+\frac1\lambda AA^\top\Big)u + b = 0 \ \Rightarrow\ u^*=-\Big(I+\frac1\lambda AA^\top\Big)^{-1}b, $$
再回代
$$ \boxed{\ x^*=(A^\top A+\lambda I)^{-1}A^\top b\ } $$
（Woodbury 恒等式可验证与上式一致）。
4) PL 条件下梯度下降的线性收敛
假设：$f$ 是 $L$-光滑（梯度 $L$-利普希茨），且满足 PL 条件
$$ \frac12\|\nabla f(x)\|^2 \ge \mu\big(f(x)-f^\star\big),\quad \mu>0. $$
取梯度下降迭代 $x_{k+1}=x_k-\eta\nabla f(x_k)$，令 $\eta\in(0, 2/L]$。
由光滑函数的下降引理（Descent Lemma）：
$$ f(x_{k+1})\le f(x_k) - \eta\Big(1-\frac{L\eta}{2}\Big)\|\nabla f(x_k)\|^2. $$
用 PL 条件下界梯度范数：
$$ \|\nabla f(x_k)\|^2 \ge 2\mu\big(f(x_k)-f^\star\big). $$
合并得
$$ f(x_{k+1})-f^\star \le\Big[1-2\mu\eta\Big(1-\frac{L\eta}{2}\Big)\Big](f(x_k)-f^\star). $$
因此 $\{f(x_k)-f^\star\}$ 以线性率收敛到 0，只要 $\eta\in(0,2/L)$。
取最常用步长 $\eta=\frac1L$：
$$ \boxed{\ f(x_{k+1})-f^\star \le \Big(1-\frac{\mu}{L}\Big)(f(x_k)-f^\star)\ }. $$
这给出全局线性收敛。注意这里不要求凸性：PL 条件已经保证了每个驻点都是全局最优（因为 $\nabla f=0\Rightarrow f=f^\star$），从而 GD 不会"卡在坏驻点"——这就是许多"非凸但很快"的现象背后的数学解释。