运筹学OR2-Ch11-非线性规划

1、第十一章 非线性规划Nonlinear Programming11-1 非线性规划概述11-2 一维搜索11-3 无约束优化11-4 有约束优化11-5 投资组合决策分析11-6 非线性规划的计算机求解11-1 非线性规划概述一、非线性规划的一般模型：为模型的等式与不等式约束；为模型的目标函数为规划模型的n维决策变量；*Page 2 of 88 二、极值问题定义定义2：对于非线性规划模型(1)，设X*,存在正数，使得当X且 时 总有 成立则称X*是 f 在上的一个局部极小点。若对于一切X，总有 成立就称X*是 f 在上的严格局部极小点。定义1：对于非线性规划模型(1)，称点集为模型的可行激活可

2、行域。11-1 非线性规划概述极值问题*Page 3 of 88 定义3：对于非线性规划模型(1)，设有点 X*使得 对一切X成立，就称X*是f 在上的全局极小点；若对于一切X(XX*),有 成立，则称X*是f 在上的严格全局极小。11-1 非线性规划概述极值问题*Page 4 of 88 2. 梯度概念若 f(X) 具有一阶连续偏导，则称 下式为梯度。 梯度反映了函数的一阶导数信息，它是与函数的等值面正交的，并指向函数值增大的方向（见图2-1）。11-1 非线性规划概述极值问题*Page 5 of 88 事实上，对X的任意分量xi而言，xi*也是 的局部极小点，由一元函数的极值的必要条件有由

3、i 的任意性可知，f(X)在X*处存在极值的必要条件是：11-1 非线性规划概述极值问题*Page 6 of 88 3。Hesse（海赛）矩阵对于具有二阶连续偏导数的函数f(X)，称下述实对称矩阵为海赛（Hesse)矩阵：对于n 阶矩阵A，若对于任意的n维向量Z0,若 ZTAZ0 , 则称该二次型为正定；若 ZTAZ0 , 则称该二次型为负定；若为“或”关系， 则相应地称为半正定或半负定。11-1 非线性规划概述极值问题*Page 7 of 88 二次型ZT为正定的充要条件，是矩阵A的左上角各阶主子式都大于零；而它为负定的充要条件是矩阵A的左上角各阶主子式负正相间。考虑n阶对称海赛矩阵H，如果

4、二次型为正定、负定或不定时，则称矩阵H分别为正定、负定或不定。可以证明：二元函数f(X)在驻点X* （即f(x*) =0 )）处取得严格局部极小值（或局部极小值）的充分条件是海赛矩阵H(X)正定（或半正定）。即：11-1 非线性规划概述极值问题*Page 8 of 88 11-1 非线性规划概述极值问题*Page 9 of 88 例11-1：试求下面函数的极值点和极值。解：首先求其驻点，令f (x1, x2, x3 ) = 0 求得驻点X*= (1, 1, 2)在此驻点处求其二阶偏导得到海赛矩阵：H(X*)正定，驻点就是f(X)的极小点，极小值为：11-1 非线性规划概述极值问题*Page 1

5、0 of 88 三、凸函数 1. 凸集： 几何上，集合内任意两点的连线上的点都在此集合内。 解析上，对于点集D:x1 ,x2 D，则：2. 凸函数： 几何上：（弦与曲线的位置）弦在曲线之上，称之为 解析上：任意两点x 1 ,x2 ，对于函数f(x) ，若 则称之为凸函数。11-1 非线性规划概述凸函数*Page 11 of 88 类似的可以定义凹函数：几何上：弦在曲线之下；解析上：任意两点x 1 ,x 2 ,对于函数f ( x)有：2-1 非线性规划概述凸函数*Page 12 of 88 3. 凸函数的判断根据定义判断，弦在曲线上，即弦曲根据定理判断，曲切，即二阶条件：在n维欧氏空间En中，

