CS205A Lecture 10 Systems of equations; optimization in one variable

课程主页：https://graphics.stanford.edu/courses/cs205a-13-fall/schedule.html

这次回顾第十讲，这一讲介绍了多变量的非线性系统以及无条件优化问题。

多变量问题

这里将讨论多变量函数的求根问题，即

$$\begin{aligned} 给定：&f:\mathbb R^n \to \mathbb R^m\\ 找到：&\vec x' 使得f(\vec x' )=\vec 0 \end{aligned}$$

一般来说，我们假设$n\ge m$。

对于该问题，一个简单的想法是将单变量的情形推广，显然二分法很难推广（因为要对$n$个维度使用二分法），而牛顿法则可以推广：

牛顿法

首先定义雅克比矩阵：

$$Df \in \mathbb R^{m\times n}, (Df)_{ij}=\frac{\partial f_i}{\partial x_j}$$

由泰勒展开，我们可以得到如下近似：

$$f(\vec x )\approx f(\vec x_k)+Df(\vec x_k). (\vec x-\vec x_k)$$

令$f(\vec x)=\vec 0$，我们得到

$$Df(\vec x_k).(\vec x-\vec x_k) = -f(\vec x_k)$$

注意$m\le n$，所以上述方程可以求解，特别的，如果$m=n$，并且$Df(\vec x_k)​$可逆，那么

$$\vec x =\vec x_k -[Df(\vec x_k)]^{-1} f(\vec x_k)$$

利用该式即可得到牛顿法：

$$\vec x_{k+1} =\vec x_k -[Df(\vec x_k)]^{-1} f(\vec x_k)$$

注意，我们不需要显式的计算出$[Df(\vec x_k)]^{-1} $，具体的，令

$$[Df(\vec x_k)]^{-1} f(\vec x_k) =\vec y_k$$

那么

$$[Df(\vec x_k)]\vec y_k=f(\vec x_k)$$

所以可以利用高斯消元法求出$\vec y_k$。

那么该算法何时收敛呢？这里的条件是雅克比矩阵特征值的最大模小于$1​$，在该条件下，可以说明收敛速度为二次。（证明略）

拟牛顿法和Broyen

注意到雅克比矩阵$Df(\vec x_k)$每次迭代都会变化，所以无法使用$LU$分解加速求解

$$[Df(\vec x_k)]\vec y_k=f(\vec x_k)$$

因此计算量较大。为了缓解这个问题，回顾方向导数的定义：

$$D_{\vec v} f =Df.\vec v$$

我们利用折线法以及上述定义，可以认为雅克比矩阵近似满足如下条件：

$$J.(\vec x_k-\vec x_{k-1})\approx f(\vec x_k) -f(\vec x_{k-1})$$

Broyden’s method就是利用该想法设计而成的算法，该算法迭代计算每一步的$J_k$，具体的，我们求解如下问题：

$$\begin{aligned} \min_{J_k}&\ \Arrowvert J_k-J_{k-1} \Arrowvert^2_{\text{Fro}}\\ \text{such that}&\ J_k.(\vec x_k-\vec x_{k-1})= f(\vec x_k) -f(\vec x_{k-1}) \end{aligned}$$

为了求解该问题，假设

$$\begin{aligned} \Delta J&= J_k -J_{k-1}\\ \Delta \vec x&= \vec x_k -\vec x_{k-1}\\ \vec d &= f(\vec x_k) -f(\vec x_{k-1}) -J_{k-1}\Delta \vec x \end{aligned}$$

那么原问题可以化为如下形式：

$$\begin{aligned} \min_{\Delta J}&\ \Arrowvert \Delta J\Arrowvert^2_{\text{Fro}}\\ \text{such that}&\ \Delta J.\Delta \vec x =\vec d \end{aligned}$$

构造拉格朗日乘子：

$$\Lambda =\Arrowvert \Delta J\Arrowvert^2_{\text{Fro}} + \vec \lambda^T(\Delta J.\Delta \vec x -\vec d)$$

关于$(\Delta J)_{ij}​$求偏导并令其为$0​$得到

$$0 =\frac{\partial \Lambda}{(\Delta J)_{ij}} =2(\Delta J)_{ij} +\lambda_i (\Delta \vec x)_j$$

所以

