回顾我们在梯度下降法中介绍的通用迭代框架：

x⃗t+1=x⃗t+ηv⃗t,t=0,1,⋯\vec{x}_{t+1}=\vec{x}_t+\eta\vec{v}_t,\quad t=0,1,\cdots

这一讲我们会在这一框架的基础上介绍一些进阶优化问题算法。

坐标下降法（Coordinate Descent）

首先我们介绍与梯度下降比较类似的迭代方法：坐标下降法，其特别适用于多元函数。其迭代推导如下：

  • 考虑下述凸优化问题 p∗=min⁡x⃗∈Rnf(x⃗),x⃗=[x1x2⋮xn]p^*=\min_{\vec{x}\in\R^n}f(\vec{x}),\quad \vec{x}=\begin{bmatrix}x_1\\x_2\\\vdots\\x_n\end{bmatrix} 记x⃗i:j=(xi,xi+1,⋯ ,xj−1,xj)∈Rj−i+1\vec{x}_{i:j}=(x_i,x_{i+1},\cdots,x_{j-1},x_{j})\in\R^{j-i+1}，迭代初始值为x⃗(0)\vec{x}^{(0)}，那么在第t+1t+1轮迭代中（t≥0t\geq 0），x⃗(t)\vec{x}^{(t)}的各个分量会按顺序进行最小化迭代。即： x1(t+1)∈arg min⁡x1∈Rf(x1,x⃗2:n(t))x2(t+1)∈arg min⁡x2∈Rf(x1(t+1),x2,x⃗3:n(t))⋮xn(t+1)∈arg min⁡xn∈Rf(x⃗1:n−1(t+1),xn).\begin{aligned} x_1^{(t+1)} &\in \argmin_{x_1 \in \mathbb{R}} f(x_1, \vec{x}_{2:n}^{(t)}) \\ x_2^{(t+1)} &\in \argmin_{x_2 \in \mathbb{R}} f(x_1^{(t+1)}, x_2, \vec{x}_{3:n}^{(t)}) \\ &\vdots \\ x_n^{(t+1)} &\in \argmin_{x_n \in \mathbb{R}} f(\vec{x}_{1:n-1}^{(t+1)}, x_n). \end{aligned} 由此可知坐标下降法中后续分量的最小化依赖之前分量的最优值。这样我们就将多元函数的优化问题转换为一系列单变量函数优化问题。（当然，上述分量的优化顺序也可以随机）

    btw，这种坐标维度序列迭代的思想让我想到吉布斯抽样hh

  • 下面探讨坐标下降法的适定性与收敛性。对于适定性，只要上述迭代中arg min⁡\argmin值可以计算出（良定义），那么这个算法就是可行的（也称对应的优化问题是适定的）。而对于收敛性，这种类似贪心的算法实际上并不保证一定收敛到全局最优解，然而如果对目标函数加以一定的假设，那么坐标下降法的收敛性还是可以保证的。具体讨论如下：
    • 事实上，根据无约束凸优化问题的一阶最优化条件，若x⃗∗\vec{x}^*为f(x⃗)f(\vec{x})在e⃗i\vec{e}_i（即第ii个分量方向）上的一个最优解，那么其满足 ∂f∂xi(x⃗∗)=0\frac{\partial f}{\partial x_i}(\vec{x}^*)=0 而如果上式对任意ii均成立，那么就有∇f(x⃗∗)=0⃗\nabla f(\vec{x}^*)=\vec{0}，于是x⃗∗\vec{x}^*即为ff的一个全局最小值点。由此我们便能得到如下定理：
    • 设函数f:Rn→Rf:\R^n\to\R为可微凸函数，且在每个分量上都严格凸（即对于任意ii，xi→f(x⃗1:i−1,xi,x⃗i+1,n)x_i\to f(\vec{x}_{1:i-1},x_i,\vec{x}_{i+1,n})在x⃗1:i−1\vec{x}_{1:i-1}与x⃗i+1,n\vec{x}_{i+1,n}固定时均为严格凸函数），那么只要优化问题有解，且坐标下降法可行，就可以通过坐标下降法迭代收敛到最优解。
    • 对于不可微凸函数，使用坐标下降法一般无法保证收敛。但是，如果函数可表示为如下形式： f(x⃗)=g(x⃗)+∑i=1nhi(xi)f(\vec{x})=g(\vec{x})+\sum_{i=1}^nh_i(x_i) 其中g(x⃗)g(\vec{x})为可微凸函数，而每个hih_i也为凸函数（不一定可微）【即函数的不可微部分可以独立拆分到每个分量】，那么其通过坐标下降法也能收敛到最优解。
      • 实际上，当hih_i为绝对值函数∣xi∣|x_i|时，对应的就是LASSO回归问题。具体而言，对于下述LASSO回归问题： f(x⃗)=12∥Ax⃗−y⃗∥22+λ∥x∥1f(\vec{x})=\frac{1}{2}\|A\vec{x}-\vec{y}\|_2^2+\lambda\|x\|_1 其坐标下降法的迭代式如下（推导留给读者）： ri=a⃗i⊤(y⃗−A1:i−1x⃗1:i−1(t+1)−Ai+1:nx⃗i+1:n(t))ri>λ  ⟹  xi(t+1)=ri−λ∥a⃗i∥22,ri<−λ  ⟹  xi(t+1)=ri+λ∥a⃗i∥22,∣ri∣≤λ  ⟹  xi(t+1)=0.\begin{aligned} r_i& = \vec{a}_i^\top \left( \vec{y} - A_{1:i-1} \vec{x}_{1:i-1}^{(t+1)} - A_{i+1:n} \vec{x}_{i+1:n}^{(t)} \right)\\ r_i > \lambda &\implies x_i^{(t+1)} = \frac{r_i - \lambda}{\|\vec{a}_i\|_2^2}, \\ r_i < -\lambda &\implies x_i^{(t+1)} = \frac{r_i + \lambda}{\|\vec{a}_i\|_2^2}, \\ |r_i| \leq \lambda &\implies x_i^{(t+1)} = 0. \end{aligned} 其中Ai:jA_{i:j}表示AA的第ii列到第jj列组成的矩阵。

