无约束方法.ppt

机械优化设计第四章 长江大学机械工程学院(HQS) 第四章 无约束优化方法 一）解法分类 1）直接法 其有哪些信誉好的足球投注网站方向直接取定或由计算目标函数值所得的信息来确定； 2）间接法（解析法） 确定有哪些信誉好的足球投注网站方向时用到一阶或（和）二阶导数的方法。 二）研究无约束优化方法的意义 §4-2 坐标轮换法 §4-2 Powell法 二）Powell法（ Powell修正算法） 2)Powell对基本算法的改进 在获得新方向构成新方向组时,不是轮换地去掉原来的方向,而是经判别后,在n+1个方向中留下最接近共轭的n个方向. 三）Powell条件 四）更换方向的步骤 §4-4 梯度法 一）梯度方向 §4-5 共轭梯度法 §4-6 牛顿法 二）阻尼牛顿法 §4-8 无约束优化方法的评价准则 一）可靠性 在满足合理精度要求的情况下、在一定时间内对各类问题解题的成功率。（梯度法较好，牛顿法较差，其余居中） 二）有效性（收敛性） 在同一题目、同样精度、同一初始点情况下比较。（具有二次收敛性的方法较好） 三）简便性 比较准备工作量和存储单元。（用到二阶导数及矩阵求逆的方法较差） §4-7 DFP变尺度法 二）基本思路 三）构造矩阵应满足的条件 * * 1) 坐标轮换法; 2) 鲍威尔法; 3) 梯度法; 4) 共轭梯度法; 5) 牛顿法; 6) DFP变尺度法. §4-1 概 述 1)几何描述(以二维问题为例） 二）迭代步骤 依次沿个n个正交坐标轴的方向有哪些信誉好的足球投注网站： 一）有哪些信誉好的足球投注网站方向 2) 坐标轮换法流程图 从 出发沿 方向进行一维有哪些信誉好的足球投注网站得 ： 给定 结束 三.算法特点 如:(1)等值线为椭圆,且长短轴分别平行于坐标轴时--高效 (2)等值线为如图脊线时--无效 (3)一般情况--低效 1）编程简单，容易掌握； 2）收敛速度通常较低（其有效性取决于目标函数的性态），仅适于低维的情况。 3）若目标函数为正定二次函数，n轮结束后即可到达最优点。 2）每轮迭代产生一个新方向取代原来的第一方向，n轮迭代后可产生n个彼此共轭的方向； 1）开始采用坐标轴方向； 一）Powell基本算法 应用 Powell基本算法时，若有一次有哪些信誉好的足球投注网站的最优步长为0，且该方向被换掉，则该算法失效。 1）问题的提出 * ①根据Powell条件判定是否需换方向； ②如需换向，则换掉函数值下降量最大的方向. 如下述两不等式 同时成立则需换向，否则仍取原方向组。 计算: （映射计算） 3）更换方向： 2）构造新方向： 1）找出该轮迭代中目标函数值下降量最大的方向（假定其标号为m）； Powell 修正算法 F3F1 QD Si=Si+1 i=m,m+1,…n i = n 输出X*=Xn F*=F（X*） 结束 给定X0,Si=ei i=1,2,…n, ε K=0 i=1 自Xi-1始，沿Si方向有哪些信誉好的足球投注网站得一维最优点Xi i=i+1 Xn+1=2Xn-X0 Sn+1=Xn-X0 自Xn始，沿Sn+1方向有哪些信誉好的足球投注网站得一维最优点X* K=K+1 F1=F(X0), F2=F(Xn), F3=F(Xn+1) 求Δ及方向标号m Y Y Y Y N N N X0=X* N Xn-X0 ≤ε *可取最优步长或下降步长 二）基本思想 梯度方向是目标函数上升最快的方向，负梯度方向则是最速下降方向； 2）迭代公式 1）沿负梯度方向有哪些信誉好的足球投注网站： 三）终止判别条件 给定 X0 ，ε K=0 ，X（K）=X0 K=K+1 X(k)=X△ X*= X（K） F*=F（X*） 结 束 N Y 计算 从 出发，沿 有哪些信誉好的足球投注网站得 * “最速下降性”只是迭代点邻域的局部性质。从全局看，并非最速下降方向。 四.迭代步骤 第二方向： 第一方向： 二.共轭方向的构成 *利于突破函数的非二次性; 每轮有哪些信誉好的足球投注网站方向为一组共轭方向, 但第一方向为负梯度方向. 一.基本思路 * 可表示为两个负梯度方向的线性组合。 ， 以后新方向均按下述迭代公式产生： 因而， 因为 （A是二次函数的Hessian 矩阵） 二次函数 其梯度为 故有 故有 又 （正交） 刘惟信用数学归纳法对此法的共轭性作出过证明。 K n 给定X0, n, ε K=1, X(K)=X0 S(K)= -▽F(X(K)) 从X(K)始，沿S(K)进行一维有哪些信誉好的足球投注网站得X(K+1) K=K+1 是 是 否 否 计算 结 束 重置负梯度方向 三.迭代步骤 四.共轭梯度法的特点 1.为共轭方向法,具有二次收敛性; 2.算法简单,编程容易,存储量小; 3.需用到一阶导数. （牛顿方向） 1）迭代方向： * * 鲍威尔法需迭代 (n+1)n 次才能到达二次函数