1、第四章第四章 无约束优化方法无约束优化方法 第一节第一节 概概 述述研究无约束优化问题的目的：研究无约束优化问题的目的：1 1、有些问题的数学模型本身就是一个无约束优、有些问题的数学模型本身就是一个无约束优化问题；化问题；2 2、通过研究无约束优化问题，为研究约束优化、通过研究无约束优化问题，为研究约束优化问题打下基础；问题打下基础；3 3、有些约束优化问题的求解可以通过一系列无、有些约束优化问题的求解可以通过一系列无约束优化方法来达到。约束优化方法来达到。所以无约束优化问题的方法是优化设计方所以无约束优化问题的方法是优化设计方法的基本组成部分，也是优化方法的基础。法的基本组成部分，也是优化方
2、法的基础。数学模型：数学模型：求求n维设计变量维设计变量Tn21xxxx使目标函数使目标函数 对对 没有任何限制条件没有任何限制条件 minfxx 对于无约束优化问题的求解，可以直接应对于无约束优化问题的求解，可以直接应用第二章讲述的极值条件来确定极值点位置，用第二章讲述的极值条件来确定极值点位置，这就是把求函数极值问题变成求解方程这就是把求函数极值问题变成求解方程 的问题。的问题。0f 即求即求 ，使其满足：，使其满足：x0 xf0 xf0 xfn21数值计算方法最常用的是搜索法。数值计算方法最常用的是搜索法。基本思想：基本思想：从给定的初始点从给定的初始点 出发，沿某一搜索方出发，沿某一搜
3、索方向向 进行搜索，确定最佳步长进行搜索，确定最佳步长 ，使函数，使函数值沿值沿 下降最大。依此方法按下述公式不断下降最大。依此方法按下述公式不断进行，形成迭代的下降算法。进行，形成迭代的下降算法。0 x0d00d,kkkk1k210dxx 各种无约束优化方法的区别就在于确定其各种无约束优化方法的区别就在于确定其搜索方向搜索方向 的方法不同，所以搜索方向的构成的方法不同，所以搜索方向的构成是无约束优化方法的关键。是无约束优化方法的关键。kd 是第是第k+1次搜索方向，称为搜索或迭代次搜索方向，称为搜索或迭代方向。方向。kd 它是根据数学原理由目标函数和约束条件它是根据数学原理由目标函数和约束条
4、件的局部信息状态形成的。的局部信息状态形成的。确定确定 的方法很多，相应的确定使的方法很多，相应的确定使 取极值的取极值的 方法也是不同的，方法也是不同的，具体方法在一维搜索方法中已进行了讨论。具体方法在一维搜索方法中已进行了讨论。kdkkkfdx*k 根据构成搜索方向所使用的信息性质的不根据构成搜索方向所使用的信息性质的不同，无约束优化方法可分为两类：同，无约束优化方法可分为两类：间接法：间接法：利用目标函数的一阶或二阶导数。利用目标函数的一阶或二阶导数。如：最速下降法，如：最速下降法，牛顿法。牛顿法。直接法：直接法：利用目标函数值。利用目标函数值。如：坐标轮换法如：坐标轮换法 ，单形替换法
5、及鲍威尔，单形替换法及鲍威尔法。法。第二节第二节 最最 速速 下下 降降 法法 优化设计是追求目标函数值优化设计是追求目标函数值 最小。因最小。因此，一个很自然的想法是从某一点此，一个很自然的想法是从某一点 出发，其出发，其搜索方向搜索方向 取该点的负梯度方向（最速下降方取该点的负梯度方向（最速下降方向），使函数值在该点附近的范围内下降最快。向），使函数值在该点附近的范围内下降最快。按此规律不断走步，形成以下迭代的算法：按此规律不断走步，形成以下迭代的算法：xfxd,kfkkk1k210 xxx 由于最速下降法是以负梯度方向作为搜索由于最速下降法是以负梯度方向作为搜索方向的，所以最速下降法又称
6、为梯度法。方向的，所以最速下降法又称为梯度法。为了使目标函数值沿搜索方向为了使目标函数值沿搜索方向 能获得最大的下降值，其步长因子能获得最大的下降值，其步长因子 应取一应取一维搜索的最佳步长，即：维搜索的最佳步长，即：kf xk minffminfffkkkkk1kxxxxx 根据一元函数极值的必要条件和多元复合函根据一元函数极值的必要条件和多元复合函数求导公式，得：数求导公式，得：0fffkTkkkxxx即即或或0ffkT1kxx0kT1kdd例例4-14-1求目标函数求目标函数 的极小点的极小点 222125xxfx解：解：T022x104f0 x100450 x2xf0210 xx000
7、0001100242100422fxxx 22110022542f x01002500042800002003072.03125262602001103071785.0919877.1100242x 686164.3f1x经经1010次迭代后次迭代后 0f00 x*T*x讨论：讨论：令令22115xyxy 2221yyfyxT022x即即T0102y1040y 2042y2y210y0000001201042204102yyy 221201042y02010404280005.0522600020104200y 01y 2221yyfyx2122221212122221yy2002yy21yy
8、y,yxx50002xx2125xxx,xf1121 最速下降法的收敛速度和变量的尺度关系最速下降法的收敛速度和变量的尺度关系很大，这一点可以从最速下降法收敛速度的估很大，这一点可以从最速下降法收敛速度的估计式上来看。计式上来看。在适当条件下，有：在适当条件下，有：*k22*1kMm1xxxx海赛矩阵最大特征值上界海赛矩阵最大特征值上界海赛矩阵最小特征值下界海赛矩阵最小特征值下界 当相邻两个迭代点之间满足上式时，称相当相邻两个迭代点之间满足上式时，称相应的迭代方法具有线性收敛速度的迭代方法。应的迭代方法具有线性收敛速度的迭代方法。因此最速下降法是具有线性收敛速度的迭因此最速下降法是具有线性收敛
9、速度的迭代法。代法。第三节第三节 牛顿型方法牛顿型方法 牛顿型方法和最速下降法一样，也是求解牛顿型方法和最速下降法一样，也是求解极值问题古老的算法之一。极值问题古老的算法之一。对于一元函数，牛顿迭代公式：对于一元函数，牛顿迭代公式：0,1,2,kxfxfxxkkk1k 对于多元函数对于多元函数 f(x)，设，设 xk 为为 f(x)极小点极小点x*的一个近似点，在的一个近似点，在 x*处将处将 f(x)进行泰勒进行泰勒展开，保留到二次项，得：展开，保留到二次项，得：kk2TkkTkk-f-21-fffxxxxxxxxxxx 设设 为为 的极小点，它作为的极小点，它作为 极极小点小点 的下一个近
10、似点。根据极值的必要条的下一个近似点。根据极值的必要条件：件：1kx x xf*x0 x1k即即 0 xxk1kk2kxfxf得得k1k2k1kffxxxx这就是多元函数求极值的牛顿迭代公式。这就是多元函数求极值的牛顿迭代公式。对于二次函数，上述泰勒展开式不是近似对于二次函数，上述泰勒展开式不是近似的，而是精确的。的，而是精确的。是一个常矩阵，其中是一个常矩阵，其中各元素均为常数。因此无论从任何点出发，只各元素均为常数。因此无论从任何点出发，只需一步就可以找到极小点。牛顿方法是二次收需一步就可以找到极小点。牛顿方法是二次收敛的。敛的。k2xf例：例：用牛顿法求用牛顿法求 的极小值的极小值222
11、12125xxx,xf解：解：T022x则则100450 x2xf0210 xx 50002xf02 5010021xf102代入牛顿法迭代公式代入牛顿法迭代公式001004501002122ff010201xxxx经过一次迭代即求得极小点经过一次迭代即求得极小点 从牛顿迭代公式的推演中可以看到，迭代从牛顿迭代公式的推演中可以看到，迭代点的位置是按照极值条件确定的，其中并未含点的位置是按照极值条件确定的，其中并未含有沿下降方向搜寻的概念。因此对于非二次函有沿下降方向搜寻的概念。因此对于非二次函数，如果采用上述牛顿法迭代公式，有时会使数，如果采用上述牛顿法迭代公式，有时会使函数值上升，为此需对上
12、述牛顿法进行改进，函数值上升，为此需对上述牛顿法进行改进，引入数学规划法的搜寻概念，提出所谓的阻尼引入数学规划法的搜寻概念，提出所谓的阻尼牛顿法。牛顿法。k1k2kffxxd称为牛顿方向称为牛顿方向阻尼牛顿法采取如下迭代公式：阻尼牛顿法采取如下迭代公式：,2,1,0kffk1k2kkkkk1kxxxdxx阻尼因子阻尼因子可通过极小化过程求得：可通过极小化过程求得：kkkkk1kfminffdxdxx 这样，原来的牛顿法就相当于阻尼牛顿这样，原来的牛顿法就相当于阻尼牛顿法的步长因子取成固定值法的步长因子取成固定值1 1的情况。的情况。由于阻尼牛顿法每次迭代都是在牛顿方由于阻尼牛顿法每次迭代都是在
13、牛顿方向上进行一维搜索，这就避免了迭代后函数值向上进行一维搜索，这就避免了迭代后函数值上升的现象，从而保持了牛顿法二次收敛性，上升的现象，从而保持了牛顿法二次收敛性，而对初始点的选取并没有苛刻的要求。而对初始点的选取并没有苛刻的要求。阻尼牛顿法的计算步骤：阻尼牛顿法的计算步骤：1 1）给定初始点）给定初始点 ，收敛精度，收敛精度 ；0 x2 2）计算）计算k1k2k1k2k2kfffffxxdxxx0k 3 3）求）求kkk1kdxx4 4）检查收敛精度，若满足，停机；）检查收敛精度，若满足，停机；否则，否则，返回返回2 2），继续搜索。），继续搜索。1kk 牛顿法和牛顿阻尼法统称为牛顿型法。
14、主牛顿法和牛顿阻尼法统称为牛顿型法。主要缺点是每次迭代都要计算函数的二阶导数矩要缺点是每次迭代都要计算函数的二阶导数矩阵，并对该矩阵求逆，这样工作量很大，特别阵，并对该矩阵求逆，这样工作量很大，特别是矩阵求逆，当维数高时工作量更大。是矩阵求逆，当维数高时工作量更大。最速下降法的收敛速度比牛顿法慢，而牛最速下降法的收敛速度比牛顿法慢，而牛顿法又存在上述缺点，针对最速下降法，提出顿法又存在上述缺点，针对最速下降法，提出共轭梯度法；针对牛顿法提出变尺度法。共轭梯度法；针对牛顿法提出变尺度法。第七节第七节 坐坐 标标 轮轮 换换 法法 坐标轮换法是每次搜索中只允许一个变量坐标轮换法是每次搜索中只允许一
15、个变量变化，其余变量保持不变。即沿坐标方向轮流变化，其余变量保持不变。即沿坐标方向轮流进行搜寻的方法。进行搜寻的方法。它把多变量的优化问题轮流的转化成单变它把多变量的优化问题轮流的转化成单变量（其余变量视为常量）的优化问题。因此又量（其余变量视为常量）的优化问题。因此又称这种方法为变量轮换法。称这种方法为变量轮换法。在搜索过程中可以不需要目标函数的导数，在搜索过程中可以不需要目标函数的导数，只需目标函数值信息。只需目标函数值信息。特点：特点：简单易行，但由于只能轮流沿简单易行，但由于只能轮流沿n个坐标方个坐标方向前进，因而效率低下，特别是维数较高或目向前进，因而效率低下，特别是维数较高或目标函
16、数性态不好的情况下，收敛速度很慢。标函数性态不好的情况下，收敛速度很慢。第九节第九节 单单 形形 替替 换换 法法基本原理：基本原理：函数的导数是函数性态的反映，它对选择函数的导数是函数性态的反映，它对选择搜索方向提供了有用的信息。搜索方向提供了有用的信息。在不计算导数的情况下，先算出若干点处在不计算导数的情况下，先算出若干点处的函数值，从它们之间的大小关系中也可看出的函数值，从它们之间的大小关系中也可看出函数变化的大概趋势，为寻求函数的下降方向函数变化的大概趋势，为寻求函数的下降方向提供依据。提供依据。这里所说的若干点，一般取在单纯形的顶这里所说的若干点，一般取在单纯形的顶点上。点上。所谓单
17、纯形是指在所谓单纯形是指在 n 维维空间中具有空间中具有 n+1个顶点的多面体。个顶点的多面体。利用单纯形的顶点，计算其函数值并加以利用单纯形的顶点，计算其函数值并加以比较，从中确定有利的搜索方向和步长，找到比较，从中确定有利的搜索方向和步长，找到一个较好的点取代单纯形中较差的点，组成新一个较好的点取代单纯形中较差的点，组成新的单纯形来代替原来的单纯形，使单纯形不断的单纯形来代替原来的单纯形，使单纯形不断地向目标函数的极小点靠近，直到搜索到极小地向目标函数的极小点靠近，直到搜索到极小点为止。点为止。以二元函数为例，说明单形替换法的基本以二元函数为例，说明单形替换法的基本思想：思想：在在 平面上
18、取不在同一条直线上的平面上取不在同一条直线上的三点三点 ，以它们为顶点组成一个单，以它们为顶点组成一个单纯形，计算各顶点函数值，设：纯形，计算各顶点函数值，设：21xx 321xxx321fffxxx1414452xxxxxx反射点反射点计算反射点的函数计算反射点的函数值，可能出现以下值，可能出现以下几种情况：几种情况：1 1）35ffxx扩张扩张1446xxxx扩张因子，扩张因子，1.2 1.2 2.02.0如果如果56ffxx扩张成功！扩张成功！否则，扩张不利！否则，扩张不利！2 2）253fffxxx反射可行！反射可行！3 3）152fffxxx4 4）15ffxx4547xxxx收缩因
19、子，收缩因子，0.50.5若若 则用则用 代替代替 ，构成新的单，构成新的单纯形，否则，纯形，否则，不用。不用。57ffxx7x1x7x4141448xxxxxxx若 则用 代替 ，构成新的单纯形，否则，不用，转5）18ffxx8x1x8x5）缩边 以上说明，可以通过反射、扩张、收缩和以上说明，可以通过反射、扩张、收缩和缩边等方式得到一个新单纯形，其中至少有一缩边等方式得到一个新单纯形，其中至少有一个顶点的函数值比原单纯形要小。个顶点的函数值比原单纯形要小。二、计算步骤二、计算步骤 将上述对二元函数的处置方法扩展应用到将上述对二元函数的处置方法扩展应用到多元函数中，其计算步骤如下：多元函数中，
20、其计算步骤如下：1 1）构造初始单纯形）构造初始单纯形2 2）计算各顶点的函数值）计算各顶点的函数值3 3）比较函数值的大小，确定最好点）比较函数值的大小，确定最好点 ，最，最差点差点 和次差点和次差点 ，即有：，即有：LxHxGx,n1,h-1,h0,1,2,ifmaxff,n0,1,2,ifmaxff,n0,1,2,ifminffiiGGiiHHiiLLxxx4 4）检验是否满足收敛准则）检验是否满足收敛准则LLHfff如满足，则如满足，则 ，停机，否则转，停机，否则转5 5）L*xx 5 5）计算除）计算除 点之外各点的重心点之外各点的重心Hx1nxn0iHi1nn1xxx反射点：反射点
21、：2n2nH1n2nff2xxxx当当 时，以时，以 代替代替 ，构成新，构成新单纯形，然后返回单纯形，然后返回3 3）；）；G2nLfff2nxHx6 6）扩张：当）扩张：当 时，取扩张点：时，取扩张点：L2nff1n2n1n3nxxxx3n3nffx当当 时，以时，以 代替代替 ，构成新单，构成新单纯形，否则以纯形，否则以 代替代替 ，代替代替 形成新的单纯形，然后返回形成新的单纯形，然后返回3 3）；）；2n3nff3nxHx2nxHx2nfHf7 7）收缩：当）收缩：当 时，则需要收缩。时，则需要收缩。G2nff4nx4n4nffx 否则以否则以 代替代替 ，计算收缩点，计算收缩点 及
22、及其函数值其函数值 ，如果，如果 ，则以，则以 代代替替 ，代替代替 ，形成新的单纯形，形成新的单纯形，然后返回然后返回3 3）；否则转）；否则转8 8）。）。H4nffHx4nx2nxHxHf4nf1n2n1n4nxxxx4nf 如果如果 则取收缩点：则取收缩点：H2nffLiiLLi2121xxxxxxn,2,1,0i并返回到2）。8 8）缩边：将单纯形缩边，可将向量）缩边：将单纯形缩边，可将向量n,2,1,0iLi xx的长度都缩小一半，即：的长度都缩小一半，即：例4-7 试用单形替换法求下列函数的极小值：2221216x5x4x,xf第四节第四节 共轭方向及共轭方向法共轭方向及共轭方向
23、法一、共轭方向的概念一、共轭方向的概念 为了直观起见，首先考虑二维情况：为了直观起见，首先考虑二维情况：二元二次函数的等值线为一族椭圆，任选二元二次函数的等值线为一族椭圆，任选一点一点 沿某一方向沿某一方向 作一维搜索得作一维搜索得0 x0d1x0001dxx 因为因为 是沿是沿 方向搜索的最佳步长，方向搜索的最佳步长，即在即在 点处函数点处函数 沿沿 方向的方向导方向的方向导数为零。数为零。00d1x0d xf 0ff0T1x01dxd111*dxx 应该满足什应该满足什么条件？么条件？1d对于具有正定矩阵对于具有正定矩阵的二次函数的二次函数 cxbGxxxTT21f有有 bGxx11f当当
24、 时，时，*1xx 01由于由于 是函数是函数 的极小点，应满足极值必要的极小点，应满足极值必要条件。故有：条件。故有：*x xf 0Gddxd1T011T0f即即将上式两边同时左乘将上式两边同时左乘 ，并注意，并注意 T0d01 0GdxbGdGxbdxGx111111111*ff 0Gdd1T0 就是关于就是关于G 的共轭矩阵的共轭矩阵1d0d二、共轭方向的性质二、共轭方向的性质 0*bGxxf*定义：定义：设设G为为nn对称正定矩阵，若对称正定矩阵，若n维空间中有维空间中有m个非零向量个非零向量 满足：满足：1m10,ddd ji1m,2,1,0j,i0jTiGdd则称则称 对对G共轭，
25、或称它们是共轭，或称它们是G的的共轭方向。共轭方向。1m10,ddd当当 时（单位矩阵）则：时（单位矩阵）则：IG ji0jTidd即向量即向量 互相正交。互相正交。1m10,ddd 由此，共轭是正交的推广，正交是共轭的由此，共轭是正交的推广，正交是共轭的特例。特例。性质性质1 1：若非零向量系若非零向量系 是对是对G的共轭，的共轭，则这则这m个向量是线性无关的。个向量是线性无关的。1m10,ddd性质性质2 2：在在n维空间中互相共轭的非零向量的个数维空间中互相共轭的非零向量的个数不超过不超过n个。个。性质性质3 3：从任意初始点从任意初始点 出发，顺次沿出发，顺次沿n个个G的共的共轭方向轭
26、方向 进行一维搜索，最多经过进行一维搜索，最多经过n次迭代就可以找到二次函数次迭代就可以找到二次函数 的极小的极小点点 。0 x1n10ddd,*x xf 此性质表明，这种迭代方法具有二次收敛此性质表明，这种迭代方法具有二次收敛性。性。这就是为使这就是为使 直指极小点直指极小点 ，所必所必须满足的条件。须满足的条件。1d*x1d三、共轭方向法三、共轭方向法 共轭方向法是建立在共轭方向性质共轭方向法是建立在共轭方向性质3 3的基的基础上的，它提供了求二次函数极小点的原则方础上的，它提供了求二次函数极小点的原则方法。其步骤是：法。其步骤是：1 1）选定初始点）选定初始点 ，下降方向，下降方向 和收
27、和收敛敛 精度，置精度，置 。0 x0d0k2 2）沿）沿 方向进行一维搜索，得方向进行一维搜索，得kdkkk1kdxx3 3）判断）判断 是否满足，若满足，是否满足，若满足，停机，否则转停机，否则转4 4。1kxf4 4）提供新的共轭方向）提供新的共轭方向 ，使，使1kd k210j01kTj,Gdd5 5）置）置 ，转，转2 2。1 kk 提供共轭向量系的方法有许多种，从而形提供共轭向量系的方法有许多种，从而形成各种具体的共轭方向法，如共轭梯度法，鲍成各种具体的共轭方向法，如共轭梯度法，鲍威尔法等。威尔法等。这里首先介绍格拉姆这里首先介绍格拉姆-施密特向量系共轭施密特向量系共轭化方法，它是
28、格拉姆化方法，它是格拉姆-施密特向量系正交方法施密特向量系正交方法的推广。的推广。设已选定线性无关向量系设已选定线性无关向量系1-n10vvv,取取00vd 令令01011dvd 0dvGdGdd0101T01T0 0T01T010GddGvd 00T01T011dGddGvdvd设已求得共轭向量设已求得共轭向量k10ddd,现求现求1kd令令rk0rr,1k1k1kdvd为使为使 与与 共轭，应有共轭，应有1kdjd 0dvGdGddk0rrr,1k1kTj1kTj由此解得由此解得 Tjk 1k 1,jTjj dGvdGd于是于是 jk0jjTj1kTj1k1kdGddGvdvd例例4-3
29、4-3 求求210121012 G的一组共轭向量系的一组共轭向量系012,dd d 0e1e2e解：选三个坐标轴上的单位向量解：选三个坐标轴上的单位向量、作为一组线性无关向量系作为一组线性无关向量系012100010001 eee取取00100 de设设10110ded01100021001001211012012101210012100120TT dGedGd-得得 1101211012000 d设设 21022120dedd12211121001101210201212132102110121120120TT dGedGd-022000210010012100121021011001210
30、0120TT dGedGd-得得 211302220133100 d计算表明计算表明0,0,1,20Tijiji jijdGd说明说明012,dd d对对G G共轭。共轭。上述算法是针对二次函数的，但也上述算法是针对二次函数的，但也可以用于一般非二次函数。可以用于一般非二次函数。非二次函数在极小点附近可用二次非二次函数在极小点附近可用二次函数来近似。函数来近似。*ffxxxGxxxxT21 式中的海赛矩阵相当于二次函数中式中的海赛矩阵相当于二次函数中的矩阵的矩阵 ，但，但 未知。当迭代点未知。当迭代点 充充分靠近分靠近 时，可用时，可用 构造共轭向量构造共轭向量系。系。G0 x*x*x0 xG
31、 更有效的共轭方法是构造共轭向量更有效的共轭方法是构造共轭向量系时避开海赛矩阵。系时避开海赛矩阵。共轭梯度法是共轭方向法中的一种，因为共轭梯度法是共轭方向法中的一种，因为在该方法中每一个共轭矢量都是依赖迭代点处在该方法中每一个共轭矢量都是依赖迭代点处的负梯度而构造出来的，所以称为共轭梯度法。的负梯度而构造出来的，所以称为共轭梯度法。对二次函数：对二次函数：cxbGxxxTT21f第五节第五节 共共 轭轭 梯梯 度度 法法从从 点出发，沿点出发，沿 的某一共轭方向的某一共轭方向 作一维搜作一维搜索，到达索，到达 点，即点，即kxGkd1kx1kkkkxxd或或1kkkkxxd而在而在 、点处的梯
32、度点处的梯度 、分别为分别为kx1kxkg1kgkkgGxb11kkgGxb所以所以11()kkkkkkggG xxGd若若 和和 对对 是共轭的，则有是共轭的，则有kdjdG()0jTkdGd所以所以1()()0jTkkdgg计算过程：计算过程：1 1）设初始点）设初始点 ，第一个搜索方向取，第一个搜索方向取 点的负梯点的负梯度度 ，即，即 ，沿，沿 进行一维搜索，进行一维搜索，得得 ，并计算出，并计算出 点处的梯度点处的梯度 。是以是以 为切线和某等值线的切点。根据梯度和为切线和某等值线的切点。根据梯度和该点等值面切面相垂直的性质，因此该点等值面切面相垂直的性质，因此 和和 正正交，有交，
33、有 ，从而，从而 和和 正交，正交，即即 ，和和 组成平面正交系。组成平面正交系。0 x0 x0g00 dg0d1000 xxd1x1g1x0d1g0d01()0Tdg1g0g100Tg g1g0g2 2）在）在 、所构成的平面正交系中求所构成的平面正交系中求 的共的共轭方向轭方向 ，作为下一步的搜索方向。把，作为下一步的搜索方向。把 取取成成 与与 两个方向的线性组合，即两个方向的线性组合，即0g1g0d1d1d1g0d1010 dgd由由110()()0Tdgg有有211102000TTgg gg gg此式展开，由于此式展开，由于 ，可求得，可求得100Tg g01()0Tdg211012
34、0 gdgdg01010()()0Tgdgg1d2111xxd2g120Tdg沿沿方向进行一维搜索，得方向进行一维搜索，得，并算出该点梯度，并算出该点梯度，有，有，即，即01020Tgdg0d1d因为和共轭，有0210Tdgg0g1g2g由此可知、构成一个正交系。0g1g2g0d1d2d3 3）在）在、所构成的正交系中，求与所构成的正交系中，求与和和均共轭的方向均共轭的方向。设设 221100 dggg 2d0d1d因为要求因为要求与与和和均共轭，有均共轭，有 2110010211002100TTgggggggggg1110002211100TTTTg gg gg gg g令令11，有，有22
35、2211211111011000TTTT gg gg ggg gg g所以所以 22110021110001211021 dggggggggdgd则：则：2221221 gdgdg再沿再沿2d方向继续进行一维搜索，如此继续方向继续进行一维搜索，如此继续下去可求得共轭方向的递推公式：下去可求得共轭方向的递推公式：21k+1120,1,2,1kkkkkn gdgdgL 沿着这些共轭方向一直搜索下去，直到最后沿着这些共轭方向一直搜索下去，直到最后迭代点处梯度的模小于给定允许值为止。迭代点处梯度的模小于给定允许值为止。若目标函数为非二次函数，经若目标函数为非二次函数，经n n次搜索还未次搜索还未达到最
36、优点时，则以最后得到的点作为初始点达到最优点时，则以最后得到的点作为初始点，重新计算共轭方向，一直到满足精度要求为，重新计算共轭方向，一直到满足精度要求为止。止。例例4.4 用共轭梯度法求以下二次函数的极小点用共轭梯度法求以下二次函数的极小点及极小值。及极小值。221212112,242f x xxxxx x 解：取初始点解：取初始点 01 1Tx则则 01200212244422xxfxxxgx 取取 0042 dg沿沿 方向进行一维搜索，得方向进行一维搜索，得 0d01000001 414121 2 xxd令令 11minf x则则 10001401021411 22 x 为建立第二个共轭
37、方向为建立第二个共轭方向 1d，需计算，需计算 1x点处的梯点处的梯度及系数度及系数 0值，得值，得 11211212241422xxfxxxgx 2102051204gg从而求得第二个共轭方向从而求得第二个共轭方向1010214132242 dgd再沿再沿 1d进行一维搜索，得进行一维搜索，得 1211111222213132222 xxd令令 22minfx则则 2101112122413222 x 计算计算 点处的梯度点处的梯度2x21222212240420 xxfxx xgx 0说明说明 点满足极值必要条件，再根据点满足极值必要条件，再根据 点的点的海赛矩阵海赛矩阵2x2x22224
38、G x是正定的，可知是正定的，可知 满足极值充分必要条件。故满足极值充分必要条件。故为极小点，即为极小点，即2x*242 xx*8f x 从共轭梯度法的计算过程可以看出，第一从共轭梯度法的计算过程可以看出，第一个搜索方向取作负梯度方向，这就是最速下降个搜索方向取作负梯度方向，这就是最速下降法。其余各步的搜索方向是将负梯度偏转一个法。其余各步的搜索方向是将负梯度偏转一个角度，也就是对负梯度进行修正。所以共轭梯角度，也就是对负梯度进行修正。所以共轭梯度法实质上是对最速下降法进行的一种改进，度法实质上是对最速下降法进行的一种改进，故它又被称作故它又被称作旋转梯度法旋转梯度法。上述共轭梯度法是上述共轭
39、梯度法是19641964年由弗来彻（年由弗来彻（FletcherFletcher）和里伍斯（）和里伍斯（ReevesReeves）两人提出的。）两人提出的。此法的优点是程序简单，存储量少，具有最速此法的优点是程序简单，存储量少，具有最速下降法的优点，而在收敛速度上比最速下降法下降法的优点，而在收敛速度上比最速下降法快，具有二次收敛性。快，具有二次收敛性。第六节第六节 变变 尺尺 度度 法法一、尺度矩阵的概念一、尺度矩阵的概念 变量的尺度变换是放大或缩小各个坐标变量的尺度变换是放大或缩小各个坐标。通过尺度变换可以把函数的偏心程度降低到。通过尺度变换可以把函数的偏心程度降低到最低限度。最低限度。如
40、：如：221212,25f x xxx11225yxyx221212,y yyy对于一般二次函数对于一般二次函数 12TTfcxx Gxb xxQx1122TTTx Gxx Q GQx则在新的坐标系中，函数则在新的坐标系中，函数 的二次项变为的二次项变为 fx目的：降低二次项的偏心程度。目的：降低二次项的偏心程度。若矩阵若矩阵G 是正定的，则总存在矩阵是正定的，则总存在矩阵Q 使使TQ GQI将函数偏心度变为零。将函数偏心度变为零。右乘上式两边右乘上式两边 1Q1TQ GQQ 左乘上式两边左乘上式两边 TQQ GI所以所以 1TQQG说明二次函数矩阵说明二次函数矩阵G 的逆阵，可以通过尺度变的
41、逆阵，可以通过尺度变换矩阵换矩阵Q 来求得。来求得。牛顿法迭代过程中的牛顿方向便可写成牛顿法迭代过程中的牛顿方向便可写成 1kkTkff dGxQQx 牛顿法迭代公式即为牛顿法迭代公式即为 1kkkkTkkkfxxdxQQx 例如例如12212121222011,2505022Txf x xxxxxxx Gx20050G102105 2Q11002010221050101005 25 2TQ GQI1111000222111000505 25 2TGQ Q牛顿法牛顿法 1kkTkkfxxQQx 梯度法梯度法 1kkkkfxxx x空间内测空间内测量距离大小量距离大小的一种度量的一种度量，称作尺
42、度，称作尺度矩阵矩阵H THQQ变换前变换前12Txx x变换后变换后 111222TTTTHxQxQxxQQxx Hx 为使这种尺度有用，必须对一切非零向量为使这种尺度有用，必须对一切非零向量的的x均有均有 ，即要求尺度矩阵，即要求尺度矩阵H正定。正定。0Tx Hx1kkkkfxxHx 因此，牛顿法就可看成是经过尺度变换后因此，牛顿法就可看成是经过尺度变换后的梯度法。经过尺度变换，使函数偏心率减小的梯度法。经过尺度变换，使函数偏心率减小到零，函数的等值面变为球面（或超球面），到零，函数的等值面变为球面（或超球面），使设计空间中任意点处函数的梯度都通过极小使设计空间中任意点处函数的梯度都通过极
43、小点，用最速下降法只需一次迭代就可达到极小点，用最速下降法只需一次迭代就可达到极小点。点。二、二、变尺度矩阵的建立变尺度矩阵的建立 对于一般函数对于一般函数 ，当用牛顿法寻求极，当用牛顿法寻求极小点时，其牛顿迭代公式为小点时，其牛顿迭代公式为 fx110,1,2,kkkkkkxxG gL2kkkkffgxGx 为避免在迭代公式中计算海赛矩阵的逆阵，可为避免在迭代公式中计算海赛矩阵的逆阵，可用在迭代中逐步建立的变尺度矩阵用在迭代中逐步建立的变尺度矩阵kkHH x来替换来替换 ，即构造一个矩阵序列，即构造一个矩阵序列 来逼来逼近海赛逆矩阵序列近海赛逆矩阵序列 。每迭代一次，尺度。每迭代一次，尺度就
44、改变一次，这就是就改变一次，这就是“变尺度变尺度”的含义。的含义。1kGkH1kG10,1,2,kkkkkkxxH gLkkk dH g当当 时，它就变成最速下降法。时，它就变成最速下降法。kHI为了使变尺度矩阵为了使变尺度矩阵 确实与确实与 近似，并具近似，并具有容易计算的特点，必须对有容易计算的特点，必须对 附加某些条附加某些条件。件。kH1kGkH1 1）为保证迭代公式具有下降性质，要求）为保证迭代公式具有下降性质，要求 中中的每一个矩阵都是对称正定的。的每一个矩阵都是对称正定的。kH 因为若要求搜索方向因为若要求搜索方向 为下降方为下降方向，即要求向，即要求 ，也就是，也就是 ，即即
45、，亦即，亦即 应为对称正定。应为对称正定。kkk dH g0Tkkg d0Tkkkg H g0Tkkkg H gkH2 2）要求）要求 之间的迭代具有简单的形式。之间的迭代具有简单的形式。kH 显然显然 为最简单的形式，其中为最简单的形式，其中 为校正矩阵。该式称作校正公式。为校正矩阵。该式称作校正公式。1kkkHHEkE3 3）要求）要求 必须满足必须满足拟牛顿条件拟牛顿条件。kH设迭代过程已进行到设迭代过程已进行到 步，步，、均已均已求出，现在推导求出，现在推导 所必须满足的条件。所必须满足的条件。1k 1kg1kx1kH当当 为具有正定矩阵为具有正定矩阵G的二次函数时，根据的二次函数时，
46、根据泰勒展开可得泰勒展开可得 fx11kkkkggG xx111kkkkGggxx 因为具有正定海赛矩阵因为具有正定海赛矩阵 的一般函数，的一般函数，在极小点附近可用二次函数很好的近似，所以在极小点附近可用二次函数很好的近似，所以就联想到如果迫使就联想到如果迫使 满足类似于上式的关系满足类似于上式的关系1kG1kH111kkkkkHggxx拟牛顿条件拟牛顿条件 11kkkkkkyggsxx令令1kkkHys则则根据上述拟牛顿条件，不通过海赛矩阵求逆就根据上述拟牛顿条件，不通过海赛矩阵求逆就可以构造一个矩阵可以构造一个矩阵 来逼近海赛距阵的逆阵来逼近海赛距阵的逆阵 ，这类方法统称作拟牛顿法。，这
47、类方法统称作拟牛顿法。1kH11kG 由于变尺度矩阵的建立应用了拟牛顿条件由于变尺度矩阵的建立应用了拟牛顿条件，所以变尺度法也是一种拟牛顿法。，所以变尺度法也是一种拟牛顿法。还可以证明，变尺度法对于具有正定矩阵还可以证明，变尺度法对于具有正定矩阵G的二次函数，能产生对的二次函数，能产生对G共轭的搜索方向，因共轭的搜索方向，因此变尺度法又可以看成是一种共轭方向法。此变尺度法又可以看成是一种共轭方向法。三、三、变尺度法的一般步骤变尺度法的一般步骤 对一般多元函数对一般多元函数 ，用变尺度法求极，用变尺度法求极小点小点 的一般步骤是：的一般步骤是：fx*x1 1）选定初始点）选定初始点 和收敛精度和
48、收敛精度 ；0 x2 2）计算）计算 ，选取初始对称正定矩阵，选取初始对称正定矩阵 （例如（例如 ），），；00fgx 0H0HI0k 3 3）计算搜索方向）计算搜索方向 ；kkk dH g4 4）沿）沿 方向进行一维搜索方向进行一维搜索 ，计，计算算 ，；kd1kkkkxxd11kkfgx 1kkksxx1kkkygg5 5）判断是否满足迭代终止准则，满足则）判断是否满足迭代终止准则，满足则 ，停机，否则转，停机，否则转6 6）；）；*1kxx6 6）当迭代）当迭代n n次后还没找到极小点时，重置次后还没找到极小点时，重置 为为单位矩阵单位矩阵I I，并以当前设计点为初始点，并以当前设计点为
49、初始点 ，返回到，返回到2 2）进行下一轮迭代，否则转到）进行下一轮迭代，否则转到7 7）；）；kH01kxx7 7）计算矩阵）计算矩阵 ，置，置 ，返，返回到回到3 3）。）。1kkkHHE1kk 对于校正矩阵对于校正矩阵 ，可由具体的公式来计，可由具体的公式来计算，不同的公式对应不同的变尺度法，将在下算，不同的公式对应不同的变尺度法，将在下面进行讨论。但不论哪种变尺度法，面进行讨论。但不论哪种变尺度法，必须满必须满足拟牛顿条件足拟牛顿条件kEkE1kkkHyskkkkHEys即即或或kkkkkE ysH y 满足上式的满足上式的 有无穷多个，因此上述变有无穷多个，因此上述变尺度法（属于拟牛
50、顿法）构成一族算法。尺度法（属于拟牛顿法）构成一族算法。kE四、四、DFP算法算法 在变尺度法中，校正矩阵在变尺度法中，校正矩阵 取不同的形取不同的形式，就形成不同的变尺度法。式，就形成不同的变尺度法。kEDFP算法中的校正矩阵算法中的校正矩阵 取下列形式：取下列形式：kETTkkkkkkkEu uv v对称秩一对称秩一 对称秩一对称秩一 kkkkkE ysH yTTkkkkkkkkkku uv vysH yTTkkkkkkkkkkku u yv v ysH y若取若取 TTkkkkkkkkkkk u u ysv v yH y取取 kkkkkusvH y11kkTTkkkkk s yy H y