牛顿法（Newton’s Method）

在梯度下降法中，我们假定目标函数一阶可微，并利用了函数的梯度。而牛顿法则进一步假设目标函数二阶可微，从而利用Hessian矩阵作为迭代搜索方向。其迭代推导如下：

  • 设ff为二阶可微严格凸函数，在x⃗(t)\vec{x}^{(t)}处的Hessian矩阵为正定矩阵。那么我们可以写出函数在x⃗(t)\vec{x}^{(t)}处的二阶泰勒近似： f^2(x⃗;x⃗(t))=f(x⃗(t))+[∇f(x⃗(t))]⊤(x⃗−x⃗(t))+12(x⃗−x⃗(t))⊤[∇2f(x⃗(t))](x⃗−x⃗(t)).\hat{f}_2(\vec{x}; \vec{x}^{(t)}) = f(\vec{x}^{(t)}) + [\nabla f(\vec{x}^{(t)})]^\top (\vec{x} - \vec{x}^{(t)}) + \frac{1}{2} (\vec{x} - \vec{x}^{(t)})^\top [\nabla^2 f(\vec{x}^{(t)})] (\vec{x} - \vec{x}^{(t)}). 然后我们就能得到一个凸二次规划问题 min⁡x⃗∈Rnf^2(x⃗;x⃗(t))\min_{\vec{x}\in\R^n}\hat{f}_2(\vec{x}; \vec{x}^{(t)}) 对此，我们直接使用梯度零点求解： ∇f^2(x⃗∗;x⃗(t))=∇f(x⃗(t))+[∇2f(x⃗(t))](x⃗∗−x⃗(t))=0⃗⟹x⃗∗=x⃗(t)−[∇2f(x⃗(t))]−1[∇f(x⃗(t))].\begin{aligned} \nabla \hat{f}_2(\vec{x}^*; \vec{x}^{(t)}) &= \nabla f(\vec{x}^{(t)}) + [\nabla^2 f(\vec{x}^{(t)})](\vec{x}^* - \vec{x}^{(t)})=\vec{0} \\ &\Longrightarrow \vec{x}^* = \vec{x}^{(t)} - [\nabla^2 f(\vec{x}^{(t)})]^{-1}[\nabla f(\vec{x}^{(t)})]. \end{aligned} 于是得到牛顿法的迭代公式： x⃗(t+1)=x⃗(t)−[∇2f(x⃗(t))]−1[∇f(x⃗(t))]\vec{x}^{(t+1)} = \vec{x}^{(t)} - [\nabla^2 f(\vec{x}^{(t)})]^{-1}[\nabla f(\vec{x}^{(t)})] 我们称[∇2f(x⃗(t))]−1[∇f(x⃗(t))][\nabla^2 f(\vec{x}^{(t)})]^{-1}[\nabla f(\vec{x}^{(t)})]为牛顿方向向量。
  • 当然，上述迭代公式对应的只是最基础的牛顿法，在实际运用中，为保证收敛，我们参考梯度下降法引入步长η>0\eta>0，此时迭代公式变为 x⃗(t+1)=x⃗(t)−η[∇2f(x⃗(t))]−1[∇f(x⃗(t))]\vec{x}^{(t+1)} = \vec{x}^{(t)} - \eta[\nabla^2 f(\vec{x}^{(t)})]^{-1}[\nabla f(\vec{x}^{(t)})] 这也被称作阻尼牛顿法。实验证明阻尼牛顿法的迭代相比梯度下降法要快很多，当然代价是Hessian的计算相比梯度更加复杂。

    关于阻尼牛顿法的收敛性证明不作详细展开，请自行查阅。【事实上，关于牛顿法收敛性的研究到现在仍然是一个前沿课题】

  • 上述讨论中都假设Hessian矩阵为正定矩阵。事实上，如果不对Hessian矩阵加以约束，同样也可以使用一种类似牛顿法的方法（被称为拟牛顿法，quasi-Newton’s methods）处理，这里不详细展开。

