CS205A Lecture 10 Systems of equations; optimization in one variable

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

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

多变量问题

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

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

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

牛顿法

首先定义雅克比矩阵:

由泰勒展开,我们可以得到如下近似:

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

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

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

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

那么

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

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

拟牛顿法和Broyen

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

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

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

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

为了求解该问题,假设

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

构造拉格朗日乘子:

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

所以

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

因此

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

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

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

回顾Sherman-Morrison Formula

所以我们有

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

Chapter 8 无条件优化

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

无条件优化:动机

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

例1(非线性最小二乘)

考虑

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

最优性

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

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

定义8.1 (全局最小值)

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

定义8.2 (局部最小值)

可微的情形

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

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

如果

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

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

为了叙述算法,我们给出如下定义:

定义8.3 (驻点)

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

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

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

利用泰勒展开可得

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

因此有如下结论:

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

通过函数性质求解最优值

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

定义8.4 (凸)

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

命题 8.1

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

令$\alpha \to 0$可得

这就与假设矛盾。

与之对应的是拟凸性

定义8.4 (拟凸性)

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

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

本文标题:CS205A Lecture 10 Systems of equations; optimization in one variable

文章作者:Doraemonzzz

发布时间:2019年04月07日 - 13:42:00

最后更新:2019年04月23日 - 00:39:02

原始链接:http://doraemonzzz.com/2019/04/07/CS205A Lecture 10 Systems of equations; optimization in one variable/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。