第十讲非线性规划一运筹学清华大学林谦演示文稿

第十讲非线性规划一运筹学清华大学林谦演示文稿目前一页\总数四十三页\编于十八点（优选）第十讲非线性规划一运筹学清华大学林谦目前二页\总数四十三页\编于十八点§1非线性规划问题的现实来源－问题的提出

（2）

[解]设公司应经营销售第一、二种设备数额分别为x1件和x2件，追求的目标为最大销售额，即：目标函数f(X)=30x1+450x2取极大由于营业时间有限，必须满足：0.5x1+(2+0.25x2)x2≤800当然，销售设备数不会为负数，即：x1≥0，x2≥0综合得出该问题数学模型为：

目标函数max：f(X)=30x1+450x2约束条件0.5x1+2x2+0.25x22≤800

x1≥0，x2≥0目前三页\总数四十三页\编于十八点§2非线性规划的数学模型及特点

（1）

非线性规划的数学模型通常表示成以下形式。

minf(X)

hi(X)=0i=1，2，…，m

gj(X)≥0j=1，2，…，l[例4-3]求解下述非线性规划

minf(X)=(x1－2)2+(x2－2)2

h(X)=x1+x2－6=0 目前四页\总数四十三页\编于十八点显然，与直线AB相切的点必为最优解。图4-1(a)中的D点即为最优点，此时目标函数值为：f(X*)=2，x1*=x*2=3Af(X)=4f(X)=2x1x26320236BCD图4-1(a)§2非线性规划的数学模型及特点

（2）目前五页\总数四十三页\编于十八点[例4-4]非线性规划为minf(X)=(x1－2)2+(x2－2)2

h(X)=x1+x2－6≤0显然，此时的最优解为C点(x1*=x2*=2，f(X*)=0)，该点落在可行或内部，其边界约束失去作用。从前面例中看出，非线性规划的最优解（如果存在）可在其可行域上任一点达到。因而，非线性规划数学模型可以没有约束条件，即存在无约束最优化问题。

§2非线性规划的数学模型及特点

（3）目前六页\总数四十三页\编于十八点§3解和算法的基本性质

（1）

1．极小点、凸集及其关系①极小点定义i)对于X*

Q，如果存在一个

>0，使所有与X*的距离小于

的X

Q（即X

Q，且|X－X*|<）都满足不等式f(X)≥f(X*)，则称X*为f在Q上的一个相对极小点或局部极小点。若对于所有X

Q，X≠X*且与X*距离小于

，有f(X)>f(X*)，则称X*为f在Q上的一个严格相对极小点。目前七页\总数四十三页\编于十八点§3解和算法的基本性质

（2）

ii)点X*

Q，如果对于所有X

Q成立f(X)≥f(X*)，则称X*为f在Q上的全局极小点。同样，若对于所有X

Q，X≠X*时，存在f(X)>f(X*)，则称X*为f在Q上的严格全局极小点。尽管问题的提法往往求全局极小点，然而，无论从理论上或从计算观点看，实践现实性表明我们必须以很多情形上满足一个相对极小点。当然，对于凸规划，这二者是统一的。

目前八页\总数四十三页\编于十八点§3解和算法的基本性质

（3）

②相对极小点的判定可行方向概念：沿给定方向作离开该点运动，若运动轨迹在可行域内，则称该运动方向为可行方向（通常用d表示）。若从某点开始，沿任一可行方向运动（运动距离很小）都不能使目标函数减少，则据定义，知该点即为相对极小点。i)判定极小点的必要条件（证明从略）

目前九页\总数四十三页\编于十八点§3解和算法的基本性质

（4）

