最优化理论与方法2(2014-简版)

1、最优化理论与方法讲义(下)第三章 整数规划线性规划问题的最优解可能是分数或小数，但对于某些问题，常要求解必须是整数(称为整数解)。这样的问题称为整数线性规划(integer linear programming)，简称ILP。一、 整数规划(IP)(1) 要求一部分或全部决策变量取整数值的规划问题称为整数规划。u 不考虑整数条件，由余下的目标函数和约束条件构成的规划问题称为整数规划的松弛问题。u 若松弛问题是一个线性规划，则称整数规划为整数线性规划。(2) 整数线性规划的一般形式 (3) 整数线性规划问题的种类 纯整数线性规划它指全部决策变量都必须取整数值的整数线性规划。 0-1型整数线性规划

2、决策变量只能取值0或1的整数线性规划。 混合整数线性规划决策变量中有一部分必须取整数值，另一部分可以不取整数值的整数线性规划。(4) 举例例1：工厂和生产某种物资。由于该种物资供不应求，故需要再建一家工厂。相应的建厂方案有和两个。这种物资的需求地有、四个。各工厂年生产能力、各地年需求量、各厂至各需求地的单位物资运费，见下表：工厂或开工后，每年的生产费用估计分别为1200万或1500万元。现要决定应该建设工厂还是，才能使今后每年的总费用最少。解：这是一个物资运输问题，特点是事先不能确定应该建还是中哪一个，因而不知道新厂投产后的实际生产物资。为此，引入0-1变量：再设为由运往的物资数量，单位为千吨

3、；表示总费用，单位万元。则该规划问题的数学模型可以表示为：例2：现有资金总额为。可供选择的投资项目有个，项目所需投资额和预期收益分别为和，此外由于种种原因，有三个附加条件： 若选择项目1，就必须同时选择项目2。反之不一定； 项目3和4中至少选择一个； 项目5、6、7中恰好选择2个。应该怎样选择投资项目，才能使总预期收益最大。解：对每个投资项目都有被选择和不被选择两种可能，因此分别用0和1表示，令表示第j个项目的决策选择，记为：投资问题可以表示为：二、 整数规划的求解线性规划问题的最优解可能是分数或小数，为满足整数解的要求，似乎可以把已得到的带有分数或小数的解“舍入化整”。这种方法可行吗？例 设

4、整数规划问题如下： 用图解法求出最优解为：x13/2, x2 = 10/3，且有Z = 29/6。 现求整数解(最优解)：如用舍入取整法可得到4个点，即(1,3), (2,3), (1,4), (2,4)。显然，它们都不可能是整数规划的最优解。 按整数规划约束条件，其可行解肯定在线性规划问题的可行域内且为整数点。故整数规划问题的可行解集是一个有限集。由上例看出，将线性规划的最优解经过“化整”来解原整数线性规划，虽是最容易想到的，但常常得不到整数线性规划的最优解，甚至根本不是可行解。1、整数规划问题解的特征l 最优点不一定在顶点处取得；l 最优解不一定是松弛问题最优解的邻近整数解；l 整数可行解

5、远多余于顶点，枚举法不可取；l 可行解是其松弛问题的可行解，反之不一定，但如果松弛问题的最优解还满足整数约束条件，是整数规划的最优解。2、整数规划问题的求解方法2.1 割平面法1、基本思想：由松弛问题的可行域向整数规划的可行域逼近。2、方法：利用超平面切除要求：(1)整数解保留；(2)松驰问题最优值增加。具体为：即 首先不考虑变量 xi 是整数这一条件，仍然是用解线性规划的方法去解松弛问题。 若得到非整数的最优解，则增加线性约束条件(或称为割平面)，割去非整数解，切割掉原可行域的一部分，使得只切割掉非整数解，没有切割掉任何整数可行解。以下仅讨论纯整数线性规划的情形。例 求解 目标函数 约束条件

6、： 先不考虑条件的整数约束条件，求得相应的松弛线性规划的最优解为：，最优值为。最优解是图中域的极点，但不符合整数约束条件。现设想，如能找到像CD那样的直线去切割域，去掉三角形域ACD，那么具有整数坐标的C点(1，1)就是域的一个极点。如在域上求解原来的松弛问题，而得到的最优解又恰巧在C点，就得到原问题的整数解，所以解法的关键是怎样构造一个这样的“割平面”CD，尽管它可能不是唯一的，也可能不是一步能求到的。首先，将松弛规划化为标准型，即在原问题的前两个不等式中增加非负松弛变量x3、x4，使两式变成等式约束： 用单纯形表求解，见下表。由于目前得到的解不满足整数最优解要求，需要考虑将带有分数的最优解

