数值优化｜线搜索方法_星辉-星辉娱乐-官方指定站

数值优化｜线搜索方法

2024-06-10行业资讯

上一节主要学习了无约束优化问题的解的条件，这一节主要学习优化问题求解中步长的确定

求解最优化问题的基本方法是迭代算法，迭代算法是指采用逐步逼近的计算方法来逼近精确解，即选择一个初始点 $x_0$ 后，根据迭代算法生成 $x_1,x_2,...,x_k$ ，使得 $x^\\rightarrow x^*$ ，其中 $x^*$ 为精确解。最优化方法有两种求解方式

线搜索方法
信赖域方法

首先介绍线搜索方法

给定初始点 $x^0$ ，k=0
判断 $x^k$ 是否满足终止条件，是，则终止
寻找 $x^k$ 处的下降方向 $d^k$
选择合适的的步长 $\\alpha_k > 0$ ，使得 $f(x^k+\\alpha_kd^k)< f(x^k)$
令 $x^{k+1}:=x^k+\\alpha_kd^k,k:=k+1$ 转步骤2

这个算法中需要解决三个问题

算法什么时候终止，即终止条件是什么
下降方向如何选择
步长的确定，步长的确定也被称为一维搜索【因为只有一个变量】或线搜索问题

这一节将先解决问题1和3，第二个问题的解决将留到下一节中介绍

其他说明：线搜索方法和信赖域方法的区别在于是先选择下降的方向还是先选择步长，线搜索方法在 $x_k$ 点求得下降方向 $d^k$ 在沿 $d^k$ 确定步长 $\\alpha^k$ ，而信赖域方法是先限定步长的范围，再同时确定下降方向 $d^k$ 和步长 $\\alpha^k$

判断算法的终止条件主要有三种

$\\|\\bigtriangledown f(x)\\| \\leq \\varepsilon$

根据最优解的一阶必要条件，最优解 $x^*$ 为平稳定满足 $\\bigtriangledown f(x)=0$ ，因此可以使用

$\\|\\bigtriangledown f(x)\\| \\leq \\varepsilon\\\\$ 作为终止条件

缺点：

$\\varepsilon$ 的选择大小将决定迭代点 $x^k$ 近似 $x^*$ 的精度
对于最优解邻域内比较陡函数，即使该邻域中的点已经相当接近极小点，其梯度仍有可能较大，从而迭代很难停止

$\\|x^k-x^{k+1}\\|\\leq \\varepsilon$

即迭代点的改变很小

$f(x^k)-f(k^{k+1}) \\leq \\varepsilon$

即目标函数的改善非常小

第二种和第三种终止条件的缺点：无法保证 $\\|x^k-x^*\\|$ 或 $f(x^k)-f(x^{k+1})$ 足够小，即无法保证终止时 $x^k$ 非常接近 $x^*$

已经确定好了下降方向，现在需要确定步长，使得 $f(x^k+\\alpha d^k)$ 最小，记

$f(x^k+\\alpha d^k) :=\\phi(\\alpha)\\\\$ 因为迭代点 $x^k$ 和下降方向 $d^k$ 已知，因此 $f(x^k+\\alpha d^k)$ 是关于 $\\alpha$ 的一元函数

因此线搜索问题转换为求解一元函数最优解的问题，即

$\\alpha^k=\\min \\{\\phi(\\alpha):=f(x^k+\\alpha d^k)|\\alpha > 0 \\}\\\\$ $\\alpha^k$ 表示第 $k$ 次迭代过程中 $\\phi(\\alpha)$ 的最小点

求解 $\\alpha^k$ 的方法主要有：

精确线性搜索
直接搜索
不精确线性搜索

根据最优解的一阶必要条件， $\\alpha ^k$ 满足

