Truncated Gradient

L1正则化法

L1正则化

$$w^{(t+1)} = w^{(t)} - \eta^{(t)}g^{(t)} - \eta^{(t)} \lambda sgn(w^{(t)})$$

• $\lambda$：正则化项参数
• $sgn$：符号函数
• $g^{(t)}=\nabla_w L(w^{(t)}, Z^{(t)})$：损失函数对参数梯度

• L1正则化项在0处不可导，每次迭代使用次梯度计算正则项梯度
• OGD中每次根据观测到的一个样本进行权重更新 （所以后面正则项次梯度只考虑非0处？？？）

简单截断法

简单截断法：以$k$为窗口，当$t/k$非整数时，使用标准SGD迭代， 否则如下更新权重

$$\begin{align*} w^{(t+1)} & = T_0 (w^{(t)} - \eta^{(t)} G^{(t)}, \theta) \\ T_0(v_i, \theta) & = \left \{ \begin{array}{l} 0, & |v_i| \leq \theta \\ v_i, & otherwise \end{array} \right. \end{align*}$$

• $w^{(t)}$：模型参数
• $g^{(t)}$：损失函数对模型参数梯度
• $T_0$：截断函数
• $\theta$：控制参数稀疏性

截断梯度法

截断梯度法：以$k$为窗口，当$t/k$非整数时，使用标准SGD迭代， 否则如下更新权重

$$\begin{align*} w^{(t+1)} & = T_1(w^{(t)} - \eta^{(t)} g^{(t)}, \lambda^{(t)} \eta^{(t)}, \theta) \\ T_1(v_i, \alpha, \theta) & = \left \{ \begin{array}{l} max(0, v_i - \alpha), & v_i \in [0, \theta] \\ min(0, v_1 + \alpha), & v_i \in [-\theta, 0] \\ v_i, & otherwise \end{array} \right. \end{align*}$$

• $\lambda, \theta$：控制参数$w$稀疏性

• 对简单截断的改进，避免在实际（OgD）中参数因训练不足过小 而被错误截断，造成特征丢失

  

Forward-Backward Spliting

FOBOS：前向后向切分，权重更新方式为proximal method如下

$$\begin{align*} w^{(t.5)} & = w^{(t)} - \eta^{(t)} g^{(t)} \\ w^{(t+1)} & = \arg\min_w \{ \frac 1 2 \|w - w^{(t.5)}\| + \eta^{(t+0.5)} \Phi(w) \} \\ & = \arg\min_w \{ \frac 1 2 \|w - w^{(t)} + \eta^{(t)} g^{(t)}\| + \eta^{(t+0.5)} \Phi(w) \} \end{align*}$$

L1-FOBOS

L1-FOBOS：即令$Phi(w)=\lambda |w|_1$，则根据可加性如下

$$\begin{align*} w^{(t+1)} & = \arg\min_w \sum_{i=1}^N (\frac 1 2 (w_i - v_i)^2 + \tilde \lambda |w_i|) w_i^{(t+1)} = \arg\min_{w_i} (\frac 1 2 (w_i - v_i)^2 + \tilde \lambda |w_i|) \end{align*}$$

• $V=[v_1, v_2, \cdots, v_N]:=w^{(t.5)}$：为方便
• $\tilde \lambda := \eta^{t.5} \lambda$：为方便
• $\eta^{t.5}$：学习率，常取 $\eta^{(t)} \in \theta(\frac 1 {\sqrt t})$

• 则对$w_i$求次梯度、分类讨论，解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} v_i - \tilde \lambda, & v_i > \tilde \lambda \\ 0, & |v_i| < \tilde \lambda \\ v_i + \tilde \lambda, & v_i < -\tilde \lambda \end{array} \right.$$

  • 可以理解为：到当前样本为止，维度权重小于阈值 $\eta^{(t.5)} \lambda$）时，认为该维度不够重要， 权重置为0

  • 可视为$k=1, \theta=\infty$的Tg算法

• 另外，显然有$w_i^{(t+1)} v_i \geq 0$

  $$\begin{align*} \frac 1 2 (w_i^{(t+1)} - v_i)^2 + \tilde \lambda |w_i^{(t+1)}| & = \frac 1 2((w_i^{(t+1)})^2 - 2 w_i^{(t+1)} v_i + v_i^2) + \tilde \lambda |w_i^{(t+1)}| \\ & \leq \frac 1 2 v_i^2 \end{align*}$$

  • 考虑$w_i^{(t+1)}$使得目标函数最小，带入$w=0$则得

Regularized Dual Averaging

RDA算法：正则对偶平均算法，权重更新方式为 包含[增广]正则项的最速下降

$$w^{(t+1)} = \arg\min_w {\frac 1 t \sum_{r=1}^t g^{(r)} w + \Phi(w) + \frac {\beta^{(t)}} t h(w)}$$

• 目标函数包括三个部分

  • $\frac 1 t \sum_{r=1}^t g^{(r)} w$：包含之前所有梯度 均值
  • $\Phi(w)$：正则项
  • $\frac {\beta^{(t)}} t h(w)$：额外正则项，严格凸，且 不影响稀疏性

• 相较于TG、FOBOS是从另一方面求解在线最优化，更有效地提升 特征权重稀疏性

L1 RDA

L1 RDA：令$\Phi(w) := \lambda |w|_1$， 再设$h(w) := |w|_2^2$，根据可加性则有

$$\begin{align*} w^{(t+1)} & = \arg\min_w \{ \frac 1 t \sum_{r=1}^t <g^{(t)}, w> + \lambda \|w\|_1 + \frac {\gamma} {2\sqrt t} \|w\|_2^2 \} \\ w_i^{(t+1)} & = \arg\min_{w_i} \{bar g_i^{(t)} w_i + \lambda |w_i| \frac {\gamma} {2 \sqrt t} w_i^2 \} \end{align*}$$

• $\lambda > 0, \gamma > 0$
• $\bar gi^{(t)} = \frac 1 t \sum{r=1}^t g_i^{(r)}$

• 对$w_i$求次梯度、置零、求解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} -\frac {\sqrt t} {\gamma} (\bar g^{(t)} - \lambda), & \bar g_i^{(t)} > \lambda \\ 0, & |\bar g_i^{(t)}| \leq \lambda \\ -\frac {\sqrt t} {\gamma} (\bar g^{(t)} + \lambda), & \bar g_i^{(t)} < -\lambda \\ \end{array} \right.$$
  • 可以理解为：某维度梯度累计均值绝对值$|bar g_i^{(t)}$ 小于阈值$\lambda$时，对应权重被置零、产生稀疏性

