坐标轮换法.ppt

第三章 无约束优化方法,无约束优化设计的数学模型为： 无约束优化方法是优化设计技术中最重要和基本的内容之一，主要因为：1.这类方法可以直接用来求解某些无约束的工程设计问题；2. 对某些约束优化问题可以通过一定的办法转化为无约束问题，直接用无约束优化方法求解；3.通过对无约束优化方法的研究给约束优化方法提供良好的概念和基础。,无约束求优的过程是从某一选定的初始点出发，沿着按一定规律产生的搜索方向组逐次寻求函数值下降的新迭代点，使之逐步逼近最优点，即 满足 可见，各种无约束优化方法的区别，主要在于搜索方向的不同，搜索方向的构成问题是无约束约束优化方法的主要特征。 主要分为两大类：一是直接法，即不用导数信,息的算法，只需要进行函数值的计算与比较，来确定迭代方向和步长，如坐标轮换法、共轭方向法和鲍威尔共轭方向法；另一类是间接法，即利用函数的一阶或二阶偏导数矩阵，来确定迭代方向和步长，如最速下降法，牛顿法和变尺度法。,无约束极小化算法框图,2.坐标轮换法 坐标轮换法又称变量轮换法，属于直接法，其基本原理为：将一个多维无约束优化问题转换为一系列一维优化问题来求解，即依次沿着坐标轴的方向进行一维搜索，求得极小点。 对于n维无约束优化问题，先将（n-1)个变量固定不动，只变化第一个变量 ，即由起始点沿着第一个变量 的方向进行一维搜索，得到好点 ;而后再保持（n-1）,个变量不变，对第二个变量 进行一维搜索，此时搜索方向为 ，得到好点 。如此沿 方向（即坐标方向），且将前一次一维搜索的好点作为本次一维搜索的好点作为本次一维搜索的起始点，依次进行一维搜索后，完成一轮计算。若未收敛，则以前一轮的末点 为起始点，进行下一轮的循环，如此一轮一轮迭代下去，直到满足收敛准则，逼近最优点为止。,二维坐标轮换法的迭代示意图,迭代步骤：1.任选初始点 作为第一轮的起点 ，置n个坐标轴方向矢量为单位坐标矢量,2.按照下面迭代公式进行迭代计算 式中K为迭代轮数的序号，k=1,2,···，i是该轮中一维搜索的序号，依次取i=1，2，3等步长一般通过一维优化求出其最优步长。（3）按下式判别是否该终止迭代？,若满足，迭代终止，并输出最优解坐标轮换法特点：1.方法结构简单，易于掌握，但计算效率低，对维数较高的优化问题更为突出，通常用于低维优化问题；2.本方法的收敛效果在很大程度上取决于目标函数等值线的形状。 等值线为椭圆族，其长、短轴与坐标轴,平行或圆族等值线，该方法收敛效果好，速度快。如下图（a） 当椭圆族的长、短轴与坐标轴斜交，迭代次数将大大增加，收敛速度很慢,如下图（b） 。 当目标函数等值线出现“脊线”时，沿坐标轴方向搜索均不能使函数值有所下降，该方法在求优过程中将失败，这类函数对坐标轮换法来说是“病态”函数。如下图（c）。,3.共轭方法法及其构成,坐标轮换法的收敛速度很慢，原因在于搜索方向总是平行于坐标轴，不适应函数的变化情况。若将一轮的起点和末点连接起来，形成一个新的搜索方向,由右图可知，从这个搜索方向出发可以极大的加速收敛速度，方向 具有什么性质，它与 方向有何关系？,设函数 的极值点极值点附近的等值线为近似的同心椭圆族，如上图所示，给定两个平行方向 ，沿这两个方向分别进行一维搜索，求得极小点 和 。显然， 和 分别是两条平行线与函数等值线的相切点，连接这两个切点构成向量 ，即 ，可证明 与 关于函数f（X）的海塞矩阵H共轭。,3.1共轭方向的定义 设A为 阶实对称正定矩阵，而 ， 为n维欧式空间 中的两个非零向量，如果满足 ，则称向量 与 关于是实对称正定矩阵A是共轭的，或简称 与 关于A共轭。 可以将这种算法推广到n维函数，逐步构成一组关于H共轭的向量。对于对称正定的n维函数，从任意点出发沿着这n个线性相关的方向进行一维搜索，就能得到目标函数的极小点，因此共轭方向法具有有限步收敛的特性。对非二,次n维目标函数，经过n步共轭方向一维搜索就不一定能达到极小点，可以进行第二轮迭代。共轭方向法的基本原理： 首先采用坐标轮换法进行第一轮迭代，然后以第一轮迭代的最末一个极小值与初始点相连，构成一个新的方向，并以此方向为最末一个方向，而去掉第一个方向，得到第二轮迭代的n个方向，如此进行下去，直到求出问题的最小点。,二维问题的共轭方向法迭代过程,共轭方向法的缺陷： 共轭方向法的基本要求是，各方向组的向量之间是线性无关的，但是在实际的运算中，常常产生的新方向有可能出现了线性相关，使得搜索运算将在维数下降了的空间运行，从而导致计算不能收敛到真正的极小值点而失败。 鲍威尔针对这个问题提出了改进方法。（1）在每轮迭代完成并产生共轭方向后，先对共轭方向的好坏进行判断，检验它是否与其他方向线性相关，若共轭方向不好，则,不用它，仍用原来的一组迭代方向。 （2）若共轭方向好，则可用它替代前一轮迭代中使函数值下降最多的一个方向，而不一定替换第一个方向。 在鲍威尔法中，判断是否用新的方向去替换原方向组中的某一个方向的判定准则为：,式中： 表示在第k次循环中起始点 的函 数值 ； 第k次循环中沿基本方向组中个迭代方向 依次一维搜索后的终点 的函值 ； 为映射点函数值， ， 为 对 的映射点， ； 表示循环中函数值下降量最大者，即,其相应的方向为 。,式中符号含义,如果满足判别准则，则在下一次循环时，用新方向 补入k+1次循环基本方向组的最后，并去掉 ，从而构成新的方向组。并取第k+1次循环的起始点为 。（ 为第k次循环中沿新方向 一维搜索的极小点） 如果不能满足判别准则，则第k+1次循环时仍用原来的方向组，而初始点按下式选取：,鲍威尔迭代法的步骤：1.给定初试点 和允许误差 ；2.取n个坐标轴的单位向量 为搜索方向 ，置k=1（k为迭代轮数）， ；3.从 出发，分别沿 作一维搜索，依次得n个极小点 ，计算各相邻极小点目标函数的差值 ，,并找出其中的最大差值及其相应的方向：计算反射点 ，并计算 ， ， ；,5.如果满足判别准则，则在下一次循环时，用新方向 补入k+1次循环基本方向组的最后，并去掉 ，从而构成新的方向组。并取第k+1次循环的起始点为 。（ 为第k次循环中沿新方向 一维搜索的极小点） 如果不能满足判别准则，则第k+1次循环时仍用原来的方向组，而初始点按下式选取：,6.验证是否满足迭代终止条件：若能满足 或,则可终止迭代，得 为最优点，输出结果 ， ；否则，置 ， ；返回第3步。,