7、的可行域中分数部分割去，再求最优解。然后，可从最终计算表中得到非整数变量对应的关系式：为了得到整数最优解，将上式变量的系数和常数项都分解成整数和非负真分数两部分之和 然后将整数部分与分数部分分开，移到等式左右两边，得到现考虑整数约束条件要求都是非负整数，于是由条件、可知也都是非负整数，这一点对以下推导是必要的，如不都是整数，则应在引入之前乘以适当常数，使之都是整数。上式中，从等式左边看是整数；等式右边也应是整数，即则整数条件可由下式所代替：即 这就得到一个切割方程(或称为切割约束)，将它作为增加约束条件，再解例题。引入松弛变量x5，得到等式将这新的约束方程加到上述的最终计算表，得下表。这从表的

8、b列中可看到，这时得到的是非可行解，于是需要用对偶单纯形法继续进行计算。选择为换出变量，计算将做为换入变量，再按原单纯形法进行迭代，得表。由于的值已都是整数，解题已完成。注意：新得到的约束条件 如用表示，由、式得这就是平面内形成的新的可行域，即包括平行于轴的直线和这直线下的可行区域，整数点也在其中，没有切割掉，见图。求一个切割方程的步骤为：Step1令是相应线性规划最优解中为分数值的一个基变量，由单纯形表的最终表得到： (3-4)其中，指构成基变量的指标集合；，指构成非基变量的指标集合。Step2 将和都分解成整数部分与非负真分数之和，即 (3-5)而N表示不超过b的最大整数。例如：若b=2.

9、35， 则N=2，f=0.35若b= 0.45，则N= 1，f=0.55代入(3-4)式得 (3-6)Step3 现在提出变量(包括松弛变量)为整数的条件。 (3-6)这时，上式由左边看必须是整数，但由右边看，因为，所以不能为正，即 (3-7)这就是一个切割方程。由(3-4)式，(3-6)式，(3-7)式可知：切割方程(3-7)式真正进行了切割，至少把非整数最优解这一点割掉了。没有割掉整数解，这是因为相应的线性规划的任意整数可行解都满足(3-7)式的缘故。2.2 分枝定界法 对于规模较小的问题，变量个数很少，可行解的组合数也较小时，这个方法是可行的，也是有效的。但对于大型问题，可行的整数组合数

10、会很大。例如在指派问题中，将n项任务指派n个人去完成，不同的指派方案共有n!种，当n=10时，可能的指派方案数超过300万；当n=20时，超过21018。显然，穷举法是不可取的。(1) 分枝定界法的简介20世纪60年代初由Land Doig和Dakin等提出，是解整数线性规划的重要方法之一。基本思想：将要求解的整数规划问题逐步通过设置某些决策变量的范围，把问题分解成若干子问题，对每个子问题再利用去掉整数约束得到松弛的子问题，使用线性规划方法求解松弛子问题，得到原问题最优值的上界。考虑最大化整数线性规划问题A，与它相应的线性规划记为问题B 若B无可行解，则A无可行解； 若B有最优解，且满足整数约

11、束，则它也是A的最优解； 若B有最优解，但不满足整数约束条件，这时B的最优值是A的最优值的上界；分枝定界法可用于解纯整数或混合整数线性规划问题，考虑如下问题 2、解题步骤(以极大化问题为例)(1)确定整数规划最优解的上下界l 若B无可行解，则A无可行解，停机；l 若B有最优解且为整数解，则此解为A的最优解，停机；l 若B有最优解但不是整数解，记目标函数值是；l 用观察法找A的一个可行整数解，其函数值记为。若观察不到，则可令，即得(2)分枝、求解(增加约束条件将问题分枝)任意选一个非整数解的变量，在松弛问题中加上约束： 和 组成两个新的松弛问题，称为分枝，并求解这两个问题。举例：松弛问题：松弛问

12、题的最优解：则分解为二个子问题和： (3)定界、剪枝u 定界：修改上界：每解完一对分枝后，都要修改上界，在所有未被分枝的问题中找出最优目标函数值的最大者作为新的上界。在分枝定界法的整个过程中上界的值不断减少。修改下界：每求出一次已符合整数条件的可行解时，都要修改下界。在所有符合条件的各分枝中，找出目标函数值最大者作为新的下界。在分枝定界法的整个过程中，下界的值不断增大。u 剪枝若分枝无可行解树叶，则剪掉该分枝；分枝的最优目标函数值，剪掉该分枝(枯枝)；若分枝的最优目标函数值，则继续分枝，转，直到 ，则。注：继续分枝时，先对目标函数值较大的那枝进行分枝求解。对目标函数值较差的那一枝暂且放下，待目

