运筹学 第3版 课件 11 非线性规划

第11章非线性规划主要内容§11-1非线性规划基础§11-2一维搜索§11-3无约束极值问题§11-4有约束极值问题§11-5投资组合决策分析§11-6非线性规划的计算机求解§11-1非线性规划基础一、非线性规划问题的一般模型二、极值问题三、凸函数四、下降类算法步骤一、非线性规划问题的一般模型其中，X=（x1,x2,……,xn）是n维欧氏空间En中的点（向量）

f(X)、gi(X),hi(X)为X的实函数，且至少有一个是非线性函数。←目标函数←不等式约束 （1）←等式约束例如二、极值问题1、定义定义1：对于非线性规划模型（1），称点集为模型的可行域。定义2：对于非线性规划模型（1），设X*∈Ω,存在正数δ，使得当X∈Ω

且时，总有f(X)≥f(X*)成立，则称X*是f在Ω上的一个局部极小点 若对于一切X∈Ω,,X≠X*，总有f(X)＞f(X*)成立，则称X*是f在Ω上的一个严格局部极小点。定义3：对于非线性规划模型（1），设有点X*∈Ω，使得f(X)≥f(X*)对于一切X∈Ω成立，就称X*是f在Ω上的全局极小点； 若对于一切X∈Ω（X≠X*），总有f(X)＞f(X*)成立，则称X*是f在Ω上的严格全局极小点。例有三个局部极小点，但只有中间一个是全局极小点。二、极值问题2、梯度概念若f(X)具有一阶连续偏导，则称下式为梯度梯度反映了函数的一阶导数信息，它是与函数的等值面正交的，并指向函数值增大的方向。x0二、极值问题3、极值存在的必要条件

f(X)在X*∈Ω处存在极值的必要条件是或二、极值问题4、海赛矩阵◆若

f(X)二阶连续可微，则称下述实对称矩阵为海赛矩阵◆对于n阶矩阵A，若对于任意的n维向量Z≠0

若ZTAZ＞0，则称该二次型为正定； 若ZTAZ

＜0，则称该二次型为负定； 若为“≥”或“≤”关系，则相应地称为半正定或半负定。二、极值问题4、海赛矩阵◆二次型ZTAZ正定的充要条件是矩阵H的顺序主子式都大于零；二次型负定的充要条件是矩阵A的顺序主子式负正相间。◆考虑n阶对称海赛矩阵H，如果二次型ZTHZ为正定、负定或不定，其对称矩阵H分别为正定、负定或不定。◆二元函数f(X)在驻点X*处取得严格局部极小值（或局部极小值）的充分条件是海赛矩阵H(X*)正定（或半正定），即ZTAZ

＞0一阶必要条件二阶充分条件一维f(X)f’(X)＝0f’’(X)＞0极小f’’(X)＜0极大多维f(X)H(X)正定或半正定时极小H(X)负定或半负定时极大二、极值问题例11-1试求下面函数的极值点和极值解：首先求其驻点，令求驻点解得X*=(1,1,-2)T在此驻点处求其二阶偏导得到海赛矩阵：所以H(X*)正定，驻点X*=(1,1,-2)T就是f(X)的极小点，极小值为：二、极值问题1.凸集几何上，集合内任意两点的连线上的点都在此集合内。解析上，对于点集D：X1,X2∈D，则：2.凸函数几何上，（弦与曲线的位置）弦在曲线之上，称之为凸函数。解析上，任意两点X1,X2对于函数f(X)，若则称之为凸函数f(x2)f(x1)f(αx1

+(1-α)x2)αf(x1)+(1-α)f(x2)x2x1αx1

+(1-α)x2f(x)x凸函数二、极值问题凹函数f(x2)f(x1)f(αx1+(1-α)x2)αf(x1)+(1-α)f(x2)x2x1αx1+(1-α)x2f(x)x三、凸函数类似的可以定义凹函数：几何上，弦在曲线之下；解析上，任意两点X1,X2对于函数f(X)有：

