1、第四章第四章 无约束优化方法无约束优化方法坐标轮换法坐标轮换法鲍威尔法鲍威尔法梯度法梯度法牛顿法牛顿法DFP变尺度法变尺度法BFGS变尺度法变尺度法无约束优化方法的评价准则及选用无约束优化方法的评价准则及选用 无约束优化方法是优化技术中基本的也是非常重要的内无约束优化方法是优化技术中基本的也是非常重要的内容。无约束优化问题的数学模型容。无约束优化问题的数学模型求上述问题最优解（求上述问题最优解（ x*,F*） 的方法，称为无约束优化方的方法，称为无约束优化方法法 无约束优化方法，不仅可以直接求无约束优化设计问题无约束优化方法，不仅可以直接求无约束优化设计问题的最优解，而且通过对无约束优化方法的
2、研究给约束优的最优解，而且通过对无约束优化方法的研究给约束优化方法建立明确的概念、提供良好的基础化方法建立明确的概念、提供良好的基础 某些优化设计某些优化设计方法就是先把约束优化设计问题转化为无约束问题后，方法就是先把约束优化设计问题转化为无约束问题后，再直接用无约束优化方法求解。再直接用无约束优化方法求解。 无约束优化理论研究开展得较早，构成的优化方法巳很多无约束优化理论研究开展得较早，构成的优化方法巳很多，也比较成熟，新的方法仍在陆续出现。本章的内容与目的，也比较成熟，新的方法仍在陆续出现。本章的内容与目的是讨论几个常用无约束优化方法的基本思想、方法构成、迭是讨论几个常用无约束优化方法的基
3、本思想、方法构成、迭代步骤以及终止准则等方面问题。代步骤以及终止准则等方面问题。 在在 n维无约束优化方法的算法中，用函数的一阶、二价维无约束优化方法的算法中，用函数的一阶、二价导数进行求解的算法，称为解析法导数进行求解的算法，称为解析法 ; 无约束优化方法总体分成两大类型无约束优化方法总体分成两大类型 :解析法或称解析法或称 间接法间接法 、直接搜索法或简称直接搜索法或简称 直接法直接法 ；对于对于 n维优化问题，如果只利用函数值求最优值的解法，称维优化问题，如果只利用函数值求最优值的解法，称为直接搜索法为直接搜索法 ； 解析法的收敛速率较高，直接法的可靠性较高。解析法的收敛速率较高，直接法
4、的可靠性较高。 本章介绍的坐标轮换法和鲍威尔法属于直接法；梯度法本章介绍的坐标轮换法和鲍威尔法属于直接法；梯度法、共轭梯度法、牛顿法和变尺度法属于解析法、共轭梯度法、牛顿法和变尺度法属于解析法 无约束优化方法算法的基本过程是无约束优化方法算法的基本过程是 :从选定的某初始点从选定的某初始点 x(k)出发，沿着以一定规律产生的出发，沿着以一定规律产生的搜索方向搜索方向 S(k) ,取适当的步长取适当的步长 a(k) ,逐次搜寻函数值下降的逐次搜寻函数值下降的新迭代点新迭代点 x(k+1),使之逐步逼近最优点使之逐步逼近最优点 x* 。 可以把初始点可以把初始点 x(k) 、 搜索方向搜索方向 S
5、(k) 、 迭代步长迭代步长 a(k) 称为优化方法算法的三要称为优化方法算法的三要素。其中以搜索方向素。其中以搜索方向 S(k)更为突出和重要，它从根本上决更为突出和重要，它从根本上决定着一个算法的成败、收敛速率的快慢等。所以，一个定着一个算法的成败、收敛速率的快慢等。所以，一个算法的搜索方向成为该优化方法的基本标志，分析、确算法的搜索方向成为该优化方法的基本标志，分析、确定搜索方向定搜索方向 S(k)是研究优化方法的最根本的任务之一。是研究优化方法的最根本的任务之一。坐标轮换法坐标轮换法坐标轮换法属于直接法，既可以用于无约束优化坐标轮换法属于直接法，既可以用于无约束优化问题的求解，又可以经
6、过适当处理用于约束优化问题问题的求解，又可以经过适当处理用于约束优化问题求解。求解。坐标轮换法是每次搜索只允许一个变量变化，其坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。不需要目标函数的导数。一、坐标轮换法的迭代
7、过程一、坐标轮换法的迭代过程如图，以二次函数为例。任取一初始点任取一初始点 x(0)作为第一轮的始点作为第一轮的始点 x0 (1),先沿第一坐先沿第一坐标轴的方向标轴的方向 e1作一维搜索，用一维优化方法确定最优步作一维搜索，用一维优化方法确定最优步长长 1(1) ，得第一轮的，得第一轮的 第一个迭代点第一个迭代点x1(1) =x0(1) + 1(1) e1，然后以然后以 x1 (1)为新起点，沿第二坐标轴的方向为新起点，沿第二坐标轴的方向 e2作作 一维一维搜索，确定步长搜索，确定步长 2(1) ，得第一轮的，得第一轮的 第二个迭代点第二个迭代点x2(1) =x1(1) + 1(1) e2第
8、二轮第二轮 迭代，需要迭代，需要x0(2) x2 (1)x1(2) = x0(2) + 1(2) e1x2(2) =x1(2) + 2(2) e2依次依次 类推，不断迭代，目标函数值不断下降，最后类推，不断迭代，目标函数值不断下降，最后逼近该目标函数的最优点。逼近该目标函数的最优点。二、终止准则二、终止准则可以采用点距准则可以采用点距准则注意：注意：若采用点距准则或函数值准则，其中采用的点应该是一轮若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。迭代的始点和终点，而不是某搜索方向的前后迭代点。坐标轮换法的计算步骤坐标轮换法的计算步骤 任选初始点任选初始点作为第一轮的起点作为第一轮的起点 ，置，置 n个坐标轴方向矢量为单位个坐标轴方向矢量为单位坐标矢量：坐标矢量： 按照下面迭代公式进行迭代计算按照下面迭代公式进行迭代计算k为迭代轮数的序号，取为迭代轮数的序号，取 k=1， 2， ；i为该轮中一维搜索的序号，取为该轮中一维搜索的序号，取 i=1， 2， n步长步长 一般通过一维优化方法求出其最优步长。一般通过一维优化方法求出其最优步长。 按下式判断是否中止迭代按下式判断是否中止迭代如满足，迭代中止如满足，迭代中止，并输出最优解，并输出最优解最优解最优解 否则，令否则，令 kk+1返回步骤（返回步骤（ 2）