• 相较于L1-FOBOS的截断

  • 截断阈值为常数，更加激进、容易产生稀疏性
  • 截断判断对象为梯度累加均值，避免由于训练不足而产生 截断
  • 只需条件$\lambda$参数，容易权衡精度、稀疏性

Follow the Regularized Leader

FTRL：综合考虑L1-RDA、L1-FOBOS

L1-FOBOS、L1-RDA变换

• 将L1-FOBOS类似近端算法收敛证明中展开、去除无关项、放缩， 得到类似L1-RDA目标函数

  $$\begin{align*} w^{(t+1)} & = \arg\min_w \{ \frac 1 2 \|w - w^{(t)} + \eta^{(t)} g^{(t)}\| + \eta^{(t)} \lambda \|w\|_1 \} \\ & = \arg\min_w \{ g^{(t)} w + \lambda \|w\|_1 + \frac 1 {2 \eta^{(t)}} \|w - w^{(t)}\|_2^2 \} \end{align*}$$

• 将L1-RDA目标函数整体整体放缩，得到

  $$w^{(t+1)} = \arg\min_w \{ g^{(1:t)} w + t \lambda \|w\|_1 + \frac 1 {2\eta^{(t)}} \|w - 0\|_2^2 \}$$

  • $g^{(1:t)} := \sum_{r=1}^t g^{(r)}$

• FTRL综合考虑L1-FOBOS、L1-RDA，得到目标函数

  $$w^{(t+1)} = \arg\min_w \{ g^{(1:t)} W + \lambda_1 \|w\|_1 + \frac {\lambda_2} 2 \|w\|_2^2 + \frac 1 2 \sum_{r=1}^t \sigma^{(r)} \|w - w^{(r)}\|_2^2 \}$$
  • 使用累加梯度更新，避免因训练不充分错误截断
  • 包含L1-FOBOS、L1-RDA全部正则化项

求解

• 将FTRL中最后一项拆分、去除无关项

  $$\begin{align*} w^{(t+1)} & = \arg\min_w \{(g^{(1:t)} - \sum_{r=1}^t \sigma^{(r)} w^{(r)})w + \lambda_1 \|w\|_1 + \frac 1 2 (\lambda_2 + \sum_{r=1}^t \sigma^{(r)}) \|w\|_2^2 + \frac 1 2 \sum_{r=1}^t \sigma^{(r)} \|w^{(r)}\|_2^2 \} \\ & = \arg\min_w \{ z^{(t)} w + \lambda_1 \|w\|_1 + \frac 1 2 (\lambda_2 + \sum_{r=1}^t \sigma^{(r)}) \|w\|_2^2 \} \\ z^{(t)} &= g^{(1:t)} - \sum_{r=1}^t \sigma^{(r)} w^{(r)} \end{align*}$$

