第三章无约束问题的最优化方法.pptx

1、第三章无约束问题的最优化方法13.1 引言一. 目的：求一组 n 维设计变量 X= x1, x2 ,x n T, 使目标函数达到 min. f(x) XRn即求目标函数的最优解：最优点 x* 和最优值 f(x*) 。二. 意义： 为有约束优化方法的研究提供了策略思想、概念基础和基本方法； 为有约束优化问题的间接解法提供了有效而方便的方法； 对于某些工程问题，进行分析后，便于提供解决的有效方法； 不可避免地还存在无约束优化的设计问题。23.1 引言三. 内容：一维搜索： 求最优步长因子(k)多维（变量）优化：确定搜索方向 S (k)黄金分割插值法 坐标轮换法共轭方向法梯度法共轭梯度法牛顿法DFP

2、变尺度法 33.2 一维搜索方法一. 一维搜索：定义: 在第K次迭代时，从已知点 X(k)出发，沿给定方向求最优步长因子(k)，使 f (X(k) + S(k) )达到最小值的过程，称为一维搜索。方法：1. 解析法： f (x (k+1) ) = min. f (x (k) + S (k) ) = f (x (k) + (k) S ( k) ) 步骤: f(X(k) + S(k) ) 沿S(k) 方向x(k) 台劳展开； 取二次近似： 43.2 一维搜索方法对求导，令其为零。 2. 数值迭代法：直接法应用区间消去原理： 分数法、黄金分割法近似法利用多项式函数逼近（曲线拟合）原理： 二次插值法、

3、 三次插值法 一维搜索也称直线搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。 求得最优步长因子：53.2 一维搜索方法单峰区间： 在区间 1，3 内，函数只有一个峰值，则此区间为单峰区间。单峰区间内，一定存在一点*，当任意一点2*时，f(2)f(*)，说明： 单峰区间内，函数可以有不可微点，也可以是不连续函数；二. 搜索区间的确定：f (x)0130f (x)31f ()32*10当2*时，仍有f (2 ) f(*) ，则*是最优点，也即为最优步长因子(k)。2确定的搜索区间必定是一个含有最优点*的单峰区间。62、确定初始单谷区间的进退法基本思想：

4、对f(x)任选一个初始点a1及初始步长h， 通过比较这两点函数值的大小，确定第三点位置，比较这三点的函数值大小，确定是否为 “高低高” 形态。步骤：（1）选定初始点a, 初始步长hh0，计算 y1f(a1)，y2f(a1h)。（2）比较y1和y2。 （a）如y1y2, 向右前进；加大步长 h2 h ，转（3）向前； （b）如y1y3, 加大步长 h2 h ，a1=a2, a2=a3,转（3）继续探测。 （b）如y2y3, 则初始区间得到： a=mina1,a3， b=maxa3,a1，函数最小值所在的区间为a， b 。8y1y3y2y2y1a3a2a2a1a1Oaa3h0h02h0y1y2a2

5、a3a1a2a1Oaa32h0h0h0y3y1y2y1y2y3a1a2 确定初始单谷区间进退法示意图9进退法程序框图 103.2 一维搜索方法3.一维搜索的区间消去方法： 基本原理： 搜索区间确定之后，采用区间消去法逐步缩短搜索区 间，从而找到极小点的数值近似解。在搜索区间内a,b 任取两点a1、b1，令f1f（a1）， f2f（b1）f(a1)f(b1)f(a1)f(b1)f(a1)f(b1)a1a1 a1 b1baabab b1b1(1)如f1f2, 则缩小的新区间为a1,b;(3)如f1=f2, 则缩小的新区间为a1,b1113.2 一维搜索方法 黄金分割法： 黄金分割法适用于a,b区间

6、上的任何单谷函数求极小值问题。对函数除要求“单谷”外不作其他要求，甚至可以不连续。因此，这种方法的适应面相当广。 黄金分割法也是建立在区间消去法原理基础上的试探方法。 在搜索区间内a,b适当插入两点，将区间分成三段；利用区间消去法，使搜索区间缩小，通过迭代计算，使搜索区间无限缩小，从而得到极小点的数值近似解。 黄金分割法还要求在保留下来的区间内再插入一点所形成的区间新三段，与原来区间的三段具有相同的比例分布 。123.2 一维搜索方法黄金分割法要求插入两点：13黄金分割法的搜索过程：1）给出初始搜索区间及收敛精度 ，将 赋以0.618。2）按坐标点计算公式计算 , ；并计算其对应的函数值。3）

