6-优化设计-3多维优化之无约束优化方法概要.ppt

1,多 维 优 化 方 法,１、概念：针对多元函数进行多变量优化的相关数值迭代方法的总称２、分类： 无约束优化方法 约束优化方法,2,１、 无约束优化问题一般形式,求设计变量 X=[x1,x2,…,xn]T , X∈Rn 满足目标函数minf(X) 的 无约束最优解X* 及对应的最优函数值minf (X*),多 维 优 化-无约束优化方法,3,2、无约束优化方法分类 根据“搜索方向” 构成形式分为：,1）导数法 — 梯度法、共轭梯度法 基于目标函数一阶、二阶导数构造搜索方向而形成算法收敛性、收敛速度好 2）模式法— 鲍威尔法 通过对目标函数几个已知点函数值分析比较构造搜索方向形成算法利于实现复杂目标函数的优化,4,3、 梯度法（最速下降法）,1）概念：依据梯度（函数某点一阶偏导数）确定搜索方向而形成的优化方法3）梯度法迭代公式、收敛条件,2）特点:通过沿迭代点负梯度方向的反复迭代搜索，使迭代点逐步逼近优化点,5,,5）梯度法的本质原理,将多维无约束优化问题转化为系列沿目标函数负梯度方向寻优的一维优化问题进行求解,F(X)多 元 目 标 函 数,F( ak) 基于当前已知迭代点Xk关于步长ak的一元函数,,求解,一维优化方法,代 入,转 化,6,6）梯度法实现步骤,1、给定初始点和收敛精度 2、以初始点为迭代起点，计算梯度，以负梯度方向作为当前搜索方向. 3、在当前搜索方向上用一维搜索法确定最忧步长αk以及所对应的下一迭代点． 4 、以下一迭代点的负梯度方向为搜索方向继续计算搜索直到满足收敛条件．,7,梯度法搜索过程,相邻两次搜索方向正交，迭代全过程搜索 路线呈锯齿状。

缺点：越靠近极值点收敛速度越慢,8,,梯度法算例,,,,,,,,例1 用梯度法求下列无约束优化问题，,已知X(0)=[1, 1]T，ε＝0.1,解：1）第一次迭代,求,令,则,9,,令,还应继续迭代计算,,因,求导,10,,2)第二次迭代 因 解得,因,还应继续迭代计算,11,,最后得此问题的最优解为：,12,共 轭 梯 度 法,1、共轭方向概念,设H为一正定对称矩阵，若有非零向量Si, Sj满足,则称向量Si ,Sj关于矩阵H共轭, Si 、Sj互为共轭 方 向,若H为单位阵，则,向量共轭是正交的推广，正交是共轭的特例,,13,２、共轭方向性质,性质1：若Si(i=1,2…n) 为关于某n元正定二次函数海森矩阵H共轭的n个向量，则从任意初始点Ｘ０出发，依次沿此n个向量Si的方向进行一维搜索，最多n次即可达到极小点14,性质1证明,设函数为：,给定初始点X(0)并沿某一下降方向S(0)作一维搜索，可得优化点X(1),由梯度法迭代过程中相邻搜索方向相互垂直可知,点X(1) 梯度为,15,从点X(1)开始沿另一下降方向S(1)作一维搜索，可得另一迭代点X(２),与之对应，函数在点X(２)的梯度为,若X(２) 为极小点则有,带入,得,16,展开,,两端左乘S(0)，因,点 X(1) 的 梯 度,,可得：,即S(0)，S(1) 关于函数二阶导数矩阵H共轭.,这说明，沿与该二元二次函数的二阶导数矩阵共轭的方向两次搜索可达极值点.,17,性质2：对于某函数，若从任意两点X1和X2出发分别沿同一方向S0进行一维搜索得到两个极小点 X1min和 X2min，则连接此两点的向量 S1 与S0 关于该函数海森矩阵H共轭 即：S0 H S1=0 其中 S1= X1min- X2min 意义：按当前搜索方向构造关于目标函数二阶导数矩阵共轭的向量,18,3、共轭梯度法的成因,以负梯度的共轭方向进行目标函数极值的迭代搜索可大大加快收敛速度,函数在负梯度方向下降最快,沿与目标函数海森矩阵共轭方向经有限次迭代可达极值点,共轭梯度法,,,,19,概念：依据共轭向量性质，利用目标函数相邻两点的梯度构造共轭方向进行迭代运算的优化方法．,４、共轭梯度法的概念和方法特点,特点： 共轭梯度法初始寻优仍以初始点的负梯度为方向，即：,以后各步寻优则在构造的共轭方向上进行。

20,共轭梯度法迭代公式,共轭梯度方向公式,21,4）共轭梯度法实现步骤,22,,共轭梯度法算例,,,,,,,,用共轭梯度法求无约束优化问题，,已知X(0)=[1, 1]T，ε＝0.1解：1）第一次迭代搜索 - 在梯度方向,求,令,则,23,,令,继续在梯度共轭方向进行第二迭代搜索,,因,带入原目标函数,24,,第二次迭代搜索 - 在梯度共轭方向,计算与梯度共轭的搜索方向,基于,,25,26,1、 梯度法 搜索方向为目标函数负梯度方向 计算速度开始几步快，愈接近极值点愈慢 对初始点选择要求不高 适合与其它方法结合使用 2、共轭梯度法 第一步沿负梯度方向以后沿负梯度共轭方向 计算效率优于梯度法， 对初始点无特殊要求 计算量与梯度法相当 适用于各种规模的问题,6）梯度法与共轭梯度法的对比,。