6、有一个凸集，f (x)在其上具有二阶的连续偏导数，则f(x)为凸函数的充要条件为其海赛矩阵为正定或半正定。11-1 非线性规划概述凸函数*Page 13 of 88 4. 凸函数的极值一般而言，局部极小不等于全局极小；对于凸函数而言，任一局部极小就等于全局极小。5. 凸规划对于一般的数学规划若f(X)凸，gi(X)凹，则称之为凸规划。可以证明，凸规划所对应的可行域为凸集，所以，对于凸规划求到一个局部极小，即为全局极小。11-1 非线性规划概述凸函数*Page 14 of 88 四、无约束下降类算法步骤采用逐步迭代算法：步骤：1）确定初始点X0 ；2）确定搜索方向Pk3）确定步长4）终止准则11

7、-1 非线性规划概述算法步骤*Page 15 of 88 作业：教材11-1 非线性规划概述*Page 16 of 88 11-2 一维搜索一维搜索即求单变量函数的极值问题，其方法很多，可概括为二类（1）试探法：分数法；0.618法（2）插值法：切线法；抛物线法*Page 17 of 88 11-2 一维搜索分数法（Fibonacci方法）原理：思想：函数f(t)在a , b 区间内有极小点t* ，逐步缩小该区间直至ar ,br ，使其宽度满足精度要求为止。取点：可以证明，按Fibonacci方法取点是最优的。（见邓乃杨所著运筹学）Fibonacci级数n0 1 2 3 4 5 6 7 F1

8、1 2 3 5 8 13 21 一、分数法（Fibonacci方法）*Page 18 of 88 算法步骤：根据精度要求确定取点数n：精度要求有：绝对精度： 相对精度：根据给定的精度和初始区间a，b ，确定取点数n：根据Fn查Fibonacci级数表，确定取点数n 。11-2 一维搜索分数法（Fibonacci方法）*Page 19 of 88 第一取点，取两点t1，t1，按 Fn-1/Fn 的比例。11-2 一维搜索分数法（Fibonacci方法）*Page 20 of 88 第二次取点，取一点t2(或t2)，从t1和t1中选择函数值较大者，作为新的边界点。如图：11-2 一维搜索分数法（F

9、ibonacci方法）*Page 21 of 88 第k次取点，取点tk （或tk）如图 所示：第n-1次取点：取点tn-1 (或tn-1)，取点比例为两者较小者即为所求极小点。11-2 一维搜索分数法（Fibonacci方法）*Page 22 of 88 例11-2：试用分数法求函数 在区间-2,2上近似的极小点和近似极小值，要求误差不超过0.2。解：不难验证，函数 是区间-2,2上仅有唯一极小点的单峰函数。极小点为 ，极小值为 ，以供下面求解验证。要求绝对误差 查Fibonacci级数表得 n=7，又知道区间端点为11-2 一维搜索分数法（Fibonacci方法）*Page 23 of 8

10、8 11-2 一维搜索分数法（Fibonacci方法）*Page 24 of 88 11-2 一维搜索分数法（Fibonacci方法）*Page 25 of 88 并取x6=0.4762为近似极小点，近似极小值为f(x6)=0.7506不难验证： 即为所求。 11-2 一维搜索分数法（Fibonacci方法）*Page 26 of 88 二、0.618法（黄金分割术）在Fibonacci搜索法中，若用n个点来缩短区间长度时，其各次缩短率分别为： 这些值是在逐步变动的。这种取点方式虽然是最优的，但每次变动的区间缩短率却给计算带来一定的麻烦。如果每次缩短区间长度都按固定比值来进行，那计算起来就方便

