最优化之最速下降法
- 格式:ppt
- 大小:3.22 MB
- 文档页数:16
最优化方法与应用大作业(一)
---最速下降法部分:
1.问题描述:
用梯度下降法求解以下优化问题
min f(x)=(x1+10*x2)^2+5(x3-x4)^2+(x2-2*x3)^4+10*(x1-x4)^4
2.编程感想:
该算法需要计算Hesse矩阵,C语言在向量运算时没有Matlab方便,所以手工完成了理论计算,再输入,破坏了程序的移植性。
同时,实验表明当初始值离理想点较远且精度要求较高时,最速下降法的收敛速率极慢,迭代几乎不可能完成,这对初值的选取提出了一定限制。
3.结果分析:
编译界面(Mac os X,Xcode环境)
输入参数(设定为(0.1,0.2,0.3,0.4)):
结果(此处列出每次迭代结果)。
明显的看到,最速下降法的收敛较慢,最终结果接近理论值(F(0,0,0,0)=0)所以该结果可以满意。
4.算法代码见下页
西安电子科技大学电子工程学院020951
李骏昊02095005。
最优化Armijo算法确定步长的最速下降法资料最速下降法是最优化算法中最简单、最基础的一种方法,但其收敛速度较慢且容易陷入局部最优解。
因此,在最速下降法的基础上,可以通过引入步长的方法来提高算法的收敛速度。
而Armijo算法就是一种常见的用于确定步长的方法。
最速下降法基础假设我们要最小化目标函数f(x),那么最速下降法的思路就是从一个初始点x0开始,不断朝着负梯度方向进行迭代,直到找到最优解x∗,即:$x_{k+1} = x_k - \\alpha_k \ abla f(x_k)$其中,ablaf(x k)是f(x)在x k处的梯度,$\\alpha_k$ 是步长(也称为学习率),表示每次迭代的步长大小。
但这里还有一个问题:如何确定每次迭代的步长呢?Armijo算法Armijo算法是一种基于梯度下降法的步长确定方法。
它的思路是,每次迭代的步长不应该过大,否则容易导致超出收敛区域。
同时,步长也不应该过小,否则收敛速度会变得非常缓慢。
因此,步长的大小应该恰到好处,即在一定范围内找到一个最优的步长大小。
具体地,Armijo算法通过二分搜索的方法,在可行步长范围内找到一个最优的步长 $\\alpha_k$。
具体过程如下:1.首先初始化 $\\alpha_0$,并设定一些参数,如尝试步长大小t、可行步长下界 $\\tau$ 和函数下降的最小比例 $\\gamma$。
2.计算目标函数f(x k−t ablaf(x k)),以及根据一定准则确定下一个$\\alpha$。
3.如果 $f(x_k - \\alpha_k\ abla f(x_k))$ 函数值比f(x k)减小了一些比例$\\gamma$,则认为当前 $\\alpha_k$ 是可行的步长。
4.如果当前 $\\alpha_k$ 不是可行的步长,则将其折半,即 $\\alpha_k\\leftarrow \\alpha_k/2$,直到找到一个可行的步长为止。
随着人工智能、模糊控制、模式识别、人工网络等新技术的应用和发展。
可以让它们与广义预测控制相结合,建立高精度、多模态的预测模型。
使广义预测控制在异常情况下可以稳定运行,推进广义预测控制的进一步发展。
2.2.1最速下降法最速下降法是无约束最优化中是比较有效的方法,它是以d}=一可(x})作为下降方向的算法。
其迭代格式为xx+i=xx一。
*Of (xk)上式中,一般通过精确线搜索准则求得步长因子。
*,当然也不排除可以利用非精确线搜索准则来求得步长因子。
*。
不管最速下降法采取何种线搜索准则,它均具有全局收敛性,但是这也不能直接就认为最速下降算法就是一个良好的优化算法。
在实际试验中,有很多优化问题利用最速下降法并不是下降的特快,反而下将的十分缓慢。
这是因为出现了锯齿现象:就是在计算过程中,最速下降法开始几步还是挺快的,但是当目标函数f (x)的等高线接近于一个球的时候,就出现了类似锯齿现象,前进十分缓慢,降低了算法的效能。
2.2.12.2.2牛顿法牛顿法也是无约束最优化问题中的一种经典算法,它是利用目标函数.f (x)的二次泰勒展开式,并将二次泰勒展开式进行极小化。
其迭代格式为x}+}=xA十d}(2-5)其中步长因子。
、=l} d、为02f (x} )d + Of (xA ) = 0的解。
当目标函数f(x)是正定二次函数的时候,牛顿法可以一步达到最优解;当目标函数f (x)是非二次函数的时候,牛顿法经过有限次迭代之后就不能确保求得目标函数f (x)的最优解。
我们知道目标函数f (x)在极小点附近是很接近于二次函数的,所以,假如初始点非常靠近无约束最优化问题((1-1)的最优解x的时候,并且}Z.f (x.)正定的时候,那么牛顿法就会有很快的收敛速度,而由此算法产生的点列也具有了超线性收敛速度,同时还在一定条件下具有二次收敛性;假如初始点与无约束最优化问题(1-1)的最优解x’相距比较远的时候,这时的}Z.}(x})就不一定是正定的了,也就存在了一个问题,那就是此时的牛顿方向就不一定是下降方向,有可能是上升方向,此时由此算法产生的点列可能也就不收敛于无约束最优化问题((1-1)的最优解了。