解决线性约束优化问题

牛顿法除了可以解决无约束二阶可微凸优化问题之外，还可以处理带线性约束的同类优化问题，即

p∗=min⁡x⃗∈Rnf(x⃗)s.t. Ax⃗=y⃗.\begin{aligned} p^* = \min_{\vec{x} \in \mathbb{R}^n}\quad &f(\vec{x}) \\ \text{s.t. } \quad& A\vec{x} = \vec{y}. \end{aligned}

由于可行域为凸集，我们可以套用上述二阶泰勒近似，将这一问题转化为带凸约束的凸二次规划问题：

p∗=min⁡x⃗∈Rnf^2(x⃗;x⃗(t))s.t. Ax⃗=y⃗.\begin{aligned} p^* =\min_{\vec{x}\in\R^n}\quad &\hat{f}_2(\vec{x}; \vec{x}^{(t)})\\ \text{s.t. } \quad& A\vec{x} = \vec{y}. \end{aligned}

注意到这个问题具有强对偶性（满足Slater条件），因此可以使用KKT条件求解。具体而言，写出其拉格朗日函数

L(x⃗,v⃗)=f(x⃗(t))+[∇f(x⃗(t))]⊤(x⃗−x⃗(t))+12(x⃗−x⃗(t))⊤[∇2f(x⃗(t))](x⃗−x⃗(t))+v⃗⊤(Ax⃗−b⃗).L(\vec{x}, \vec{v}) = f(\vec{x}^{(t)}) + [\nabla f(\vec{x}^{(t)})]^\top (\vec{x} - \vec{x}^{(t)}) + \frac{1}{2} (\vec{x} - \vec{x}^{(t)})^\top [\nabla^2 f(\vec{x}^{(t)})] (\vec{x} - \vec{x}^{(t)}) + \vec{v}^\top (A\vec{x} - \vec{b}).

那么KKT条件可表示为：

Ax⃗∗=y⃗0⃗=∇x⃗L(x⃗∗,ν⃗∗)=∇f(x⃗(t))+[∇2f(x⃗(t))](x⃗∗−x⃗(t))+A⊤ν⃗.\begin{aligned} A\vec{x}^*&=\vec{y}\\ \vec{0} &= \nabla_{\vec{x}} L(\vec{x}^*, \vec{\nu}^*)= \nabla f(\vec{x}^{(t)}) + [\nabla^2 f(\vec{x}^{(t)})](\vec{x}^* - \vec{x}^{(t)}) + A^\top \vec{\nu}. \end{aligned}

如果记v⃗(t)≔x⃗∗−x⃗(t)\vec{v}^{(t)}\coloneqq\vec{x}^* - \vec{x}^{(t)}，那么有Av⃗(t)=0⃗A\vec{v}^{(t)}=\vec{0}。于是KKT条件可改写为

Av⃗(t)=0⃗∇f(x⃗(t))+[∇2f(x⃗(t))]v⃗(t)+A⊤ν⃗=0⃗.\begin{aligned} A\vec{v}^{(t)}&=\vec{0}\\ \nabla f(\vec{x}^{(t)}) + [\nabla^2 f(\vec{x}^{(t)})]\vec{v}^{(t)} + A^\top \vec{\nu}&=\vec{0}. \end{aligned}

用矩阵表示即为：

[∇2f(x⃗(t))A⊤A0][v⃗(t)v⃗]=[−∇f(x⃗(t))0].\begin{bmatrix} \nabla^2 f(\vec{x}^{(t)}) & A^\top \\ A & 0 \end{bmatrix} \begin{bmatrix} \vec{v}^{(t)} \\ \vec{v} \end{bmatrix} = \begin{bmatrix} -\nabla f(\vec{x}^{(t)}) \\ 0 \end{bmatrix}.

在求出这个方程组的解v⃗(t)\vec{v}^{(t)}后，就得到牛顿法迭代式：

x⃗(t+1)=x⃗(t)+v⃗(t).\vec{x}^{(t+1)}=\vec{x}^{(t)}+\vec{v}^{(t)}.