11、多了，0.618法就是这样一种方法。11-2 一维搜索0.618法（黄金分割术）*Page 27 of 88 事实上，fibonacci搜索法的缩短率的极限为： 取0.618的不变缩短率代替Fibonacci的变动缩短率，进行等速对称的搜索，每次的试点均取在区间的0.382和0.618处，这是个实现容易、效果良好的办法，故又称黄金分割术。 0.618法的计算步骤如下：11-2 一维搜索0.618法（黄金分割术）*Page 28 of 88 设f(x)是区间a，b上只有一个极小点的单峰函数，给定精度yesnoyesno11-2 一维搜索0.618法（黄金分割术）*Page 29 of 88 三、

12、切线法（Newton法）分数法和0.618法只是对给定区间上的部分点的函数值进行了比较，而函数的一些解析性质却丝毫未被利用。而切线法却较好的利用了函数的解析性质。假定f(x)是区间a,b上仅有一个极值点的单峰函数，且具有三阶导数。如果f(x)在x*处取得极小值，则必有f (x*)=0。因此，只要求出f (x ) 在区间a,b上的零点即求得极小值。1. 是凸函数，即 ，为求 的零点 ，在区间a，b内靠近b点处选取一点 ，并在点 处作 的切线(如图)，切线方程为： 11-2 一维搜索切线法（Newton法）*Page 30 of 88 令 得到切线与横轴的交点x1令 得与x轴的交点：如此迭代，直至

13、满足所要求的精度为止。类似的再在x1,f (x1)处作切线,其方程为： 11-2 一维搜索切线法（Newton法）*Page 31 of 88 切线法的一般计算步骤如下：yesno11-2 一维搜索切线法（Newton法）*Page 32 of 88 2. 是凹函数，即注：此种情况的任给初始点x0只能在a 端附近，而不能在b端附近,其余的均与上相同。例2-3：求 在区间1，5上的极小点，精度要求为解：由可知在区间1，5上 有唯一的极小点，不难看出这个极小点是 。在靠近右端值5附近，取一初始值 ，显然有：11-2 一维搜索切线法（Newton法）*Page 33 of 88 现有 ，故停止迭代。

14、得到近似极小点为3.0001，近似极小值为:11-2 一维搜索切线法（Newton法）*Page 34 of 88 作业：教材11-2 一维搜索切线法（Newton法）*Page 35 of 88 11-3 无约束极值问题 这里 表示 为n维欧氏空间的一个 点，或是一个n为向量，而 f(x) 则表示一个n元函数。 n元函数的无约束极值问题的一般表达式为： n元函数的极值问题的解法大体上分为两类：解析法和直接法。*Page 36 of 88 这里的方向 p(0) 和步长 0 是待定的，为了使函数 f(x) 的值在x(0)点沿p(0)方向移动步长0之后有所下降，将 f(x) 在点展成泰勒级数：一、

15、最速下降法（梯度法）此法是1847年由柯西（Cauchy）给出的，它是解析法中最古老的一种，其它方法或是它的变形或是受它的启发而得到的，因此，它是最优化方法的基础。算法思想：设目标函数 f(x) 二次连续可微且有极小点 x* ，取一初始近似点x(0) 作射线 11-3 无约束极值问题最速下降法（梯度法）*Page 37 of 88 其中：为函数 在 点的梯度。则有：为保证即选定的方向p(0) 该与该点的梯度的内积要小于0，也即：必须使得：11-3 无约束极值问题最速下降法（梯度法）*Page 38 of 88 即函数f(x)在点x(0)处沿梯度的反方向是函数值下降最快的方向，所以我们称这个方法

16、为梯度法。由此我们得到：推而广之，梯度法的一般公式为： 剩下的问题就是如何确定步长11-3 无约束极值问题最速下降法（梯度法）*Page 39 of 88 下面介绍两种确定步长 k 的方法。(1) 定步长法：每次迭代的k 都取相同的值，不过这时的搜索方向p(k)应取单位向量，即：此法的优点是简单，而缺点是步长取多大合适没有明确标准，若取的过小，则收敛太慢；步长过大又很难满足 的要求，甚至造成往复振荡而达不到极小点。11-3 无约束极值问题最速下降法（梯度法）*Page 40 of 88 (2) 最速下降法： k不取固定的值，而是与x(k)有关的一个变量。柯西给出了一个最优步长梯度法最速下降法，