13、标函数值较优的那枝全部分解到不能再分解，再考虑目标函数值较差的那枝。例：用分枝定界法求解整数规划问题(用图解法计算)解：首先去掉整数约束，变成一般线性规划问题用图解法求(LP)的最优解，如图所示。， 即也是(IP)最大值的上限。取对于，取值和；对于，取值和。先将(LP)划分为(LP1)和（LP2），取，则有下式：现在只要求出（LP1）和（LP2）的最优解即可。首先求(LP1)，如图所示。其在B点取得最优解，。此时 找到整数解，此枝停止计算。其次，求(LP2)，如图所示。其在C点取得最优解，。此时， 由于，原问题可能有比16更大的最优解，但不是整数，故利用和，加入条件。对于LP2，加入条件：和，

14、则有下式：然而分别求出(LP21)和(LP22)的最优解即可。LP21：在D点取得最优解。即，。此时， LP22：无可行解，不再分枝。由于LP21中不是整数，可继续分枝，即(LP211)和( LP212)。求解过程同上，在此略。LP211：在E点取得最优解，即，。此时， LP212：在F点取得最优解，即，。至此，原问题(IP)的最优解为：，。上述求解过程用一个树形图表示如右：结论1：(IP)的最优解一定在某个子问题中；2：子问题的可行域父问题的可行域 子问题的最优值父问题的最优值；3：子问题中的整数解都是（IP）的可行解。第四章 非线性规划的基本理论一、 数学基础1、多元函数的泰勒展开多元函数

15、在点作泰勒展开，取其前三项。写成矩阵形式： 式中称为的海森(Hessian)矩阵，常用表示。由于元函数的偏导数有个，而偏导数的值与求导次序无关，所以函数的二阶偏导矩阵是对称矩阵。例1：一般二元二次函数 ，求。解： 4.2 方向导数与梯度具有n个自变量的函数在点的一阶偏导数记为它是一个标量。函数的偏导数仅仅描述了函数沿其自变量所在坐标轴的特定方向上的变化率在许多实际问题中，常常需要知道函数沿其它任一方向上的变化率。对这样的问题就要借助于函数的方向导数来描述。4.2.1 方向导数二元函数在点处沿某一方向的方向导数方向导数实质上是偏导数概念的推广，其关系为：元函数在点处沿方向的方向导数 当，值在点处

16、沿方向是增加的(或称的方向是在处的上升方向)； 当，值在点处沿方向是减少的(或称的方向是在处的下降方向)； 当，方向与的等值面相切，这时，在点处沿S方向不增也不减。 从同一点出发，沿不同方向的方向导数不相同。犹如爬山一样，把目标函数值看作山的海拔高度，方向导数不同犹如沿不同的路线或方向山的坡度不一样。方向导数越大，表明沿这个方向或路线山的坡度越大。问题：从点出发，可以有无穷多个方向，那么究竟哪一个方向函数的变化率最大呢？这个问题要借助于函数的梯度来判定。4.2.2 最速下降方向二元函数的梯度 其中 为函数在点处的梯度。可见，函数在点的梯度是由函数在该点的各个一阶偏导数组成的向量。设，则 梯度方

17、向和S方向重合时，方向导数值最大。梯度的模为：当为单位向量，则有梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值，负梯度方向函数值下降最快。梯度方向与等值线的关系，如右图所示。由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。梯度两个重要性质：性质1：函数在某点的梯度不为零，则必与过该点的等值面垂直；性质2：梯度方向是函数具有最大变化率的方向。例1 试求目标函数在点处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。解：由于则函数在处的最速下降方向是这个方向上的单位向量是：则新点为：几个常用的梯度公式：(1)，则；(2)

18、 ,则；(3) ,则;(4) ，为对称矩阵，则。因此，对于一般二次函数，。4.3 二次函数及正定矩阵二次函数的一般形式为：其中均为常数，且。其向量矩阵表示形式是：其中，为对称矩阵。定义：设Q为nn对称矩阵(1)若，均有，则称矩阵Q是正定的；(2)若，均有，则称矩阵Q是负定的；(3)若，均有，则称矩阵Q是半正定的；(4)若，均有，则称矩阵Q是半负定的。对于满足(1) (4)情形的二次型，称其为有定的；如果不是上述四种情形，则称其为不定的。l 一个nn对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶主子式都是正的。即， ， l 一个nn对称矩阵Q是负定矩阵的充要条件是矩阵Q的各阶主子式的值负、正相间。

19、， ， 如果Q是正定的，则目标函数的等值面是同心椭球面族，且其中心点为4.4 凸函数与凸规划当极值点能使在整个可行域中为最小值时，即在整个可行域中对任一都有时，则就是最优点，且称为全域最优点或整体最优点。若为局部可行域中的极小值而不是整个可行域中的最小值时，则称为局部最优点或相对最优点。最优化的目标是全域最优点。 函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。 一、凸函数具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单峰函数。1、定义：设为定义在维欧氏空间中的一个凸集上的函数，如果对任何实数以及对中