当然也可以写出阻尼牛顿迭代式版本，此处作略。

内点法（Interior Point Method）

内点法建立在牛顿法的基础之上，可以用来解决带不等式约束的优化问题：

P:p∗=min⁡x⃗∈Rnf0(x⃗)s.t.fi(x⃗)≤0,i=1,2,⋯ ,mAx⃗=y⃗.\begin{aligned} \mathcal{P}:\quad p^* = \min_{\vec{x} \in \mathbb{R}^n} \quad & f_0(\vec{x}) \\ \text{s.t.} \quad & f_i(\vec{x}) \leq 0, \quad i = 1, 2, \cdots, m \\ & A\vec{x} = \vec{y}. \end{aligned}

其中f0,f1,⋯ ,fmf_0,f_1,\cdots,f_m均为二阶可微凸函数。

  • 在介绍内点法的原理之前，首先引入屏障函数（barrier functions）。我们的目标是消除不等式约束，一种直接的策略是用示性函数将不等式约束融入目标函数中（就像对偶问题的做法一样）： p∗=min⁡x⃗∈Rn  f0(x⃗)+∑i=1mI(fi(x⃗))Ax⃗=b⃗.\begin{aligned} p^* &= \min_{\vec{x} \in \mathbb{R}^n} \; f_0(\vec{x}) + \sum_{i=1}^m I(f_i(\vec{x})) \\ &\quad A\vec{x} = \vec{b}. \end{aligned} 其中 I(z)=1{z≤0}={0,if z≤0+∞,if z>0I(z) = \mathbf{1}_{\{z \leq 0\}} = \begin{cases} 0, & \text{if } z \leq 0 \\ +\infty, & \text{if } z > 0 \end{cases} 当然，这破坏了目标函数的可微性，于是我们使用屏障函数ϕ\phi近似表示示性函数。屏障函数需要是凸递增函数，且有lim⁡z→∞ϕ(z)=+∞\displaystyle\lim_{z\to\infty}\phi(z)=+\infty。满足这种条件的屏障函数不少，其中最常用的是对数屏障函数，形式如下： ϕα(z)=−1αlog⁡(−z)\phi_\alpha(z)=-\frac{1}{\alpha}\log(-z) 其中α>0\alpha>0控制了函数的近似准确度，当α\alpha越大，对指示函数的近似准确度就越高。这样我们就将原始问题P\mathcal{P}转化如下： P^(α):p^α∗=min⁡x⃗∈Rnf0(x⃗)+∑i=1mϕα(fi(x⃗))s.t.Ax⃗=y⃗.\begin{aligned} \widehat{\mathcal{P}}(\alpha): \quad \widehat{p}_{\alpha}^* = \min_{\vec{x} \in \mathbb{R}^n} \quad & f_0(\vec{x}) + \sum_{i=1}^m \phi_\alpha(f_i(\vec{x})) \\ \text{s.t.} \quad & A\vec{x} = \vec{y}. \end{aligned} 这样目标函数就二阶可微，从而可以用牛顿法求解。
  • 实际上，上述问题P^(α)\widehat{\mathcal{P}}(\alpha)得到解的只是P\mathcal{P}的近似解，二者的接近程度由参数α\alpha决定。可以证明，当α\alpha取值较大时能得到一个较好的近似解。
    • 那么，为什么不直接取一个接近无穷的α\alpha值呢？这是因为，当α\alpha较大时，会使可行域边界处的Hessian矩阵变化变快，从而不容易收敛到最优解。
    • 一种解决方案是使用屏障法：即开始时使用较小α\alpha值得到近似解，然后再调大α\alpha值（一般乘上一个因子μ>1\mu>1），以这个解为迭代初始点进一步迭代。由于牛顿法在接近最优解时收敛速度极快，因此这一流程极大地改善了牛顿法的收敛性。【其实这也属于算法改进的一种通用范式：又粗到细的网格搜索】

      注：屏障法需要初始解严格可行，这样才能保证得到的近似解有限，后续偏导数才能顺利计算。

OK，到这里CS127笔记就基本梳理完了。原来讲义最后还有两个最优化的应用，其中一个就是著名的支持向量机（可见机器学习方法），但笔者经过考虑后还是决定略去，留给未来的自己思考吧~

整体回顾下来感觉课程内容还是比较干练的，基本将最核心的优化理论都讲了一下，不过还是略去了一些比较深入的概念知识（当然我觉得这样也挺好，至少完整刷下来没有太多不懂的地方ww）。

下学期笔者在学校里还是会上《最优化理论》课程（这也是为什么我急着要在开学前将这个系列完结），大概还是会以Cheat Sheet的形式呈现，这个系列正好作为对照，完美！