无约束优化问题的求解方法
minimize
f
(
x
)
\text{minimize} \quad f(x)
minimizef(x)
其中
f
:
R
n
→
R
f: \mathbf{R}^{n} \rightarrow \mathbf{R}
f:Rn→R 是二次可微凸函数(这意味着
dom
f
\operatorname{dom} f
domf 是开集).我们假定该问题可解，即存在最优点
x
⋆
x^{\star}
x⋆ . 更准确地说，
x
⋆
x^{\star}
x⋆ 不仅存在，并且唯一.我们用
p
⋆
p^{\star}
p⋆ 表示最优值
inf
x
f
(
x
)
=
f
(
x
⋆
)
\underset{x}{\inf} f(x)=f\left(x^{\star}\right)
xinff(x)=f(x⋆) . 既然
f
f
f 是可微凸函数，最优点
x
⋆
x^{\star}
x⋆ 应满足下述充要条件
∇ f ( x ⋆ ) = 0 \nabla f\left(x^{\star}\right)=0 ∇f(x⋆)=0
因此，求解无约束优化问题等价于求解 n n n 个变量 x 1 , ⋯ , x n x_{1}, \cdots, x_{n} x1,⋯,xn 的 n n n 个方程.在一些特殊情况下，我们可以通过解析求解最优性方程 确定优化问题的解，但一般情况下，必须采用迭代算法求解方程，即计算点列 x ( 0 ) , x ( 1 ) , ⋯ ∈ dom f x^{(0)}, x^{(1)}, \cdots \in \operatorname{dom} f x(0),x(1),⋯∈domf 使得 k → ∞ k \rightarrow \infty k→∞ 时 f ( x ( k ) ) → p ⋆ f\left(x^{(k)}\right) \rightarrow p^{\star} f(x(k))→p⋆ .这样的点列被称为优化问题的极小化点列.当 f ( x ( k ) ) − p ⋆ ⩽ ϵ f\left(x^{(k)}\right)-p^{\star} \leqslant \epsilon f(x(k))−p⋆⩽ϵ 时算法将终止，其中 ϵ > 0 \epsilon>0 ϵ>0 是设定的容许误差值.
初始点和下水平集
本章介绍的方法需要一个适当的初始点
x
(
0
)
x^{(0)}
x(0), 该初始点必须属于
dom
f
\operatorname{dom} f
domf ，并且下 水平集
S
=
{
x
∈
dom
f
∣
f
(
x
)
⩽
f
(
x
(
0
)
)
}
S=\left\{x \in \operatorname{dom} f \mid f(x) \leqslant f\left(x^{(0)}\right)\right\}
S={x∈domf∣f(x)⩽f(x(0))}
必须是闭集.如果
f
f
f 是闭函数，即它的所有下水平集是闭集，上述条件对所有的
x
(
0
)
∈
dom
f
x^{(0)} \in \operatorname{dom} f
x(0)∈domf 均能满足.因为
dom
f
=
R
n
\operatorname{dom} f=\mathbf{R}^{n}
domf=Rn 的连续函数是闭函数，所以如果
dom
f
=
R
n
\operatorname{dom} f=\mathbf{R}^{n}
domf=Rn, 任何
x
(
0
)
x^{(0)}
x(0) 均能满足初始下水平集条件.另一类重要的闭函数是其定义域为开集的连续函数，这类
f
(
x
)
f(x)
f(x) 将随着
x
x
x 趋近
b
d
dom
f
\mathbf{b d} \operatorname{dom} f
bddomf 而趋于无穷.
预备知识
偏导数, 梯度, 方向导数, 梯度方向始终是是函数的增大方向的解释
首先,偏导数是构成梯度和方向导数的基础,在求偏导数时,无论多么复杂的多元函数,在求偏导数时我们可以将原函数看成是一个简单的一元函数,然后将求偏导看成是对一元函数求导数,然而我们发现求出的导数会有一个很好的性质.
∇
f
(
x
0
)
=
limit
Δ
x
→
0
f
(
x
0
+
Δ
x
)
−
f
(
x
0
)
Δ
x
\nabla f(x_{0}) = \underset{\Delta x \rightarrow0}{\text{limit}} \frac{f(x_0+\Delta x)-f(x_0)}{\Delta x}
∇f(x0)=Δx→0limitΔxf(x0+Δx)−f(x0)
由于偏导数只考虑函数在某一个维度
x
i
x^{i}
xi 上的变化,因此函数在求导点
x
0
i
x^{i}_{0}
x0i 的邻域内, 要么在这一维度的正方向上增大,要么在这一维度的负方向上增大.而导数的正负恰恰向我们指明了函数增大的方向,或者说函数自己本身的趋势就向我们指明了导数的正负,函数在维度
x
i
x^{i}
xi 的
x
0
i
x^{i}_{0}
x0i 点附近处于递增趋势时,求得的偏导数为正,则自变量向正方向移动会使函数值变大,反之,求得的偏导数为负,则自变量向负方向移动会使函数值变大.而梯度中的每一个元素的值都等于函数在某一维度上的偏导数的值, 因此梯度中的每一个元素都指向了函数在某一维上的增大方向,因此,梯度这个向量所代表的方向就表示了函数的增大方向.
∂ f ∂ x 0 i = limit Δ x i → 0 f ( x 0 i + Δ x i ) − f ( x 0 i ) Δ x i \frac{\partial f}{\partial x^{i}_{0}} = \underset{\Delta x^{i} \rightarrow 0}{\text{limit}} \frac{f(x^{i}_{0}+\Delta x^{i})-f(x^{i}_{0})}{\Delta x^{i}} ∂x0i∂f=Δxi→0limitΔxif(x0i+Δxi)−f(x0i)
梯度是一个向量, 而方向导数是一个标量.
若函数
f
(
x
)
f(x)
f(x) 在点
x
0
x_{0}
x0 处可微分，与方向
l
l
l 同方向的单位向量为
e
l
\boldsymbol{e}_{l}
el, 则函数
f
(
x
)
f(x)
f(x) 在点
x
0
x_{0}
x0 处, 方向
l
l
l 上的方向导数为:
∂ f ∂ l ∣ x 0 = ∇ f ( x 0 ) ⋅ e l \begin{aligned} \left.\frac{\partial f}{\partial l} \right |_{x_{0}} =\nabla f(x_{0}) \cdot \boldsymbol{e}_{l} \end{aligned} ∂l∂f∣∣∣∣x0=∇f(x0)⋅el
式中,
θ
\theta
θ 为梯度与方向
l
l
l 的夹角
(1) 当
θ
=
0
\theta=0
θ=0, 方向
l
l
l 与梯度方向同向，函数
f
(
x
)
f(x)
f(x) 增长最快;
(2) 当
θ
=
π
\theta=\pi
θ=π, 方向
l
l
l 与梯度方向相反，函数
f
(
x
)
f(x)
f(x) 减少最快;
(3) 当
θ
=
π
/
2
\theta=\pi / 2
θ=π/2, 方向
l
l
l 与梯度方向正交，函数
f
(
x
)
f(x)
f(x) 变化率为0;
梯度下降算法 Gradient Descent
用负梯度做搜索方向,令 ∇ x = − ∇ f ( x ) \nabla x = -\nabla f(x) ∇x=−∇f(x), 是一种自然的选择,相应的方法被称为梯度方法或者梯度下降算法.
梯度下降算法描述
给定初始点
x
∈
dom
f
x \in \operatorname{dom} f
x∈domf.
重复进行
- Δ x : = − ∇ f ( x ) \Delta x:= -\nabla f(x) Δx:=−∇f(x).
- 直线搜索, 通过精确或回溯直线搜索方法确定步长 t t t
- 修改, x : = x + t Δ x x:=x+ t \Delta x x:=x+tΔx 直到满足停止准则.
停止准则通常取为
∥
∇
f
(
x
)
∥
2
⩽
η
\|\nabla f(x)\|_{2} \leqslant \eta
∥∇f(x)∥2⩽η, 其中
η
\eta
η 是小正数. 大部分情况下, 步骤 1 完成后就检验停止条件, 而不是在修改后才检验.
收敛性:无论是精确搜索还是非精确搜索都是线性收敛
最速下降算法 Steepest Descent
对
f
(
x
+
v
)
f(x+v)
f(x+v) 在
x
x
x 处进行一阶 Taylor 展开,
f
(
x
+
v
)
≈
f
^
(
x
+
v
)
=
f
(
x
)
+
∇
f
(
x
)
T
v
f(x+v) \approx \widehat{f}(x+v)=f(x)+\nabla f(x)^{T} v
f(x+v)≈f
(x+v)=f(x)+∇f(x)Tv
其中右边第二项 ∇ f ( x ) T v \nabla f(x)^{T} v ∇f(x)Tv 是 f f f 在 x x x 处沿方向 v v v 的方向导数. 它近似给出了 f f f 沿小的步径 v v v 会发生的变化. 如果其方向导数是负数, 步径 v v v 就是下降方向. 我们现在讨论如何选择 v v v 使其方向导数尽可能小. 由于方向导数 ∇ f ( x ) T v \nabla f(x)^{T} v ∇f(x)Tv 是 v v v 的 线性函数，只要我们将 v v v 取得充分大, 就可以使其方向导数充分小 (在 v v v 是下降方向的前提下, 即 ∇ f ( x ) T v < 0 \nabla f(x)^{T} v<0 ∇f(x)Tv<0 ). 为了使问题有意义，我们还必须限制 v v v 的大小, 或者规范 v v v 的长度. 不然只要 v v v 足够大或者足够小, 方向导数就会很小.
首先, 假设我们选一个初始点
x
k
x^{k}
xk, 令方向
v
∈
R
n
v \in R^{n}
v∈Rn, 那么
min
x
f
(
x
)
⇔
min
v
f
(
x
k
+
v
)
\underset{x}{\min} f(x) \Leftrightarrow \underset{v}{\min} f\left(x^{k}+v\right)
xminf(x)⇔vminf(xk+v).
这个时候我们把右边这个函数在
x
k
x^{k}
xk 展开, 则问题变成
min
v
f
(
x
k
)
+
∇
f
(
x
)
T
v
\underset{v}{\min} f\left(x^{k}\right)+\nabla f(x)^{T} v
vminf(xk)+∇f(x)Tv
这个问题便是最速下降法本质上求解的问题.
但是可以看到, 如果选的点
∇
f
(
x
k
)
≠
0
\nabla f\left(x^{k}\right) \neq 0
∇f(xk)=0 的 话, 总是能够找到
v
v
v 使得目标函数到负无穷. 所以我们需要对这个目标函数进行限制.
(1) 用 ∥ v ∥ 1 = 1 ( v 中 所 有 分 量 总 和 为 1 ) \|v\|_{1}=1(v中所有分量总和为1) ∥v∥1=1(v中所有分量总和为1) 来限制
d
k
+
1
=
arg
min
v
{
f
(
x
k
)
+
∇
f
(
x
k
)
T
v
∣
∥
v
∥
1
=
1
}
d^{k+1}=\arg \underset{v}{\min}\left\{f\left(x^{k}\right)+\nabla f\left(x^{k}\right)^{T} v \mid\|v\|_{1}=1\right\}
dk+1=argvmin{f(xk)+∇f(xk)Tv∣∥v∥1=1}
此时是可以算出最优解
v
=
d
k
+
1
v=d^{k+1}
v=dk+1 的, 表达式为
d
k
+
1
=
v
=
[
0
⋮
(
−
1
)
sgn
(
∇
f
(
x
k
)
i
)
⋮
0
]
d^{k+1}=v=\left[\begin{array}{c}0 \\ \vdots \\ (-1) \operatorname{sgn}\left(\nabla f\left(x^{k}\right)_{i}\right) \\ \vdots \\ 0\end{array}\right]
dk+1=v=⎣⎢⎢⎢⎢⎢⎢⎡0⋮(−1)sgn(∇f(xk)i)⋮0⎦⎥⎥⎥⎥⎥⎥⎤
其中
∇
f
(
x
k
)
i
\nabla f\left(x^{k}\right)_{i}
∇f(xk)i 满足
∣
∇
f
(
x
k
)
i
∣
=
max
{
∣
∇
f
(
x
k
)
1
∣
,
…
,
∣
∇
f
(
x
k
)
n
∣
}
\left|\nabla f\left(x^{k}\right)_{i}\right|=\max \left\{\left|\nabla f\left(x^{k}\right)_{1}\right|, \ldots,\left|\nabla f\left(x^{k}\right)_{n}\right|\right\}
∣∣∇f(xk)i∣∣=max{∣∣∇f(xk)1∣∣,…,∣∣∇f(xk)n∣∣}
即，最优方向与梯度的分量绝对值最大的方向相反, 这也是为什么叫做最速 (最陡) 下降法的原因, 绝对值分量最大的那一个维度就是最陡的.
(2) 用 ∥ v ∥ 2 = 1 \|v\|_{2}=1 ∥v∥2=1 来限制
d
k
+
1
=
arg
min
v
{
f
(
x
k
)
+
∇
f
(
x
k
)
T
v
∣
∥
v
∥
2
=
1
}
d^{k+1}=\arg \underset{v}{\min}\left\{f\left(x^{k}\right)+\nabla f\left(x^{k}\right)^{T} v \mid\|v\|_{2}=1\right\}
dk+1=argvmin{f(xk)+∇f(xk)Tv∣∥v∥2=1}
同理可得,
d
k
+
1
=
v
=
−
∇
f
(
x
k
)
∥
∇
f
(
x
k
)
∥
2
d^{k+1}=v=-\frac{\nabla f\left(x^{k}\right)}{\left\|\nabla f\left(x^{k}\right)\right\|_{2}}
dk+1=v=−∥∇f(xk)∥2∇f(xk)
此时最速下降法就是梯度下降法给梯度做了个单位化, 与梯度下降法并无区别.
(3) 用 ∥ v ∥ ∞ = 1 ( v 中 所 有 分 量 中 最 大 值 为 1 ) \|v\|_{\infty}=1(v中所有分量中最大值为1) ∥v∥∞=1(v中所有分量中最大值为1) 来限制
d k + 1 = arg min v { f ( x k ) + ∇ f ( x k ) T v ∣ ∥ v ∥ ∞ = 1 } d^{k+1}=\arg \underset{v}{\min}\left\{f\left(x^{k}\right)+\nabla f\left(x^{k}\right)^{T} v \mid\|v\|_{\infty}=1\right\} dk+1=argvmin{f(xk)+∇f(xk)Tv∣∥v∥∞=1}
同理可得,
d
k
+
1
=
v
=
[
1
,
⋯
,
1
]
⋅
[
(
−
1
)
sgn
(
∇
f
(
x
k
)
1
)
⋮
(
−
1
)
sgn
(
∇
f
(
x
k
)
n
)
]
\begin{aligned} d^{k+1} &=v \\ &=[1, \cdots, 1] \cdot\left[\begin{array}{c}(-1) \operatorname{sgn}\left(\nabla f\left(x^{k}\right)_{1}\right) \\ \vdots \\ (-1) \operatorname{sgn}\left(\nabla f\left(x^{k}\right)_{n}\right)\end{array}\right] \end{aligned}
dk+1=v=[1,⋯,1]⋅⎣⎢⎡(−1)sgn(∇f(xk)1)⋮(−1)sgn(∇f(xk)n)⎦⎥⎤
最速下降方法使用最速下降方向作为直线搜索方向.
收敛性:线性收敛.
坐标轮换法 Coordinate Descent
思路：
最速下降法实际上是找到梯度分量的绝对值最大的那一个维度(对方向
v
v
v 的约束为1范数时)，然后沿着那个维度的反方向下降.
但是这样找需要提前计算出梯度才行，反正都是沿着某一个维度/坐标方向下降，那么完全可以不计算梯度, 而是沿着每一个维度/坐标都下降一次，有点像穷举的办法.
但是要注意的是, 说是说让迭代点沿着每一个坐标都下降一次. 不一定每一个坐标方向都真的会让函数值下降, 因此在每一次坐标下降后, 要对步长进行一次线搜索, 找到让函数值下降了的步长，然后继续坐标下降(更新
x
i
k
)
\left.x_{i}^{k}\right)
xik), 搜索步长
α
i
\alpha_{i}
αi, 依次下去把坐标都轮换一遍.
具体算法过程:
x
k
x^{k}
xk, 单位向量
e
i
e_{i}
ei, 第
i
i
i 号元素为1,其他均为0
对第
i
i
i个坐标轮换:
(
d
i
k
)
∗
=
arg
min
d
i
k
f
(
x
k
+
d
i
k
e
i
)
使
用
精
确
搜
索
或
者
非
精
确
搜
索
寻
找
步
长
t
x
i
k
+
1
:
=
x
i
k
+
t
(
d
i
k
)
∗
\begin{aligned} &(d_{i}^{k})^{*}=\arg \underset{d_{i}^{k}}{\min}f(x^{k}+d_{i}^{k}e_{i}) \\ &使用精确搜索或者非精确搜索寻找步长t \\ &x_{i}^{k+1}:=x_{i}^{k} + t (d_{i}^{k})^{*} \\ \end{aligned}
(dik)∗=argdikminf(xk+dikei)使用精确搜索或者非精确搜索寻找步长txik+1:=xik+t(dik)∗
缺点: 对多维度的优化问题不友好, 计算量太大了.
块坐标下降法 Block Coordinate Descent:
要求
f
f
f 为凸函数, 光滑,且只考虑变量
x
x
x 和
y
y
y 时,函数比较简单.
思路： 将自变量分成多个块, 比如
f
(
x
,
y
)
f(x, y)
f(x,y), 单纯的坐标轮换是对
x
1
,
…
,
x
n
,
y
1
,
…
,
y
m
x_{1}, \ldots, x_{n}, y_{1}, \ldots, y_{m}
x1,…,xn,y1,…,ym 的 每一个维度去轮换，现在是固定一个块(比如固定
y
)
y)
y), 假定函数值的变化情况与另一块的自变量有关(
f
(
x
)
f(x)
f(x) ), 然后去坐标轮换，轮换完了再固定这一块, 对之前那一块轮换.
具体算法过程:
-
f
(
x
,
y
)
,
x
k
,
y
k
f(x, y), x^{k}, y^{k}
f(x,y),xk,yk固定
y
k
y^{k}
yk 不动, 输入
x
k
x^{k}
xk, 对
f
(
x
,
y
k
)
f\left(x, y^{k}\right)
f(x,yk) 执行与
x
x
x 的坐标轮换, 得到
x
k
+
1
x^{k+1}
xk+1
固定 x k + 1 x^{k+1} xk+1 不动 - 输入 y k y^{k} yk, 对 f ( x k + 1 , y ) f\left(x^{k+1}, y\right) f(xk+1,y) 执行与 y y y 的坐标轮换, 得到 y k + 1 y^{k+1} yk+1
- 输入 ( x k + 1 , y k + 1 ) \left(x^{k+1}, y^{k+1}\right) (xk+1,yk+1)
牛顿法 Newton method
当目标函数二阶可微时，我们可以从最速下降法导出牛顿法.
牛顿法的下降方向可以认为是在梯度下降法的基础上用Hessian矩阵对梯度做了一些修正
在目标二阶可微时, 把
f
(
x
k
+
v
)
f\left(x^{k}+v\right)
f(xk+v) 二阶展开就可以导出牛顿法.
f
(
x
k
+
v
)
=
f
(
x
k
)
+
∇
f
(
x
k
)
T
v
+
1
2
v
T
∇
2
f
(
x
k
)
T
v
f\left(x^{k}+v\right)=f\left(x^{k}\right)+\nabla f\left(x^{k}\right)^{T} v+\frac{1}{2} v^{T} \nabla^{2} f\left(x^{k}\right)^{T} v
f(xk+v)=f(xk)+∇f(xk)Tv+21vT∇2f(xk)Tv.
对
v
v
v 求偏导得出
d
k
=
v
=
−
(
∇
2
f
(
x
k
)
)
−
1
∇
(
x
k
)
d^{k}=v=-\left(\nabla^{2} f\left(x^{k}\right)\right)^{-1} \nabla\left(x^{k}\right)
dk=v=−(∇2f(xk))−1∇(xk)
这个就是牛顿法的下降方向. 如果我们再把目光放到上述二阶展开式中可以发现, 如果迭代点的函数值
f
(
x
k
+
v
)
f\left(x^{k}+v\right)
f(xk+v) 接近最优值
f
∗
f^{*}
f∗ 时, 有函数的一阶导数
∇
f
(
x
k
)
→
0
\nabla f\left(x^{k}\right) \rightarrow 0
∇f(xk)→0, 这意味展开式中
f
(
x
k
+
v
)
与
f
(
x
k
)
相
当
接
近
f(x^{k}+v)与f(x^{k})相当接近
f(xk+v)与f(xk)相当接近, 则
∇
f
(
x
k
)
T
v
=
f
(
x
k
+
v
)
−
f
(
x
k
)
\nabla f\left(x^{k}\right)^{T} v = f(x^{k}+v)-f(x^{k})
∇f(xk)Tv=f(xk+v)−f(xk) 会变得很小, 将
v
v
v 的最优值代入, 得到停止条件
∇
f
(
x
k
)
T
v
=
∥
∇
f
(
x
k
)
T
(
∇
2
f
(
x
k
)
)
−
1
∇
f
(
x
k
)
∥
≤
ε
\nabla f\left(x^{k}\right)^{T} v=\left\|\nabla f\left(x^{k}\right)^{T}\left(\nabla^{2} f\left(x^{k}\right)\right)^{-1} \nabla f\left(x^{k}\right)\right\| \leq \varepsilon
∇f(xk)Tv=∥∥∥∇f(xk)T(∇2f(xk))−1∇f(xk)∥∥∥≤ε
ε
\varepsilon
ε 足够小时(小于自己规定的精度), 算法差不多收敛了，可以不用继续迭代了.
∃
η
>
0
∥
∇
f
(
x
)
∥
2
<
η
阻力收敛damped newton phase
∥
∇
f
(
x
)
∥
2
>
η
二次收敛quadratically convergent
最
优
解
附
近
对
函
数
进
行
一
阶
泰
勒
展
开
,
一
阶
导
数
会
接
近
于
0
,
因
此
,
如
果
泰
勒
展
开
中
一
阶
导
数
趋
近
于
0
,
那
就
说
明
我
们
快
要
接
近
最
优
值
了
(
仅
在
凸
问
题
中
成
立
)
\begin{array}{ll} \exists \eta>0\\ \|\nabla f(x)\|_{2}<\eta \text{ 阻力收敛damped newton phase} \\ \|\nabla f(x)\|_{2}>\eta \text{ 二次收敛quadratically convergent} \\ 最优解附近对函数进行一阶泰勒展开,一阶导数会接近于0,\\ 因此,如果泰勒展开中一阶导数趋近于0,\\ 那就说明我们快要接近最优值了(仅在凸问题中成立) \end{array}
∃η>0∥∇f(x)∥2<η 阻力收敛damped newton phase∥∇f(x)∥2>η 二次收敛quadratically convergent最优解附近对函数进行一阶泰勒展开,一阶导数会接近于0,因此,如果泰勒展开中一阶导数趋近于0,那就说明我们快要接近最优值了(仅在凸问题中成立)
离最优解远时收敛的慢, 近时变得很快, 比线性收敛还快:
拟牛顿法 Quasi-Newton Method
拟牛顿法的迭代方向与牛顿法有略微不同,具体形式如下:
d
k
=
−
B
⋅
∇
f
(
x
k
)
d^{k}=-B \cdot \nabla f\left(x^{k}\right)
dk=−B⋅∇f(xk)
这里里的 B B B 是一个数值矩阵, 用来近似牛顿法中的 ∇ 2 f ( x k ) \nabla^{2} f\left(x^{k}\right) ∇2f(xk) 的. ∇ 2 f ( x k ) \nabla^{2} f\left(x^{k}\right) ∇2f(xk) 的近似现在有许多的办法, 不同的近似思路导致 B B B 的计算模式也不同,产生了不同的拟牛顿算法,比如 B F G S BFGS BFGS 法, L − B F G S L-BFGS L−BFGS 法和 D F P DFP DFP 法.