命题1（一阶必要条件）：设是En子集，f(X)C1(C1表明存在一阶导数)是上函数，若X*是f(

X)在上一个相对极小点，则对于任一X*的可行方向dEn必有▽f(X*)·d≥0。（其中，▽f(X*)表示函数f(

X)的一阶梯度或导数）命题2（二阶必要条件——有约束情况）：设是En的一个子集，且f(

X)Ｃ2（Ｃ2表明存在二阶导数）是上的一个函数。若X*是f(

X)在上的一个相对极小点。则对于任一X*处的可行方向dＥn有：A)▽f(X*)·d≥0B)▽f(X*)·d=0，则必有dT·▽2f(X*)·d≥0▽2f(

X)表示f(

X)的第二阶梯度或二阶导数，又称Hess或海森阵，亦可用H或F表示。

目前十页\总数四十三页\编于十八点§3解和算法的基本性质

（5）

命题3（二阶必要条件——无约束情况）：设X*是集合的内点，且X*是函数f(X)C2在上一个相对极小点。则：A)▽f(X*)=0B)对于所有d，则dT▽2f(X*)·d≥0ii)判断极小点的充分条件命题（二阶充分条件——无约束）：设f(X)C2是定义在以X*为内点的一个区域上的函数，若A)▽f(X*)=0B)Hess阵H(X*)正定（或负定）则X*是f(X)的严格极小点（或极大点）

目前十一页\总数四十三页\编于十八点§3解和算法的基本性质

（6）

iii)极小点的充分必要条件——无约束情形。（略）③凸函数与凹函数i)定义：·凸集：若在X集合中，任意两点之联线都落在该集合内，则称该集合为X的凸集。·凸函数：定义在凸集上的函数f(X)称为凸函数，条件是对于每一对x1，x2及每一个a，0≤a≤1存在：f(ax1+(1－a)x2)≤af(x1)+1(1－a)f(x2)

上式中，若≤变为<，则称为严格凸函数。

目前十二页\总数四十三页\编于十八点§3解和算法的基本性质

（7）凸函数在2维空间的形状象一口锅的纵剖面，参见图4-2。·凹函数：定义在凸集上的函数g(X)称为凹函数，条件是函数f(X)=－g(X)是凸的。若

－g(X)是严格凸的，则g(X)是严格凹的，因此凸与凹是严格对应的，以后就只研究凸函数即可。

(a)严格凸x凸x非凸x图4-2(b)(c)目前十三页\总数四十三页\编于十八点§3解和算法的基本性质

（8）

ii）有关性质（凸函数性质）·设f1(X)，f2(X)是凸集上的凸函数，则函数f1(X)+f2(X)在上也是凸函数。·设f(X)是凸集上的凸函数，则对任意的a≥0，函数af(X)是凸的。·设f(X)是凸集上的凸函数，对每一个实数C，则集合C＝{x：x，f(X)C}是凸集。iii)凸函数的判定（略）

目前十四页\总数四十三页\编于十八点§3解和算法的基本性质

（9）

④凸规划定义：已知非线性规划：

minf(X)gj(X)≥0若f(X)为凸函数，gj(X)为凹函数，则称该规划为凸规划。凸规划的局部极值点即为全局极值点。线性规划为凸规划。2．下降算法的收敛性问题（定性分析）（略）

目前十五页\总数四十三页\编于十八点§4非线性规划求解方法分类（1）

1．一维最优化①斐波那契（Fibonacci）法②黄金分割法（0.618法）③牛顿法（切线法）④抛物线逼近法⑤成功和失败法目前十六页\总数四十三页\编于十八点§4非线性规划求解方法分类（2）

2．多维最优化①无约束情形(i)采用导数：

(a)梯度法

(b)牛顿法

(c)共轭梯度法

(d)变尺度法目前十七页\总数四十三页\编于十八点§4非线性规划求解方法分类（3）

(ii)不采用导数：

(a)直接法（模式搜索法）

(b)可变多面体法

(c)鲍威尔法

(d)随机搜索法

目前十八页\总数四十三页\编于十八点§4非线性规划求解方法分类（4）