7、根据区间消去法原理缩短搜索区间。为了能用原来的坐标点计算公式，需进行区间名称的代换，并在保留区间中计算一个新的试验点及其函数值。如果 ，则新区间 令 记N0=0； 如果 ，则新区间 ，令 ，记N0=1； 4）检查区间是否缩短到足够小和函数值收敛到足够精度，如果收敛条件满足，则取最后两试验点的平均值作为极小点的数值近似解。如果条件不满足则转向步骤5）。14f(a1)f(a2)f(a1)f(a2)a1(a) a1(a2) a2(b)abab a2(a1)a1a2如N0=0，则取如N0=1，则取5）产生新的插入点：转向3）进行新的区间缩小。15黄金分割法程序框图例 ：用黄金分割法求函数f(x)=3x

8、3-4x+2的极小点，给定 x0=0, h=1, =0.2。16例 ：用黄金分割法求函数f(x)=3x3-4x+2的极小点，给定 x0=0, h=1, =0.2。解：1）确定初始区间x1=x0=0, f1=f(x1)=2x2=x0+h=0+1=1, f2=f(x2)=1由于f1f2, 应加大步长继续向前探测。x3= x0+2h=0+2=2, f3=f(x3)=18由于f2f3,可知初始区间已经找到，即a,b=x1,x2=0,22）用黄金分割法缩小区间 第一次缩小区间： x1=0+0.382X(2-0)=0.764, f1=0.282 x2=0+0.618 X(2-0)=1.236, f2=2.

9、72 f10.2 第二次缩小区间： 令 x2=x1=0.764, f2=f1=0.282 x1=0+0.382X(1.236-0)=0.472, f1=0.317 由于f1f2, 故新区间a,b=x1,b=0.472, 1.236因为 b-a=1.236-0.472=0.7640.2, 应继续缩小区间。173.2 一维搜索方法四.一维搜索的插值类方法1.牛顿法 设f(x)为一个连续可微的函数，则在x0附近，该函数应该与一个二次函数接近，即可在点x0附近用一个二次函数(x)来逼近函数f(x) ，即：用二次函数的(x)极小点x1作为f(x)极小点的一个近似点。根据极值必要条件: 得到：依次继续下去

10、，可得牛顿迭代公式：18 牛顿法的优点是收敛速度快。缺点是要计算函数的一阶和二阶导数，因而增加了每次迭代的工作量。如果用数值微分计算函数的二阶导数，其舍入误差将严重影响牛顿法的收敛速度， f(x)的值越小，这个问题就越严重。另外，牛顿法要求初始点选的比较好，也就是说应离极小点不太远，否则有可能使极小化序列发散或收敛到非极小点。193.2 一维搜索方法二次插值法. 基本原理：步骤：203.2 一维搜索方法 缩短区间若f(x)本身为二次函数，则在理论上按前式一次求值就可找到最优点 ；若f(x)为高于二次的函数或为其他函数 ,可采用区间消去法逐步缩小区间 。 根据xp* ，x2，f(xp* )和f(

11、x2)的相互关系，分4种情况进行区间缩小。 在已有的四x1,x2,x3,xp* 中选择新的三个点x1,x2,x3，再进行二次插值。 213.2 一维搜索方法 方法评价：与黄金分割法相比，二次插值法充分利用函数值的信息；收敛快；调用函数次数少。二次插值法的程序框图22例 ： 用二次插值法求函数f(x)=3x3-4x+2的极小点，给定 x0=0, =0.2。解： 1）确定初始区间初始区间a,b=0,2, 中间点x2=1。2）用二次插值法逼近极小点相邻三点的函数值: x1=0, x2=1, x3=2; f1=2, f2=1, f3=18. 代入公式：xp*0.555, fp=0.292由于fpf2,