17、此法要求从 x(k) 点沿方向 走下去达到极小点，由此确定步长k ：即： 也就是说，要沿着负梯度方向进行一维搜索，确定出使f(x) 达到该方向极小化的k 。此方法固然最优，但也太繁杂。为此，我们还可以求出一个近似的最优步长，将此函数展成泰勒级数：11-3 无约束极值问题最速下降法（梯度法）*Page 41 of 88 对上式求导并令其等于零： 得到近似最优步长： 11-3 无约束极值问题最速下降法（梯度法）*Page 42 of 88 最速下降法的算法流程 为：11-3 无约束极值问题最速下降法（梯度法）*Page 43 of 88 3.优缺点：优点：简单，搜索方向很容易找，且理论上证明是收敛

18、的。缺点：收敛慢。(越靠近极小点时收敛越慢，而且在靠近极小点处收敛的轨迹呈锯齿状)例11-4：教材11-3 无约束极值问题最速下降法（梯度法）*Page 44 of 88 二、共轭梯度法(或称共轭方向法) 1.正定二次函数二次函数一般形式为：其中A是一个对称方阵，如果A正定，则此二次函数为正定二次函数。（除了一次函数之外，二次函数是最简单的函数。）为什么要讨论二次正定函数呢？(1)简单；(2)等值面是椭球面；(3)一般函数在极小点附近，其形态近似于一个二次正定函数。11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 45 of 88 共轭方向(1)正交：对于n为欧氏空间E(n)中

19、的两个非零向量x和y，如果有：xTy=0则称x和y是正交的。(2)共轭：假定A是对称正定矩阵，如果向量x和Ay正交，即：xTAy=0则称x和y关于A共轭。显然当A为单位矩阵时，(2)时就变为(1)式，所以A共轭概念实际上是通常正交概念的推广。不过要注意的是A共轭与通常正交之间并无任何联系。也就是说，两个向量关于A是共轭的，这两个向量可能正交，也可能不正交。11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 46 of 88 例如：关于A共轭。11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 47 of 88 定义：对于n阶对称正定矩阵A，如果非零向量组满足条件：则

20、称该向量组为关于A共轭的向量组。定理：设A为n阶对称正定矩阵， 为A共轭的非零向量组，则该向量组一定是线性无关的。证明略注意：在n维欧氏空间中，任意n个线性无关的向量组都可以构成n维向量空间的一个基（即任何一个向量都可以由n个基向量线性表示）。所以，如上所述的n个关于A共轭的非零向量组同样构成n维向量空间的一个基。11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 48 of 88 3正定二次函数的共轭梯度法求极小值其中：A是n阶正定矩阵，x、b是n维向量，c是常数。设 为极小点， 为任意给定的初始点，如果为A共轭向量组，它们构成n维向量空间的一个基，所以，向量 可以唯一的表示为

21、这组共轭向量的线性组合：11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 49 of 88 3正定二次函数的共轭梯度法求极小值显而易见，只要能求出系数 便可以求出 极小点 。为此，将(1)式两边都左乘以 得到：另一方面，因 是二次函数的极小点，应有：代入(2)式得：11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 50 of 88 需要指出的是，这样求得的 ak 实际上是二次函数f(x)从 x(k)出发沿方向 p(k) 进行一维搜索的的最佳步长。11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 51 of 88 下面介绍两种确定共轭方向的方法：(

22、1). 单位向量法设给定初始点 ，并取第一个方向 ，求得下一点： 其中0为最佳步长。再取第二个方向：其中 ，且 ，所以，将上式两边左乘 得：11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 52 of 88 假定已经求出 x(k) 以及k个A共轭方向 ，为求 x(k+1) 需求：利用 (j=0,1,2,k-1)的共轭性，在上面等式的两边同时左乘 得：这里 ek 是单位向量 ，将j 依次代入上式便求得 p(k) ，由此便求得：11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 53 of 88 (2) 梯度法（Gram-Schnid法）满足：11-3 无约束极值问题