②有约束情形(i)线性逼近法(ii)可行方向法(iii)罚函数法(iv)可变容差法非线性规划的求解方法很多，上面列出的仅是一些常用的方法。后面将简单介绍几个最基本解法的思路和步骤。目前十九页\总数四十三页\编于十八点第十讲非线性规划（二）§1一维最优化方法

§2多维无约束寻优方法（使用导数）目前二十页\总数四十三页\编于十八点§1一维最优化方法

（1）

目前常用的一些方法有：·斐波那契（

Fibonacci）法——序贯试验法·黄金分割法（0.618法）·牛顿切线法·抛物线逼近法·成功与失败试探法下面将着重介绍斐波那契与黄金分割法的主要思路及步骤。目前二十一页\总数四十三页\编于十八点§1一维最优化方法

（2）

一、斐波那契法与黄金分割法的基本思路1．非线性规性的所有求解方法在理论上都是寻找出局部极值点，即所搜寻区域是单峰函数。当然，作为一维搜索方法的斐波那契法与黄金分割法亦不例外。然而，这两种方法的寻优途径不是直接找出最优点，而是不断缩小最优点所处区域，直到符合精度为止。这两种方法的主要特点为：①适于单峰（谷）函数；②压缩峰（谷）点所处的区域。目前二十二页\总数四十三页\编于十八点§1一维最优化方法

（3）

现在分析该法是如何进行寻优的：设已知单峰函数f(t)的峰点t*（最小点）处在t=[a，b]区间（见图4-3a）在区间[a，b]中，任取两点a1、b1且a1<b1，并计算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)所示。目前二十三页\总数四十三页\编于十八点§1一维最优化方法

（4）

0a

b2

t*

a1

b1

b

tf(t)(a)0a

a1

t*

b1

b

t图4-3f(t)f(t)f(t)(b)可见，只要在[a，b]内任取两点，就必能把t*压缩在区间[a，b1]或[a1，b]内。若要继续缩小区间，只需再计算1个点，又可缩短一部分区间长度。

目前二十四页\总数四十三页\编于十八点§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，都不能压缩原区间）。目前二十五页\总数四十三页\编于十八点§1一维最优化方法

（6）

F2=2（a1、b1取在中间点附近，可近似缩短一半，故把新区间作为1，则原区间为2）。同理可得，F3=3，F4=5，…经分析，知序列{Fn}符合递推公式Fn=Fn－1+Fn－2(n≥2)计算点数n与原区间长度（令新区间为1时）Fn的关系可示于表4-1中。目前二十六页\总数四十三页\编于十八点§1一维最优化方法

（7）

Fn又称为斐波那契常数，其含义是经过n次计算后，区间缩短率为1/Fn，采用斐波那契常数进行一维寻优称为斐波那契法。用该法寻优收敛快。计算次数少，然而每步取点繁琐，且各步缩短率不同。为此，引出黄金分割法。

表4-1

n

012345…Fn

112358…目前二十七页\总数四十三页\编于十八点§1一维最优化方法

（8）

黄金分割法与斐波那契法思路完全相同，仅仅是在区间内的取点方式简单化，现不加推导的引出该法的区间内取点规则。设原区间为[a0，b0]，中间取两点为a1，b1（见图4-4）

00.3820.6181a0b2a1b1b0图4-4目前二十八页\总数四十三页\编于十八点§1一维最优化方法

（9）

令线段即，若经计算f(a1)与f(b1)后，知f(a1)<f(b1)，则保留[a0，b1]区间。此时即a1在新区间地位等同于目前b1在原区间地位，于是在新区间[a0，b1]中只需取点b2，使，便又可进行下一步计算。该法每迭代一次，使区间缩小到原来的0.618倍，故又称0.618法。目前二十九页\总数四十三页\编于十八点§1一维最优化方法

（10）

二、其它有关方法概述1．牛顿切线法2．抛物线拟合法3．成功与失败试探法目前三十页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（1）

无约束极值问题可简单表述为：minf(X)，XEn

（n维欧氏空间）X(k+1)=X(k)+p(k)且满足f[X(k+1)]<f[X(k)]这样逐步迭代直至满足精度条件