20、任意两点恒有：则为上的凸函数。2、几何意义在凸函数曲线上取任意两点(对应于轴上的坐标)联成一直线线段，则该线段上任一点(对应于轴上的点)的纵坐标值必大于或等于该点处的原函数值。 3、性质(1)若为定义在凸集上的一个凸函数，且 是一个正数（），则也必是定义在凸集上的凸函数；(2)定义在凸集上的两个凸函数，其和亦必为该凸集上的一个凸函数；(3)若为定义在凸集上的两个凸函数，和为两个任意正数，则函数仍为上的凸函数。二、凸性条件(1)若为定义在凸集上且具有连续一阶导数的函数，则为凸函数的充分必要条件为：对于任意两点，不等式恒成立。(2)设为定义在凸集上具有连续二阶导数的函数，则在上为凸函数的充分必要条

21、件是海赛矩阵在上处处半正定。三、凸规划对于约束优化问题式中若、均为凸函数，则称此问题为凸规划。凸规划有如下性质：(1)若给定一点，则集合为凸集。此性质表明，当为二元函数时其等值线呈现大圈套小圈形式；(2)可行域为凸集；(3)凸规划的任何局部最优解就是全局最优解。4.5 无约束优化问题的极值条件多元函数极值定义：在点的某邻域内，若，则为严格极大值点；，则为严格极小值点。 极值存在的必要条件：即(零向量)，点为驻点。 极值存在的充要条件：且需通过二阶导数来判断。若，即是正定的，则为严格极小值点；若，即是负定的，则为严格极大值点。4.6 约束优化问题的极值条件 无约束优化设计问题最优解：不受约束条件