23、共轭梯度法(或称共轭方向法) *Page 54 of 88 11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 55 of 88 用共轭梯度法求二次函数极小值的步骤概括如下：yesno11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 56 of 88 作业：教材11-3 无约束极值问题共轭梯度法(或称共轭方向法) *Page 57 of 88 11-4 有约束极值一般非线性规划模型：解决上述问题的思路可以分为三类： *Page 58 of 88 一、最优性条件1。 起作用约束和可行下降方向：起作用约束：选定点X0满足直观上讲，起作用约束落在可行域的边界上。等式约束

24、 都是起作用约束；对于大于等于约束 在可行点X0满足 的约束为起作用约束，否则为不起作用约束。则X0点可行，如果有：则对于 叫做起作用约束。 11-4 有约束极值最优性条件*Page 59 of 88 可行方向D：对于n维空间的点 ，使得当 时，可行下降方向D：11-4 有约束极值最优性条件*Page 60 of 88 2。一阶必要条件（KuhnTucker条件，简称KT条件）正则点：X*是可行域内的一点，若在该点处起作用约束的梯度线性无关，则X*点为正则点。KT条件：若X*是极小点，且是正则点，则定存在常数向量 满足：即目标函数在X*点的梯度等于起作用约束在该点梯度的线性组合。11-4 有约

25、束极值最优性条件*Page 61 of 88 3。二阶充分条件： 若X*是满KT条件的点，且对于满足： 的一切非零向量Y有：则X*是最优点。 11-4 有约束极值最优性条件*Page 62 of 88 例2-8：试验证h(x)与g1(x)=0的交点A是否为最小点。11-4 有约束极值最优性条件*Page 63 of 88 解：A点的坐标为：(1) 是否满足KT条件 X*R，可行正则点： ，两者线性无关。由jgj(X*)=0, 得2=011-4 有约束极值最优性条件*Page 64 of 88 (2) 是否满足二阶充分条件：对于一切Y成立，所以满足二阶充分条件，A点是最小点。（注：若不给出点，则

26、要用KT条件同时找、和X*。）11-4 有约束极值最优性条件*Page 65 of 88 4。二次规划(1) 问题形式：目标函数二次，约束函数线性称此规划为二次规划。二次规划是除线性规划之外的比较简单的一类数学规划。11-4 有约束极值最优性条件*Page 66 of 88 (2) 求解极值 （利用KT条件转化为线性规划）上述二次规划中目标函数及约束的梯度如下：KT条件：注意m+n个乘子： 11-4 有约束极值最优性条件*Page 67 of 88 给（1）式中加入人工变量zj,给原约束加入松弛变量xn+i，构造出如下的线性规划模型：（注：zj0，且其前符号与cj同号，此举为了形成初始可行基）

27、11-4 有约束极值最优性条件*Page 68 of 88 解此线性规划得到最优解： 其中： 即为原二次规划问题的最优解 但应注意，所得解要满足KT条件的第二条： ；以及 。例11-9（见教材P.179例2）11-4 有约束极值最优性条件*Page 69 of 88 二、可行方向法可行方向法是一种搜索法，它是通过在可行域内直接搜索最优解的办法来求解。 现在的问题是： 如何寻求下降可行方向D(k)； 沿下降可行方向D(k)行进的步长k如何选取。 根据本节第一个问题中所述的可行下降方向，我们知道可行下降方向D应满足： 11-4 有约束极值可行方向法*Page 70 of 88 容易看出这个不等式组