12、 xp * 0.2, 应继续迭代。在新区间，相邻三点的函数值: x1=0, x2=0.555, x3=1; f1=2, f2=0.292, f3=1.xp*0.607, fp=0.243 由于fpx2, 新区间a,b=x2, b=0.555,1 |x2-xp * |=0.0520.2, 迭代终止。 xp*0.607, f*=0.243233.3 多维优化算法无约束优化问题的概念和数学模型： 求n维设计变量x=x1，x2， ，xnT使目标函数为minf（x），而对x没有任何限制；如果存在x*，使minf（x）=f（x*），则称x*为最优点，f（x*）为最优值。 数学模型: minF(x) x=x

13、1，x2， ，xnTRn 求上述问题最优解的方法，称为无约束优化方法。24 无约束优化的地位： 1、有些实际问题，其数学模型本身就是无约束优化问题，或者除了在非常接近极小点的情况下，都可以按无约束问题来处理。 2、通过熟悉无约束优化问题的解法，可以为研究约束优化问题打下良好的基础。 3、约束优化问题的求解往往可以通过一系列无约束优化方法来实现。 所以，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。25无约束优化方法数值计算方法的步骤： 1、选择一个初始点x（0），这一点越靠近极小点x*越好。 2、若已经取得某设计点x（k），并且该点不是近似极小点，则在x（k）点根据函数

14、f（x）的性质，选择一个方向S（k），并且沿此方向搜索函数值是下降的，称下降方向。 3、当搜索方向S（k）确定后，由 x（k） 点出发，沿S（k）方向进行搜索， 定出步长因子 （k） ， 得到新的设计点 x（k+1）=x（k）+（k）S（k），并满足f（x（k+1）f（x（k） 4、若x（k+1）满足迭代计算终止条件， x（k+1）点作为x*；否则从该点出发，返回第二步继续搜索迭代。26 无约束优化数值计算方法的关键问题： 无约束优化数值计算方法采用的是搜索方法，其基本思想是从给定的初始点出发，沿某一个搜索方向进行不断的搜索，确定最佳步长使函数值沿搜索方向下降最大，其迭代公式为 x（k+1）=

15、x（k）+（k）S（k） 各种无约束优化方法的区别在于确定其搜索方向的S（k）的方法不同。所以，搜索方向的构成问题使无约束优化问题的关键。27 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n 20）问题，一般情况下比间接法效率低。 间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 （1）间接法：要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度法等。 （2）直接法：不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。无约束优化方法的分类： 无约束优化方法的分类依据就是根据（k）和S（k）的确定方法而定的。 若根

16、据构成搜索方向所使用的信息性质的不同，可以分为两类。 281 、 梯度法基本思想： 函数的负梯度方向是函数值在该点下降最快的方向。将n 维问题转化为一系列沿负梯度方向用一维搜索方法寻优的问题，利用负梯度作为搜索方向，故称最速下降法或梯度法。 搜索方向s取该点的负梯度方向 (最速下降方向) ，使函数值在该点附近的范围内下降最快 。29 为了使目标函数值沿搜索方向 能够获得最大的下降值，其步长因子 应取一维搜索的最佳步长。即有 根据一元函数极值的必要条件和多元复合函数求导公式，得： 30 在最速下降法中，相邻两个迭代点上的函数梯度相互垂直。而搜索方向就是负梯度方向，因此相邻两个搜索方向互相垂直。这

17、就是说在迭代点向函数极小点靠近的过程，走的是曲折的路线。形成“之”字形的锯齿现象，而且越接近极小点锯齿越细。 31方法特点： （1）初始点可任选，每次迭代计算量小，存储量少，程序简短。即使从一个不好的初始点出发，开始的几步迭代，目标函数值下降很快，然后慢慢逼近局部极小点。 （2）任意相邻两点的搜索方向是正交的，它的迭代路径为绕道逼近极小点。当迭代点接近极小点时，步长变得很小，越走越慢。 3233沿负梯度方向进行一维搜索，有为一维搜索最佳步长，应满足极值必要条件 例： 求目标函数 的极小点。解：取初始点 则初始点处函数值及梯度分别为 算出一维搜索最佳步长 34继续作下去，经10次迭代后，得到最优

