无约束最优化方法的基本结构
现在我们正式进入第二章的学习, 在开始学习无约束最优化方法之前我们先学习几个知识.
在以后的章节, 如果没有特殊说明, 我们总假定目标函数 f ( x ) f(x) f(x)的一阶导数存在, 当算法要求存在二阶导数时, 那就存在二阶导数, 并且一,二阶导数我们这里记作:
g ( x ) = ∇ f ( x ) = [ ∂ f ( x ) ∂ x 1 ∂ f ( x ) ∂ x 2 ⋯ ∂ f ( x ) ∂ x n ] T G ( x ) = ∇ 2 f ( x ) = [ ∂ 2 f ( x ) ∂ x 1 2 ∂ 2 f ( x ) ∂ x 1 x 2 ⋯ ∂ 2 f ( x ) ∂ x 1 x n ∂ 2 f ( x ) ∂ x 2 x 1 ∂ 2 f ( x ) ∂ x 2 x 2 ⋯ ∂ 2 f ( x ) ∂ x 2 x n ⋮ ⋮ ⋮ ∂ 2 f ( x ) ∂ x n x 1 ∂ 2 f ( x ) ∂ x n x 2 ⋯ ∂ 2 f ( x ) ∂ x n x n ] T g(x)=\nabla f(x)= \begin{bmatrix} \frac{\partial f(x)}{\partial x_1}&\frac{\partial f(x)}{\partial x_2}&\cdots&\frac{\partial f(x)}{\partial x_n} \end{bmatrix}^T\\ G(x)=\nabla^2f(x)= \begin{bmatrix} \frac{\partial^2 f(x)}{\partial x_1^2}&\frac{\partial^2 f(x)}{\partial x_1x_2}&\cdots&\frac{\partial^2 f(x)}{\partial x_1x_n}\\ \frac{\partial^2 f(x)}{\partial x_2x_1}&\frac{\partial^2 f(x)}{\partial x_2x_2}&\cdots&\frac{\partial^2 f(x)}{\partial x_2x_n}\\ \vdots&\vdots& &\vdots\\ \frac{\partial^2 f(x)}{\partial x_nx_1}&\frac{\partial^2 f(x)}{\partial x_nx_2}&\cdots&\frac{\partial^2 f(x)}{\partial x_nx_n}\\ \end{bmatrix}^T\\ g(x)=∇f(x)=[∂x1∂f(x)∂x2∂f(x)⋯∂xn∂f(x)]TG(x)=∇2f(x)= ∂x12∂2f(x)∂x2x1∂2f(x)⋮∂xnx1∂2f(x)∂x1x2∂2f(x)∂x2x2∂2f(x)⋮∂xnx2∂2f(x)⋯⋯⋯∂x1xn∂2f(x)∂x2xn∂2f(x)⋮∂xnxn∂2f(x) T
其中的 g ( x ) , G ( x ) g(x),G(x) g(x),G(x)是 f ( x ) f(x) f(x)在x点处的梯度向量和Hesse矩阵
通常我们记:
f ∗ = f ( x ∗ ) , g ∗ = g ( x ∗ ) , G ∗ = G ( x ∗ ) f^*=f(x^*),\ \ \ g^*=g(x^*),\ \ \ G^*=G(x^*) f∗=f(x∗), g∗=g(x∗), G∗=G(x∗)
最优性条件
之前在网上看到一个笑话:打开罐头前, 我们先学习一下如何打开罐头, 按照如下流程学习:罐头的定义,罐头的性质,罐头的特点,罐头的历史,罐头的…
虽然这个是笑话, 但是在实际的学习中我们确实有必要学习完整的知识体系, 对于我们这个最优化问题求解这个知识体系中, 我们自然要先了解什么是解, 也就是什么是我们要求的最优解,最优解的定义是什么?
最优解有分类, 其被分为全局最优解和局部最优解, 我们对这两种分类进行定义,进 而组合成最优解的定义
全局最优解: 对任意 x ∈ R n , f ( x ) ≥ f ∗ , 则 x ∗ 为全局最优解 , 而如果对任意 x ∈ R n , 且 x ≠ x ∗ , f ( x ) > f ∗ , 则 x ∗ 为严格全局最优解 对任意x\in R^n, f(x)\ge f^*,则x^*为全局最优解,而如果对任意x\in R^n, 且x\neq x^*,f(x)> f^*,则x^*为严格全局最优解 对任意x∈Rn,f(x)≥f∗,则x∗为全局最优解,而如果对任意x∈Rn,且x=x∗,f(x)>f∗,则x∗为严格全局最优解
也就是任意点上的函数值都比全局最优解的函数值大
局部最优解: 对 x ∗ ∈ R n , ∃ ε > 0 , 对任意 x ∈ R n , 当 ∣ ∣ x − x ∗ ∣ ∣ < ε 时 , 有 f ( x ) ≥ f ∗ 则称 x ∗ 为局部最优解 , 而当 x ∗ ∈ R n , ∃ ε > 0 , 对任意 x ∈ R n , 当 ∣ ∣ x − x ∗ ∣ ∣ < ε 且 x ≠ x ∗ 时 , 有 f ( x ) > f ∗ 则称 x ∗ 为严格局部最优解 对x^*\in R^n,\exist\varepsilon>0,对任意x\in R^n,当||x-x^*||<\varepsilon时,有f(x)\ge f^*则称x^*为局部最优解,而当x^*\in R^n,\exist\varepsilon>0,对任意x\in R^n,当||x-x^*||<\varepsilon且x\neq x^*时,有f(x)> f^*则称x^*为严格局部最优解 对x∗∈Rn,∃ε>0,对任意x∈Rn,当∣∣x−x∗∣∣<ε时,有f(x)≥f∗则称x∗为局部最优解,而当x∗∈Rn,∃ε>0,对任意x∈Rn,当∣∣x−x∗∣∣<ε且x=x∗时,有f(x)>f∗则称x∗为严格局部最优解
也就是当一个点无限靠近于局部最优解时,其函数值比局部最优解的函数值大, 学习过高等数学的极限的概念的话, 想必不会对这种定义方式感到陌生
当我们要解决的问题是极小值问题时最优解
x
∗
x^*
x∗也是极小点,可记作:
x
∗
=
arg min
f
(
x
)
x^*=\argmin f(x)
x∗=argminf(x)
“arg"是"argument”(自变量)的缩写, 也就是求使得函数
f
(
x
)
f(x)
f(x)最小时自变量
x
x
x的取值
比如图中的BD点都满足了局部最优解, 但是假设该函数的定义域如图所示, 那么只有D点满足全局最优解的定义
本书介绍的所有算法都是求局部解的算法
有了最优解的定义, 我们是不是就可以求最优解了呢, 学过数学的你一定有强烈的预感:那就是绝对不可能!
直接通过定义我们还无法很好地得到最优解的获取条件, 但是通过定义我们可以找到等价的其他数学表示方法从而有利于我们之后对最优化问题的求解, 接下来我就开始介绍一下最优性条件
最优性条件也就是使得某一点是最优解(具有最优性)的条件(充分条件和必要条件)
下面的定理给出了 x ∗ x^* x∗是无约束最优化问题局部最优解的充分和必要的条件:
- 一阶必要条件: 设 f ( x ) ∈ C 1 , x ∗ 为 f ( x ) 的一个局部极小点 , 则 g ( x ∗ ) = 0 设f(x)\in C^1,x^*为f(x)的一个局部极小点, 则g(x^*)=0 设f(x)∈C1,x∗为f(x)的一个局部极小点,则g(x∗)=0
其实这个定义我们在上图二维图像上看会绝对很自然, 其实这个和高中题目中求函数极小点的知识是一样的(也可以用费马定理推出), 但是我们知道, 光是函数的一阶导为0只能说明这个点是个驻点, 而驻点可能是极大值点也可能是极小值点也有可能是拐点(该点左右图像凹凸性不同), 所以这个条件只是一个必要条件
- 证明:
我们使用反证法, 假定对于最优解 x ∗ x^* x∗, 有 g ( x ∗ ) ≠ 0 g(x^*)\neq0 g(x∗)=0,
我们知道 g ( x ∗ ) g(x^*) g(x∗)其实就是一个向量, 如果这个向量不为0, 那么它必定是有方向的,
有了方向我们就肯定可以找到一个向量 d ∈ R n d\in R^n d∈Rn
向量 d d d满足条件 d T g ( x ∗ ) < 0 d^T g(x^*)<0 dTg(x∗)<0, 也就是向量 d d d和向量 g ( x ∗ ) g(x^*) g(x∗)的方向夹角超过了90度
比如说 d = − g ( x ∗ ) d=-g(x^*) d=−g(x∗)
而 d T g ( x ∗ ) < 0 d^T g(x^*)<0 dTg(x∗)<0, 且我们假定 g ( x ) g(x) g(x)是连续的,
那么根据函数极限的保号性, 我们可以知道, 必定 ∃ δ > 0 \exist \delta>0 ∃δ>0, 使得 d T g ( x ∗ + α d ) < 0 , α ∈ [ 0 , δ ] d^T g(x^*+\alpha d)<0,\alpha\in[0, \delta] dTg(x∗+αd)<0,α∈[0,δ]
根据柯西中值定理, 当我们再取 α 1 ∈ [ 0 , α ] \alpha_1 \in [0, \alpha] α1∈[0,α]
则有 f ( x ∗ + α 1 d ) − f ( x ∗ ) d α 1 = d T g ( x ∗ + α 1 d ) \frac{f(x^*+\alpha_1 d)-f(x^*)}{d\alpha_1}=d^T g(x^*+\alpha_1 d) dα1f(x∗+α1d)−f(x∗)=dTg(x∗+α1d)
同样根据保号性, 我们有 d T g ( x ∗ + α 1 d ) < 0 d^T g(x^*+\alpha_1 d)<0 dTg(x∗+α1d)<0
则 f ( x ∗ + α 1 d ) − f ( x ∗ ) d α 1 < 0 \frac{f(x^*+\alpha_1 d)-f(x^*)}{d\alpha_1}<0 dα1f(x∗+α1d)−f(x∗)<0
所以 f ( x ∗ + α 1 d ) < f ( x ∗ ) f(x^*+\alpha_1 d)<f(x^*) f(x∗+α1d)<f(x∗)
显然表明该函数在点 x ∗ x^* x∗上可以沿着 d d d方向继续下降, 说明这个点并不是最小点, 即可反证出一阶必要条件
- 二阶必要条件: 设 f ( x ) ∈ C 2 , x ∗ 为 f ( x ) 的一个局部极小点 , 则 G ( x ∗ ) 半正定 设f(x)\in C^2,x^*为f(x)的一个局部极小点, 则G(x^*)半正定 设f(x)∈C2,x∗为f(x)的一个局部极小点,则G(x∗)半正定
虽然是高维数据, 但是我们依然可以用一维数据二阶导的知识来类比, 所谓汉森矩阵其实就是一维函数中的二阶导的结果, 只不过在高维函数中我们必须要用矩阵的形式来表示, 如果学习过线性代数, 我们知道对于矩阵的半正定我们可以简单理解为二阶导大于等于0, 用数学定义表示就是 ∃ d , d T G ( x ∗ ) d ≥ 0 \exist d,d^TG(x^*)d\geq0 ∃d,dTG(x∗)d≥0, 显然, 在一维函数中, 我们说一个函数的二阶导大于等于0, 可以想象出这个函数的向下凹的(高等数学的凹凸函数和这个书中的凸函数不太一样), 显然一个极小值点肯定是要满足这个条件的, 但是光有这个条件是不够的, 所以这个只是最优性的二阶必要条件
- 证明:
还是使用反证法, 上面我们说这个条件用数学表示是 ∃ d , d T G ( x ∗ ) d ≥ 0 \exist d,d^TG(x^*)d\geq0 ∃d,dTG(x∗)d≥0,
所以我们假定 ∃ d , d T G ( x ∗ ) d < 0 \exist d,d^TG(x^*)d<0 ∃d,dTG(x∗)d<0
假定 G ( x ∗ ) G(x^*) G(x∗)连续
由保号性可知 ∃ δ , d T G ( x ∗ + α d ) d < 0 , α ∈ [ 0 , δ ] \exist \delta, d^TG(x^*+\alpha d)d<0,\alpha \in [0, \delta] ∃δ,dTG(x∗+αd)d<0,α∈[0,δ]
但是这次和上面的使用中值定理不一样了, 这次我们使用 f ( x ) f(x) f(x)的泰勒展开式
有 f ( x ∗ + α d ) = f ( x ∗ ) + 1 2 α 2 d T G ( x ∗ + α 1 d ) d , α 1 ∈ [ 0 , α ] f(x^*+\alpha d)=f(x^*)+\frac{1}{2}\alpha^2d^TG(x^*+\alpha_1 d)d, \alpha_1\in[0,\alpha] f(x∗+αd)=f(x∗)+21α2dTG(x∗+α1d)d,α1∈[0,α]
显然可知 f ( x ∗ + α d ) < f ( x ∗ ) f(x^*+\alpha d)<f(x^*) f(x∗+αd)<f(x∗)
即可反证二阶必要条件
- 二阶充分条件: 设 f ( x ) ∈ C 2 , 在点 x ∗ 有 g ( x ∗ ) = 0 , 且 G ( x ∗ ) 正定 , 则 x ∗ 是严格的局部极小点 设f(x)\in C^2,在点x^*有g(x^*)=0,且G(x^*)正定, 则x^*是严格的局部极小点 设f(x)∈C2,在点x∗有g(x∗)=0,且G(x∗)正定,则x∗是严格的局部极小点
是不是可以看出这个其实和一维函数求极小点十分相似, 只要类比一下一阶导等于0二阶导大于0的条件, 我们很快就能记住这个理论了
- 证明:
对于 ∀ d ∈ R n \forall d\in R^n ∀d∈Rn, f ( x ) f(x) f(x)在 x ∗ x^* x∗的泰勒展开式如下:
f ( x ∗ + α d ) = f ( x ∗ ) + α g ( x ∗ ) d + 1 2 α 2 d T G ( x ∗ ) d + o ( α 2 ) f(x^*+\alpha d)=f(x^*)+\alpha g(x^*)d+\frac{1}{2}\alpha^2d^TG(x^*)d+o(\alpha^2) f(x∗+αd)=f(x∗)+αg(x∗)d+21α2dTG(x∗)d+o(α2)
由已知条件: G ( x ∗ ) G(x^*) G(x∗)半正定, ∃ γ > 0 , ∀ d ∈ R n \exist \gamma>0,\forall d\in R^n ∃γ>0,∀d∈Rn有 d T G ( x ∗ ) d ≥ γ d^TG(x^*)d\geq\gamma dTG(x∗)d≥γ, 且有 g ( x ∗ ) d = 0 g(x^*)d=0 g(x∗)d=0
则 f ( x ∗ + α d ) ≥ f ( x ∗ ) + 1 2 γ α 2 + o ( α 2 ) f(x^*+\alpha d)\geq f(x^*)+\frac{1}{2}\gamma\alpha^2+o(\alpha^2) f(x∗+αd)≥f(x∗)+21γα2+o(α2)
可知$ f ( x ∗ + α d ) > f ( x ∗ ) f(x^*+\alpha d)> f(x^*) f(x∗+αd)>f(x∗)
即可推出二阶充分条件
值得注意的是高维函数的泰勒展开:
方向导数
话题一转, 你可能会疑惑为什么我直接转到方向导数这个话题来了, 还记得我上面说的吗, 在定义了最优解之后, 我们必然是无法直接通过定义来求最优解的, 因此我们提出了等价的一阶必要条件, 二阶必要条件和二阶充分条件, 但是, 除此之外呢, 我们还可以使用方向导数来提出同样等价的最优性条件
那么我们先来讲讲方向导数的定义:
对 ∀ d ∈ R n / { 0 } \forall d\in R^n / \{0\} ∀d∈Rn/{0},如果极限 lim α → 0 + f ( x + α d ) − f ( x ) α ∣ ∣ d ∣ ∣ \lim_{\alpha\rightarrow0^+}\frac{f(x+\alpha d)-f(x)}{\alpha ||d||} α→0+limα∣∣d∣∣f(x+αd)−f(x)存在,则这个极限值就是函数 f ( x ) f(x) f(x)在 x x x点 d d d方向上的方向导数,记作 ∂ f ( x ) ∂ d \frac{\partial f(x)}{\partial d} ∂d∂f(x)或者D(f(x);d)
给出了方向导数的定义, 接下来我们不给出证明得定义出一阶二阶方向导数的计算公式:
对于
f
(
x
)
∈
C
1
f(x)\in C^1
f(x)∈C1
∂
f
(
x
)
∂
d
=
1
∣
∣
d
∣
∣
g
(
x
)
T
d
\frac{\partial f(x)}{\partial d} = \frac{1}{||d||}g(x)^Td
∂d∂f(x)=∣∣d∣∣1g(x)Td
对于
f
(
x
)
∈
C
2
f(x)\in C^2
f(x)∈C2
∂
2
f
(
x
)
∂
d
2
=
1
∣
∣
d
∣
∣
2
d
T
G
(
x
)
d
\frac{\partial^2 f(x)}{\partial d^2} = \frac{1}{||d||^2}d^TG(x)d
∂d2∂2f(x)=∣∣d∣∣21dTG(x)d
这些定义可以由导数的定义得到, 这里不做推导
那么接下来我也不加证明的给出由方向导数得出的最优解条件:
1.一阶必要条件:
设
f
(
x
)
∈
C
1
,
x
∗
为
f
(
x
)
的一个局部极小点
,
则
f
(
x
∗
)
沿任意方向的一阶方向导数为
0
设f(x)\in C^1,x^*为f(x)的一个局部极小点,则f(x^*)沿任意方向的一阶方向导数为0
设f(x)∈C1,x∗为f(x)的一个局部极小点,则f(x∗)沿任意方向的一阶方向导数为0
2. 二阶充分条件:
设
f
(
x
)
∈
C
2
,
f
(
x
∗
)
沿任意方向的一阶方向导数为
0
,
当
f
(
x
∗
)
沿任意方向二阶方向导数为正时
,
x
∗
是严格的局部极小点
设f(x)\in C^2,f(x^*)沿任意方向的一阶方向导数为0,当f(x^*)沿任意方向二阶方向导数为正时,x^*是严格的局部极小点
设f(x)∈C2,f(x∗)沿任意方向的一阶方向导数为0,当f(x∗)沿任意方向二阶方向导数为正时,x∗是严格的局部极小点
学习过多元函数的话就能很快理解为什么可以把这两个条件和上面的两个条件等价, 比如说对于多元函数, 一阶导数向量为零等价于所有方向的方向导数为零是因为, 方向向量的导数就是一阶导数向量和一个方向向量的点乘
方法的特性
讲完了最优解相关的东西, 我们开始了解一下求解最优解方法的相关特性
我们先来掌握一些前置知识:
稳定点: g ( x ) = 0 g(x)=0 g(x)=0的点
线搜索方法
方法的基本结构:最优化问题的基本求解方法是迭代的算法, 因为无法直接求出解, 需要一步一步向最优解收敛才可以, 最优化方法主要包括: 线搜索方法, 信赖域方法
我们先来讨论线搜索方法的基本结构
以极大化问题为例子, 解决极大化问题可以类比成一个爬山的决策, 首先我们需要决定一个出发点, 然后我们要确定一个方向, 沿着这个方向走一定的路程, 接着停下来后极限寻找下一个方向, 这里我们只要保证每一次寻找的方向都是向上的方向, 那么在爬了足够长的路程后我们就可以爬到不能再往上爬的地方了,
当然这里有一个问题, 有人可能会问:一个方向可能在起点走一步是上升, 但是走两步可能就会下降, 怎么就能保证一定是上升的呢, 所以这里我们对步长的选取也有限定
那么回过头来看, 我们可以发现, 是否能通过这个决策方式爬上山, 主要取决与是否能找到上升的方向, 和是否能选取合适的步长
而最优化算法其实就是使用这样的迭代思想来求解的, 对于极小化问题我们同样可以用类似的思想实现
接下来我会用较为偏数学的方式解释一下"下山"(极小化问题)的步骤, 首先我们选取一个起始迭代点 x 0 ∈ R n x_0\in R^n x0∈Rn, 在这个点处, 选一个可以下降的方向, 比如说梯度方向 g 0 g_0 g0(正好也是下降最快的方向), 然后通过某种策略选取一个合适的步长 α 0 > 0 \alpha_0>0 α0>0, 就可以得到下一个迭代点 x 1 + α 0 g 0 x_1+\alpha_0g_0 x1+α0g0, 那么第k+1个迭代点就是 x k + 1 = x k + α k g k x_{k+1}=x_k+\alpha_kg_k xk+1=xk+αkgk, 且满足 f ( x k + 1 ) < f ( x k ) f(x_{k+1})<f(x_k) f(xk+1)<f(xk)
那么把问题拆分开来我们可以得到几个问题:
- 如何选取初始点
- 如何选取方向
- 如何选取步长
首先, 不排除存在一些有利于找到全局最优解的确定初始点的策略, 我们一般随机选取初始点, 或者在题目中会指定初始点位置
其次, 对于方向的选取, 我们只要求方向向量
d
d
d满足
∃
α
,
f
(
x
)
>
f
(
x
+
α
d
)
\exist\alpha,f(x)>f(x+\alpha d)
∃α,f(x)>f(x+αd), 而通过泰勒展开公式:
f
(
x
+
α
d
)
=
f
(
x
)
+
α
g
T
d
+
O
(
∣
∣
α
d
∣
∣
2
)
f(x+\alpha d)=f(x)+\alpha g^T d+O(||\alpha d||^2)
f(x+αd)=f(x)+αgTd+O(∣∣αd∣∣2), 可得方向向量需要满足
g
T
d
<
0
即可
g^Td<0即可
gTd<0即可, 几何上形容就是方向要和梯度方向的夹角为钝角
接下来我们就可以提出无约束最优化算法的基本结构(也就是线搜索型方法)的官方定义了:
- 给定初始点 x 0 ∈ R n , k : = 0 x_0\in R^n,k:=0 x0∈Rn,k:=0
- 若在 x k x_k xk点终止准则满足, 则输出有关信息, 停止迭代
- 确定 f ( x ) f(x) f(x)在 x k x_k xk处的下降方向 d k d_k dk
- 确定步长 α k \alpha_k αk, 使 f ( x k + α k d k ) f(x_k+\alpha_k d_k) f(xk+αkdk)较 f ( x k ) f(x_k) f(xk)有某种意义上的下降
- 令 x k + 1 = x k + α k d k , k = k + 1 ; x_{k+1}=x_k+\alpha_k d_k,k=k+1; xk+1=xk+αkdk,k=k+1;转第二步
这几个步骤中最主要的就是方向和步长, 而不同的策略方法可以得到不同的方向和步长, 这些不同的策略就是各种各样的无约束最优化算法
我们可以看到, 线搜索方法的主要流程是先确定方向再确定步长, 而信赖域方法是先限定步长的范围, 再同时确定方向和步长, 本书所涉及的方法以线搜索方法为主
需要强调的是, 这里我们约定好:
x ( k ) = ( x 1 ( k ) , x 2 ( k ) , ⋯ , x n ( k ) ) T x^{(k)}=(x^{(k)}_1,x^{(k)}_2,\cdots,x^{(k)}_n)^T x(k)=(x1(k),x2(k),⋯,xn(k))T
f k = f ( x k ) , g k = g ( x k ) , G k = G ( x k ) f_k=f(x_k), g_k=g(x_k), G_k=G(x_k) fk=f(xk),gk=g(xk),Gk=G(xk)
值得注意的是, 在上面的第二步中, 我们提到了"终止准则", 而在之前我们是没有定义的, 那么接下来我们就要开始解释"终止准则"了
顾名思义, 终止准则就是终止迭代的准则, 当满足终止准则的条件后, 就可以终止迭代了, 一般来说终止准则有一下几种定义:
- ∣ ∣ g ( x k ) ∣ ∣ ≤ ε ||g(x_k)||\leq \varepsilon ∣∣g(xk)∣∣≤ε
- ∣ ∣ x k − x k + 1 ∣ ∣ ≤ ε ||x_k-x_{k+1}||\leq \varepsilon ∣∣xk−xk+1∣∣≤ε
-
f
k
−
f
k
+
1
≤
ε
f_k-f_{k+1}\leq \varepsilon
fk−fk+1≤ε
这里的 ε \varepsilon ε表示一个无限趋于 0 + 0^+ 0+的数, 分别表示: - f ( x ) f(x) f(x)在 x k x_k xk点上的一阶导无限接近于0
- 当前迭代点和下一迭代点的距离无限小, 也就是迭代发生的变化微乎其微
- 迭代过后函数的变化微乎其微
当然了, 实际情况中我们肯定是要定义一个确定的足够小的 ε \varepsilon ε
对于这三个定义, 第一个定义如果是对于极小点处附近梯度变化很大的函数可能会导致迭代难以停止, 第二第三个定义都只顾及到了一个方面顾及到迭代点足够变化小却不一定函数值变化小, 函数值变化小而迭代点不一定变化小.
讲完了终止准则我们接下来开始介绍下一个知识点: 收敛速度
对于一个算法而言, 能否得到解很重要, 而能否相对快速得到解同样很重要, 在次基础上, 算法收敛的快慢成为了算法优劣评估的一种标准, 首先什么是收敛, 收敛的定义如下:
若一个算法产生的输出值{x_k}在某种范数|| ⋅ \cdot ⋅||意义下满足如下等式, 则称该算法收敛
lim k → ∞ ∣ ∣ x k − x ∗ ∣ ∣ = 0 \lim_{k\rightarrow\infty}||x_k-x^*||=0 k→∞lim∣∣xk−x∗∣∣=0
更进一步地, 如果这个算法从任何地方出发都可以收敛到X*则称这个算法有全局收敛性, 而如果是起始点足够接近X*时才能收敛到X*则称为局部收敛性
下面有几种收敛速度的定义:
- 线性收敛:
lim k → ∞ ∣ ∣ x k + 1 − x ∗ ∣ ∣ ∣ ∣ x k − x ∗ ∣ ∣ = a , a ∈ ( 0 , 1 ) \lim_{k\rightarrow\infty}\frac{||x_{k+1}-x^*||}{||x_k-x^*||}=a,a\in (0,1) k→∞lim∣∣xk−x∗∣∣∣∣xk+1−x∗∣∣=a,a∈(0,1)
- 超线性收敛:
lim k → ∞ ∣ ∣ x k + 1 − x ∗ ∣ ∣ ∣ ∣ x k − x ∗ ∣ ∣ = 0 \lim_{k\rightarrow\infty}\frac{||x_{k+1}-x^*||}{||x_k-x^*||}=0 k→∞lim∣∣xk−x∗∣∣∣∣xk+1−x∗∣∣=0
- 二阶收敛:
lim k → ∞ ∣ ∣ x k + 1 − x ∗ ∣ ∣ ∣ ∣ x k − x ∗ ∣ ∣ 2 = a , a ∈ R \lim_{k\rightarrow\infty}\frac{||x_{k+1}-x^*||}{||x_k-x^*||^2}=a,a\in R k→∞lim∣∣xk−x∗∣∣2∣∣xk+1−x∗∣∣=a,a∈R
一般来说具有超线性收敛速度和二阶收敛速度的算法是较快的了
而后又是一个新的知识点: 二次终止性
对于一个算法, 如果它对任意一个二次函数, 从任意初始起始点出发经过有限次迭代可以达到极小点, 我们就说该算法有二次终止性
假定在迭代点 x k x_k xk, 我们已经得到了迭代方向 d k d_k dk, 要得到步长 α k \alpha_k αk, 这种求步长的问题被称为一维搜索或线搜索问题, 其主要包含两个内容:
- 取步长要满足什么要求
- 满足了要求的步长具体怎么取
对于这个内容, 我们有两个最直观的方法:
-
精确线搜索准则:
在迭代点 x k x_k xk处, 迭代方向 d k d_k dk已知, 为了使得在这个方向上走得尽量到最低点, 我们要满足取 α = arg min f ( x k + α d k ) \alpha = \argmin f(x_k+\alpha d_k) α=argminf(xk+αdk), 由我们之前提到的一阶必要条件, 这个 f ( x k + α d k ) f(x_k+\alpha d_k) f(xk+αdk)函数对 α \alpha α求导得到 g k + 1 d k = 0 g_{k+1}d_k=0 gk+1dk=0从几何上理解比较容易, 就是沿着 d k d_k dk这个方向走一步, 这一步直接到达一个点, 在这个点上 d k d_k dk这个方向无法使得函数值降低, 也就是说步长一只增大知道无法下降为止, 这里给出了明确的公式求得步长, 但是实际情况中大多会有很大的n和很复杂的 f ( x ) f(x) f(x), 这步长的计算量是很大的, 实际上在迭代点尚且原理解时没必要使用高精度线搜索的, 而是使用非精确线搜索
-
非精确线搜索:
既然不好直接求解, 那我们给个范围吧, 我们只需要下一步的函数值下降就行, 那么就有: f ( x k + α d k ) < f ( x k ) f(x_k+\alpha d_k)<f(x_k) f(xk+αdk)<f(xk)
但是我们考虑如下图所示的情况:
我们会发现, 这两种图分别对应了步长过大和过小两种情况导致迭代始终无法收敛的情况, 而这两种情况都满足我们上面写的不等式, 这个反例可以说明, 仅仅满足上面那个不等式还不行, 我们还要防止步长过大和过小给步长另一个限制
首先我们来看看图(a), 我们发现迭代的后期, 当前迭代点和下一迭代点连线的斜率相当小, 导致几乎无法收敛到最优解, 但是如果我们强制要求这个斜率一定要比较陡的话, 这个情况就可以得到解决,
这样我们就提出了第一个准则:
Armijo准则:
这个准则就一个不等式: f ( x k + α d k ) ≤ f ( x k ) + ρ g k T d k α f(x_k+\alpha d_k)\leq f(x_k)+\rho g_k^T d_k \alpha f(xk+αdk)≤f(xk)+ρgkTdkα
其中 ρ ∈ ( 0 , 1 ) \rho \in (0,1) ρ∈(0,1), 这里左边就是下一迭代点的高度, 右边是过 ( x k , f ( x k ) ) (x_k,f(x_k)) (xk,f(xk))点的一条直线, 直线的斜率是 ( x k , f ( x k ) ) (x_k,f(x_k)) (xk,f(xk))点切线斜率的 ρ \rho ρ倍, 也就是斜率变平缓了大致图像如下:
通过调节 ρ \rho ρ的值我们可以要求迭代点下降的程度的下界, 保证了下一迭代点在数值上有一定量的下降, 而不是下降量>0即可,这样处理了步长过大的问题, 我们继续关注步长过小的问题, 对此就提出了:
Goldstein准则:
这个准则除了继承了Armijo准则的一条不等式之外, 又加上了另一条不等式: f ( x k + α d k ) ≥ f ( x k ) + ( 1 − ρ ) g k T d k α f(x_k+\alpha d_k)\geq f(x_k)+(1-\rho) g_k^T d_k \alpha f(xk+αdk)≥f(xk)+(1−ρ)gkTdkα
其中 ρ ∈ ( 0 , 1 / 2 ) \rho \in (0,1/2) ρ∈(0,1/2), 可以明显看出来, 这是延续了Armijo的思想, 同样是通过调整 ρ \rho ρ使得在下一迭代点在数值上有一定量的下降, 只不过是通过两条直线, 确定了步长选取的合适范围, 保证在这个范围内步长不算过长也不算过短
除此之外还有一个准则和Goldstein准则不太一样
Wolfe准则:
wolfe准则也是在Armijo准则的基础上加上一个不等式 g ( x k + α d k ) T d k ≥ σ g k T d k g(x_k+\alpha d_k)^T d_k\geq \sigma g_k^T d_k g(xk+αdk)Tdk≥σgkTdk
有 1 > σ > ρ > 0 1>\sigma>\rho>0 1>σ>ρ>0, 我们发现, 在不断迭代到最低点的过程中梯度是不断向0靠近的, 而如果迭代步长过小, 不仅可以从函数值变化上看出来, 也可以从函数值导数变化量上看出来, 这里的不等式就是要求下一迭代点切线的斜率要比原迭代点切线斜率一定程度上变平缓后还要平缓, 保证了迭代步长不会过小
这里的"原迭代点切线斜率平缓化"是由 σ \sigma σ决定的, 那么如果我们把这个值赋值足够接近0, 那么岂不直接就是精确线搜索准则了? 实则不然, 这里让 σ = 0 \sigma=0 σ=0会得到不等式 g ( x k + α d k ) T d k ≥ 0 g(x_k+\alpha d_k)^T d_k\geq 0 g(xk+αdk)Tdk≥0也就是说只要下一迭代点导数大于0就可以, 这不一定是逼近最低点, 也有可能是震荡的情况, 所以进一步提出了
强Wolfe准则:
这次的强wolfe准则把不等式 g ( x k + α d k ) T d k ≥ σ g k T d k g(x_k+\alpha d_k)^T d_k\geq \sigma g_k^T d_k g(xk+αdk)Tdk≥σgkTdk改成了 ∣ g ( x k + α d k ) T d k ∣ ≤ − σ g k T d k |g(x_k+\alpha d_k)^T d_k|\leq -\sigma g_k^T d_k ∣g(xk+αdk)Tdk∣≤−σgkTdk
这时候我们就发现, 在这个不等式的约束下, σ \sigma σ给的值越小, 步长的选取越接近精确线搜索结果
上面我详细解释一下几种非精确线搜索的准则, 处于学习的目的, 我们可以来思考一下这两个问题:
- 满足非精确线搜索准则的步长存在吗
- 收敛性可以保证吗
当然了, 既然这些方法可以被写入教材, 那肯定是可行的方法, 不过我们要知其然且知其所以然
首先, 这里课本给出了非精确线搜索步长存在性定理:
设 f ( x k + α d k ) f(x_k+\alpha d_k) f(xk+αdk)在 α > 0 \alpha >0 α>0时有下界, 且 g k T d k < 0 g_k^T d_k<0 gkTdk<0, 则必存在 α k \alpha_k αk, 在点 x k + α k d k x_k+\alpha_k d_k xk+αkdk满足Wolfe准则或Goldstein准则
我们不妨分别来证明一下:
首先由泰勒公式有
:
f
(
x
k
+
α
d
k
)
=
f
(
x
k
)
+
g
k
T
d
k
α
+
O
(
∣
∣
α
d
k
∣
∣
2
)
因为
g
k
T
d
k
<
0
,
所以
g
k
T
d
k
<
ρ
g
k
T
d
k
,
有
f
(
x
k
+
α
d
k
)
<
f
(
x
k
)
+
ρ
g
k
T
d
k
α
同理有
:
f
(
x
k
+
α
d
k
)
<
f
(
x
k
)
+
(
1
−
ρ
)
g
k
T
d
k
α
由条件可知
,
原函数有下界
,
而这两条直线
{
f
(
x
k
)
+
(
1
−
ρ
)
g
k
T
d
k
α
和
f
(
x
k
)
+
ρ
g
k
T
d
k
α
}
都单调递减
显然会分别有交点
α
1
,
α
2
,
则
α
∈
[
α
1
,
α
2
]
肯定满足
G
o
l
d
s
t
e
i
n
准则
首先由泰勒公式有:\\\ f(x_k+\alpha d_k)=f(x_k)+g_k^T d_k \alpha +O(||\alpha d_k||^2)\\ 因为g_k^T d_k<0, 所以g_k^T d_k<\rho g_k^T d_k, 有f(x_k+\alpha d_k)<f(x_k)+\rho g_k^T d_k \alpha\\ 同理有: f(x_k+\alpha d_k)<f(x_k)+(1-\rho) g_k^T d_k \alpha\\ 由条件可知, 原函数有下界, 而这两条直线\{f(x_k)+(1-\rho) g_k^T d_k \alpha和f(x_k)+\rho g_k^T d_k \alpha\}都单调递减\\ 显然会分别有交点\alpha_1, \alpha_2, 则\alpha \in [\alpha_1, \alpha_2]肯定满足Goldstein准则
首先由泰勒公式有: f(xk+αdk)=f(xk)+gkTdkα+O(∣∣αdk∣∣2)因为gkTdk<0,所以gkTdk<ρgkTdk,有f(xk+αdk)<f(xk)+ρgkTdkα同理有:f(xk+αdk)<f(xk)+(1−ρ)gkTdkα由条件可知,原函数有下界,而这两条直线{f(xk)+(1−ρ)gkTdkα和f(xk)+ρgkTdkα}都单调递减显然会分别有交点α1,α2,则α∈[α1,α2]肯定满足Goldstein准则
上述证明了Goldstein准则的步长存在性定理
下面证明Wolfe准则的步长存在性定理
根据中值定理
,
在区间
(
0
,
α
1
)
中存在
α
k
有
f
(
x
k
+
α
1
d
k
)
=
f
(
x
k
)
+
α
1
g
(
x
k
+
α
k
d
k
)
T
d
k
即
g
(
x
k
+
α
k
d
k
)
T
d
k
=
f
(
x
k
+
α
1
d
k
)
−
f
(
x
k
)
α
1
=
ρ
g
k
T
d
k
>
σ
g
k
T
d
k
即
x
k
满足
w
o
l
f
e
准则
根据中值定理,在区间(0, \alpha_1)中存在\alpha_k\\ 有f(x_k+\alpha_1 d_k)=f(x_k)+\alpha_1 g(x_k+\alpha_k d_k)^T d_k\\ 即g(x_k+\alpha_k d_k)^Td_k=\frac{f(x_k+\alpha_1 d_k)-f(x_k)}{\alpha_1}=\rho g_k^T d_k>\sigma g_k^T d_k\\ 即x_k满足wolfe准则
根据中值定理,在区间(0,α1)中存在αk有f(xk+α1dk)=f(xk)+α1g(xk+αkdk)Tdk即g(xk+αkdk)Tdk=α1f(xk+α1dk)−f(xk)=ρgkTdk>σgkTdk即xk满足wolfe准则
其次, 我们有非精确线搜索收敛性的定理如下:
设在水平集 { x ∣ f ( x ) ≤ f ( x 0 ) } \{x|f(x)\le f(x_0)\} {x∣f(x)≤f(x0)}上, f ( x ) f(x) f(x)有下界, g ( x ) g(x) g(x)一致连续, 方向 d k d_k dk与 − g k -g_k −gk之间的夹角 Θ k \Theta_k Θk一致有界, 即对某一 μ > 0 \mu>0 μ>0有; 0 ≤ Θ k ≤ π 2 − μ , ∀ k 0\le \Theta_k \le \frac{\pi}{2}-\mu,\forall k 0≤Θk≤2π−μ,∀k若Wolfe准则对任意给定k都成立, 则或者存在N, 使 g ( N ) = 0 g(N)=0 g(N)=0或者 g ( N ) → , k → ∞ g(N)\rightarrow ,k\rightarrow \infty g(N)→,k→∞
这里的证明书上有, 我就不多赘述了
这里的(2.12)和(2.13)就是Wolfe准则的第一和第二条不等式
ok, 说完了精确线搜索和非精确线搜索之后, 等等…我们好像还没有说完, 我们回顾一下, 精确线搜索实际上就是通过数学公式推导的方式之间求出问题答案的解析解, 这样解在符合准则的前提下同时就被求出来了, 而后我们因为求精确解的计算量大选择只要求解符合准则, 但是我们好像还没提如何求出符合准则的具体的解呢
那么接下来, 我们开始介绍两类符合上面提及的线搜索准则的算法: 0.618方法和插值法
首先我们来看0.618方法
- 0.618方法
先大致介绍一下0.618方法的基本步骤, 首先对于一个在区间[a, b]上的单峰函数(函数形状高-低-高, 类似二次函数) φ ( α ) \varphi(\alpha) φ(α), 其中存在一个点 α ∗ \alpha^* α∗使得 φ ( α ) \varphi(\alpha) φ(α)在区间[a, α ∗ \alpha^* α∗]单调递减, 在区间[ α ∗ \alpha^* α∗, b]单调递增, 然后不断按0.618的比例将这个区间缩小, 但是保证这个最低点始终在缩小后的区间之中, 这样当区间缩小到足够小之后, 就可以取区间的中间值近似这个最小点
具体步骤:
- 先用进退法求初始搜索区间, 也就是找到[a,b]区间使得函数是高-低-高的形状
- 使用0.618方法迭代
可以看出, 这个方法的核心就是同时把边界向中间缩小, 保留函数值下降不那么多的一边的迭代结果, 反复迭代, 这里的0.618你如果高兴自然也可以取0.7, 0.6, 只不过黄金分割比之所以被采用, 是因为它在理论上证明了在不增加函数评估次数的情况下能够提供最佳收敛效率, 如果选择其他的数值可能导致迭代效率下降
- 多项式插值法
多项式插值法是一种通过构造一个多项式函数来逼近已知数据点的方法, 其核心思想是找到一个次数尽可能低的多项式, 使得该多项式在给定的数据点上精确地通过, 比如说我们有n+1个不同的点已知, 构造的函数 p ( α ) p(\alpha) p(α)满足 p ( α i ) = φ ( α i ) , i = 0 , 1 , . . . , n p(\alpha_i)=\varphi(\alpha_i),i=0,1,...,n p(αi)=φ(αi),i=0,1,...,n,这个条件称为插值条件, 这里的 α 0 , . . . \alpha_0,... α0,...称为插值节点, p ( α ) p(\alpha) p(α)称为插值多项式, φ ( α ) \varphi(\alpha) φ(α)称为被插函数
这里具体提出一个例子, 两点二次插值法求步长:
设0,
α
0
>
0
\alpha_0>0
α0>0这两个点已知,
φ
(
0
)
=
f
(
x
k
)
,
φ
′
(
0
)
=
g
k
T
d
k
,
φ
(
α
0
)
=
f
(
x
k
+
α
0
d
k
)
\varphi(0)=f(x_k), \varphi'(0)=g^T_kd_k, \varphi(\alpha_0)=f(x_k+\alpha_0d_k)
φ(0)=f(xk),φ′(0)=gkTdk,φ(α0)=f(xk+α0dk)
假定在
α
0
\alpha_0
α0处Armjio准则不满足(所以不能直接取
α
0
\alpha_0
α0作步长), 构造:
p
(
α
)
=
a
α
2
+
b
α
+
c
p(\alpha)=a\alpha^2+b\alpha+c
p(α)=aα2+bα+c
满足:
p
(
0
)
=
φ
(
0
)
,
p
′
(
0
)
=
φ
′
(
0
)
,
p
(
α
0
)
=
φ
(
α
0
)
p(0)=\varphi(0),p'(0)=\varphi'(0),p(\alpha_0)=\varphi(\alpha_0)
p(0)=φ(0),p′(0)=φ′(0),p(α0)=φ(α0)
全部带入求解出abc, 则:
p
(
α
)
=
φ
(
α
0
)
−
φ
(
0
)
−
φ
′
(
0
)
α
0
α
0
2
α
2
+
φ
′
(
0
)
α
+
φ
(
0
)
p(\alpha)=\frac{\varphi(\alpha_0)-\varphi(0)-\varphi'(0)\alpha_0}{\alpha_0^2}\alpha^2+\varphi'(0)\alpha+\varphi(0)
p(α)=α02φ(α0)−φ(0)−φ′(0)α0α2+φ′(0)α+φ(0)
令这个函数一阶导等于0, 则
p
(
α
)
p(\alpha)
p(α)的稳定点为:
α
1
=
−
φ
′
(
0
)
α
0
2
2
[
φ
(
α
0
)
−
φ
(
0
)
−
φ
′
(
0
)
α
0
]
\alpha_1=\frac{-\varphi'(0)\alpha_0^2}{2[\varphi(\alpha_0)-\varphi(0)-\varphi'(0)\alpha_0]}
α1=2[φ(α0)−φ(0)−φ′(0)α0]−φ′(0)α02
上面这个就是多项式插值法的一种, 除此之外还有三点三次插值法, 这里不多赘述
信赖域方法
到此为止我们才算基本介绍完线搜索方法, 接下来我们开始介绍上面提到过的和线搜索并列的信赖域方法
我们原来的问题是 min f ( x k + d ) \min f(x_k+d) minf(xk+d)确定这个d, 也就是确定迭代的步长和方向, 我们可以在d不是很长的情况下用一阶或二阶泰勒展开来近似拟合这个原函数, 然后用对泰勒展开式求解原题, 本书涉及的信赖域方法使用的是二阶近似, 我们计这个函数为 q k ( d ) q_k(d) qk(d), 也就是说问题变成了求解 min q k ( d ) \min q_k(d) minqk(d)得到 d k d_k dk
上面我们提及, 如果d 不是很大我们是可以使用近似的, 那么显然, 这个函数近似的好坏受到了d大小的影响, 也就是 x k x_k xk处领域大小的影响, 这个领域自然也不能太小, 正如先前提及的, 太小的步长会使得收敛变得很慢, 这个领域就是信赖域, 在这个信赖域中, 我们坚信 q k ( d ) q_k(d) qk(d)是 f ( x k + d ) f(x_k+d) f(xk+d)很好的近似函数
具体算法
这里我来说明一下, Δ \Delta Δ表示信赖域半径, γ k = Δ f k Δ q k \gamma_k=\frac{\Delta f_k}{\Delta q_k} γk=ΔqkΔfk表示实际函数减少量和拟合函数减少量之比, 反应了拟合的好不好, (2.22)公式就是求 γ k \gamma_k γk
简述一下步骤就是根据初始半径和拟合函数同时求解出方向和步长(方向向量), 根据 γ k \gamma_k γk查看这个方向向量选的好不好, 如果好就扩大半径, 不好就缩小半径, 一般般就保持不变, 方向都搞错了的话就退回上一步, 不断迭代直至满足终止准则
具有上面这个结构的算法都是信赖域方法, 当然这里选取近似函数和信赖域修正的方式都是多种多样的
以上就是数值最优化的第二章的内容
标签：xk,frac,dk,迭代,无约束,步长,alpha,方法,最优化 From： https://blog.csdn.net/qq_37998735/article/details/143369635