三、凸函数4.凸函数的判断（1）根据定义判断，弦在曲线上，即弦＞曲（2）根据定理判断，曲＞切，即（3）二阶条件：在n维欧式空间En中，有一个凸集Ω，f(X)在其上具有二阶的连续偏导数，则f(X)为凸函数的充要条件为其海赛矩阵为正定或半正定。三、凸函数若f(X)凸，gj(X)凹，则称之为凸规划。可以证明，凸规划所对应的可行域为凸集，所以，对于凸规划求到一个局部极小，即为全局极小。5.凸函数的极值（1）一般而言，局部极小不等于全局极小；（2）对于凸函数而言，局部极小就等于全局极小。6.凸规划对于一般的数学规划三、凸函数四、无约束下降类算法步骤采用逐步迭代算法：步骤：

1）确定初始点X0

2）确定搜索方向Pk 3）确定步长

4）终止准则§11-2一维搜索一维搜索即求单变量函数的极值问题，其方法很多，可概括为二类

（1）试探法： Fibonacci法；0.618法（2）插值法： 切线法；抛物线法1.原理①思想：函数f(t)在[a，b]区间内有极小点t*，逐步缩小该区间直至[ar,br]，使其宽度满足精度要求为止。②取点：可以证明，按Fibonacci法取点是最优的。③Fibonacci级数n01234567…Fn1123581321…a

t1

t*t2

btf(t)f(t1)f(t2)一、Fibonacci法（斐波那契法或分数法）2.算法步骤

①根据精度要求确定取点数n：

精度要求有：

绝对精度：│bn－an│≤ε

相对精度：（bn－an

）/（b0－a0

）≤δ

根据给定的精度ε和初始区间[a,b]，确定取点数n：一、Fibonacci法（斐波那契法或分数法）（2）算法步骤

②第一次取点，取两点t1，t1’，按Fn-1/Fn的比例a0b0FnFn-1Fn-2t1t1’Fn-1Fn-2t1点坐标为：t1’点坐标为：一、Fibonacci法（斐波那契法或分数法）（2）算法步骤

③第二次取点，取一点t2（或t2’）。从t1和t1’中选择函数值较大者作为新的边界点，另外计算一点t2（或t2’）。a0b0FnFn-1Fn-2t1t1’例如：假设f(t1)＞f(t1’)，则取a1

＝t1，b1

＝b0，t2

＝t1’，并计算点t2’坐标t2’点坐标为：Fn-3Fn-2a1b1t2t2’一、Fibonacci法（斐波那契法或分数法）（2）算法步骤③第二次取点，取一点t2（或t2’）。从t1和t1’中选择函数值较大者作为新的边界点，另外计算一点t2（或t2’）。a0b0FnFn-1Fn-2t1t1’例如：假设f(t1)＜f(t1’)，则

取b1

＝t1’，a1

＝t0，t2’＝t1，并计算点t2坐标t2点坐标为：Fn-2Fn-3t2t2’a1b1一、Fibonacci法（斐波那契法或分数法）（2）算法步骤④第k次取点，取点tk（或tk’）ak-1bk-1tktk’⑤第n-1次取点，取点tn-1（或tn-1’），取点比例为F1/F2＝1/2，两者较小者即为所求极小点一、Fibonacci法（斐波那契法或分数法）例11-2

试用分数法求函数在区间[-2,2]上近似的极小点和近似极小值，要求误差不超过0.2。解：不难验证，函数是区间[-2,2]上仅有唯一极小点的单峰函数。极小点为，极小值为，以供下面求解验证。要求绝对误差查Fibonacci级数表得n=7，又知道区间端点为a0=－2，b0=2一、Fibonacci法（斐波那契法或分数法）一、Fibonacci法（斐波那契法或分数法）一、Fibonacci法（斐波那契法或分数法）并取x6=0.4762为近似极小点，近似极小值为f(x6)=0.7506不难验证：即为所求。一、Fibonacci法（斐波那契法或分数法）在Fibonacci搜索法中，若用n个点来缩短区间长度时，其各次缩短率分别为：