$\\phi^{'}(\\alpha)=\\bigtriangledown f(x^k+\\alpha d^k)^T d^k=0\\\\$ 解出等式的解以后需要通过通过Hessen矩阵判断是否为最优解

缺点：

求解梯度和Hessen矩阵计算量大
对于一些非光滑函数【即可导函数】或导数表达式复杂的函数无法应用精确搜索法

对于精确线性搜索存在的问题，可以采用直接搜索法去求解步长。一般都采用基于搜索区间的直接搜索法，直接搜索法要求事先知道一个包含最优解 $\\alpha^k$ 的搜索区间

搜索区间的定义：设 $\\alpha^k$ 是 $\\phi(\\alpha)$ 的极小点，若存在区间 $[a,b]$ ，使得 $a^k \\in[a,b]$ ，并且要求 $\\phi(\\alpha)$ 在此区间是单峰函数。即搜索区间需要满足两个条件

包含极小点 $\\alpha^k$
在该区间 $\\phi(\\alpha)$ 是单峰函数

单峰函数的定义：若存在 $\\alpha^k \\in[a,b]$ ，使 $\\phi(\\alpha)$ 在 $[a,\\alpha^k]$ 上单调下降，在 $[\\alpha^k,b]$ 上单调上升，则称 $\\phi(\\alpha)$ 是区间 $[a,b]$ 上的单峰函数，

搜索区间的确定：

采用进退法求初始区间 $[a,b]$ ，该方法的基本思路是先选定一个初始点 $\\alpha_0 > 0$ 和一个初始步长 $\\gamma_0$ ，从 $\\alpha_0$ 起以 $\\gamma_0$ 为步长向前搜索一步得 $\\alpha_0+\\gamma_0$ 。若该点的目标函数值较 $\\alpha_0$ 处的目标函数值减小了，则加大 $\\gamma_0$ 继续向前搜索，直到新一点目标函数值较前一点的目标函数值大则停止；否则从 $\\alpha_0$ 为初始点以 $-\\gamma_0$ 为初始步长向反方向进行搜索

直接搜索法的思想：确定了初始区间 $[a,b]$ ，如果区间较大求解将非常困难，因此一个思路是不断缩小区间 $[a,b]$ 但仍需保证 $\\alpha^k$ 在缩小后的区间内，将 $[a,b]$ 缩小到很小的区间时，可以任取区间内的一点 $\\alpha$ 近似于 $\\alpha^k$ 。因此需要不断的缩小搜索区间，选取两点 $\\lambda,\\mu \\in[a,b]$ ，且 $\\lambda < \\mu$

若 $\\phi(\\lambda) < \\phi(\\mu)$ ，则得到新得搜索区间 $[a_1,b_1]:=[a,\\mu]$
若 $\\phi(\\lambda) > \\phi(\\mu)$ ，则得到新得搜索区间 $[a_1,b_1]:=[\\lambda,b]$

常见的直接搜索法：

设 $\\phi(\\alpha)$ 是区间 $[a,b]$ 上的单峰函数，令

$[a,b]=[a_0,b_0]\\\\$

均匀搜索法

令 $\\delta=\\frac{b_0-a_0}{N},\\alpha_i=a_0+i\\delta,i=1,2,...,N-1$ ，即将初始区间N等分，比较相邻三个点对应的函数值，若对于某个 $i$ 有

$\\phi(\\alpha_{i-1}) > \\phi(\\alpha_i) < \\phi(\\alpha_{i+1})\\\\$ 则 $\\alpha^k \\in[\\alpha_{i-1},\\alpha_{i+1}]$ ，则得到新的搜索区间 $[a_1,b_1]=[\\alpha_{i-1},\\alpha_{i+1}]$ 。选取新区间以后继续重复上述过程，该算法进行一次搜索区间将缩小为原搜索区间的 $\\frac{2}{N}$

0.618法【黄金分割法】

令 $\ au=\\frac{\\sqrt{5}-1}{2}\\approx 0.618\\\\$ 在搜索区间 $[a_0,b_0]$ 中插入两个试探点 $\\lambda,\\mu$ ，其中

$\\lambda=a_0+(1-\ au)(b_0-a_0),\\mu=a_0+\ au(b_0-a_0)\\\\$ 即 $\\frac{\\mu-a_0}{b_0-a_0}=\\frac{b_0-\\lambda}{b_0-a_0}=\\frac{\\lambda-a_0}{u-a_0}\\approx 0.618\\\\$ 若 $\\phi(\\lambda) < \\phi(\\mu)$ ，则 $\\alpha^k \\in[a_0,\\mu]$ ，产生新的搜索区间 $[a_1,b_1]=[a_0,\\mu]$ ，反之产生的新区间为 $[a_1,b_1]=[\\lambda,b]$ 。选取新区间以后继续重复上述过程直至 $b_i-a_i < \\varepsilon$ 则停止迭代，此时 $\\alpha^k=\\frac{b_i+a_i}{2}$ 。该算法进行一次搜索区间将缩小为原区间的 $0.618$

0.618法和均匀搜索法相比

基于导数信息的二分法

记区间的中点 $\\lambda=\\frac{a_0+b_0}{2}$ ，计算该点的导数值 $\\phi^{'}(\\lambda)$

若 $\\phi^{'}(\\lambda)=0$ ，则 $\\alpha^k=\\lambda$

若 $\\phi^{'}(\\lambda)<0$ ，则 $\\alpha^k \\in[\\lambda, b_0]$ ，产生新的搜索区间 $[a_1,b_1]=[\\lambda, b_0]$

若 $\\phi^{'}(\\lambda)> 0$ ，则 $\\alpha^k \\in[a_0,\\lambda]$ ，产生新的搜索区间 $[a_1,b_1]=[a_0,\\lambda]$

选取新区间以后重新选取中点继续上述过程，该算法进行一次搜索区间将缩小为原搜索区间的 $\\frac{1}{2}$

采用精确搜索法和直接搜索法求解 $\\alpha^k$ 虽然会使得目标函数在每次迭代中下降较多，但计算量非常大，没必要将线性搜索搞得十分精准，特别在计算的初始阶段，此时迭代点 $x^k$ 离目标函数的最优解还很远，过分地追求线性搜索的精度会降低整个方法的效率。可以适当放松对 $\\alpha^k$ 的要求，只要求满足适当的条件即为 $\\phi(\\alpha)$ 的最优解

4.3.1 Armijo条件

设 $0 < c_1 < 1$ ，若 $\\phi(\\alpha)$ 满足

$\\phi(\\alpha) \\leq \\phi(0)+c_1\\alpha\\phi^{'}(0)\\\\$ 当 $c_1=0$ 时， $\\phi(0)+c_1\\alpha\\phi^{'}(0)=\\phi(0)$ ，图像是一条直线

当 $c_1=1$ 时， $\\phi(0)+c_1\\alpha\\phi^{'}(0)=\\phi(0)+c_1\\phi^{'}(0)$ ，图像是在点 $\\phi(0)$ 的切线

结合图像

4.3.2 Goldsteint条件

称除了满足 Armijo条件以外，还需要满足

$\\phi(\\alpha) \\geq \\phi(0)+c_2\\alpha\\phi^{'}(0)\\\\$ 其中 $c_2$ 满足 $0 <c_1 < c_2 < 1$

结合图像

对一个算法除了要考虑步长及梯度方向的选择以外，还需考虑算法的收敛性，在算法收敛的情况下还需要考虑算法的收敛速度，因为算法的收敛性是判断一个算法优劣的重要标准

若一个算法产生的迭代序列 $\\{x^k\\}$ 在某种范数 $\\|.\\|$ 下满足 $\\lim_{k \\rightarrow \\infty}\\|x^k-x^*\\|=0\\\\$ 则称这个算法是收敛的，进一步根据初始点 $x^0$ 选取的不同，可以进一步将收敛性分为：

全局收敛性：从任意初始点 $x^0$ 出发， $\\{x^k\\}$ 都能收敛到 $x^*$
局部收敛性：当初始点 $x^0$ 与 $x^*$ 充分接近时， $\\{x^k\\}$ 才能收敛到 $x^*$

设迭代序列 $\\{x^k\\}$ 收敛到 $x^*$ ，若存在极限 $\\lim_{k \\rightarrow \\infty}{\\frac{\\|x^{k+1}-x^*\\|}{\\|x^k-x^*\\|}}=\\beta\\\\$ 当 $0 < \\beta < 1$ 时，称迭代序列 $\\{x^k\\}$ 是线性收敛的

当 $\\beta=0$ 时，称迭代序列 $\\{x^k\\}$ 是超线性收敛的

若存在 $p>1$ ，极限满足 $\\lim_{k \\rightarrow \\infty}{\\frac{\\|x^{k+1}-x^*\\|}{\\|x^k-x^*\\|^p}}=\\beta\\\\$ 则称迭代序列 $\\{x^k\\}$ 是 $p$ 阶收敛的，一般通常考虑二阶收敛，并且 $p$ 阶收敛必为超线性收敛

证明：

对极限做一个如下变形

$\\lim_{k \\rightarrow \\infty}{\\frac{\\|x^{k+1}-x^*\\|}{\\|x^k-x^*\\|^p}}=\\lim_{k \\rightarrow \\infty}{\\frac{\\|x^{k+1}-x^*\\|}{\\|x^k-x^*\\|}}{\\frac{1}{\\|x^k-x^*\\|^{p-1}}}\\\\$ 当 $k \\rightarrow \\infty$ ， $\\|x^k-x^*\\|$ 将非常小，因此 $\\frac{1}{\\|x^k-x^*\\|^{p-1}}\\\\$

将非常大，若 $\\lim_{k \\rightarrow \\infty}{\\frac{\\|x^{k+1}-x^*\\|}{\\|x^k-x^*\\|^p}}\\\\$ 收敛，则 ${\\frac{\\|x^{k+1}-x^*\\|}{\\|x^k-x^*\\|}}\\rightarrow 0\\\\$ 因此此时是满足超线性收敛的

收敛速度比较：线性收敛 < 超线性收敛 < $p$ 阶收敛

对于一个算法，如果它对任意的正定二次型，从任意初始点出发，可以经有限步迭代求得极小值点，则称该算法具有二次终止性

星辉动态
公司动态
行业资讯

联系信息
电话：400-123-4657
手机：13800000000
邮箱：admin@youweb.com
传真：+86-123-4567
地址：广东省广州市天河区88号

星辉动态
国内考研和出国读研：哪个更划算？是不是去国外更好些？ 2024-11-04
自考生申请美国文学硕士可以吗？有什么条件？ 2024-11-04
出国留学的好处有哪些？_4 2024-11-04
中国美术学院硕士留学申请指南 2024-11-04

您当前位置：