18、解 第一次迭代设计点位置和函数值 这个问题的目标函数的等值线为一簇椭圆，迭代点从起点出发走的是锯齿形路线。1135将上例中目标函数 引入变换其等值线由椭圆变成一簇同心圆。 仍从 即 出发进行最速下降法寻优。则函数f(X)变为：y1=x1, y2=5x2 经变换后，只需一次迭代，就可找到最优解。这是因为经过尺度变换等值线由椭圆变成圆。36梯度法特点：（1）理论明确，程序简单，对初始点要求不严格。（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下降方向仅仅是指某点的一个局部性质。（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极小

19、点时逼近速度较慢。（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。372、牛顿法及其改进设 为 的极小点，则 基本思想 ： 将 f(x) 在 x(k) 点作台劳展开，取二次函数式(x)作为近似函数,以(x) 的极小值点作为 f(x) 的近似极小值点。牛顿法是求函数极值的最古老算法之一。 这就是多元函数求极值的牛顿法迭代公式。 38 对于二次函数 ，海赛矩阵H是一个常矩阵，其中各元素均为常数。因此，无论从任何点出发，只需一步就可找到极小点。 例：求目标函数 的极小点。解：取初始点经过一次迭代即求得极小点39 从牛顿法迭代公式的推演

20、中可以看到，迭代点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿迭代公式，有时会使函数值上升 。阻尼牛顿法： 阻尼因子 ，沿牛顿方向进行一维搜索的最佳步长，由下式求得： 40 阻尼牛顿法程序框图41方法特点： （1） 初始点应选在X*附近，有一定难度； （2） 尽管每次迭代都不会是函数值上升，但不能保证每次下降 ； （3） 若迭代点的海赛矩阵为奇异，则无法求逆矩阵，不能构造牛顿法方向； （4）不仅要计算梯度，还要求海赛矩阵及其逆矩阵，计算量和存储量大。此外，对于二阶不可微的F(X)也不适用。 虽然阻尼牛顿法有上述缺点，但在特定条件下它具有收敛

21、最快的优点，并为其他的算法提供了思路和理论依据。42一般迭代式：梯度法：牛顿法：阻尼牛顿法：433、 变尺度法 DFP变尺度法首先有戴维顿（Davidon）与1959年提出，又于1963年由弗莱彻（Fletcher）和鲍维尔加以发展和完善，成为现代公认的较好的算法之一。 DFP法是基于牛顿法的思想又作了重要改进。这种算法仅用到梯度，不必计算海赛阵及其逆矩阵，但又能使搜索方向逐渐逼近牛顿方向，具有较快的收敛速度。 44 基本思想： 变尺度法的基本思想与牛顿法和梯度法有密切联系。观察梯度法和牛顿法的迭代公式 x(k+1)=x(k)-(k)g(k)和 xk+1 = xk - (k)G(xk)-1 g

22、(k) 分析比较这两种方法可知： 梯度法的搜索方向为-g(k) ，只需计算函数的一阶偏导数，计算量小，当迭代点远离最优点时，函数值下降很快，但当迭代点接近最优点时收敛速度极慢。 牛顿法的搜索方向为- G(xk)-1 g(k) ，不仅需要计算一阶偏导数，而且要计算二阶偏导数及其逆阵，计算量很大，但牛顿法具有二次收敛性，当迭代点接近最优点时，收敛速度很快。 45 思考： 若迭代过程先用梯度法，后用牛顿法并避开牛顿法的海赛矩阵的逆矩阵的烦琐计算，则可以得到一种较好的优化方法，这就是“变尺度法”产生的基本构想。 为此，综合梯度法和牛顿法的优点，提出变尺度法的基本思想。 变尺度法的基本迭代公式写为下面的

23、形式： xk+1 = xk - kA(k) g(k) 式中的A(k)为构造的n n阶对称矩阵，它是随迭代点的位置的变化而变化的。 变尺度法的搜索方向- A(k) g(k) ，称为拟牛顿方向。 若A(k) =I，上式为梯度法的迭代公式，若A(k) = G(xk)-1 ，上式为阻尼牛顿法的迭代公式。当矩阵Ak 不断地迭代而能很好地逼近A(k) = G(xk)-1 时，就可以不再需要计算二阶导数。变尺度法的关键在于尺度矩阵Ak的产生 。46尺度矩阵的概念： 通过坐标变换可以改变函数的偏心程度，我们也称之为尺度变换。尺度变换能显著地改进几乎所有极小化方法的收敛性质。 如用梯度法求f(x)=x12+25