22、限制，使目标函数达到最小值的一组优化变量，即最优点和最优值构成无约束问题最优解。约束优化设计问题最优解：满足约束条件，使目标函数达到最小值的一组设计变量，即最优点和最优值构成约束问题最优解。4.6.1 有约束问题最优点的几种情况1、无适时约束目标函数是凸函数，可行域是凸集，则最优点是内点。(相当于无约束问题的最优点, 如图(a)。 图(a)2、有适时约束(1)目标函数是凸函数，可行域是凸集，则目标函数等值线与适时约束曲面的切点为最优点，而且是全局最优点，如图(b)。 图(b)(2)目标函数是非凸函数(图c），或可行域是非凸集(图d）： 图(c) 图(d)则目标函数等值线与适时约束曲面可能存在多

23、个切点，是局部极值点，其中只有一个点是全局最优点。4.6.2 拉格朗日乘子法拉格朗日乘子法是求解等式约束优化问题的另一种经典方法，它是通过增加变量将等式约束优化问题变成无约束优化问题。所以又称作升维法。(1)等式约束设目标函数为受约束于，则构建一新函数式中为拉格朗日乘子。由无约束极值条件，则极值必要条件为： 由上述解出的，即为目标函数的极值点。例：求函数的极值点，受约束于 。解：由约束极值必要条件： 代入中，则得其极值点为(2)不等式约束极值条件(Kuhn-Tuker条件)设目标函数为和受约束于，则构建一新函数式中为将转化为等式约束的松弛变量。则存在极值的必要条件(由等式约束极值条件得)： 对

24、于凸函数(目标函数)，K-T条件也是充分条件，此时为部分最优解，也必为问题全局的最优解。将上式中松弛变量消去得到：(3)既有不等式约束又有等式约束问题K-T条件这就是著名的库恩塔克条件(kuhn-Tucker)。K-T条件的几何意义在于：如果是一个局部极小点，则该点的目标函数应落在该点诸约束面(所有起作用约束条件)梯度和组成的角锥范围内。图(a)中设计点不是约束极值点 图(b)的设计点是约束极值点。K-T条件是多元函数取得约束极值的必要条件，以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。对于目标函数和约束函数都是凸函数的情况，符合K-T条件的点一定是全局最优点。这种情况K

25、-T条件即为多元函数取得约束极值的充分必要条件。例 库恩塔克（K-T）条件应用举例判断1 0T是否为约束最优点。解：(1)当前点为可行点，因满足约束条件：；(2)在起作用约束为和，因(3)各函数的梯度：(4)求拉格朗日乘子、即 则得到 ，由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足K-T条件第五章 一维搜索算法求一元函数的最优点及其最优值，就是一维求优，或一维搜索。一维搜索优化方法是优化方法中最简单、最基本的方法。它不仅用来求解一维目标函数的求优问题，更常用于多维优化问题在既定搜索方向上寻求最优步长的一维搜索。一维优化方法分为二类：一类为直接法，即按照某种规律取若干点计算其目标函

26、数值，并通过比较目标函数值来确定最优值，如黄金分割法、格点法等；另一类为间接法，即解析法，需要利用导数，如插值法、切线法等。5.1 一维优化方法其数值迭代方法亦称为一维搜索方法。优化算法的基本迭代公式中点已由前一步迭代计算得到，搜索方向由某种优化方法规定。因此本次迭代点由步长，使点处的目标函数最小。数值迭代法公式：假定给定了搜索方向，从点出发沿方向进行搜索，要确定步长，使得记即确定步长，就是单变量函数的搜索问题，称为一维搜索问题。一维搜索的思路: (1)确定极小点所在的区间a, b，在此区间内，函数呈现“大小大”变化趋势搜索区间。(2)在a, b内找将区间长度逐步缩短。0.618法与二次插值法

27、就是解决第二个步骤的方法二、搜索区间的确定(进腿法)基本思想：对任选一个初始点及初始步长，确定第二点；通过比较这两点函数值的大小，确定第三点位置；比较这三点的函数值大小，确定是否为 “高低高” 形态。初始搜索区间：a, b（以含有唯一极小点的“单峰区间”为例）初始探查确定进退 进行前进或后退寻查 确定搜索区间的方法与步骤、试探运算取试点，并计算函数值选择一个初始点和初始步长：第一个试点：(如)，令步长；第二个试点：。然后计算各个试点的函数值：和比较函数值和。l “前进运算”；l “后退运算”；l (区间找到)、前进运算加大步长(例如加大一倍)取第三个点，并计算函数值。，比较相邻的最后两点的函数

28、值和。 步长加倍，继续前进运算。取第四个试点，比较第三和第四个试点的函数值，如此反复循环，直到在相继的三个试点中，出现“高低高”的函数值情形为止。上述比较第三、第四试点的函数值，实质上是将原来的三个试点：向前(向后)移动一步。若新求得的：，则重复上面向前移动的步骤直到成立为止：、后退运算反向排列原来的两个试点并加大步长取第三个试点，计算相应的函数值。，比较最后相邻两点的函数值和。 步长加倍，继续后退运算。取新试点(新试点为新的，原来的向左移动一步：；)，计算其函数值，重复上述比较过程，如此反复循环，直到在相继的三个试点中，出现“高低高”的函数值情形为止。此时，区间的左右端点为：。例 用进退法确

29、定函数的一维优化初始搜索区间a,b。设初始点，初始步长。解：按顺序进行计算，有(1) ， ， (2)比较，作前进运算，步长加大一倍，即。则，(3)比较，继续作前进运算，步长再加大一倍，即。则 ，(4)由于，则此时初始搜索区间为1,7，即，。5.2 黄金分割法(0.618法)一、消去法的基本原理基本思路：逐步缩小搜索区间，直至最小点存在的区间达到允许的误差范围为止。设一元函数的起始搜索区间为，为的极小点。在搜索区间内任取两点。且，计算、。将、进行比较，可能出现三种情况：(1) 。在这种情况下，可以丢掉部分，而最小点必定在内；(2) 。此时，可以丢掉部分，而最小点必定在内。(3) ，此情形，可以丢

30、掉部分，也可以丢掉部分，而最小点必定在内。因此，这种情况可以并入上面的任意一种情况。二、0.618的由来黄金分割法就是基于上述原理来选择区间内计算点的位置，它有以下要求：(1) 点在中的位置对称；(2)每次区间的缩短率不变，或称要求保留的区间长度与原区间长度之比等于被消去的区间长度与保留区间长度之比，即令，代入上式，则有求解得到 该方法保证每次迭代都以同一比率缩小区间，缩短率为0.618，故黄金分割法又称0.618法。三、0.618法的迭代过程及算法框图(1)在初始区间内取两个计算点，其值分别为计算和，令，。(2)比较函数值，缩小搜索区间，则丢掉区间部分，取为新区间，在计算中作置换：，,则丢掉

31、区间部分，取为新区间，在计算中作置换：,，(3)判断迭代终止条件当缩短的区间距离小于某一个预先规定的精度，即时，终止迭代。一般取符合精度要求的缩短后区间的中点作为最优解。即例 用0.618法求一元函数的极小点。初始搜索区间为，取迭代精度。解：(1)在初始区间内取二点，并计算函数值 (2)比较函数值，缩短搜索区间由于，故，(3)判断迭代终止条件由于，因此需继续缩短区间。，新点，由于，故，判断迭代终止条件：，继续缩短！，新点，由于，故，判断迭代终止条件：，继续缩短！， 新点，由于，故，判断迭代终止条件：因此迭代终止，取（理论解）。四、Fibonacci法(斐波那契数列法)(1) 问题的提出由0.6

32、18法可知，经次迭代后的搜索区间的长度。当事先给定搜索算法的迭代次数时，问按何种规则选取试探点可以使给定的搜索区间长度最快地缩短？(2) 思路由0.618法的推导过程知：在一般搜索算法的迭代过程中，缩短率满足，且。又知：经次迭代后的搜索区间的长度。待解决的问题转化为优化问题：可以证明，此优化问题的最优解为其中数列为Fibonacci数列，即满足条件：因此，Fibonacci法又称分数法。其迭代公式为：(3) 注意事项l 迭代次数n-1的确定若原始区间为，要求最终区间长度，则即，这就可以确定(查下表)。Fibonacci数列012345678910111211235813213455891442

33、33l 第n-1次迭代中两个试点的选取方式在第次迭代时，由于试点，此时可令其中为辨别常数。或者(4) 算法步骤Step 1 给定初始区间(要保证函数在该区间上是单峰的)及精度要求，辨识常数，计算迭代次数，使。Step 2 计算最初两个试探点：计算函数值和，置。Step 3 若时，转第Step4；否则转第Step5。Step 4 向右搜索。令，并计算(或)和，转Step 6。Step 5 向左搜索。令，并计算(或)和，转Step 6。Step 6 置，若，转Step3；若，转Step7。Step 7 令(或)，计算。若，则令；否则，令，停止计算，极小点含于，可取其中点或函数值较小的端点作为近似极

34、小值点。举例：用Fibonacci法求函数在区间上的极小点。要求最终区间长度不大于原始区间长度的0.08倍。解：函数在区间上为下单峰函数。由，查表可知。第一次迭代：此时由于，缩短后区间为第二次迭代：，则， 。，此时，缩短后区间为第三次迭代：，则，。，此时，缩短后区间为。第四次迭代：，则，。，。此时，缩短后区间为。第五次迭代：，则，。现令，则，此时，缩短后区间为。由于，可取近似极小值点为0.548，近似极小值为1.752。缩短后区间长度为0.548-0.231=0.317，而0.317/4=0.079250.08。述评：(1) Fibonacci法的优点效率最高，有限个试点的情况下，可将最优点所

35、在的区间缩小到最小。(2) Fibonacci法的缺点搜索前先要计算搜索的步数；每次搜索试点计算的公式不一致.(3) Fibonacci法与0.618法的主要区别：一是需要先计算出迭代次数；二是区间收缩的比率不是常数，而是由Fibonacci数列来确定。(4) Fibonacci法与0.618法的关系： ，表明时，两者的区间缩短率相同，或称0.618法为Fibonacci法的极限形式。 Fibonacci法较0.618法更有效，但0.618法简单易行，应用更广泛。5.3 牛顿法牛顿迭代法(Newtonsmethod)又称为牛顿-拉夫逊方法(Newton-Raphsonmethod)，它是牛顿在

36、17世纪提出的一种在实数域和复数域上近似求解方程的方法，其基本思想是利用目标函数的二次Taylor展开，并将其极小化。牛顿法使用函数的泰勒级数的前面几项来寻找方程的根。牛顿法是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时非线性收敛，但是可通过一些方法变成线性收敛。1、基本思想在极小点附近，将目标函数进行二阶Taylor展开为二次多项式，用该多项式的极小点近似原问题的极小点。对目标函数在初始点进行二阶Taylor展开：为求的驻点，令，则因此新的极小点 又令2、牛顿法的几何解释(1)在下图中，在处用一抛物线代替曲线，用一斜直线代替曲线

37、。这样各个近似点是通过对作切线后求得与轴的交点找到的，所以，牛顿法又称作切线法。 牛顿迭代公式(通式)：令，和分别为在点处的梯度和Hesse矩阵。则迭代通式可写成称为牛顿方向。(2)当正定时，是一个超椭球面，在二维时右边所表示的就是等高线为一族椭圆，的极小点就是这个椭圆的中心，以此中心作为极小点的新的近似。结论：设存在连续二阶导数，满足、，初始点接近，由牛顿法产生的迭代序列收敛于。3、计算步骤给定目标函数及梯度、，精度要求。(1)选定初始点，计算、，置；(2)若，迭代停止，得到；否则，进行下一步；(3)计算，然后由方程，解出；(4)计算，以及、；(5)转步骤(2)。说明：牛顿法具有二阶收敛速度

38、，这是它的最大优点。对于二次正定函数(对于凸二次函数，其近似二次函数就是目标函数本身，是一个精确表达式)，仅需一步迭代即可达到最优解，具有二次终结性。而对于非二次函数，牛顿法并不能保证有限次迭代求得最优解，但由于目标函数在极小点附近近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛速度一般是快的。此算法没有使用，而是使用，主要是从计算量来考虑的。同时它只需解方程组，而解方程组有标准的程序可以调用，这样可以求出方向。牛顿法具有以下不足： 牛顿法是局部收敛的，即初始点选择不当，可能会导致不收敛； 牛顿法不是下降算法，当二阶Hesse阵非正定时，不能保证牛顿方向是下降方向；（或者说，在实际求解中，

39、当初始点远离最优解时，Hesse矩阵不一定正定。牛顿方向不一定是下降方向，其收敛性不能保证。） 二阶Hesse阵必须可逆，否则算法将无法进行下去； 对函数分析性质要求苛刻(需计算一、二阶导数)，计算量大，仅适合小规模优化问题。举例：用牛顿法求的最优解：，取，。解：由题意知，从而 ，不满足精度要求，故进行第一次迭代运算：则 已经满足计算精度，所以求得最优解由于牛顿法有良好的收敛速度，人们对它的缺点进行了多方面改进或修正，如割线法等。割线法：导数的近似计算，如右图：不需计算导数，但收敛速度较牛顿法慢。5.4 二次插值法(或称抛物线法)黄金分割法在对最优解的整个搜索过程中只对函数值进行了比较，在删除

40、“坏”区间的时候，已经计算出的函数值并没有得到充分的利用。下面介绍用低次多项式来逼近目标函数，然后用近似多项式的极小点作为新区间的分割点的方法。近似多项式取二次多项式，则为二次插值法；取三次多项式，则为三次插值法。1、基本思想设函数在内呈现“大小大”单峰函数变化，在上以低次(二次或三次)插值多项式来逼近目标函数，求得多项式的极值点，逐步缩短搜索区间。反复计算，直到给定精度。 如下图，在内设定三点、和且，分别对应有，且，。构造，则由插值条件确定待定的，即解之得，求的极值点，令则得到 或 其中 ，。求出的极值点后，代入后比较函数值，取函数值最小的点及左右相邻两点作为下一步的三点。(1)， ，(2)

41、 ,，(3) ,，(4) ,，小结：比较两点的大小，缩短搜索区间。 ，时，； ，时，； ，时，； ，时，。2、注意事项l 三个试探点，且，呈现“大小大”变化；l 迭代终止条件。记与是前一次迭代的插值函数极小点与极小值；记与是本次迭代的插值函数极小点与极小值是给定的精度。若 或 例：利用二次插值法对作一搜索，初始搜索点，。解：(1)取，则，(2) ，此时。(3)比较和的大小由于，则新三点为：，此时，(4)返回第二步，计算，此时而，故可见，三个点(1)， (2)和(3)逐渐逼近极小点。一般地，函数在其极小点附近，可用一元二次函数很好地逼近。故二次插值法有较高的收敛速度。5.5 格点法(全面搜索法)

42、设一维函数为，搜索区间为，一维收敛精度为。在区间 的内部取个等分点：。区间被分为等分，各分点坐标为：对应各点的函数值为。比较其大小，取最小者，则在区间内必包含极小点，取为缩短后新区间，若新区间满足收敛条件：，则最优解为。若不能满足精度要求，把当前区间作为初始搜索区间，重复上述步骤直至满足精度为止。格点法的区间缩短示意图如下：举例：用格点法求一维目标函数的最优解。给定搜索区间为，迭代精度，内分点数。解：计算区间端点的函数值由得到四个内分点的位置，并计算其函数值，计算结果见下页表。其中最小的函数值为：，其对应的点。新区间的端点为： 新区间的长度为：，不满足精度要求。再做第二次区间缩短后，得到区间端

43、点为： 新区间的长度为：，满足迭代精度。其最优解为：，6. 不精确的一维搜索前面介绍的几种一维搜索方法，都是为了获得一元函数的最优解，所以习惯上称为精确一维搜索。在解非线性规划问题中，一维搜索一般很难得到真正的精确值。因此，不精确的一维搜索开始为人们所重视。即在点确定了下降方向后，只计算少量的几个函数就可得到一个满足的近似点。对于不精确的一维搜索，要求产生的点列具有某种收敛性。所以除了对下降方向有要求之外，对步长也有要求，即要求目标函数要“充分的下降”。下面令，我们讨论满足的条件。对于一元函数，精确一维搜索的条件为。不精确一维搜索的条件，或。但在实际计算中上式不好控制，一般的方法是的选取：不宜

44、太大，否则下降不够充分；不宜太小，否则“太精确”。通常选择适合的范围：比1稍小一些。以函数为例，作一解释。此时，取，则控制条件为，即 或 6.1 Wolfe算法（一）Wolfe原则设可微，取，选取，使 (6.1) (6.2)或用下面更强的条件代替上式(6.2)： (6.3)关于满足Wolfe原则的步长的存在性：定理6.1 设有下界且。令，则存在区间，使得任意的均满足式(6.1)和(6.2)(也满足(6.3)。问题：设已知和下降方向，求问题的近似值，使满足(6.1)和(6.2)。算法6.1 不精确一维搜索Wolfe算法Step 1 给定，令Step 2 ，计算；若满足(6.1)和(6.2)式，则

45、令； 若不满足(6.1)式，则令，转step3； 若不满足(6.2)式，则令，转step 4；step 3 令，转step 2；step 4 令，转step 2。举例：用不精确一维搜索求Rosenbrock函数在点处沿方向的近似步长。解：step 1 给定，令；step 2 ，由于 ，所以式(6.1)成立，转step 3。step 3 令，转step 2，重新计算。迭代四次得到满足Wolfe条件的步长7 共轭方向法与共轭梯度法7.1共轭方向法 构成各种不同最优化方法，往往取决于如何从基本迭代公式中确定搜索方向； 在最速下降法中，由于取从而导致搜索路线出现锯齿状，收敛速度降低； 而在Newton

46、法中，由于选取 收敛速度虽很快，但计算量很大，特别是还要求Hesse矩阵正定，从而导致该算法对初始点选择要求过严。(一) 共轭方向概念及其些性质定义7.1 设是对称矩阵，对于非零向量， 若有，则称和关于共轭或称和为正交的。对于非零向量组，若有 则称是共轭方向组或正交方向组，也称它们是一组的共轭方向。若为(阶单位矩阵)，则或。由此可知，共轭概念是正交概念的推广，共轭方向是正交方向的推广。定理7.1 设是正定矩阵，是非零向量。若是一组共轭方向，则它们是线性无关的。证明 设有一组实数使得依次以左乘上式得到由于是一组的共轭方向，故有又由于是正定矩阵，故对于，有由上两式可以得到 则得以证明是线性无关的，

47、或必正交的。证毕推论：在维空间中，互相共轭的非零向量的个数不超过个。定理7.2 设是对称正定矩阵，是一组的共轭方向。对于问题 若从任意点出发依次沿进行一维搜索，则至多经过次直线搜索，可得上述问题的最优解。证明 设从点出发依次按方向进行一维搜索产生的迭代点是，。其中最优步长是通过下式来确定的。 由于，则即 也就是其中。对上式右乘，可得又因为是共轭方向，故得或 由于进行直线搜索时，为确定最优步长，有故对于，即有 特别地，当时，有 由于是一组的共轭方向，由定理7.1知它们是线性无关的，因而向量可表示为这些向量的线性组合其中是实数。因此， 即有，于是得到即是的驻点。又因为是对称正定，故是凸函数，因而是

48、问题的最优解以上说明，至多经过n 次迭代必可求得问题的最优解.通常，我们把从任意点出发，依次沿某组共轭方向进行一维搜索的求解最优化问题的方法，叫做共轭方向法。(二) 共扼方向法的思路任选初始点，从出发沿某个下降方向作一维搜索得到(如图所示)。由于 而且向量所在的直线必与某条等值线(椭圆)相切于点。下一次迭代，如果按最速下降法选择负梯度方向为搜索方向，那末将要发生锯齿现象。为了克服这种现象，我们设想下一次迭代的搜索方向能否选择直指极小点。如果能够选定这样的搜索方向，那么对于二元二次函数只须顺次进行两次直线搜索就可以求到极小点了。下面来讨论这样的方向应该满足什么条件，如何确定？因为直接指极小点所以

49、可写成 其中是最优步长因子，显然，当时，。由于是极小点，则 将式代入式可得等式两边同时左乘，并注意到式和，于是 这就是为使直指极小点所必须满足的条件。显然式中和是的共轭向量。由式不难给出的表达式(即与线性无关，从而存在使得) 两边同时左乘，有由此得到 将上式代入式，则得到 即就是在处沿式式的进行精确一维搜索，可直接到达问题的最优解。述评：一般地，在维空间中可以找出个互相共轭的方向，对于元正定二次函数，从任意初始点出发，顺次沿这个共轭方向最多作次直线搜索就可以求得目标函数的极小点，这就是共轭方向法的算法形成的基本思想。对于元正定二次目标函数，从任意初始点出发，如果经过有限次迭代就能够求得极小点，

50、那么这种算法称为具有二次终止性。例如Newton法对于二次函数只须经过一次迭代就可以求得极小点，因此是二次终止的；而最速下降法不具有二次终止性；共轭方向法（包括共轭梯度法，变尺度法等）是二次终止的。一般来说，具有二次终止性的算法，在用于一般函数时，收敛速度较快。(三) 共轭方向法迭代步骤已知具有正定矩阵的二次目标函数和终止条件。Step1 选定初始点和具有下降的方向，置k=0；Step2 作直线搜索；Step3 判别是否满足；若满足，则输出，停机；否则转Step4。Step4 提供共轭方向，使得，Step5 置，转Step2。举例：求二次函数的极小值点。解：由于Hesse矩阵是正定矩阵，所以是正定二次函数。又由于只有二个变量，用共轭方向法经两次迭代可到达其唯一极小值点。取初始迭代点，第一次迭代。令，在处沿作精确一维搜索，最佳步长从而得到 则得 令 在处沿进行精确一维搜索，最佳步长。从而此时，故就是