凸优化之无约束优化问题的求解方法

无约束优化问题的求解方法

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) xinf​f(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.
重复进行

  1. Δ x : = − ∇ f ( x ) \Delta x:= -\nabla f(x) Δx:=−∇f(x).
  2. 直线搜索, 通过精确或回溯直线搜索方法确定步长 t t t
  3. 修改, 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) xmin​f(x)⇔vmin​f(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 vmin​f(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​)∗=argdik​min​f(xk+dik​ei​)使用精确搜索或者非精确搜索寻找步长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) ), 然后去坐标轮换,轮换完了再固定这一块, 对之前那一块轮换.
具体算法过程:

  1. 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 不动
  2. 输入 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
  3. 输入 ( 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+21​vT∇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 法.

参考资料

上一篇:selenium - webdriver 多窗口切换 switch_to.window()


下一篇:C# 有道API翻译