28、等价于存在数0，使得：为了求出x(k)处的可行下降方向，只需求出满足上述不等式组的方向D及数。为使步长尽可能大，则应尽可能小（0）。因此构造如下线性规划模型：11-4 有约束极值可行方向法*Page 71 of 88 其中，限定方向D的各个分量|dj|1，为的是该线性规划有有限最优解；我们的目的在于确定搜索的方向D，只需知道其各个分量的相对大小即可。11-4 有约束极值可行方向法*Page 72 of 88 可行方向法的迭代过程：给定x(0)及1,20；置k=0确定下标集合：yesx(k)为最有解，停止yesnono得解：noyesk=k+1得到：k11-4 有约束极值可行方向法例11-10（

29、教材） *Page 73 of 88 三制约函数法（罚函数法）此法之思想就是将有约束的非线性规划的求解转化为一系列的无约束极值问题。因此，也称此方法为序列无约束最小化技术SUMT（Sequential Unconstrained Minimization Technique）。即：11-4 有约束极值制约函数法用这一系列无约束规划问题找有约束规划问题的最优解，关键是如何构造函数。常用的方法有两类：本部分内容暂略*Page 74 of 88 作业：教材11-4 有约束极值制约函数法*Page 75 of 88 11-5 投资组合决策分析投资组合决策问题（教材）投资组合决策是非线性规划的重要应用领

30、域之一。作为大公司的高层管理者的首要任务之一就是如何最有效地运用其巨额资金。一般而言，在风险投资中管理者会从两个基本目标考虑：投资组合的收益值最大；投资组合的风险最小。一般情况下此两目标是相互冲突的，即增大期望收益就要冒较大的风险；要减小投资的风险性就会减小期望收益。因此，管理者的目标是：在获得一定的期望收益前提下尽可能减小风险；或在一定的风险率条件下使期望收益值最大。马拉松公司的最佳投资组合决策问题分析：*Page 76 of 88 11-5投资组合决策分析马拉松公司的投资方向组合是：爱德文特、GSS、数字设备马拉松投资三个公司的股票资产历史统计信息为：*Page 77 of 88 11-5

31、投资组合决策分析*Page 78 of 88 11-5投资组合决策分析现在假定马拉松公司的投资组合目标为：期望收益率为11.0%，在此基础上使投资组合风险最小投资组合期望收益的标准差最小。因此，得到规划模型1为：投资组合目标的另一种设定：希望组合投资的风险率不超过3.1%，在此基础上使期望收益值最大。则规划模型2为：*Page 79 of 88 作业：教材11-5投资组合决策分析*Page 80 of 88 11-6 非线性规划的计算机求解正如前面所述，非线性规划的求解一般是比较困难的，通常利用函数的微分性质进行近似逼近而得到近似最优解。由于非线性函数结构上的多样性，使得大多数算法和计算机软件

32、只能求的规划模型的局部最优解。了解这一点是非常重要的。有许多规划求解软件都可以求解非线性规划，但随其起作用程度的不同而有很大的差别。通常用于教学或演示的软件只能求解很小的非线性规划模型（几个变量几个约束），而能够求解较大模型的专业的软件包通常是很昂贵的。Excel电子制表软件中的规划求解软件是一个中等性的软件组，一般而言只能求解较小型的问题。*Page 81 of 88 11-6非线性规划的计算机求解用电子制表软件解非线性规划的问题模型的基本结构：同线性规划一样，首先把非线性规划格式化为电子表格文件，它包括基础数据、决策变量、目标函数、约束的右端项（RHS)、左端项(LHS)，通过工具菜单选择规划求解项，进入规划求解参数窗口，将规划模型基础结构数据的位置填入窗口的相应栏内；点击求解按钮，进入求解参数窗口，在此窗口中要确定“假定线性模型”复选框没有选中，这一点非常重要；适当调整该窗口中的参数。根据问题的需要，为了得到比较好的阶，可以适当调整重口中的参数，这与线性