二、0.618法（黄金分割法）这些值是在逐步变动的。这种取点方式虽然是最优的，但每次变动的区间缩短率却给计算带来一定的麻烦。如果每次缩短区间长度都按固定比值来进行，那计算起来就方便多了。0.618法就是这样一种方法。Fibonacci法缩短率的极限是0.618，取0.618的不变的缩短率代替Fibonacci的变动的缩短率，进行等速对称的搜索，每次的试点均取在区间的0.382和0.618处，这是比较容易实现、效果良好的办法。事实上，Fibonacci搜索法的缩短率的极限为：取0.618的不变缩短率代替Fibonacci的变动缩短率，进行等速对称的搜索，每次的试点均取在区间的0.382和0.618处，这是个实现容易、效果良好的办法，故又称黄金分割术。0.618法的计算步骤如下：二、0.618法（黄金分割法）给定[a,b]和ε及kK=1:ak=a;bk=b│bk－ak│≤ε？xk+1=bk－0.618(bk－ak)x’k+1=ak+0.618(bk－ak)k=k+1ak+1=xk；bk+1=bkak+1=ak；bk+1=xk+1求f(xk+1)和f(x’k+1)f(xk+1)＞f(x’k+1)yesno0.618法的计算步骤：设f(X)是区间[a，b]上只有一个极小点的单峰函数，给定精度ε二、0.618法（黄金分割法）三、切线法（Newton法）分数法和0.618法只是对给定区间上的部分点的函数值进行了比较，而函数的一些解析性质却丝毫未被利用。而切线法却较好的利用了函数的解析性质。假定f(x)是区间[a,b]上仅有一个极值点的单峰函数，且具有三阶导数。如果f(x)在x*处取得极小值，则必有f’(x*)=0。因此，只要求出f’(x)

在区间[a,b]上的零点即求得极小值。1.是凸函数，即，为求的零点，在区间[a，b]内靠近b点处选取一点x0，并在点[]处作的切线(如图)，切线方程为：令得到切线与横轴的交点x1令得与x轴的交点：如此迭代，直至满足所要求的精度为止。类似的再在[x1,f’(x1)]处作切线,其方程为：

三、切线法（Newton法）yesno三、切线法（Newton法）切线法的一般计算步骤如下：2.

是凹函数，即[注：此种情况的任给初始点x0只能在a端附近，而不能在b端附近，其余的均与上相同。]例11-3求在区间[1，5]上的极小点，精度要求为解：由可知在区间[1，5]上有唯一的极小点，不难看出这个极小点是。在靠近右端值5附近，取一初始值，显然有：三、切线法（Newton法）现有，故停止迭代。得到近似极小点为3.0001，近似极小值为:三、切线法（Newton法）

这里表示为n维欧氏空间的一个点，或是一个n为向量，而f(x)

则表示一个n元函数。n元函数的无约束极值问题的一般表达式为：n元函数的极值问题的解法大体上分为两类：解析法和直接法。§11-3无约束极值问题

这里的方向p(0)

和步长λ0是待定的，为了使函数f(X)的值在X(0)点沿p(0)方向移动步长λ0之后有所下降，将f(X)在点展成泰勒级数：一、最速下降法（梯度法）此法是1847年由柯西（Cauchy）给出的，它是解析法中最古老的一种，其它方法或是它的变形或是受它的启发而得到的，因此，它是最优化方法的基础。算法思想：设目标函数f(x)二次连续可微且有极小点x*

，取一初始近似点x(0)

作射线其中：为函数在点的梯度。则有：为保证即选定的方向p(0)

该与该点的梯度的内积要小于0，也即：必须使得：一、最速下降法（梯度法）即函数f(x)在点x(0)处沿梯度的反方向是函数值下降最快的方向，所以称这个方法为梯度法。由此得到：推而广之，梯度法的一般公式为：剩下的问题就是如何确定步长λk一、最速下降法（梯度法）下面介绍两种确定步长λk

的方法。(1)定步长法：每次迭代的λk

都取相同的值λ，不过这时的搜索方向p(k)应取单位向量，即： 此法的优点是简单，而缺点是步长取多大合适没有明确标准，若取的过小，则收敛太慢；步长过大又很难满足的要求，甚至造成往复振荡而达不到极小点。一、最速下降法（梯度法）(2)最速下降法：λk不取固定的值，而是与X(k)有关的一个变量。柯西给出了一个最优步长梯度法——最速下降法，此法要求从x(k)

点沿方向走下去达到极小点，由此确定步长λk

：即：

也就是说，要沿着负梯度方向进行一维搜索，确定出使f(X)达到该方向极小化的λk