• 则同样根据可加性，对各分量求次梯度、置零、求解得

  $$w_i^{(t+1)} = \left \{ \begin{array}{l} \frac 1 {\lambda_1 + \sum_{r=1}^t \sigma^{(r)}} (z_i^{(t)} - \lambda_1 z_i), & z_i > \lambda_1 \\ 0, & |z_i^{(t)}| \leq \lambda_1 \\ \frac 1 {\lambda_1 + \sum_{r=1}^t \sigma^{(r)}} (z_i^{(t)} + \lambda_1 z_i), & z_i < -\lambda_1 \\ \end{array} \right.$$

• 其中学习率$\eta$为类似Adagrad优化器的学习率，但包括可学习 参数$\alpha, \beta$

  $$\eta_i^{(t)} = \frac {\alpha} {\beta + \sqrt{\sum_{r=1}^t (g_i^{(r)})^2}}$$

Proximal Operator

$$prox_{f}(x) = \arg\min_u (f(u) + \frac 1 2 \|u - x\|^2)$$

• $f(x)$：凸函数

• 由于$L_2$范数的强凸性，近端算子也强凸，解总是唯一存在
• 直观理解：寻找距离点$x$不太远、$f(u)$尽可能小的$u$
• 以下算法都是近端算法的特例
  • shrinkage thresholding algorithm
  • projected Landweber
  • projected gradient
  • alternating projections
  • alternating-directions method of multipliers
  • alternating split Bregman

• 近端算子连续可微

Moreau Envolop

$$\begin{align*} M_{\gamma, f}(x) & = prox_{\gamma, f}(x) \\ &= \arg\min_u (f(u) + \frac 1 {2\gamma} \|u - x\|^2) \\ \nabla prox_{\gamma, f}(x) & = \frac 1 {\gamma}(x - prox_f(x)) \end{align*}$$

• $\gamma > 0$：平衡参数，$\gamma = 1$即为普通近端算子

近端算子求解

• 对一般凸$f(x)$，通常使用次梯度进行优化，其近端算子解为 （即解变动方向$p-x$为负次梯度方向）

  $$p = prox_f(x) \Leftrightarrow x - p \in \partial f(p) \quad (\forall (x,p) \in R^N * R^N)$$

• 对光滑凸函数$f$，上述等式对其近端算子约简为 （即解变动方向$p-x$为负梯度方向）

  $$p = prox_f(x) \Leftrightarrow x-p = \bigtriangledown f(p)$$

性质

分离函数

$$\begin{align*} f(x_1, \cdots, x_m) & = \sum_{i=1}^m f_i(x_i) \\ prox_f(x_1, \cdots, x_m) & = [prox_{f_1}(x_1), \cdots, prox_{fm}(x_m)] \end{align*}$$

• 取$f(x) = |x|_1$，即可得即软阈值算子

  $$(prox_{\gamma, f}(x))_i = \left \{ \begin{array}{l} x_i - \gamma, & x_i \geq \gamma \\ 0, & |x_i| < \gamma \\ x_i + \gamma, & x_i \leq -\gamma \end{array} \right.$$

  • 参考坐标下降：近端算子中二次项中各分量无关，所以一轮 迭代即为最优解

仿射函数分解

$$\begin{align*} f(x) & = g(Ax + b) \\ prox_f(x) & = x + \frac 1 {\alpha} A^T (prox_{\alpha g}(Ax + b) - Ax - b) \end{align*}$$

• $A^T A = \alpha I, \alpha > 0$：线性变换
• $g$：良好闭凸函数

第一投影定理

• 取$f(x)$为示性函数、约束条件，即得到投影算子

$$\begin{align*} prox_{\gamma, f}(x) & = proj_C(x) = \arg\min_{u \in C} \|u - x\|_2^2 \\ f(x) & = I_C(x) = \left \{ \begin{array}{l} 0, x \in C \\ \infty, x \notin C \end{array} \right. \end{align*}$$

第二临近定理

• $f$为良好闭凸函数，则以下三条等价

  • $y = prox_f(x)$
  • $x - y \in \partial f(y)$：由近端算子定义即得
  • $\forall z, \leq f(z) - f(y)$

Moreau Decomposition

$$\begin{align*} prox_f(x) + prox_{f^{*}}(x) & = x \\ prox_{\lambda f}(x) + \lambda prox_{f^{*}/lambda}(x/\lambda) & = x, \lambda > 0 \end{align*}$$

最小值

$$\begin{align*} \min_x prox_f(x) & = \min_x f(x) \\ \arg\min_x prox_f(x) & = \arg\min_x f(x) \end{align*}$$

证明

$$\begin{align*} f(x_f) & = f(x_f) + \frac 1 2 \|x_f - x_f\|_2^2 \\ & \geq \min_u {f(u) + \frac 1 2 \|u - x_f\|_2^2} \\ & = prox_f(x_f) \\ & \geq prox_f(x_p) \\ & = f(x_p) + \frac 1 2 \|x_p - x_f\|_2^2 \\ & \geq f(x_p) \geq f(x_f) \end{align*}$$

• $x_f = \arg\min_x f(x)$
• $x_p = \arg\min_x prox_f(x)$

例

• $f(x)=c$：$prox_{f}(x) = x$

Projection Operator

投影算子

$$\begin{align*} proj_C(x) & = \arg\min_{y \in C} \|y - x\|^2 \\ & = \arg\min_{y \in R^N} l_C(x) + \frac 1 2 \|y-x\|^2 \end{align*}$$

• 点$x$在凸集$C$上的投影：$X$上距离$x$的欧式距离最近的点

Alternating Projection Method

POCS/project onto convex sets method：用于解同时满足多个 凸约束的算法

• $f_i$作为非空闭凸集$C_i$示性函数，表示一个约束，则整个 问题约简为convex feasibility problem

• 只需要找到位于所有$C_i$交集的解即可

• 每次迭代

  $$x^{(k+1)} = P_{C_1}P_{C_2} \cdots P_{C_n}x_k$$

• 在其他问题中投影算子不再适合，需要更一般的算子，在其他 各种同样的凸投影算子中，近端算子最合适

Proximal Gradient Method

近端算法：分两步分别优化可微凸$F(x)$、凸$R(x)$，近似优化目标 函数整体，不断迭代直至收敛

$$\min_{x \in \mathcal{H}}F(x) + R(x)$$

• $F(x)$：可微、凸函数
• $\nabla F(x)$：Lipschitz continous、利普希茨常数为$L$
• $R(x)$：下半连续凸函函数，可能不光滑
• $\mathcal{H}$：目标函数定义域集合，如：希尔伯特空间

• gredient step：从$x^{(k)}$处沿$F(x)$负梯度方向微小移动 达到$x^{(k.5)}$

  $$x^{(k.5)} = x^{(k)} - \gamma \nabla F(x^{(k)})$$

• proximal operator step：在$x^{(k.5)}$处应用$R(x)$近端 算子，即寻找$x^{(k.5)}$附近且使得$R(x)$较小点

  $$x^{(k+1)} = prox_{\gamma R}(x^{(k.5)})$$

目标函数推导

$$\begin{align*} prox_{\gamma R}(x - \gamma \nabla F(x)) & = \arg\min_u (R(u) + \frac 1 {2\gamma} \|u - x + \gamma \nabla F(x)\|_2^2) \\ & = \arg\min_u (R(u) + \frac {\gamma} 2 \|\nabla F(x)\|_2^2 + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u-x\|_2^2) \\ & = \arg\min_u (R(u) + F(x) + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u - x\|_2^2) \\ & \approx \arg\min_u(R(u) + F(u)) \end{align*}$$

• $\frac {\gamma} 2 |\nabla F(x)|_2^2, F(x)$：与$u$无关 ，相互替换不影响极值
• $0 < \gamma \leq \frac 1 L$：保证最后反向泰勒展开成立

• 则$prox_{\gamma R}(x-\gamma \nabla F(x))$解即为 “原问题最优解”（若泰勒展开完全拟合$F(x)$）

  • 近端算法中距离微调项部分可加法分离
  • 若$R(x)$部分也可分离，则整个目标函数可以分离，可以 拆分为多个一元函数分别求极值

• 考虑泰勒展开是局部性质，$u$作为极小值点只能保证在$x$附近 领域成立，可将近端算子解作为下个迭代点

  $$x^{(k+1)} = prox_{\gamma R}(x^{(k)} - \gamma \nabla F(x^{(k)}))$$

• 迭代终止条件即

  $$\hat x = prox_{\gamma R}(\hat x - \gamma \nabla F(\hat x))$$

二阶近似证明

$$\begin{align*} F(u) & = F(x) + \nabla F(x)^T (u - x) + \frac 1 2 (u - x)^T \nabla^2 F(\zeta)(u - x) \\ & \geq F(x) + \nabla F(x)^T (u - x) \\ & \leq F(x) + \nabla F(x)^T (u - x) + \frac L 2 \|u-x\|^2 \end{align*}$$

• $\nabla^2 F(\zeta)$：凸函数二阶导正定
• $|\nabla F(u) - \nabla F(x)|_2 \leq L |u-x|_2$： $\nabla F(x)$利普希茨连续性质

参数确定

• $L$已知时，可直接确定$\gamma \in (0, \frac 1 L]$，

• 否则可线性迭代搜索$\gamma := \beta \gamma,\beta < 1$， 直至

  $$F(x - PG_{\gamma R}(x)) \leq F(x) - \nabla F(x) PG_{\gamma R}(x) + \frac 1 2 \|PG_{\gamma R}(x)\|_2^2$$

  • $PG{\gamma R}(x)=x-prox{\gamma R}(x-\gamma \nabla F(x))$
  • 直接根据下述利普希茨条件须求Hasse矩阵，计算量较大

反向推导

• 对$F(x)+R(x)$在$x_0$附近作泰勒展开

  $$F(u)+R(u) \leq F(x) + \nabla F(x)^T (u - x) + \frac 1 {2\gamma} \|u - x\|_2^2 + R(x)$$

  • $\lambda \in (0, \frac 1 L]$
  • $L$：$F(x)$利普希茨常数
  • $\leq$：由Lipschitz连续可取

  • 则不等式右边就是$F(x)+R(x)$的一个上界，可以对将对其 求极小化转化对此上界求极小

• 考虑对极小化目标添加常数项不影响极值，对不等式右侧添加 与$u$无关项$\frac \gamma 2 |\nabla F(x)|_2^2$、剔除 剔除$F(x)$凑出近端算子

  $$\begin{align*} prox_{\gamma R} & = \arg\min_u (R(u) + \frac {\gamma} 2 \|\nabla F(x)\|_2^2 + \nabla F(x)^T (u-x) + \frac 1 {2\gamma} \|u-x\|_2^2) \\ & = \arg\min_u (R(u) + \|u - x + \frac 1 {2\gamma} \nabla F(x)\|_2^2) \end{align*}$$

近端算法推广

问题推广

• 求解non-differentiable凸优化问题的通用投影形式

$$\min_{x \in R^N} \sum_{i=1}^N f_i(x)$$

• $f_i(x)$：凸函数，不一定处处可微

• 目标函数中包含不处处连续可微函数，整个目标函数不光滑

  • 无法使用传统的光滑优化手段，如：最速下降、共轭梯度
  • 极小化条件为$0 \in \partial(F+R)(x)$

• 分开考虑各个函数，对非光滑函数使用近端算子处理

算子推广

• 考虑使用Bregman Divergence替代近端算子中欧式距离

$$prox_{\gamma, f}(x) = \arg\min_u (f(u) + \mu(u) - \mu(x) + <\nabla \mu(x), u - x>)$$

• 取$\mu(x) = \frac 1 2 |x|_2^2$时，即为普通近端算子

坐标下降

坐标下降法：在当前点处延一个坐标方向进行一维搜索以求得函数 的局部极小值

• 非梯度优化算法，但能提供超过一阶的信息
  • SMO算法就是两块贪心坐标下降

说明

• 优化方向从算法一开始就固定，如：选择线性空间中一组基作为 搜索方向

• 循环极小化各坐标方向上目标函数值，即：若$x^k$给定，则

  $$x_i^{(k+1)} = \arg\min_{x \in R} f(x_1^{k+1}, \cdots, x_{i-1}^{k+1}, x, x_{i+1}^{k}, \cdots, x_n^k)$$

  • $k$：第k轮迭代
  • $i$：某轮迭代中更新第i个方向

• 对初始值为$X_0$得到迭代序列$X_1, \cdots, X_n$，对精确 一维搜索类似最速下降有

  $$F(X_0) \geq F(X_1) \geq \cdots \geq F(x_n)$$

• 若某轮迭代中目标函数无法被有优化，说明已经达到驻点

Adaptive Coordinate Descent

自适应坐标下降：变换坐标系使得在考虑目标函数的情况下，新坐标 间尽可能不相关

• 对非可拆分函数（可加？），算法可能无法在较小迭代步数中 求得最优解

  • 可采用适当坐标系加速收敛，如：主成分分析进行自适应 编码
  • 性能远超过传统坐标下降算法，甚至可以达到梯度下降的 性能

  

• 自适应坐标下降具有以下特性，和最先进的进化算法相当

  • 缩放不变性
  • 旋转不变性

Block Coordinate Descent

块坐标下降：在当前点处在一个超平面内方向进行搜索以求得函数 的局部极小值

• 即同时更新一组坐标的坐标下降

例

Lasso求解

• 目标函数

  $$L(x) = RSS(x) + \lambda \|x\|_1 = \frac 1 2 (Ax - y)^T(Ax - y) + \lambda \|x\|_1$$

• RSS求导

  $$\begin{align*} \frac {\partial RSS} {\partial x} & = (Ax - y)^T A \\ (\frac {\partial RSS} {\partial x})_i & = (Ax - y)^T A_{:i} \\ & = (Ax_{i0} - y)^T A_{:i} + x_i A_{:i}^T A_{:i} \\ & = z_i + \rho_i x_i \end{align*}$$

  • $(\frac {\partial RSS} {\partial x})_i$：RSS对$x$ 导数第$i$分量，即对$x_i$偏导
  • $A_{:i}$：$A$第$i$列
  • $x_{i0}$：$x$第$i$分量置零
  • $zi = (Ax{i0} - y)^T A_{:i}$
  • $\rhoi = A{:i}^T A_{:i}$

• 则$x_i$整体次梯度为

  $$\frac {\partial L} {\partial x_i} = z_i + \rho_i x_i + \left \{ \begin{array}{l} -\lambda, & x_i < 0 \\ [-\lambda, \lambda], & x_i = 0 \\ \lambda, & x_i > 0 \end{array} \right.$$

• 分类讨论：令整体次梯度为0求解$x_i$、回带确定参数条件

  $$x_i = \left \{ \begin{array}{l} \frac {-z_i + \lambda} {\rho_i}, & z_i > \lambda \\ 0 , & -\lambda < z_i < \lambda \\ \frac {-z_i - \lambda} {\rho_i}, & z_i < -\lambda \end{array} \right.$$

  • 此算子也称soft threshholding

  

Legendre Transformation

勒让德变换：用 $f^{ * }(p)$ 表示凸、可导函数 $f(x)$ 的变换，其中 $p$ 是 $f(x)$ 导数

$$f^{*}(p) = p^T x - f(x)|_{\frac {d(p^T x - f(x))} {dx} = 0}$$

• $x$：参数，满足 $\frac {d(p^T x - f(x))} {dx} = 0$，随 $p$ 取值改变
• 可导：有导数；凸：导数唯一

• 勒让德变换是实变量的实值凸函数的对合变换
  • 把定义在线性空间上的函数变换至对偶空间的函数
  • 是点、（切）线之间对偶关系的应用
    • 严格凸函数中，切线、导数一一对应
    • 函数关系 $f(x)$ 可使用 $(x, y=f(x))$ 点集表示，也可用切线集合表示

• involution 对合：对合函数 $f$ 的反函数的为自身，即 $f(f(x))=x$；对合线性变换 $V$ 满足 $V^2 = E$

Legendre 变换理解（按 Fenchel 共轭）

• $f^{*}(p)$：可理解为斜率为 $p$、同 $f(x)$ 有交点 $x_0$ 的直线在零点处值（截距）和 $f(x_0)$ 的最大差

  

• $x$：可以理解为函数 $f(x)$ 上距离给定斜率为 $p$、过原点的直线 $f(x)=px$ 竖直距离最大的点

  

  • 类似一个端点为 $0$ 的 Bregman 散度

• Legendre 变换为对合变换，进行两次的变换得到原函数

  

  $$\begin{align*} f^{**}(x) & = \sup_{p \in dom(f^{*})} [x^T p - f^{*}(p)] \\ & = \sup_{u \in dom(f)}[x^T \nabla f(u) - \nabla f(u)^T u + f(u)] \\ & = \sup_{u \in dom(f)}[f(u) + \nabla f(u)^T (x-u)] \\ & = f(x) \end{align*}$$

• 若视凸函数 $f(x)$ 视为积分，则其共轭 $f^{ * }(x)$ 为对另一轴积分，二者导函数互为反函数

  $$f(x) + f^{*}(p) = xp, p = \frac {df(x)} {dx}$$

• 以上性质均按 Fenchel 共轭，但要求 $f(x)$ 为凸、可导函数，故等价于 Legendre 变换

Legendre 变换最大值式定义

$$\begin{align*} L(p, x) &= px - f(x) \\ \frac {\partial (px - f(x))} {\partial x} &= p - \frac {df(x)} {dx} = 0 \\ \Rightarrow & p = \frac {df(x)} {dx} \end{align*}$$

• Legendre 变换可以视为寻找 $px-f(x)$ 最大值（如前述）
  • $f(x)$ 为凸函数，则 $p=\frac {df(x)} {dx}$ 是最大值点
  • 则将 $f(x)$ 导函数的反函数 $x=f^{-1}(p)$ 带入即可

Legendre 变换数学性质

• 标度性质

  $$\begin{align*} f(x) & = a g(x) \rightarrow f^{*}(p) = a g^{*}(\frac p a) \\ f(x) & = g(ax) \rightarrow f^{*}(p) = g^{*}(\frac p a) \end{align*}$$

  由此，$r$次齐次函数的勒让德变换是$s$次齐次函数，满足

  $$\frac 1 r + \frac 1 s = s$$

• 平移性质

  $$\begin{align*} f(x) & = g(x) + b \rightarrow f^{*}(p) = g^{*}(p) - b f(x) & = g(x+y) \rightarrow f*^{*}(p) = g^{*}(p) - py \end{align*}$$

• 反演性质

  $$f(x) = g^{-1}(x) \rightarrow f^{*}(p) = -p g^{*}(\frac 1 p)$$

• 线性变换性质

  $$(Af)^{*} = f^{*}A^{*}$$

  • $f$：$R^n$上的凸函数
  • $A$：$R^n \rightarrow R^m$的线性变换
  • $A^{}: <Ax, y^{}> = $：$A$伴随算子

Fenchel Conjugate / 凸共轭

$$f^{*}(p) = \sup_{x \in R}{p^Tx - f(x)}$$

• Fenchel 共轭是对 Legendre 变换的扩展，不再局限于凸、可导函数
  • Fenchel 共轭可类似 Legendre 理解，但是适用范围更广
  • 对凸函数 Fenchel 共轭的共轭即为原函数，对非凸函数 Fenchel 共轭得到原函数凸包
  • 用罗尔中值定理描述极值、导数关系：兼容 Legendre 变换中导数支撑面

• 非凸函数线性外包络是凸函数

Fenchel-Young不等式

$$f(x) + f^{*}(p) \geq <p, x>$$

• 证明

  $$\begin{align*} f(x) + f^{*}(p) & = f(x) + \sup_{x \in dom(f)} {(x^T p - f(x))} \\ & \geq f(x) + x^T p - f(x) = x^T p \end{align*}$$

• 按积分理解，仅$p$为$x$共轭时取等号

  

Fenchel Conjugate 推导 Lagrange Duality

• 原问题 Prime

  $$\begin{align*} & \min {f(x)} \\ s.t. & g(x) \leq 0 \\ \end{align*}$$

• 约束条件 $g(x) \leq 0$ 扰动函数化、求 Fenchel 共轭

  $$\begin{align*} p(u) & = \inf_{x \in X, g(x) \leq u} f(x) \\ p^{*}(y) & = \sup_{y \in R^r} \{u^T y - p(u)\} \end{align*}$$

• 记 $\lambda = -y$，并将 $y=-\lambda$ 带入 $-p^{*}(y)$ 中得到

  $$\begin{align*} -p^{*}(y) & = \inf_{u \in R^r} \{p(u) - u^T y\} \\ d(\lambda) & = \inf_{u \in R^r} \{p(u) + u^T \lambda\} \\ & = \inf_{u \in R^r} \{\inf_{x \in X, g(x) \leq u} f(x) + \lambda^T u\} \end{align*}$$

  • $\lambda = -y$

• 将 $\inf_{x \in X, g(x) \leq u}$ 外提，并考虑到约束 $g(x) \leq u$（即 $u \geq g(x)$），则

  $$\begin{align*} \lambda \geq 0 & \Rightarrow \lambda^T g(x) \leq \lambda u \\ d(\lambda) & = \left \{ \begin{array}{l} \inf_{x \in X} \{f(x) + \lambda^T g(x)\}, & \lambda \geq 0 \\ -\infty, & otherwise \end{array} \right. \end{align*}$$

• 考虑 Fenchel 不等式

  $$\begin{align*} p(u) + p^{*}(-y) & \geq u^T (-y) \\ p(0) + p^{*}(-y) & \geq 0 \\ p(0) & \geq -p^{*}(-y) \\ p(0) & \geq d(\lambda) \end{align*}$$

• 则可得 Lagrange 对偶 Prime、Dual 最优关系

  $$L(x, \lambda) = f(x) + \lambda^T g(x), \lambda \geq 0 \\ D^{*} := \max_{\lambda \geq 0} \min_x L(x, \lambda) \leq \min_x \max_{\lambda \geq 0} L(x, \lambda) =: P^{*}$$

  

Lagrange Duality 推导 Fenchel 对偶

• Fenchel 对偶可以视为 Lagrange 对偶的应用

• 原问题、等价问题

  $$\begin{align*} & \min_x & f(x) - g(x) \\ \Leftrightarrow & \min_{x,z} & f(x) - g(z) \\ & s.t. & x = z \end{align*}$$

• 对上式取 Lagrange 对偶 $L(u)$、等价得到

  $$\begin{align*} L(u) &= \min_{x,z} f(x) - g(z) + u^T(z-x) \\ &= -(f^{*}(u) - g^{(-u)}) \end{align*}$$

• Fenchel 对偶：寻找截距差值最大的平行切线

Fourier Transformation

（连续）傅里叶变换：将时域映射到频域的变换

$$F(\xi) = \int_{-\infty}^{+\infty} f(x) e^{-2\pi ix \xi} dx$$

• $x$：自变量，多表示时间
• $F(\xi)$：频率

傅里叶变换理解

• 将自变量 $x$ 线性映射为极坐标系中角度，调整线性映射的比例（即频率），即可绘制出不同的曲线

  

• 计算不同频率下曲线围成的图像的质心（径向）坐标

  • 质心的角度坐标只需原函数沿 $x$ 轴平移即可改变
  • 若原图像不关于 $x$ 轴对称，则质心在频率 0 点处有较大值

  

• 据以上：周期函数映射在极坐标系下图像，其质心位置在对应频率下取波峰值

• https://charlesliuyx.github.io/2018/02/18/%E3%80%90%E7%9B%B4%E8%A7%82%E8%AF%A6%E8%A7%A3%E3%80%91%E8%AE%A9%E4%BD%A0%E6%B0%B8%E8%BF%9C%E5%BF%98%E4%B8%8D%E4%BA%86%E7%9A%84%E5%82%85%E9%87%8C%E5%8F%B6%E5%8F%98%E6%8D%A2%E8%A7%A3%E6%9E%90/

傅里叶变换计算

• 利用复数项 $e^{-2\pi ix \xi}$ 表示在复平面中的旋转角度

  • $x$ 为函数自变量，$\xi$ 为频率（即自变量映射比例）
  • 傅里叶变换中旋转为缺省为顺时针，所以补足负号
  • 函数在复平面中则表示为 $f(x) e^{-2\pi ix \xi}$

• 函数围成的曲线质心则为 $\frac 1 {x2 - x_1} \int{x_1}^{x_2} f(x) e^{-2\pi ix \xi} dx$

  • 系数 $\frac 1 {x_2 - x_1}$ 将积分结果放缩回质心，可省略
  • 将原积分区域外函数值定为 0，积分上下限扩展至 $-\infty, \infty$ 不影响积分结果
  • 函数有效取值部分越长，质心波动约迅速

傅里叶变换

Discrete Fourier Transformation

DFT：归一化二维离散傅里叶变换

$$\begin{align*} F(u,v) & = \frac 1 {\sqrt{NM}} \sum_{x=0}^{N-1} \sum_{y=0}^{M-1} f(x,y) e^{-\frac {2\pi i} N ux} e^{-\frac {2\pi i} M vy} \\ f(x,y) & = \frac 1 {\sqrt{NM}} \sum_{u=0}^{N-1} \sum_{v=0}^{M-1} F(u,v) e^{\frac {2\pi i} N ux} e^{\frac {2\pi i} M vy} \\ \end{align*}$$

Discrete Consine Transformation

余弦变换

• 在给定区间为满足狄利克雷条件的连续实对称函数，可以展开为 仅含余弦项的傅里叶级数

• 对于定义在正实数域上的函数，可以通过偶延拓、或奇延拓满足 上述条件

离散余弦变换

• $(x,y) or (u,v) = (0,0)$时

  $$\begin{align*} F(u,v) & = \frac 1 N \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x,y) cos[\frac \pi N u(x + \frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \\ f(x,y) & = \frac 1 N \sum_{u=0}^{N-1} \sum_{v=0}{N-1} F(u,v) cos[\frac \pi N u(x + frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \end{align*}$$

• 其他

  $$\begin{align*} F(u,v) & = \frac 1 {2N} \sum_{x=0}^{N-1} \sum_{y=0}^{N-1} f(x,y) cos[\frac \pi N u(x + \frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \\ f(x,y) & = \frac 1 {2N} \sum_{u=0}^{N-1} \sum_{v=0}{N-1} F(u,v) cos[\frac \pi N u(x + frac 1 2)] cos[\frac \pi N v(y + \frac 1 2)] \end{align*}$$

Projected Gradient Descent

受限优化问题

$$\min_{x \in C} f(x)$$

• $C \subseteq R^d$：受限凸集

投影梯度下降：采用后处理的方式，将迭代位置拉回到约束条件内

• 使用一般下降算法进行位置更新，新位置$x_{t+1}^{‘}$可能 不再满足约束条件

• 为使新位置$x{t+1}^{‘}$符合受限集合，可以选择在$L_2$范数 下距离受限集合$C$最近的的点 $x{t+1}=\arg\min{x \in C} |x - x{t+1}^{‘}|$作为下步 真正迭代位置

线性约束

Projection Matrix

• 投影矩阵：矩阵$P \in R^{n*n}$，若满足$P^T = P, P^2 = P$
• 若$A \in R^{m*n}$为行满秩矩阵，则$A$的零空间为 $L_A = {x \in R^{n} | Ax = 0}$，对应正交空间为 $L_A^{\perp} = {A^T y | y \in R^m}$

对$\forall x \in R^n$进行正交分解

$$\begin{align*} \forall x \in R^n, x & = x_1 + x_2, x_1 \in L_A, x_2 \in L_A^{\perp} \\ x_1 & = P_A x \end{align*}$$

• $P_A = I - A^T (A A^T)^{-1} A$：$A$的投影矩阵
• 投影矩阵$P_A$可由点对线性约束的投影定义，利用拉格朗日 求解

证明

$$\begin{align*} x_1 & = x - x_2 = x - A^T y \\ A x_1 & = A x - A A^T y \\ \Rightarrow y & = (A A^T)^{-1} A (x - x_1) \\ \Rightarrow x_1 & = x - A^T[(A A^T)^{-1} A (x - x_1)] \\ & = x - A^T (A A^T)^{-1} A x - A^T (A A^T)^{-1} A x_1 \\ & = (I - A^T (A A^T)^{-1} A) x = P_A x \end{align*}$$

• 投影矩阵$P$对值应用多次线性变换和只应用一次结果相同， 保持像不变

Projection Operator

$$\begin{array}{l} \min & f(x) \\ s.t. & A_1 x \leq b_1 \\ & A_2 x = b_2 \end{array}$$

• 设$x^{k}$为当前迭代点，记$A{11}$、$A{12}$分别为紧、松 约束，即

  $$\begin{align*} A_1 & = \begin{bmatrix} A_{1,1} \\ A_{1,2} \end{bmatrix}, & b_1 & = \begin{bmatrix} b_{1,1} \\ b_{1,2} \end{bmatrix} \\ A_{1,1} x^k & = b_{1,1}, & A_{1,2} x^k & \leq b_{1,2} \end{align*}$$

• 记$M = [A_{1,1}^T, A_2^T]^T$，则$s \in L_M$时是可行方向

• 对负梯度$\nabla f(x^k)$，通过$M$的投影矩阵$P_M$将其投影 至$L_M$上即得可行下降方向$s^k = -P_M \nabla f(x^k)$

  • $s^k \neq 0$：为$x^k$处可行下降方向
  • $s^k = 0$：作如下讨论

投影方向为0

• 记$w = [u, v]^T = -(M M^T)^{-1}M \nabla f(x^k)$，则有

  $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + [A_{1,1}^T, A_2^T] \begin{bmatrix} u \\ v \end{bmatrix} \\ & = \nabla f(x^k) + A_{1,1}^T u + A_2^T v \end{align*}$$

• 若$u \geq 0$，则$x^{k}$是KKT点

  $$\nabla f(x^k) + A_{1,1}^T u + A_{1,2}^T v = 0 \Rightarrow x^k 为KKT点$$

• 否则若$u$中有负分量，可设$u0 < 0$，记$\bar M$为$M$中 去除对应列矩阵，则$\bar s^k = -P{\bar M}\nabla f(x^k)$ 为$x^k$可行下降方向

  • 先反证法证明$\bar s^k \neq 0$，若$\bar s^k = 0$

    $$\begin{align*} 0 & = \nabla f(x^k) - \bar M^T (\bar M \bar M^T)^{-1} \bar M \nabla f(x^k) \\ & = \nabla f(x^k) + \bar M^T \beta \\ \beta & = -(\bar M \bar M^T)^{-1} \bar M \nabla f(x^k) \end{align*}$$

    考虑到

    $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + u_0 \alpha_0 + \bar M^T \bar w \end{align*}$$

    • $\alpha_0$：$M$中$u_0$对应行

    则有

    $$u_0 \alpha_0 + \bar M^T (\bar w - \beta) = 0$$

    与$M$行满秩条件矛盾，故$\bar s^k \neq 0$

  • 证明$\bar s^k$为下降方向

    $$\begin{align*} \nabla f(x^k)^T \bar s^k & = -\nabla f(x^k) P_{\bar M} \nabla f(x^k) \\ & = -\nabla f(x^k) P_{\bar M}^T P_{\bar M} \nabla f(x^k) \\ & = -\|P_{\bar M} \nabla f(x^k)\|_2^2 \leq 0 \end{align*}$$

  • 证明$\bar s^k$方向可行（满足约束）

    • 由$P{\bar M}$定义：$\bar M P{\bar M} = 0$，则

      $$\begin{align*} \bar M \bar s^k & = -\bar M \bar P_{\bar M} \nabla f(x^k) \\ & = \begin{bmatrix} \bar A_{1,1} \\ A_2 \end{bmatrix} \bar s^k = 0 \end{align*}$$

    • 则只需证明$\alpha_0^T \bar s^k < 0$

      $$\begin{align*} 0 & = \nabla f(x^k) + M^T w \\ & = \nabla f(x^k) + u_0 \alpha_0 + \bar M^T \bar w \\ \Rightarrow & = \nabla f(x^k)^T \bar s^k + u_0 \alpha_0^T \bar s^k + \bar w^T \bar M \bar s^k \\ & = \nabla f(x^k)^T \bar s^k + u_0 \alpha_0^T \bar s^k \end{align*}$$

      考虑到$u_0 < 0$，则$\alpha_0^T \bar s^k < 0$

  • 即此时有紧约束变为松约束

算法

• 初始化：初始点$x^0$、$k=0$、精度参数$\epsilon > 0$

• 构造$M = [A_{1,1}^T, A_2^T]^T$

  • 若$M=0$（在可行域内），令$s^k = -\nabla f(x^k)$为 迭代方向
  • 否则令$s^k = -P_M \nabla f(x^k)$为迭代方向

• 若$|s^k|_2^2 \geq \epsilon$

  • 若$M$为空（无可下降方向），停止
  • 若$M$非空、$u > 0$，停止
  • 否则，构建$M = \bar M$继续

• 若$|s^k|_2^2 > \epsilon$，确定步长$\lambda_k$

  • 显然只需保证$A_2 x_k + \lambda_k A_2 d_k \leq b_2$ 即可

  • 若$A_2 d_k < 0$，则$\lambda_k$无约束，否则

    $$\lambda_k = \max \{\frac {(b_2 - A_2 x_k)_i} {(A_2 d_k)_i}\}$$

  • 即单纯型法中确定步长方法

• 得到新迭代点$x^{k+1} = x^k + \lambda_k s^k$、$k=k+1$

约束问题局部解

$$\begin{array}{l} \min & f(x), x \in R^n \\ s.t. & c_i(x) = 0, i \in E = \{1,2,\cdots,l\}, \\ & c_i(x) \leq 0, i \in I = \{l,l+1,\cdots,l+m\} \end{array}$$

• 对于一般约束优化问题，记其可行域为

  $$D = \{x| c_i(x) = 0, i \in E, c_i(x) \leq 0, i \in I\}$$

• 若 $\forall x^{} \in D, \exists \epsilon$，使得当 $x \in D, |x - x^{}| \leq \epsilon$ 时，总有

  $$f(x) \geq f(x^{*})$$

  则称$x^{*}$为约束问题的局部解，简称为最优解

• 若 $x \in D, 0 < |x - x^{*}| \leq \epsilon$ 时，总有

  $$f(x) > f(x^{*})$$

  则称$x^{*}$是约束问题的严格局部最优解

约束问题局部解一阶必要条件

定理1

• 设 $a_1,a_2,\cdots,a_m$ 和 $w \in R^n$，$C$ 定义如下 $$

    C = \{v |\sum_{i=1}^m \lambda_i a_i, \lambda_i \geq 0,
    i=1,2,\cdots,m \}
  

  $$若 $w \notin C$，则存在超平面 $d^T w = 0$，分离 $C$ 和 $w$，即$$ \begin{align*}

    d^T w & \leq 0 \\
    d^T w & > 0
  

  \end{align*}$$

• 显然C是闭凸集，则$\exists d \in R^n, d \neq 0$， $\alpha \in R$，使得

  $$\begin{array}{l} d^T x \leq \alpha, & \forall x \in C \\ d^T w > \alpha & \end{array}$$

• 又C是锥，有$0 \in C$，所以$\alpha \geq 0$，即$d^T w > 0$

• 若$\exists \bar x \in C, d^T \bar x > 0$，则 $\forall \lambda \geq 0, \lambda \bar x \in C$，则有

  $$\lambda d^T \bar x \leq \alpha$$

  而$\lambda \rightarrow \infty$，左端趋于无穷，矛盾

Farkas引理

• 设$a_1,a_2,\cdots,a_m$和$w \in R^n$，则以下两个系统有且 仅有一个有解

  • 系统I：存在$d$满足 $$\begin{align*} a_i^T d & \leq 0, & i=1,2,\cdots,m \\ w^T d & > 0 \end{align*}$$
  • 系统II：存在非负常数$\lambda_1,\cdots,\lambda_m$使得 $$w =\sum_{i=1}^m \lambda_i a_i$$

• 若系统II有解，则系统I无解

  • 若系统II有解，即存在$\lambda_1,…,\lambda_m$且 $\lambda_i \geq 0,i=1,2,\cdot,m$，使得

    $$w = \sum_{i=1}^m \lambda_i a_i$$

  • 若系统I有解，则有

    $$0 < w^T d = \sum_{i=1}^m \lambda_i a_i^T d \leq 0$$

    矛盾，因此系统I无解

• 若系统II无解，则系统I有解

  • 系统II误解，构造闭凸锥

    $$C = \{v |\sum_{i=1}^m \lambda_i a_i, \lambda_i \geq 0, i=1,2,\cdots,m \}$$

    显然$w \notin C$

  • 由定理1，存在d满足

    $$\begin{array}{l} d^T x \leq 0, & \forall x \in C, \\ d^T w & > 0 \end{array}$$

• 此定理就是点要么在凸锥C内、边缘（系统II），要么在凸锥 外（系统I）

推论1

• 设$a_1,a_2,\cdots,a_m$和$w \in R^n$，则以下系统有且仅有 一个有解

  • 系统I：存在d满足 $$\begin{array}{l} a_i^T d \leq 0, & i=1,2,\cdots,m \\ d_j \geq 0, & j=1,2,\cdots,n \\ w^T d > 0 & \end{array}$$
  • 系统II：存在非负常数$\lambda_1,…,\lambda_m$使得 $$w \leq \sum_{i=1}^m \lambda_i a_i$$

• 若系统II有解，则系统I无解

  • 若系统I有解，取d带入矛盾

• 若系统II无解，则系统I有解

  • 若系统I无解

    todo

推论2

• 设$a1,a_2,\cdots,a{l+m}$和$w \in R^n$，则以下两个系统 有且进一有一个存在解

  • 存在d满足 $$\begin{array}{l} a_i^T d = 0, & i=1,2,\cdots,l \\ a_i^T d \leq 0, & i=l+1,l+2,\cdots,l+m \\ w^T d > 0 \end{array}$$
  • 存在常数$\lambda1,\lambda_2,\cdots,\lambda{l+m}$ 且$\lambda_i \geq 0, i=l+1, l+2, \cdots, l+m$使得 $$w = \sum_{i+1}^{l+m} \lambda_i a_i$$

迭代求解

参数部分更新

参数部分更新：每次更新一个或一组待估参数

• 应用场合

  • 适合待估参数较少、同时估计较慢，待估参数较多可能更新 速度慢，往往需要多次迭代更新参数
  • 一般用在机器学习算法中比较多

• 特点（某些算法）

  • 良好的并行特性：能够同时更新多个参数

    • Alternating Direction Method of Multipliers

  • 采用贪心策略的算法：可能无法得到最优解

    • 前向回归
    • 深度学习：网络层次太深，有些算法采用固化部分 网络结构，估计剩余部分

  • 能够平衡全局、局部：得到较好的解

    • LARS

Norm

$\mathcal{L_p}$ 范数

• $\mathcal{L_p}$ 范数

  $$\|x\|_p = (|x_1|^p + |x_2|^p + \cdots + |x_N|^p)^{1/p}$$

  • $x \in R^n$

• $\mathcal{L_p}$ Dual Norm 对偶范数

  $$\|x\|^{*} = \mathop \sup_{z}{x^Tz|\|z\| \leq 1}$$

  • $x \in R^N$
  • $|x|$：$x$的某个范数