第十讲--非线性规划(一)(运筹学基础-清华大学-王永县)解析PPT课件.ppt

Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 1 13/6/20243/6/2024第二十一讲第十讲第十讲 非线性规划（一）非线性规划（一）1非线性规划问题的现实来源问题的提出2非线性规划的数学模型及特点3解和算法的基本性质4非线性规划求解方法分类Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 2 23/6/20243/6/2024第二十一讲1 非线性规划问题的现实来源问题的提出（1）在规划模型中，如果在目标函数或在约束条件中有一个或多个是自变量的非线性函数，则称这种规划为非线性规划问题。就现实问题，严格讲来，基本属于非线性规划模型。现举例说明非线性规划的现实背景。例4-1某公司经营两种设备。第一种设备每件售价为30元，第二种设备每件售价为450元。且知，售出第一、二种设备分别需时为每件约0.5小时和（2+0.25x2）小时，其中x2为第二种设备售出数量。公司的总营业时间为800小时。求：公司为获取最大营业额（销售额）的最优营业计划。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 3 33/6/20243/6/2024第二十一讲1 非线性规划问题的现实来源问题的提出（2）解设公司应经营销售第一、二种设备数额分别为x1件和x2件，追求的目标为最大销售额，即：目标函数f(X)=30 x1+450 x2取极大由于营业时间有限，必须满足：0.5x1+(2+0.25x2)x2800当然，销售设备数不会为负数，即：x10，x20综合得出该问题数学模型为：目标函数max：f(X)=30 x1+450 x2约束条件0.5x1+2x2+0.25x22800 x10，x20Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 4 43/6/20243/6/2024第二十一讲2 非线性规划的数学模型及特点（1）非线性规划的数学模型通常表示成以下形式。minf(X)hi(X)=0i=1，2，mgj(X)0j=1，2，l例4-3求解下述非线性规划minf(X)=(x12)2+(x22)2 h(X)=x1+x26=0Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 5 53/6/20243/6/2024第二十一讲显然，与直线AB相切的点必为最优解。图4-1(a)中的D点即为最优点，此时目标函数值为：f(X*)=2，x1*=x*2=3A f(X)=4f(X)=2x1x263202 36BCD图4-1(a)2 非线性规划的数学模型及特点（2）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 6 63/6/20243/6/2024第二十一讲例4-4非线性规划为minf(X)=(x12)2+(x22)2h(X)=x1+x260显然，此时的最优解为C点(x1*=x2*=2，f(X*)=0)，该点落在可行或内部，其边界约束失去作用。从前面例中看出，非线性规划的最优解（如果存在）可在其可行域上任一点达到。因而，非线性规划数学模型可以没有约束条件，即存在无约束最优化问题。2 非线性规划的数学模型及特点（3）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 7 73/6/20243/6/2024第二十一讲3 解和算法的基本性质（1）1极小点、凸集及其关系极小点定义i)对于X*Q，如果存在一个 0，使所有与X*的距离小于 的XQ（即XQ，且|XX*|f(X*)，则称X*为f在Q上的一个严格相对极小点。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 8 83/6/20243/6/2024第二十一讲3 解和算法的基本性质（2）ii)点X*Q，如果对于所有XQ成立f(X)f(X*)，则称X*为f在Q上的全局极小点。同样，若对于所有XQ，XX*时，存在f(X)f(X*)，则称X*为f在Q上的严格全局极小点。尽管问题的提法往往求全局极小点，然而，无论从理论上或从计算观点看，实践现实性表明我们必须以很多情形上满足一个相对极小点。当然，对于凸规划，这二者是统一的。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 9 93/6/20243/6/2024第二十一讲3 解和算法的基本性质（3）相对极小点的判定可行方向概念：沿给定方向作离开该点运动，若运动轨迹在可行域内，则称该运动方向为可行方向（通常用d表示）。若从某点开始，沿任一可行方向运动（运动距离很小）都不能使目标函数减少，则据定义，知该点即为相对极小点。i)判定极小点的必要条件（证明从略）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 10103/6/20243/6/2024第二十一讲3 解和算法的基本性质（4）命题1（一阶必要条件）：设是En子集，f(X)C1(C1表明存在一阶导数)是上函数，若X*是f(X)在上一个相对极小点，则对于任一X*的可行方向dEn必有f(X*)d0。（其中，f(X*)表示函数f(X)的一阶梯度或导数）命题2（二阶必要条件有约束情况）：设是En的一个子集，且f(X)2（2表明存在二阶导数）是上的一个函数。若X*是f(X)在上的一个相对极小点。则对于任一X*处的可行方向dn有：A)f(X*)d0B)f(X*)d=0，则必有dT2 f(X*)d02 f(X)表示f(X)的第二阶梯度或二阶导数，又称Hess或海森阵，亦可用H或F表示。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 11113/6/20243/6/2024第二十一讲3 解和算法的基本性质（5）命题3（二阶必要条件无约束情况）：设X*是集合的内点，且X*是函数f(X)C2在上一个相对极小点。则：A)f(X*)=0B)对于所有d，则dT2 f(X*)d0ii)判断极小点的充分条件命题（二阶充分条件无约束）：设f(X)C2是定义在以X*为内点的一个区域上的函数，若A)f(X*)=0B)Hess阵H(X*)正定（或负定）则X*是f(X)的严格极小点（或极大点）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 12123/6/20243/6/2024第二十一讲3 解和算法的基本性质（6）iii)极小点的充分必要条件无约束情形。（略）凸函数与凹函数i)定义：凸集：若在X集合中，任意两点之联线都落在该集合内，则称该集合为X的凸集。凸函数：定义在凸集上的函数f(X)称为凸函数，条件是对于每一对x1，x2及每一个a，0a1存在：f(ax1+(1a)x2)a f(x1)+1(1a)f(x2)上式中，若变为，则称为严格凸函数。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 13133/6/20243/6/2024第二十一讲3 解和算法的基本性质（7）凸函数在2维空间的形状象一口锅的纵剖面，参见图4-2。凹函数：定义在凸集上的函数g(X)称为凹函数，条件是函数f(X)=g(X)是凸的。若g(X)是严格凸的，则g(X)是严格凹的，因此凸与凹是严格对应的，以后就只研究凸函数即可。(a)严格凸x凸x非凸x图4-2(b)(c)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 14143/6/20243/6/2024第二十一讲3 解和算法的基本性质（8）ii）有关性质（凸函数性质）设f1(X)，f2(X)是凸集上的凸函数，则函数f1(X)+f2(X)在上也是凸函数。设f(X)是凸集上的凸函数，则对任意的a0，函数af(X)是凸的。设f(X)是凸集上的凸函数，对每一个实数C，则集合Cx：x，f(X)C是凸集。iii)凸函数的判定（略）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 15153/6/20243/6/2024第二十一讲3 解和算法的基本性质（9）凸规划定义：已知非线性规划：minf(X)gj(X)0若f(X)为凸函数，gj(X)为凹函数，则称该规划为凸规划。凸规划的局部极值点即为全局极值点。线性规划为凸规划。2下降算法的收敛性问题（定性分析）（略）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 16163/6/20243/6/2024第二十一讲4 非线性规划求解方法分类（1）1一维最优化斐波那契（Fibonacci）法黄金分割法（0.618法）牛顿法（切线法）抛物线逼近法成功和失败法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 17173/6/20243/6/2024第二十一讲4 非线性规划求解方法分类（2）2多维最优化无约束情形(i)采用导数：(a)梯度法(b)牛顿法(c)共轭梯度法(d)变尺度法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 18183/6/20243/6/2024第二十一讲4 非线性规划求解方法分类（3）(ii)不采用导数：(a)直接法（模式搜索法）(b)可变多面体法(c)鲍威尔法(d)随机搜索法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 19193/6/20243/6/2024第二十一讲4 非线性规划求解方法分类（4）有约束情形(i)线性逼近法(ii)可行方向法(iii)罚函数法(iv)可变容差法非线性规划的求解方法很多，上面列出的仅是一些常用的方法。后面将简单介绍几个最基本解法的思路和步骤。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 20203/6/20243/6/2024第二十一讲第十讲第十讲 非线性规划（二）非线性规划（二）1一维最优化方法2多维无约束寻优方法（使用导数）Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 21213/6/20243/6/2024第二十一讲1 一维最优化方法（1）目前常用的一些方法有：斐波那契（Fibonacci）法序贯试验法黄金分割法（0.618法）牛顿切线法抛物线逼近法成功与失败试探法下面将着重介绍斐波那契与黄金分割法的主要思路及步骤。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 22223/6/20243/6/2024第二十一讲1 一维最优化方法（2）一、斐波那契法与黄金分割法的基本思路1非线性规性的所有求解方法在理论上都是寻找出局部极值点，即所搜寻区域是单峰函数。当然，作为一维搜索方法的斐波那契法与黄金分割法亦不例外。然而，这两种方法的寻优途径不是直接找出最优点，而是不断缩小最优点所处区域，直到符合精度为止。这两种方法的主要特点为：适于单峰（谷）函数；压缩峰（谷）点所处的区域。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 23233/6/20243/6/2024第二十一讲1 一维最优化方法（3）现在分析该法是如何进行寻优的：设已知单峰函数f(t)的峰点t*（最小点）处在t=a，b区间（见图4-3a）在区间a，b中，任取两点a1、b1且a1b1，并计算f(a1)和f(b1)，则可出现下列结果：1）f(a1)f(b1)，则t*必在区间a，b1，如图4-3中(a)所示。2）f(a1)f(b1)，则t*必在a1，b中。如图4-3(b)所示。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 24243/6/20243/6/2024第二十一讲1 一维最优化方法（4）0ab2t*a1b1bt f(t)(a)0a a1t*b1bt图4-3 f(t)f(t)f(t)(b)可见，只要在a，b内任取两点，就必能把t*压缩在区间a，b1或a1，b内。若要继续缩小区间，只需再计算1个点，又可缩短一部分区间长度。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 25253/6/20243/6/2024第二十一讲1 一维最优化方法（5）例如，如果已知t*在a，b1内，由于a1已在a，b1中，故只需取一点计算。假定取为b2，则计算f(b2),并与已计算过的f(a1)比较，又可确定出t*在a，a1或者在b2，b1中，具体见图4-3中的(a)。这样反复进行，直到把区间缩小到一定精度为止。从上述分析知，包含t*的区间缩小率与计算函数值次数及取点技巧有关。现问，采用最佳取点法，计算函数值n次，能把多大区间缩短为1呢？令Fn表示计算n个函数值后能缩短为1的最大原区间长度，则知F0=F1=1（不计算或计算一点不能把原区间缩短，参见图4-3，开始只算一点a1或b1，都不能压缩原区间）。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 26263/6/20243/6/2024第二十一讲1 一维最优化方法（6）F2=2（a1、b1取在中间点附近，可近似缩短一半，故把新区间作为1，则原区间为2）。同理可得，F3=3，F4=5，经分析，知序列Fn符合递推公式Fn=Fn1+Fn2(n2)计算点数n与原区间长度（令新区间为1时）Fn的关系可示于表4-1中。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 27273/6/20243/6/2024第二十一讲1 一维最优化方法（7）Fn又称为斐波那契常数，其含义是经过n次计算后，区间缩短率为1/Fn，采用斐波那契常数进行一维寻优称为斐波那契法。用该法寻优收敛快。计算次数少，然而每步取点繁琐，且各步缩短率不同。为此，引出黄金分割法。表4-1 n012345Fn112358Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 28283/6/20243/6/2024第二十一讲1 一维最优化方法（8）黄金分割法与斐波那契法思路完全相同，仅仅是在区间内的取点方式简单化，现不加推导的引出该法的区间内取点规则。设原区间为a0，b0，中间取两点为a1，b1（见图4-4）00.3820.6181a0b2a1b1b0图4-4Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 29293/6/20243/6/2024第二十一讲1 一维最优化方法（9）令线段即，若经计算f(a1)与f(b1)后，知f(a1)f(b1)，则保留a0，b1区间。此时即a1在新区间地位等同于目前b1在原区间地位，于是在新区间a0，b1中只需取点b2，使，便又可进行下一步计算。该法每迭代一次，使区间缩小到原来的0.618倍，故又称0.618法。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 30303/6/20243/6/2024第二十一讲1 一维最优化方法（10）二、其它有关方法概述1牛顿切线法2抛物线拟合法3成功与失败试探法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 31313/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（1）无约束极值问题可简单表述为：minf(X)，XEn（n维欧氏空间）X(k+1)=X(k)+p(k)且满足fX(k+1)fX(k)这样逐步迭代直至满足精度条件fX(k+1)1(梯度绝对值1)或fX(k+1)fX(k)2（两步计算的函数值之差的绝对值 2）时迭代停止（其中，1，2为给定精度）。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 32323/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（2）求解非线性规划问题的迭代法，关键是如何求出每步的搜索方向p(k)及步长。由于确定p(k)及的途径不同，从而导致不同的寻优方法。其中可分两大类，一类在迭代中需用到函数的一阶导数（梯度）或二阶导数，称为“解析法”，另一类不用函数的导数值，称为“直接法”。通常，“直接法”速度较慢，但由于不用函数导数值，使得十分复杂的函数极值问题可得到解决。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 33333/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（3）一、使用导数（梯度）的无约束寻优方法梯度法（最速下降法）由于选择方向时只考虑到当前下降最快，未顾及到总寻优快慢，因而又称“瞎子爬山法”。令fX(k)表示X(k)点的梯度，则X(k+1)=X(k)(k)fX(k)其中，步长(k)为寻优步长，有二种选择方法：试探法Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 34343/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（4）解析法*(k)=X(k+1)=X(k)f例4-12采用梯度法求解函数f(X)=x21+25x22的极小点：解设初始点为：X(0)=，则fX(0)=104。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 35353/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（5）X(0)处梯度fX(0)=然后沿负梯度方向求一维极小值。X(1)=X(0)fX(0)=fX(1)=(24)2+25(2100)2令df/d=0，得：2(24)(4)+50(2100)(100)=0Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 36363/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（6）解得0=0.02003072X(1)=X(0)0fX(0)=fX(1)=3.686164然后从X(1)出发，与上面同样迭代可得X(2)，直到进行约10次迭代，即可得最优解为：X*=，f*=0梯度法简单易行，虽是古老方法，至今仍被普遍应用。该法速度较慢。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 37373/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（7）2二阶导数法（牛顿法）梯度法的每步寻优方向可看作为目标函数设计的一种线性逼近；而牛顿法是二阶导数法，它是目标函数的一种二次逼近。牛顿法的每步搜索方向S选择如下：令X(k)=X(k+1)fX(k+1)则fX(k+1)用X(k)表示的二次逼近式为：fX(k+1)=fX(k)+T fX(k)X(k)+X(k)T2 fX(k)X(k)为求fX在X(k)方向上的极值点，可将fX对X分量微分然后令为零便得：X(k)=2 fX(k)1fX(k)X(k+1)=X(k)2 fX(k)1fX(k)=X(k)H1X(k)fX(k)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 38383/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（8）即，牛顿法的寻优方向及步长为在原有梯度向量上左乘二阶段度阵2f(X)（即海森阵H(X)）之逆阵。（上述牛顿法迭代公式对求极大值和极小值都适用）牛顿法通常比梯度法收敛快，然而需采用二阶梯度阵之逆阵，逆阵计算往往比较繁琐。例4-13由Rosenbrock设计的求无约束极小值的目标函数表达式如下（见图4-9）如下：fX=100(x2x12)2+(1x1)2Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 39393/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（9）1)采用梯度法设X(k)=0.5，0.5T，fX(k)=8.5fX规格化梯度在X(k)=0.5，0.5T处为=0.685，0.729TOperations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 40403/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（10）而此处规格化负梯度=0.685，0.729T沿这方向寻找X(k+1)，采用解析法求出值。X(k)=0.5，0.5T则X(k+1)=(k)fX(k+1)=f=100 x2(k+1)x1(k+1)22+1x1(k+1)2=1000.50.729(0.5+0.685)22+(1.5+0.685)2Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 41413/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（11）令f对求导且令为0，得到f关于的极值点，得到=0.164然后将代入上式得：X(k+1)=0.612，0.381T，fX(k+1)=2.6然后继续寻找S(k+1)，得到X(k+2)，直到满足收敛条件为止。事实证明，对这种函数，最速下降法不好用。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 42423/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（12）2）采用牛顿法仍从X(k)=0.5，0.5T开始，应用公式X(k+1)=X(k)2fX(k)1fX(k)而2fX(k)=X(k)=2fX(k)1fX(k)Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 43433/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（13）X(k+1)=，fX=2.33计算表明，牛顿法比梯度法收敛快。牛顿法在使用中，当找到方向矢量S(k)=2fX(k)1fX(k)后，可以象上面阐明的那样直接计算出下一个点，也可用求极值方法，寻找最佳步长，即令X(k+1)=X(k)+S(k)（在前面所用的，实质是令=1）。牛顿法对于二次函数可一次达到极值点。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 44443/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（14）共轭方向共轭梯度法共轭梯度法是共轭方向法中最常用的一种方法。其基本原理是，确定每步的新寻优方向是当前点的负梯度矢量与上一步寻优方向的线性组合。共轭梯度法步骤如下：（每步只需用现行梯度与前一次梯度及方向）。i)起始点X(0)处，令寻优方向S(0)fX(0)。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 45453/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（15）ii)在第k阶段，沿S(k)方向用一维搜索确定f(X)的极小点，得到X(k+1)。iii)计算fX(k+1)和fX(k+1)的值。iv)用下式确定新寻优方向S(k+1)：S(k+1)=fX(k+1)+kS(k)k=迭代n次后（k=n），再重复这个过程（令X(0)=X(n)）。v)当S(k)1或fX(k)2结束其中，1，2为误差精度。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 46463/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（16）4变尺度法（拟牛顿法或大步梯度法）归结起来，非线性规划的迭代公式为：X(k+1)=X(k)+S(k)=X(k)(k)X(k)fX(k)其中，X(k)称为方向阵，并代表HX(k)1的一个近似式。（可分别简写为和H1）从公式中看出：令I，是梯度法；H1是牛顿法而变尺度法就是用不同办法使不直接求H1而找到近似H1的式子。这就是变尺度法之关键所在。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 47473/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（17）在X(k+1)阶段，已知X(k)，fX(k)，fX(k+1)，g(k)和(k)，则存在近似关系式：(k)=其中，Y和Z是任意n矢量，不同选择，可得不同方法（选择原则是简单易算可行），主要有下面几种选择：令=1，Y=Z=X(k)(k)g(k)，称Broyden算法。Operations Research Operations Research Prof.Wang Prof.Wang School of Economics&ManagementSchool of Economics&Managementpage page 48483/6/20243/6/2024第二十一讲2 多维无约束寻优方法（使用导数）（18）令Y=X(k)，Z=(k)g(k)，=1，称Davidon-Fletcher-Power算法，简称DFP算法，这是最常用的变尺度法。令Y=Z=X(k)，=1，则为Pearson2算法。令Y=Z=(k)g(k)，=1，则为Pearson3算法。令 及Z=(k)g(k)，则为投影牛顿法。这几种方法的起步(0)一般都取为单位阵I，即第一步都为梯度法。使用导数的无约束非线性规划迭代寻优方法可简单归结于表4-2中。(见教科书）