24、x22的极小值时，需要迭代10次才能到达极小点x*=0 0T。若作变换 y1=x1 y2=5x2则可以将函数的等值线由椭圆变为圆，即(y)=y12+y22，从而消除了函数的偏心，用梯度法只需一次迭代即能求得极小点。47 用Q-1右乘等式两边，得 QTG=Q-1 再用Q左乘等式两边，得 QQTG=I 所以 QQT=G-1 这说明二次函数矩阵G的逆阵，可以通过尺度变换矩阵Q求得。 QQT实际上是在空间内测量距离大小的一种度量，称为尺度矩阵，记作A，即 A= QQT 对于一般二次函数 为减低函数二次项的偏心程度，进行尺度变换 xQx则在新的坐标系中，函数的二次项变为 若矩阵是正定的，则总存在矩阵Q使

25、 QTGQ=I将函数的偏心变为零。48 尺度变换矩阵的建立： 根据变尺度法的基本原理，需要构造一个变尺度矩阵序列Ak来逼近海赛逆矩阵序列Gk-1，每迭代一次，尺度改变一次。 从初始矩阵A0=I(单位矩阵)开始，通过对公式 中修正矩阵Ak 的不断修正，在迭代中逐步逼近于Gk-1. 因此，一旦达到最优点附近，就可望达到牛顿法的收敛速度。 49 尺度变换矩阵的建立： 根据变尺度法的基本原理，需要构造一个变尺度矩阵序列Ak来逼近海赛逆矩阵序列Gk-1，每迭代一次，尺度改变一次。 为了建立变尺度矩阵Ak ，必须对其附加某些条件。 1、为保证迭代公式的下降性质，要求Ak中的每一个矩阵都是对称正定的。因为若

26、要求搜索方向Sk= - Akgk 为下降方向，即要求gkT Sk 0，也就是 -gkT Akgk 0 ，即Ak应为对称正定。 2、要求Ak之间的迭代具有简单的形式，显然Ak+1= Ak+ Ak 为最简单的形式，其中Ak为校正矩阵。 3、要求必须满足拟牛顿条件。Ak+1 gk= xk其中： gk= gk+1-gk xk= xk+1-xk50一般步骤： 1、选定初始点和收敛精度； 2、计算初始点处的梯度，选取初始对称正定矩阵A0，置k=0。 3、计算搜索方向Sk= - Akgk 4、沿Sk方向一维搜索，计算gk+1、 gk 、 xk 。 5、判断是否满足终止准则，若满足输出最优解，否则转6。 6、

27、当迭代n次还未找到极小点，重置Ak为单位矩阵，并以当前点为初始点返回2，否则转7。 7、计算Ak+1= Ak+ Ak ，置k=k+1返回3。51 DFP算法由于舍入误差和一维搜索的不精确，有可能导致Ak奇异，而使数值稳定性方面不够理想。所以1970年提出更稳定的算法，称为BFGS算法，其校正公式为5253方法评价： DEF变尺度法以逐次逼近的方法实现 H-1 的计算，当目标函数的一阶导数易求时，以一阶代替二阶导数的计算是有效的方法。 算法的第一步是梯度法，最速下降；接近 x* 时，又采用二次收敛的共轭方向，总的收敛速度较快。 H(k) 近似代表 x(k)点的二阶导数，当其为零时，可判断 x(k

28、)为鞍点。 H(k) 的计算较复杂，存储量较大。 算法稳定性较差，由于计算机有舍入误差，容易使 H (k) 的正定性破坏，趋于奇异。 54例： 用DFP算法求下列问题的极值：解： 1）取初始点 ，为了按DFP法构造第一次搜寻方向d0，需计算初始点处的梯度取初始变尺度矩阵为单位矩阵A0=I，则第一次搜寻方向为 55沿d0方向进行一维搜索，得为一维搜索最佳步长，应满足得:,2）再按DFP法构造点x1处的搜寻方向d1，需计算56代入校正公式=57=第二次搜寻方向为:再沿d1进行一维搜索，得58为一维搜索最佳步长，应满足,得3）判断x2是否为极值点梯度: 海赛矩阵 : 梯度为零向量,海赛矩阵正定。可见