$$\Delta J =-\frac 1 2 \vec \lambda (\Delta \vec x)^T$$

带回$\Delta J.\Delta \vec x =\vec d​$可得

$$\vec \lambda(\Delta \vec x)^T (\Delta \vec x)=-2\vec d \Rightarrow \vec \lambda =-\frac{2\vec d}{\Arrowvert \Delta \vec x\Arrowvert^2}$$

因此

$$\Delta J=-\frac 1 2 \vec \lambda (\Delta \vec x)^T=\frac{\vec d(\Delta \vec x)^T}{\Arrowvert \Delta \vec x\Arrowvert^2}$$

回顾各项的定义，我们得到

$$\begin{aligned} J_k &=J_{k-1}+\Delta J\\ &=J_{k-1} +\frac{\vec d(\Delta \vec x)^T}{\Arrowvert \Delta \vec x\Arrowvert^2}\\ &=J_{k-1}+\frac{(f(\vec x_k) -f(\vec x_{k-1}) -J_{k-1}\Delta \vec x)} {\Arrowvert \vec x_k -\vec x_{k-1}\Arrowvert^2} (x_k -\vec x_{k-1})^T \end{aligned}$$

一般来说，我们初始化$J_0=I$，但是该方法还有一个问题，任然要计算

$$J_k^{-1}$$

所以另一个方法是直接迭代计算$J_k^{-1}$，注意我们我们的迭代形式为：

$$J_k=J_{k-1}+\vec u_k \vec v_k^T$$

回顾Sherman-Morrison Formula：

$$(A+\vec u \vec v^T)^{-1}= A^{-1} -\frac{A^{-1}\vec u\vec v^T A^{-1}}{1+\vec v^T A^{-1}\vec u}$$

所以我们有

$$\begin{aligned} J_k^{-1} &=J_{k-1}^{-1} - \frac{J_{k-1}^{-1}\vec u_k \vec v_k^TJ_{k-1}^{-1}} {1+\vec v_k^T J_{k-1}^{-1}\vec u_k} \end{aligned}$$

因此可以利用上式直接计算$J_{k}$，这里依然假设$J_0=I$。

Chapter 8 无条件优化

我们之前介绍过很多优化问题，大部分都是条件优化，并且可以求出其解析解，从这一部分开始将讨论无条件优化，绝大多数情形下最优解都无法写成解析形式。

无条件优化：动机

我们先看下讨论无条件优化问题的动机，来看如下一个例子：

例1（非线性最小二乘）

考虑

$$E(a,c)=\sum_i (y_i-ce^{ax_i})^2$$

我们要最小化上式，注意该问题的解无法显式的求出。

最优性

这部分给出一些定义，这里假设函数为

$$f:\mathbb R^n \to \mathbb R$$

注意到最大化$f$等价于最小化$-f$，所以这里只讨论求解最小值的问题。首先给出全局最小值的定义：

定义8.1 (全局最小值)

$$如果对所有\vec x\in \mathbb R^n，我们有f(\vec x')\le f(\vec x),\\ 那么称\vec x'\in \mathbb R^n是f的全局最小值$$

求解全局最小值往往是很困难的，在绝大多数情况下，我们求解的都是局部最小值：

定义8.2 (局部最小值)

$$如果存在\epsilon>0,使得当\vec x\in \mathbb R^n满足 \Arrowvert \vec x-\vec x'\Arrowvert<\epsilon\\ 我们有f(\vec x')\le f(\vec x), 那么称\vec x'\in \mathbb R^n是f的局部最小值$$

可微的情形

如果$f$可微，由泰勒展开可得

$$f(\vec x )\approx f(\vec x_0)+\nabla f(\vec x_0). (\vec x-\vec x_0)$$

如果取$\vec x-\vec x_0 =\alpha \nabla f(\vec x_0)​$，那么

$$f(\vec x_0+\alpha \nabla f(\vec x_0) )\approx f(\vec x_0)+\alpha \Arrowvert \nabla f(\vec x_0)\Arrowvert^2$$

如果

$$\Arrowvert \nabla f(\vec x_0)\Arrowvert>0$$

那么$\alpha$的符号控制了$f$在$\vec x_0$附加是递增还是递减，这还说明如果$\vec x_0$是局部最小值，那么必然有

$$\nabla f(\vec x_0)=\vec 0$$

