《最速下降法基本原理分析综述》2000字

最速下降法基本原理分析综述(一)无约束问题的最优性条件本文给出了一些关于求解非限制问题的最佳解决方案的基本前提和充分条件。定理1设f:Rn→R1在点X∈Rn处可微，如果有P∈Rn定理2设f:Rn→R1在点X∗∈Rn上可微，如果X∗是非约束问题的局部最优解，那么X∗就是函数上述定理指出，当我们得到了一个局部最优解时，且得到的梯度为0，那么就说明此时是该点的局部最优解的必要条件。定理3设f:Rn→R1在点X∗∈Rn上的Hesse矩阵∇2f(定理4设f:Rn→R1，X∗∈Rn，f是则X∗(二)最速下降法的基本思想和迭代步骤最速下降法是1847年著名数学家柯西提出的，它是最早的一种分析方法。其它的分析方法不是由其变化就是由其所启发，因此这是最优化方法的基础。这是一种最基本的算法，是实现最优解的关键。该方法具有工作量小、存储小、对起始点要求不高等特点；但其不足之处在于，其收敛速度较慢、效率较低，且往往无法达到最优解。非线性规划问题的主要目标是求解非线性函数的最优解。其理论与方法在军事、经济、管理等领域有着广阔的应用前景。在多维无约束的条件下，最优的解法应该是最速下降法。最速下降法是只需要考察目前的下降速度，而无法得到全部体现，所以它又可以叫瞎子爬山法。最速下降迭代法这是一个用于解决非线性规划问题的迭代法，其核心问题是如何求算出每个迭代的方向pk和步长t（1）搜索方向pk方向pk为单位量，pk=1，从X(k)按方向pkf可以得到在X(k)lim如果要使X(k+1)处的目标函数值比X(k∇θ为两向量之间的夹角。为了使单位时间内下降速度最快，即cosθ应取得最小值，即cosθ=−1，即pk从上述我们可以确定最速下降法的搜索方向为pk（2）求解搜索步长t。最速下降法采取的搜索步长的方法有两种：a.最优步长搜索法即：f通过求最小值求得步长。b.近似最佳步长法f对上述式子求导并等于0，可以得到步长t=∇（3）算法步骤(a).选取初始点X0，设置终止误差ϵ(b).计算∇fX(k)(c).计算搜索方向pk(d).通过对步长t的计算，可以得到X(k+1)最速下降法能够有效的解决一些无约束最优化问题。理论证明[10]，最速下降法在特定的条件之下是能够收敛的。（三）最速下降法例题求证例1minf(x)=x1−解：由题可知∇fx令搜索方向p(1)=−∇令步长为t，最优步长为t1，则X于是有f令φ1't=2t−2=0可得继续迭代得到：∇fX则有：X故f令φ2't∇fX综上知，最优解为X∗=−11.5（四）Python实现最速下降法例2fx1,Python代码如下：importmath

fromsympyimport*

#定义符号变量

x_1=symbols('x_1')

x_2=symbols('x_2')

#定义目标函数

fun=2*x_1*x_2+2*x_2-x_1**2-2*x_2**2

fun

#求导数

grad_1=diff(fun,x_1)

grad_2=diff(fun,x_2)

#定义参数

MaxIter=100

epsilon=0.0001

#定义初始点

x_1_value=0.5

x_2_value=0.5

iter_cnt=0

current_step_size=10000

grad_1_value=(float)(grad_1.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

grad_2_value=(float)(grad_2.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

current_obj=fun.subs({x_1:x_1_value,x_2:x_2_value}).evalf()

print(

'itCnt:%2dcur_point(%3.2f,%3.2f)cur_Obj:%5.4fgrad_1:%5.4fgrad_2:%5.4fstep_size:%5.4f'%(

iter_cnt,x_1_value,x_2_value,current_obj,grad_1_value,grad_2_value,current_step_size))

#while(iter_cnt<=MaxIterandabs(grad_1_value)+abs(grad_2_value)>=epsilon):

while(abs(grad_1_value)+abs(grad_2_value)>=epsilon):

iter_cnt+=1

#findthestepsize

t=symbols('t')

x_1_updated=x_1_value+grad_1_value*t

x_2_updated=x_2_value+grad_2_value*t

Fun_updated=fun.subs({x_1:x_1_updated,x_2:x_2_updated})

grad_t=diff(Fun_updated,t)

t_value=solve(grad_t,t)[0]#解决grad_t==0

#更新x_1_valueandx_2_value

grad_1_value=(float)(grad_1.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

grad_2_value=(float)(grad_2.subs({x_1:x_1_value,x_2:x_2_value}).evalf())

x_1_value=(float)(x_1_value+t_value*grad_1_value)

x_2_value=(float)(x_2_value+t_value*grad_2_value)

current_obj=fun.subs({x_1:x_1_value,x_2:x_2_value}).evalf()

current_step_size=t_value

print('itCnt:%2dcur_point(%3.2f,%3.2f)cur_Obj:%5.4fgrad_1:%5.4fgrad_2:%5.4fstep_size:%5.4