29、点满足极值充要条件，因此为极小点。594、 共轭方向法 1.共轭方向： 设G为nn阶实对称正定矩阵，如果有两个n维向量d0和d1满足 ，则称向量d0与d1 关于矩阵G共轭。当G为单位矩阵时，假设目标函数f(x) 在极值点附近的二次近似函数为对二维情况：任选取初始点x0沿某个下降方向d0作一维搜索，得x160 因为 是沿d0方向搜索的最佳步长，即在点x1处函数f（x）沿方向d0的方向导数为零。考虑到点x1处方向导数与梯度之间的关系，故有 如果按最速下降法，选择负梯度方向 为搜索方向，则将发生锯齿现象 。 取下一次的迭代搜索方向d1直指极小点x*。0d0 x0 x1x*111d1d161 如果能够

30、选定这样的搜索方向，那么对于二元二次函数只需顺次进行d0、d1两次直线搜索就可以求到极小点x* ，即有那么这样的d1方向应该满足什么条件呢 ?对于前述的二次函数:当 时，x*是f(x)极小点，应满足极值必要条件，故有将等式两边同时左乘 得：有62 就是使d1直指极小点x* ， d1所必须满足的条件 。 两个向量d0和d1称为G的共轭向量，或称d0和d1对G是共轭方向。 共轭方向的性质：性质1 若非零向量系d0,d1,d2,dm-1是对G共轭，则这m个向量是线性无关的。性质2 在n维空间中互相共轭的非零向量的个数不超过n。 性质3 从任意初始点出发，顺次沿n个G的共轭方向d0,d1, d2,进行

31、一维搜索，最多经过n次迭代就可以找到的二次函数f(x)极小点。 63关键：新的共轭方向确定？64 在无约束方法中许多算法都是以共轭方向作为搜索方向，它们具有许多特点。根据构造共轭方向的原理不同，可以形成不同的共轭方向法。 65共轭梯度法： 共轭梯度法是共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。 从xk出发，沿负梯度方向作一维搜索: 设与dk共轭的下一个方向dk+1由dk和点xk+1的负梯度的线形组合构成，即：共轭条件：66则：解得：令为函数的泰勒二次展开式则上两式相减，并代入67将式与式两边相乘，并应用共轭条件得：因此68算法步骤：69算法特点： 共轭梯度

32、法属于解析法，其算法需求一阶导数，所用公式及算法简单，所需存储量少。该方法以正定二次函数的共轭方向理论为基础，对二次型函数可以经过有限步达到极小点，所以具有二次收敛性。但是对于非二次型函数，以及在实际计算中由于计算机舍入误差的影响，虽然经过n次迭代，仍不能达到极小点，则通常以重置负梯度方向开始，搜索直至达到预定精度，其收敛速度也是较快的。70，已知初始点1,1T例： 求下列问题的极值解： 1）第一次沿负梯度方向搜寻 计算初始点处的梯度为一维搜索最佳步长，应满足迭代精度 。 得:712）第二次迭代：代入目标函数由得从而有：因收敛。725、 坐标轮换法 坐标轮换法属于直接法，既可以用于无约束优化问