注意到这只是必要条件，并不是充分条件，这是因为最大值点和马鞍点都满足上述条件，来看几个例子：

为了叙述算法，我们给出如下定义：

定义8.3 (驻点)

$$满足\nabla f(\vec x)=\vec 0的\vec x \in \mathbb R^n是f的驻点$$

所以一个简单的算法如下：

1. 找到$ f$的驻点$\vec x_i$
2. 判断其为最小值点，最大值点还是马鞍点。

如果$f$二次可微，利用Hessian矩阵可以进行第二步

$$H_{f}(\vec{x})=\left( \begin{array}{cccc} {\frac{\partial^{2} f}{\partial^{2} x_{1}}} & {\frac{\partial^{2} f}{\partial x_{1} \partial x_{2}}} & {\cdots} & {\frac{\partial^{2} f}{\partial x_{1} \partial x_{n}}} \\ {\frac{\partial^{2} f}{\partial x_{2} \partial x_{1}}} & {\frac{\partial^{2} f}{\partial^{2} x_{2}}} & {\cdots} & {\frac{\partial^{2} f}{\partial x_{2} \partial x_{n}}} \\ {\vdots} & {\cdots} & {\vdots} \\ {\frac{\partial^{2} f}{\partial x_{n} \partial x_{1}}} & {\frac{\partial^{2} f}{\partial x_{n} \partial x_{2}}} & {\cdots} & {\frac{\partial^{2} f}{\partial^{2} x_{n}}} \end{array}\right)$$

利用泰勒展开可得

$$f(\vec x )\approx f(\vec x_0)+\nabla f(\vec x_0).(\vec x-\vec x_0) +\frac 1 2(\vec x -\vec x_0)^T H_f(\vec x -\vec x_0)$$

那么在驻点$\vec x’$，我们有

$$f(\vec x )\approx f(\vec x') +\frac 1 2(\vec x -\vec x')^T H_f(\vec x -\vec x')$$

因此有如下结论：

• 如果$H_f$正定：那么$\vec x’$是$f$的局部最小值。
• 如果$H_f​$负定：那么$\vec x’​$是$f​$的局部最大值。
• 如果$H_f$不定：那么$\vec x’$是$f$的马鞍点。
• 如果$H_f$不可逆：那么会发生图8.3的情形。

通过函数性质求解最优值

在某种特殊情形下，函数的最小值很好求解，我们给出如下定义：

定义8.4 (凸)

$$函数f:\mathbb R^n \to \mathbb R是凸的，如果对\vec x,\vec y\in \mathbb R^n以及\alpha\in (0,1)，我们有\\ f((1-\alpha)\vec x+\alpha \vec y)\le (1-\alpha)f(\vec x)+\alpha f(\vec y)\\ 如果不等号是严格的，那么函数是严格凸的$$

关于凸函数有如下有用的性质：

命题 8.1

$$凸函数f:\mathbb R^n \to \mathbb R的局部最小值是全局最小值$$

证明：令$\vec x$是局部最小值，假设存在$\vec x’\neq \vec x$，使得$f(\vec x’)<f(\vec x)$。那么，对于$\alpha \in(0,1)$，我们有

$$\begin{aligned} f((1-\alpha)\vec x+\alpha\vec x') &=f(\vec x+\alpha(\vec x'-\vec x))\\ &\le (1-\alpha) f(\vec x)+\alpha f(\vec x')\\ &<(1-\alpha) f(\vec x)+\alpha f(\vec x')\\ &=f(\vec x') \end{aligned}$$

令$\alpha \to 0$可得

$$f(\vec x)\le f(\vec x')$$

这就与假设矛盾。

与之对应的是拟凸性：

定义8.4 (拟凸性)

$$函数f:\mathbb R^n \to \mathbb R是凸的，如果对\vec x,\vec y\in \mathbb R^n以及\alpha\in (0,1)，我们有\\ f((1-\alpha)\vec x+\alpha \vec y)\le \max(f(\vec x),f(\vec y))$$

对于拟凸函数，局部最小值依然是全局最小值，证明和命题8.2类似，我们依然有

$$\begin{aligned} f((1-\alpha)\vec x+\alpha\vec x') < f(\vec x') \end{aligned}$$

令$\alpha \to 0$即会产生矛盾。