CS205A Lecture 11 Optimization; Multiple variables, constraints

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

这次回顾第十一讲,这一讲介绍了BFGS和KKT条件。

黄金分割搜索

定义8.5 (Unimodular)

下面讨论如何求满足unimodular性质的函数$f$的最小值$x’​$,首先不难想象这种函数的图像是U字型的,所以可以使用类似二分法的思路求解。

假设我们有两个点$a<x_0<x_1<b​$,接下来分两种情形讨论:

  • 如果$f(x_0 )\ge f(x_1)$,那么对$x\in [a, x_0]$,我们有$f(x)\ge f(x_1)$,最小值点$x’ \in [x_0, b]$,所以删除区间$[a, x_0]$
  • 如果$f(x_1 )\ge f(x_0)$,那么对$x\in [x_1, b]$,我们有$f(x)\ge f(x_0)$,最小值点$x’\in [a,x_1]$,所以删除区间$[x_1, b]$

迭代上述算法即可求出最小值点。注意上述方法每一轮将区间需要计算两个函数值,如果计算$f$的成本很大,我们应该希望可以重复利用之前计算的结果,下面讨论如何实现这点。为了讨论方便,不妨假设$a=0, b=1​$,一般情形可以通过平移和伸缩化为该情形。假设第一轮选择的点为

如果第二轮的区间为

那么第二轮选择的点为

如果

那么可以少计算一次函数值,解该方程可得

所以$1-\alpha =\tau​$是黄金分割比例。

如果第二轮的区间为

那么第二轮选择

如果

那么可以少计算一次函数值,解该方程可得:

$1-\alpha =\tau$依旧是黄金分割比例。

将上述讨论总结,即得到如下算法:

  • 令$\tau =\frac 12 (\sqrt 5 -1)$,选择$a,b$使得$f$在$[a,b]$上unimodular

  • 选择初始划分

  • 初始化

  • 迭代直至$b-a$充分小:

    • 如果$f_0 \ge f_1​$,那么按如下方式删除区间$[a, x_0]​$:
      • 移动左端点:$a\leftarrow x_0$
      • 重复使用上一轮的值:$x_0 \leftarrow x_1, f_0 \leftarrow f_1$
      • 生成新的样本点:$x_1 \leftarrow a+\tau(b-a), f_1 \leftarrow f(x_1)$
    • 如果$f_1 >f_0$,那么按如下方式删除区间$[x_1, b]$:
      • 移动右端点:$b\leftarrow x_1$
      • 重复使用上一轮的值:$x_1 \leftarrow x_0 ,f_1 \leftarrow f_0$
      • 生成行的样本点:$x_0 \leftarrow a+(1-\tau)(b-a),f_0 \leftarrow f(x_0)$

多变量情形

这一部分考虑

的无条件优化问题。

梯度下降

上一讲我们讨论过,如果$\nabla f(\vec x )\neq \vec 0$,那么对于充分小的$\alpha >0$,我们必然有

所以考虑如下函数

我们可以搜索$t$,使得上式达到最小值,于是有如下算法:

  1. 选择初始估计值$\vec x_0 $
  2. 迭代直至$\vec x_k$收敛:
    • 令$g_k(t)=f(\vec x_k -t\nabla f(\vec x_k))$
    • 使用一维搜索算法找到$t’$,使得$g_k $最小化($t\ge 0$)
    • 令$\vec x_{k+1} =\vec x_k -t’ \nabla f(\vec x_k)$

牛顿法

多元情形也可以使用牛顿法,首先使用泰勒展开

对右边的式子关于$\vec x$求梯度可得

令上式为$\vec 0​$可得

迭代该算法最终得到$\vec x ‘$。

注意如果$H_f$不是半正定矩阵,那么$\vec x ‘$可能是鞍点,所以使用牛顿法之前需要判断$H_f$是否是半正定矩阵。

拟牛顿法——$BFGS$

牛顿法需要计算$\left[H_{f}\left(\vec{x}_{k}\right)\right]^{-1}$,而这往往需要很大计算量和存储量,类似折线法,我们可以认为Hessian矩阵满足

注意$B_k$是对称矩阵,所以可得得到如下优化问题:

注意到我们最终需要计算的是

而${\left|B_{k+1}-B_{k}\right|}$很小并不能推出$\left|H_{k+1}-H_{k}\right|$很小,所以应该求解如下问题:

求解该优化问题后,我们计算下式即可

选择不同的范数会得到不同结果,下面推导著名的BFGS算法。假设$A,W$是$n$阶对称矩阵,定义

这里我们假定

在上述范数的情形下,可以构造如下拉格朗日乘子:

在上述条件下,取矩阵$A$满足

那么

因为

那么关于$H_{ij}$求偏导并令其为$0​$可得

矩阵形式为

对(1)取转置,结合这些矩阵的性质可得

(1)+(2)可得

右乘$\vec s​$得到

对上述向量关于$\vec s$做内积可得

那么

带回(4)式可得

右乘$\vec y ^T$得到

注意

所以转置原式得到

(4)+(5)得到

因为

所以

对(7)左乘$W^{-1}$右乘$W^{-1}$得到

回顾(3)式

我们可得

Chapter 9 条件优化

这一部分将讨论条件优化问题:

其中

注意这是对之前讨论的很多问题的推广。如果取$f(\vec x) =0​$,那么该问题即为$g​$的求根问题;如果取$g(\vec x) =h(\vec x) =0​$,那么该问题即为无条件优化问题。

条件优化的理论

定义9.1(可行点和可行集)

定义9.2(条件优化的关键点)

现在假设我们找到$f​$的最小值点$\vec x ‘​$,那么对于约束条件$h(\vec x’)\ge \vec 0​$的每个分量$h_i(\vec x ‘)​$,我们有两种情形:

  • $h_i(\vec x’)=0 $,这种情形被称为边界解。这时称该约束是active。
  • $h_i(\vec x’)>0 $,这种情形被称为内部解,注意这种情形该条件不起作用。这时称该约束是inactive。

这两种情形分别对应如下两图:

如果所有约束都是active,那么该问题等价于

此时使用拉格朗日乘子法即可:

求梯度并令其为$\vec 0​$得到:

如果部分约束是inactive,那么该如何处理呢?由之前的讨论可知这部分约束不起作用,所以我们可以增加如下约束条件:对于inactive的约束,

注意对于active的约束,我们有

此时必然有

所以我们可以增加如下条件:对于所有$j$,

到目前为止,我们的处理没有区别

所以最后需要考虑这点。注意

等价于

所以我们只需要考虑如下情形:

此时拉格朗日乘子为

求梯度并令其为$\vec 0​$得到:

注意可行点的集合为

而active的点所处的集合为

因为$\nabla h_j(\vec x)$的方向指向$A$内部,所以要使得$f$最小化,$\nabla f(\vec{x})$应该和$\nabla h_j(\vec x)$同向(否则就会离开可行点集),因此$\forall j $

其中

将上述内容写成向量的形式可得

因为$D^T D$半正定,所以

将上述内容总结即得到KKT条件:

定理9.1 (Karush-Kuhn-Tucker (KKT)条件)

向量$\vec x’ \in \mathbb R^n$是如下问题的关键点(critical point)

如果存在$\vec \lambda \in \mathbb R^m $和$\vec \mu \in \mathbb R^p$,使得

  • $\vec{0}=\nabla f\left(\vec{x}’\right)-\Sigma_{i} \lambda_{i} \nabla g_{i}\left(\vec{x}’\right)-\sum_{j} \mu_{j} \nabla h_{j}\left(\vec{x}’\right)$(“stationarity”)
  • $g(\vec x’) =\vec 0, h(\vec x ‘)\ge \vec 0$(“primal feasibility”)
  • $\mu_j h_j(\vec x’)=0$(“complementary slackness”)
  • $\mu_j \ge 0$(“dual feasibility”)

例1

所以KKT条件为

本文标题:CS205A Lecture 11 Optimization; Multiple variables, constraints

文章作者:Doraemonzzz

发布时间:2019年04月23日 - 00:32:00

最后更新:2019年04月23日 - 13:46:46

原始链接:http://doraemonzzz.com/2019/04/23/CS205A Lecture 11 Optimization Multiple variables, constraints/

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