。此方法固然最优，但也太繁杂。为此，我们还可以求出一个近似的最优步长，将此函数展成泰勒级数：一、最速下降法（梯度法）对上式求导并令其等于零：得到近似最优步长：一、最速下降法（梯度法）最速下降法的算法流程图一、最速下降法（梯度法）3.优缺点优点：简单，搜索方向很容易找，且理论上证明是收敛的。缺点：收敛慢。(越靠近极小点时收敛越慢，而且在靠近极小点处收敛的轨迹呈锯齿状)一、最速下降法（梯度法）1.

正定二次函数（1）二次函数一般形式为：四、共轭梯度法（2）其中A是一个对称方阵，如果A正定，则此二次函数为正定二次函数。（3）讨论二次函数的原因 除了一次函数之外，二次函数是最简单的函数；等值面是椭球面；一般函数在极小点附近，其形态近似于一个二次正定函数。2.共轭方向 设A为n×n对称正定阵，X和Y是n维欧氏空间En中的两个向量，若有XTAY=0，则称X和Y关于A共轭，当A=I，则X与Y正交。 设A为n×n对称正定阵，若向量组P1，P2

，…，Pn∈En中任意两个向量关于A共轭，即满足条件PiTAPj=0(i≠j,i,j=1,2,…,n)，则称该向量组为A共轭。2.共轭方向

(1)正交：对于n为欧氏空间E(n)中的两个非零 向量X和Y，如果有：XTY=0，则称X和Y是正交的。(2)共轭：假定A是对称正定矩阵，如果向量X和AY正交， 即：XTAY=0，则称x和y关于A共轭。

显然当A为单位矩阵时，(2)时就变为(1)式，所以A共轭概念实际上是通常正交概念的推广。不过要注意的是A共轭与通常正交之间并无任何联系。也就是说，两个向量关于A是共轭的，这两个向量可能正交，也可能不正交。四、共轭梯度法例关于A共轭。四、共轭梯度法定义：对于n阶对称正定矩阵A，如果非零向量组满足条件：则称该向量组为关于A共轭的向量组。定理：设A为n阶对称正定矩阵，为A共轭的非零向量组，则该向量组一定是线性无关的。[证明略]注意：在n维欧氏空间中，任意n个线性无关的向量组都可以构成n维向量空间的一个基（即任何一个向量都可以由n个基向量线性表示）。所以，如上所述的n个关于A共轭的非零向量组同样构成n维向量空间的一个基。四、共轭梯度法3．正定二次函数的共轭梯度法求极小值其中：A是n阶正定矩阵，x、b是n维向量，c是常数。设为极小点，为任意给定的初始点，如果为A共轭向量组，它们构成n维向量空间的一个基，所以，向量可以唯一的表示为这组共轭向量的线性组合：四、共轭梯度法3．正定二次函数的共轭梯度法求极小值显而易见，只要能求出系数便可以求出极小点X*。为此，将(1)式两边都左乘以得到：另一方面，因X*是二次函数的极小点，应有：代入(2)式得：X四、共轭梯度法需要指出的是，这样求得的ak实际上是二次函数f(X)从X(k)出发沿方向p(k)

进行一维搜索的的最佳步长。四、共轭梯度法下面介绍两种确定共轭方向的方法(1)单位向量法设给定初始点，并取第一个方向，求得下一点：

其中，λ0为最佳步长。再取第二个方向：其中，且，所以，将上式两边左乘得：四、共轭梯度法假定已经求出X(k)

以及k个A共轭方向，为求X(k+1)

需求：利用(j=0,1,2,…,k-1)的共轭性，在上面等式的两边同时左乘得：这里ek

是单位向量

，将αj

依次代入上式便求得p(k)