33、题的求解，又可以经过适当处理用于约束优化问题求解。 坐标轮换法是每次搜索只允许一个变量变化，其余变量保持不变，即沿坐标方向轮流进行搜索的寻优方法。它把多变量的优化问题轮流地转化成单变量（其余变量视为常量）的优化问题，因此又称这种方法为变量轮换法。此种方法只需目标函数的数值信息而不需要目标函数的导数。73基本思想：搜索方向与步长： 每次以一个变量坐标轴作为搜索方向，将 n维的优化问题转化为一维搜索问题。例，第 k轮迭代的第 i 次搜索，是固定除 xi外的 n-1 个变量，沿 xi 变量坐标轴作一维搜索，求得极值点 xi(k) n 次搜索后获得极值点序列 x1(k), x2(k）, xn(k)，若

34、未收敛，则开始第 k+1 次迭代，直至收敛到最优点 x*。 74终止准则： 可以采用点距准则或者其它准则。注意： 若采用点距准则或函数值准则，其中采用的点应该是一轮迭代的始点和终点，而不是某搜索方向的前后迭代点。75流程图:入口给定：x0，K=1i=1Xik=x0沿ei方向一维搜索求ixik=xi-1k+ ikeix=xk f=f(x)i=n?|xnk-x0k|?x*=xf*=f(x*)出口i=i+1x0=x0kk=k+1NYNY76方法评价： 方法简单，容易实现。 当维数增加时，效率明显下降。 收敛慢，以振荡方式逼近最优点。 受目标函数的性态影响很大。 如图 a) 所示，二次就收敛到极值点；

35、 如图 b) 所示，多次迭代后逼近极值点； 如图 c) 所示，目标函数等值线出现山脊（或称陡谷），若搜索到 A 点，再沿两个坐标轴，以t0步长测试，目标函数值均上升，计算机判断 A 点为最优点。事实上发生错误。776、 鲍威尔方法 鲍威尔法是以共轭方向为基础的收敛较快的直接法之一，是一种十分有效的算法。 1964年，鲍维尔提出这种算法，其基本思想是直接利用迭代点的目标函数值来构造共轭方向，然后从任一初始点开始，逐次沿共轭方向作一维搜索求极小点。并在以后的实践中进行了改进。 78对函数：基本思想：在不用导数的前提下，在迭代中逐次构造G的共轭方向。 共轭方向的生成：jjkkkdddjggk+1xx

36、k+1 设xk, xk+1为从不同点出发，沿同一方向dj进行一维搜索而到的两个极小点。 这种方法是在研究具有正定矩阵G的二次函数的极小化问题时形成的。79 梯度和等值面相垂直的性质, dj和 xk, xk+1两点处的梯度gk,gk+1之间存在关系:另一方面，对于上述二次函数，其xk, xk+1两点处的梯度可表示为:因而有取 这说明只要沿dj方向分别对函数作两次一维搜索，得到两个极小点xk和xk+1 ，那么这两点的连线所给出的方向dk就是与dj一起对G共轭的方向。80算法步骤：（二维情况为例）81 方法的基本迭代格式包括共轭方向产生和方向替换两主要步骤。 把二维情况的基本算法扩展到n维，则鲍威尔

37、基本算法的要点是： 在每一轮迭代中总有一个始点（第一轮的始点是任选的初始点）和n个线性独立的搜索方向。从始点出发顺次沿n个方向作一维搜索得一终点，由始点和终点决定了一个新的搜索方向。 用这个方向替换原来n个方向中的一个，于是形成新的搜索方向组。替换的原则是去掉原方向组的第一个方向而将新方向排在原方向的最后。 此外规定，从这一轮的搜索终点出发沿新的搜索方向作一维搜索而得到的极小点，作为下一轮迭代的始点。这样就形成算法的循环。 82 鲍威尔基本算法的缺陷： 可能在某一环迭代中出现基本方向组为线性相关的矢量系的情况。 如第k环中，产生新的方向： Sk=xnk-x0k=1kS1k+ 2kS2k + +

38、 nkSnk 式中， S1k、S2k 、 、 Snk为第k环基本方向组矢量， 1k 、 2k 、 、 nk为个方向的最优步长。 若在第k环的优化搜索过程中出现1k =0，则方向Sk表示为S2k 、 S3k 、 、 Snk的线性组合，以后的各次搜索将在降维的空间进行，无法得到n维空间的函数极小值，计算将失败。83 如图所示为一个三维优化问题的示例，设第一环中1 =0 ，则新生方向与e2 、e3共面，随后的各环方向组中，各矢量必在该平面内，使搜索局限于二维空间，不能得到最优解。鲍威尔基本算法的退化x1x2x31=01e23e3S184 鲍威尔修正算法： 在某环已经取得的n+1各方向中，选取n个线性无关的并且共轭程度尽可能高的方向作为下一环的基本方向组。