《运筹学-非线性规划》由会员分享，可在线阅读，更多相关《运筹学-非线性规划（192页珍藏版）》请在金锄头文库上搜索。
1、高级运筹学,非线性规划,教材及参考书,指定教材：沈荣芳，运筹学高级教程（第二版），高等教育出版社，2008.8 参考资料： 1.韩伯棠，管理运筹学（第三版），高等教育出版社，2013.12 2. FREDERICK S. HILLIER GERALD J. LIEBERMAN ，INTRODUCTION TO OPERATIONS RESEARCH ，Ninth Edition,2010 3.吴祈宗，运筹学与最优化方法（第二版），机械工业出版社，2012 4. David G. Luenberger，Linear and Nonlinear Programming，Springer，2008,
2、非线性规划,非线性规划在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。,非线性规划研究核心问题：最优性条件（必要条件，充分条件，Lagrange乘子理论，灵敏性分析，对偶理论）迭代算法,解: 设投资决策变量为,问题归结为总资金的限制条件下, 极大化总收
3、益和总投资之比, 数学模型为,例：投资决策问题 某企业有n个项目可供选择投资, 并且至少要对其中一个项目投资. 已知该企业拥有总资金A元, 投资于第i(i=1,2,n)个项目需要花资金ai 元, 并预计收益为bi元, 试选择最佳投资方案使得总收益和总投资之比最大.,一般地，非线性规划的数学模型为,其中 X称为可行域,可行域中的点 称为可行点，f(x)称为目标函数,当 时，非线性规划模型称为无约束问题； 当 时，非线性规划模型称为有约束问题,使f(x)在X上取得最小值的点称为最优解，对应的目标函数值称为最优值,定义：如果目标函数或约束条件中至少有一个是非线性函数，则称这种规划为非线性规划问题。,
4、为统一起见,称以下模型min f(x)s.t. gi(x) 0 i=1，2，m （1）hj(x)=0 j=1，2，l 为标准的非线性规划模型,其中f(x),gi(x),hj(x)中至少有一个是x的非线性函数. 称gi(x) 0为不等式约束, hj(x)=0为等式约束.,满足所有约束条件的x称为可行解, 所有可行解构成的集合称为可行域。,例: 考虑如下非线性规划问题：min f(x)= (x14)2+(y15)2 1/2s.t. (x - 8)2 + (y - 9)2 49x 2， x 13x + y 24,非线性规划的最优解未必在顶点处达到； 非线性规划的最优解是一组同心圆最先与可行域相交的点
5、，在可行域的边界上达到,二维非线性规划问题的图解分析,例：请考虑如下非线性规划问题：min f(x)= (x8)2+(y8)2s.t. (x - 8)2 + (y - 9)2 49x 2， x 13x + y 24,非线性规划的最优解在可行域内部达到,可以看出, x2, x3, x4是局部最优解, 且x3还是全局最优解, x1, x2 , x3, x5是严格局部最优解, x4不是严格局部最优解.,一个全局最优解一定是局部最优解，反之不真。 对求极小化非线性规划问题，如果目标函数为凸函数，可行域为凸集， 则局部最优解一定为全局最优解。,与线性规划不同, 非线性规划有局部最优解和全局最优解之分.,
6、凸集 定义非空集合D称为凸集, 如果对于任意的x1, x2D及任意实数a, 0a1, 有ax1+(1a)x2D.,凸集的几何意义：若一个集合是凸的，则该集合中任意两点的线段也必包含在此集合中。,凸集,不是凸集,凸集、凸函数和凸规划,(1) 集合D=xEn |Axb, x0是凸集。,例：,定理：设D1,D2是En中的凸集，则,凸函数与凹函数 定义: D为凸集, 若对任意x1,x2D及任意实数a, 0a1有 f(ax1+(1a)x2)a f(x1)+(1a)f(x2) 则称 f(x) 为凸函数; 若变为, 称f(x)为严格凸函数。,若上式中的(), 则称f(x)为凹函数/严格凹函数。,凸函数的特征
7、是，曲线上任意两点的连线总是位于这两点间曲线的上方。,凸函数的判定 (一阶条件)：设 f(x)在凸集D上有一阶连续导数，则 f(x)是D上凸函数的充要条件是对任意两点x, z D, x z, 必有,如果上式严格成立，则是严格凸函数的充要条件。,几何意义：凸函数 f(x) 在曲线上任何一点做曲线的切线，那么f(x)都在切线上方。,(二阶条件)：设D是一个非空开凸集，设f在D上二次可微，则 f(x)是凸函数，当且仅当对所有xD, Hessian 矩阵 是半正定矩阵;,注意：Hesse矩阵在D中的每一点都是正定的，则f是严格凸的；可是，如果f是严格凸的，则Hesse矩阵在S中的每一点都是半正定的。,
8、上述定理在检验函数的凹凸性是有效的，特别是当函数为二次函数时，Hesse矩阵不依赖点x，因此检验其凸性简化为检验一个单一矩阵的特征值的非负性。,例：检验函数f(x1, x2)=2x1+6x2-2x12-3x22+4x1x2是凸的，凹的。或者两者都不是。,解：将f 改写为下面更方便的形式：,以下通过解下面的方程来计算特征值,方程的解为,凸规划定义： 已知非线性规划 若可行域D是凸集，且f(x)是定义在D上的凸函数，则该非线性规划称为凸规划。,定理：对非线性规划，如果gj(x)(i=1,2,m)是En 上的凸函数， hj(x)(j=1,2,p)为线性函数，且f(x)为可行域D上的凸函数，则该非线性
9、规划问题是凸规划。(作业1),定理1：设D为非空凸集，f(x)连续，考虑如下问题 (1) 如果 f 是凸函数，则局部最优解也是全局最优解； (2) 如果 f 是严格凸函数，则 x* 为唯一的全局最优解。,定理(最优性条件): 考虑凸规划 , (1) x*是最优解的充要条件是对xX, 有 (2) 若D是开集, x*是最优解的充要条件是,由定理结论(1)可知，如果某点x*是最优解，则对任意xD, 向量x-x*与函数f在点x*处的梯度向量 所成的角度小于90。.,分析：题意是要求验证非线性规划的最优解x*满足,解：显然，目标函数是凸函数, 且约束条件为线性函数, 故此规划问题为凸规划.,点x*=(1
10、,3)T是唯一最优解. 由于f在点(1,3)的梯度为从图中可以看出，向量 与 所成的角度小于等于90。.,而对点 (0,0)T而言，显然不是最优解。因为,对任意非零点xD, 有-3x1-10x20, 即向量(x1-0, x2-0)T 与所成角度大于90。, 不满足最优性条件,原点不会是最优解。为使目标函数值下降，最好的局部下降方向是,思考题： 如果某凸规划的可行域为D=x|x0，请讨论此凸规划问题的最优解的充要条件的形式。,无约束问题一阶二阶必要和充分条件 等式约束问题Lagrange 乘子理论 一般约束问题一阶二阶必要和充分条件,最优性条件,二阶必要条件 ：设f: RnR1在点x*Rn 处二
11、阶可微，如果x*是局部极小解, 则f(x*)=0, 且2f(x*)为半正定矩阵.,对无约束极值问题min f(x)，x Rn （1）一阶必要条件：设f: Rn R1在点x*Rn处可微，如果x* 是局部极小点, 则 f(x*)=0.,定义: 设 f: En E1在点x*处可微, 若f(x*)=0 , 称x* 函数f的驻点.,对无约束极值问题min f(x)，x Rn （1）定理(一阶必要条件)：设f: Rn R1在点x*Rn处可微，如果x* 是局部极小点, 则 f(x*)=0.,推论：设f: Rn R1在点x*Rn处可微，f是Rn上的凸函数，如果f(x*)=0 , 则x* 是无约束问题的全局最优
12、解。,定理 (二阶必要条件) ：设f: RnR1在点x*Rn 处二阶可微，如果x*是局部极小解, 则f(x*)=0, 且2f(x*)为半正定矩阵.,注意：该定理仅是必要的，而不是充分的。,定理 (二阶充分条件I)：设f: RnR1在点x*Rn 处二阶可微，如果f(x*)=0, 且2f(x*)为正定矩阵, 则x* 是无约束问题的严格局部极小解,证明: 设 为 的最小特征值. 利用二阶Taylor展式有,定理 (二阶充分条件II): 设f: EnE1在点x*En 的一个邻域 处二阶连续可微，如果 f 满足f(x*)=0, 且2f(x)在 内半正定, 则 x* 是无约束问题的局部极小解.,思考题：考
13、虑二次函数的无约束极小化问题,其中Q为n阶对称矩阵，b为n维列向量。,等式约束极值问题 min f(x)，x Rn s.t. hi(x)=0, i=1,2, m,最优性条件,(必要条件): 定理: 设等式约束问题中函数f与hi(x)(i=1,m)是连续可微函数, x*为局部最优解且为正则点(即 线性无关, 则存在实数组 ,使得,如果函数f与hi(x)(i=1,m)是二次连续可微, 则,注：等式约束问题的一阶必要条件的直观的几何意义：,注1：定理中给出的一阶必要条件仅当约束函数满足一定条件时才成立，该条件称为约束规格,注：该定理表明等式约束极值问题的极值点处的目标函数与约束函数梯度之间通过Lag
14、range乘子向量存在的关系, 是Lagrange乘子法的出发点.,引入拉格朗日函数L(x,V),其中参数向量 称为拉格朗日乘子.,n+p个方程解n+p个未知量可得L的驻点, 但是否驻点就是此非规划模型的极小解，还需要充分条件的判断； 但是对于特殊的如二次规划问题，可以通过计算L对X的Hesse矩阵判定该驻点是极大值点还是极小值点.,练习: 求等式约束极值问题 (书61-62页),(充分条件): 定理: 设等式约束问题中函数f与hi(x)(i=1,m)是二次连续可微函数,则x*是一个极小点。,1. 含不等式约束的极值问题 min f(x)，x Rn s.t. gi(x) 0, i=1,2,m
15、(3),最优性条件,设x* 是问题(3)的可行解, 约束条件gi(x) 0可分为两类, x*点的起作用约束(active constraints)：gi(x*)=0； x*点的不起作用约束(inactive constraints)：gi(x*)0.,记点x*处所有起作用约束下标的集合为I(x*), 即,如何找到在点x0处的可行方向？,如果x*为局部最优解, 则在该点处不可能存在可行下降方向.,几何意义说明如下: 设A1,A2,A3是三个二维向量.,若A1, A2, A3不在任一条直线的同一侧, 就无法找到使AiTp0 (i=1,2,3) 均满足的向量p. 这时总可以适当缩小或放大各向量Ai的长度, 使它们合成为零向量,即可找到不全为零的非负实数, 使,