‖▽f[X(k+1)]‖<

1(梯度绝对值<1)或‖f[X(k+1)]－f[X(k)]‖<

2（两步计算的函数值之差的绝对值<

2）时迭代停止（其中，1，2为给定精度）。目前三十一页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（2）

求解非线性规划问题的迭代法，关键是如何求出每步的搜索方向p(k)及步长。由于确定p(k)及的途径不同，从而导致不同的寻优方法。其中可分两大类，一类在迭代中需用到函数的一阶导数（梯度）或二阶导数，称为“解析法”，另一类不用函数的导数值，称为“直接法”。通常，“直接法”速度较慢，但由于不用函数导数值，使得十分复杂的函数极值问题可得到解决。目前三十二页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（3）

一、使用导数（梯度）的无约束寻优方法１．梯度法（最速下降法）由于选择方向时只考虑到当前下降最快，未顾及到总寻优快慢，因而又称“瞎子爬山法”。令▽f[X(k)]表示X(k)点的梯度，则X(k+1)=X(k)－(k)▽f[X(k)]其中，步长(k)为寻优步长，有二种选择方法：①试探法目前三十三页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（4）

②解析法*(k)=X(k+1)=X(k)－·▽f[例4-12]采用梯度法求解函数f(X)=x21+25x22的极小点：[解]设初始点为：

X(0)=，则f[X(0)]=104。

目前三十四页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（5）

X(0)处梯度▽f[X(0)]=然后沿负梯度方向求一维极小值。X(1)=X(0)－▽f[X(0)]=f[X(1)]=(2－4)2+25(2－100)2令df/d=0，得：2(2－4)(－4)+50(2－100)(－100)=0目前三十五页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（6）

解得0=0.02003072X(1)=X(0)－0▽f[X(0)]==f[X(1)]=3.686164然后从X(1)出发，与上面同样迭代可得X(2)，直到进行约10次迭代，即可得最优解为：X*=，f*=0梯度法简单易行，虽是古老方法，至今仍被普遍应用。该法速度较慢。目前三十六页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（7）

2．二阶导数法（牛顿法）梯度法的每步寻优方向可看作为目标函数设计的一种线性逼近；而牛顿法是二阶导数法，它是目标函数的一种二次逼近。牛顿法的每步搜索方向S选择如下：令△X(k)=X(k+1)－f[X(k+1)]则f[X(k+1)]用△X(k)表示的二次逼近式为：f[X(k+1)]=f[X(k)]+▽Tf[X(k)]△X(k)+[△X(k)]T▽2f[X(k)]△X(k)为求f[X]在△X(k)方向上的极值点，可将f[X]对△X分量微分然后令为零便得：△X(k)=－{▽2f[X(k)]}－1▽f[X(k)]∴X(k+1)=X(k)－{▽2f[X(k)]}－1▽f[X(k)]=X(k)－H－1[X(k)]▽f[X(k)]目前三十七页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（8）

即，牛顿法的寻优方向及步长为在原有梯度向量上左乘二阶段度阵▽2f(X)（即海森阵H(X)）之逆阵。（上述牛顿法迭代公式对求极大值和极小值都适用）牛顿法通常比梯度法收敛快，然而需采用二阶梯度阵之逆阵，逆阵计算往往比较繁琐。[例4-13]由Rosenbrock设计的求无约束极小值的目标函数表达式如下（见图4-9）如下：f[X]=100(x2－x12)2+(1－x1)2目前三十八页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（9）

1)采用梯度法设X(k)=[－0.5，0.5]T，f[X(k)]=8.5f[X]规格化梯度在X(k)=[－0.5，0.5]T处为=[0.685，0.729]T目前三十九页\总数四十三页\编于十八点§2多维无约束寻优方法（使用导数）（10）

而此处规格化负梯度

=[－0.685，－0.729]T沿这方向寻找X(k+1)，采用