无约束问题的最优化条件.ppt

《无约束问题的最优化条件.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、5.1无约束问题的最优性条件1．局部极小点2．严格局部极小点3．全局（总体）极小点4．严格全局（总体）极小点。注：在非线性规划中，大多数算法都致力于求最优化问题的局部极小点，一般求全局极小点极为困难，仅当问题为凸规划时，局部极小为全局极小。一、极小点的概念二、无约束问题最优性条件5.2最速下降法最速下降法又称为负梯度法，由Cauchy于1847年给出。是最为古老但又十分基本的一种方法。最速下降法解决的是具有连续可微的目标函数的无约束极值问题。最速下降法的基本思想：从当前点xk出发寻找使得目标函数下降最快的方向，即负梯度方向。优

2、点：迭代过程简单，使用方便。一.最速下降法关于梯度的复习：梯度是一个向量。n元函数f(x1,x2,…xn)在点x处的梯度为：梯度的方向与函数f的等值线的一个法线方向相同，从较低的等值线指向较高的等值线。梯度的方向就是函数f的值增加最快的方向，其相反方向就是函数值降低最快的方向。解:例1:用最速下降法求的极小值,,只迭代一次代入目标函数得：令继续迭代,计算可得二.算法终止标准三、最速下降算法收敛性定理四.最速下降法的收敛速度五.算法特点相邻两次迭代的搜索方向是正交的,迭代点列呈锯齿形前进，迭代点越靠近最优解附近,目标函数值

3、下降的速度越慢，算法收敛速度慢。5.3牛顿法例2:用牛顿法求的极小值,解:1)计算2)方向3)求最优步长代入目标函数得：令4)判断即为所求四.牛顿法的进一步修正5.4信赖域法5.5拟牛顿法例4:著名的rosenbroke函数,亦称香蕉函数该问题有唯一极小点观察不同迭代算法所得到的结果最速下降法牛顿法拟牛顿法单纯形搜索法对偶拟牛顿法最小二乘法5.6共轭方向法5.7powell算法问题1:在实际问题中往往得不到目标函数的梯度的解析形式.只能采用近似计算摄动近似法:计算在迭代点附近分别在方向分别给一微小偏差,计算问题2:在实际问题中

4、可能得不到目标函数的解析形式.只有动态的目标函数值PID调节器re+-yu一个典型工业过程控制系统结构图控制对象选择误差型目标函数,即时间乘绝对误差积分,现需要在目标函数:意义下,寻找一组最优的PID调节器参数使由于目标函数不是显含被寻参数的函数,并且目标函数是在求解系统动态过程中才能计算出来,显然无法采用前面讨论的间接搜索法为了避免计算目标函数梯度,产生了许多只需要计算目标函数值的搜索方法———称直接搜索法方法单纯形法坐标轮换法模式搜索法共轭方向方法一.Powell算法1964年由Powell提出，后经Zangwoll（19

5、67年）和Brent（1973年）改进，是迄今为止最有效的直接搜索法。该算法有效地利用了迭代过程中的历史信息，建立起能加速收敛的方向,有理论基础，以二次函数f(x)=1/2xTAx+bTx+c为模型进行研究。为什么选择二次函数作为模型?1、在非线性目标函数中，最简单的是二次函数，故任何对一般函数有效的方法首先应对二次函数有效；2、在最优点附近，非线性函数可用一个二次函数作近似，故对二次函数使用良好的方法，通常对一般函数也有效；3、很多实际问题的目标函数是二次函数。定理:假设1.n元函数f(x)=1/2xTAx+bTx+c中矩阵

6、A是对称正定的；2.向量d(0),d(1),…,d(m-1)(m

7、)*x(1)*d(2)x*二.Powell算法的迭代过程一边搜索，一边找共轭方向共分n个阶段，每一阶段都进行n+1次搜索，最后产生一个共轭方向…………………………………………………………………………………………………………任意n个线性无关的方向二维空间中的Powell方法示意图e(2)e(1)d(0)=e(1)d(1)=e(2)以二次函数f(x1,x2)为例d(0)d(1)x(1,0)x(1,1)x(1,2)d(1)x(2,2)x(2,0)x(2,1)x*对于二次函数,x*即为极小点例:用Powell法求解可以验证d(2,3)

8、与d(2,2)关于A共轭三.Powell算法流程开始给定x(0),e(1),e(2),…,e(n)及否x(k)=x(k,n)+kd(n-1)其中k为最优步长k=1,d(i)=e(i+1),i=0,1,…,n-1j=0,x(k,j)=x(k-1)x(k,j+1)=x(k,