，由此便求得：四、共轭梯度法(2)梯度法（Gram-Schnid法）满足：四、共轭梯度法四、共轭梯度法§11-4有约束极值一般非线性规划模型：解决上述问题的思路可以分为三类：一、最优性条件1.起作用约束和可行下降方向：起作用约束：选定点X0满足直观上讲，起作用约束落在可行域的边界上。等式约束都是起作用约束；对于大于等于约束在可行点X0满足的约束为起作用约束，否则为不起作用约束。则X0点可行，如果有：则对于叫做起作用约束。起作用约束示意图可行方向D：对于n维空间的点，使得当时，可行下降方向D：可行方向示意图一、最优性条件2.一阶必要条件（Kuhn－Tucker条件，简称K－T条件）正则点：X*是可行域内的一点，若在该点处起作用约束的梯度线性无关，则X*点为正则点。K－T条件：若X*是极小点，且是正则点，则定存在常数向量满足：即目标函数在X*点的梯度等于起作用约束在该点梯度的线性组合。一、最优性条件3.二阶充分条件若X*是满K－T条件的点，且对于满足：的一切非零向量Y有：则X*是最优点。一、最优性条件例11-8试验证h(x)与g1(x)=0的交点A是否为最小点。一、最优性条件解：A点的坐标为：(1)是否满足K-T条件①X*∈R，可行②正则点：，两者线性无关。由μjgj(X*)=0,得μ2=0一、最优性条件(2)是否满足二阶充分条件：对于一切Y成立，所以满足二阶充分条件，A点是最小点。（注：若不给出点，则要用K-T条件同时找λ、μ和X*。）一、最优性条件4.二次规划(1)问题形式：目标函数二次，约束函数线性称此规划为二次规划。二次规划是除线性规划之外的比较简单的一类数学规划。一、最优性条件(2)求解极值（利用K-T条件转化为线性规划）上述二次规划中目标函数及约束的梯度如下：K-T条件：注意m+n个乘子：一、最优性条件给（1）式中加入人工变量zj,给原约束加入松弛变量xn+i，构造出如下的线性规划模型：（注：zj≥0，且其前符号与cj同号，此举为了形成初始可行基）一、最优性条件解此线性规划得到最优解：其中：即为原二次规划问题的最优解但应注意，所得解要满足K-T条件的第二条：；以及。一、最优性条件二、可行方向法可行方向法是一种搜索法，它是通过在可行域内直接搜索最优解的办法来求解。现在的问题是：⑴如何寻求下降可行方向D(k)；⑵沿下降可行方向D(k)行进的步长λk如何选取。根据本节第一个问题中所述的可行下降方向，可行下降方向D应满足：容易看出这个不等式组等价于存在数β＜0，使得：为了求出x(k)处的可行下降方向，只需求出满足上述不等式组的方向D及数β。为使步长尽可能大，β则应尽可能小（β＜0）。因此构造如下线性规划模型：其中，限定方向D的各个分量|dj|≤1，为的是该线性规划有有限最优解；确定搜索方向D时，只需知道其各个分量的相对大小即可。二、可行方向法可行方向法的迭代过程：给定x(0)及ε1,ε2＞0；置k=0确定下标集合：yesx(k)为最有解，停止yesnono得解：noyesk=k+1得到：λk二、可行方向法投资组合决策问题投资组合决策是非线性规划的重要应用领域之一。作为大公司的高层管理者的首要任务之一就是如何最有效地运用其巨额资金。一般而言，在风险投资中管理者会从两个基本目标考虑：投资组合的收益值最大；投资组合的风险最小。一般情况下此两目标是相互冲突的，即增大期望收益就要冒较大的风险；要减小投资的风险性就会减小期望收益。因此，管理者的目标是：在获得一定的期望收益前提下尽可能减小风险；或在一定的风险率条件下使期望收益值最大。马拉松公司的最佳投资组合决策问题分析：§11-5投资组合决策分析§11-5投资组合决策分析马拉松公司的投资方向组合是：爱德文特、GSS、数字设备马拉松投资三个公司的股票资产历史统计信息为§11-5投资组合决策分析现在假定马拉松公司的投资组合目标为：期望收益率为11.0%，在此基础上使投资组合风险最小——投资组合期望收益的标准差最小。因此，得到规划模型1为：投资组合目标的另一种设定：希望组合投资的风险率不超过3.1%，在此基础上使期望收益值最大。则规划模型2为：§11-5投资组合决策分析§11-6非线性规划的计算机求解正如前面所述，非线性规划的求解一般是比较困难的，通常利用函数的微分性质进行近似逼近而得到近似最优解。由于非线性函数结构上的多样性，使得大多数算法和计算机软件只能求的规划模型的局部最优解。了解这一点是非常重要的。有许多规划求解软件都可以求解非线性规划，但随其起作用程度的不同而有很大的差别。通常用于教学或演示的软件只能求解很小的非线性规划模型（几个变量几个约束），而能够求解较大模型的专业的软件包通常是很昂贵的。Excel电子制表软件中的规划求解