1、运筹学运筹学（II）教材及参考书教材及参考书指定教材：沈荣芳，运筹学高级教程，高等教育出版社，指定教材：沈荣芳，运筹学高级教程，高等教育出版社，2008.8参考资料：参考资料：1.Nonlinear Programming:Theory and Algorithms 3rd Edition，M.S.Bazaraa,H.D.Sherali,C.M.Shetty,John Wiley&Sons,2006.2.运筹学运筹学非线性系统优化，李军，徐玖平，科学出版社，非线性系统优化，李军，徐玖平，科学出版社，2003.43.随机规划和模糊规划，刘宝碇，赵瑞清，清华大学出版社，随机规划和模糊规划，刘宝碇，
2、赵瑞清，清华大学出版社，1998.64.Stochastic Programming,Kall P,Wallace S.W.,John Wiley and Sons,19945.多目标规划有效性理论，胡毓达，上海科学技术出版社，多目标规划有效性理论，胡毓达，上海科学技术出版社，19946.实用多目标最优化，胡毓达，上海科学出版社，实用多目标最优化，胡毓达，上海科学出版社，19907.多目标决策的理论与方法，徐玖平，李军，清华大学出版社，多目标决策的理论与方法，徐玖平，李军，清华大学出版社，2005.3 非线性规划非线性规划 非线性规划非线性规划 在科学管理和其他领域中，大量应用问题可以归结为线
3、性规划问在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用题，但是，也有另外一些问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。线性函数，则这样的规划问题就属于非线性规划。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法，非线性规划目前还也不象线性规划那样有单纯形法这一
4、通用的方法，非线性规划目前还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。没有适合于各种问题的一般算法，这是需要深入研究的一个领域。非线性规划研究核心问题：非线性规划研究核心问题：u 最优性条件（必要条件，充分条件，最优性条件（必要条件，充分条件，LagrangeLagrange乘子理论，灵敏性乘子理论，灵敏性分析，对偶理论）分析，对偶理论）u 迭代算法迭代算法 解解:设投资决策变量为设投资决策变量为问题归结为总资金的限制条件下问题归结为总资金的限制条件下,极大化总收益和总投资之比极大化总收益和总投资之比,数学模型为数学模型为111max0.(1)0,(1,2,)niiiniiin
5、iiiiib xQa xa xAstxxin 1,(i=1,2,n)0,iixii 决定投资第决定投资第 个项目个项目决定不投资第决定不投资第 个项目个项目例：投资决策问题例：投资决策问题某企业有某企业有n个项目可供选择投资个项目可供选择投资,并且至少要对其中一个项目投资并且至少要对其中一个项目投资.已知该企业拥有总资金已知该企业拥有总资金A元元,投资于第投资于第i(i=1,2,n)个项目需要花个项目需要花资金资金ai 元元,并预计收益为并预计收益为bi元元,试选择最佳投资方案使得总收益和试选择最佳投资方案使得总收益和总投资之比最大总投资之比最大.一般地，非线性规划的数学模型为一般地，非线性规
6、划的数学模型为 min()x Xf xmax()min()x Xx Xf xf x由于可转化为等价模型,故仅考虑极小化问题.其中其中 X称为可行域称为可行域,nXR可行域中的点可行域中的点 称为可行点，称为可行点，f(x)称为目标函数称为目标函数12(,)Tnxx xx当当 时，非线性规划模型称为无约束问题；时，非线性规划模型称为无约束问题；当当 时，非线性规划模型称为有约束问题时，非线性规划模型称为有约束问题nXRnXR使使f(x)在在X上取得最小值的点称为最优解，对应的目标函数值称为上取得最小值的点称为最优解，对应的目标函数值称为最优值最优值定义定义：如果目标函数或约束条件中至少有一个是非
7、线性函数，则：如果目标函数或约束条件中至少有一个是非线性函数，则称这种规划为非线性规划问题。称这种规划为非线性规划问题。为统一起见为统一起见,称以下模型称以下模型 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为等式约束为等式约束.|()0,1,2,;()0,1,2,ijDX g Xim h Xjp 满足所有约束条件的满足所有约束条件的x称为可行解称为可行
8、解,所有可行解构成的集合所有可行解构成的集合称为可行域。称为可行域。例例:考虑如下非线性规划问题：考虑如下非线性规划问题：min f(x)=(x14)2+(y15)2 1/2 s.t.(x-8)2+(y-9)2 49 x 2，x 13 x+y 24 非线性规划的最优解未必在顶点处达到；非线性规划的最优解未必在顶点处达到；非线性规划的最优解是一组同心圆最先与非线性规划的最优解是一组同心圆最先与可行域相交的点，在可行域的边界上达到可行域相交的点，在可行域的边界上达到二维非线性规划问题二维非线性规划问题的图解分析的图解分析 例：请考虑如下非线性规划问题：例：请考虑如下非线性规划问题：min f(x)
9、=(x8)2+(y8)2 s.t.(x-8)2+(y-9)2 49 x 2，x 13 x+y 24 非线性规划的最优解在可行域内部达到非线性规划的最优解在可行域内部达到 可以看出可以看出,x2,x3,x4是局部最优解是局部最优解,且且x3还是全局最优解还是全局最优解,x1,x2,x3,x5是严格局部最优解是严格局部最优解,x4不是严格局部最优解不是严格局部最优解.xf0 x1x2x3x4x5f(x)D一个全局最优解一定是局部最优解，反之不真。一个全局最优解一定是局部最优解，反之不真。对求极小化非线性规划问题，如果目标函数为凸函数，可行域为凸集，对求极小化非线性规划问题，如果目标函数为凸函数，可
10、行域为凸集，则局部最优解一定为全局最优解。则局部最优解一定为全局最优解。与线性规划不同与线性规划不同,非线性规划有局部最优解和全局最优解之分非线性规划有局部最优解和全局最优解之分.凸集凸集i)定义定义非空集合非空集合D称为凸集称为凸集,如果对于任意的如果对于任意的x1,x2 D及任意实数及任意实数a,0a1,有有ax1+(1a)x2D.凸集的几何意义：若一个集合是凸的，则该集合中任意两凸集的几何意义：若一个集合是凸的，则该集合中任意两点的线段也必包含在此集合中。点的线段也必包含在此集合中。x1x2Dx1x2D凸集凸集不是凸集不是凸集凸集、凸函数和凸规划凸集、凸函数和凸规划(1)集合集合D=xE
11、n|Axb,x0是凸集。是凸集。例：例：121112,01,1,2,1,.,nmiimmniiiiimx xxRimDxExxDxx xx2 设对任意的且则集合是凸集中的点 叫做点的凸组合.(D称为多胞形)定理：设定理：设D1,D2是是En中的凸集，则中的凸集，则 11121212121,.2,.3.Dx xDDDxy xDyDDDDD是凸集 其中 是实数是凸集也是凸集是凸集 凸函数与凹函数凸函数与凹函数定义定义:D为为凸集凸集,若对任意若对任意x1,x2 D及任意实数及任意实数a,0a1有有f(ax1+(1a)x2)a f(x1)+1(1a)f(x2)则称则称 f(x)为为;若若变为变为,称
12、称f(x)为为。若上式中的若上式中的(),则称则称f(x)为为凹函数凹函数/。凸函数的特征是，曲线上任意两点的连线总是位于这两点间曲线的上方。凸函数的特征是，曲线上任意两点的连线总是位于这两点间曲线的上方。凸函数的判定凸函数的判定(一阶条件一阶条件)：设：设 f(x)在凸集在凸集D上有一阶连续导数，则上有一阶连续导数，则 f(x)是是D上上凸函数的充要条件是对任意两点凸函数的充要条件是对任意两点x,z D,x z,必有必有()()()()Tf zf xf xzx如果上式严格成立，则是严格凸函数的充要条件。如果上式严格成立，则是严格凸函数的充要条件。几何意义：凸函数几何意义：凸函数 f(x)在曲
13、在曲线上任何一点做曲线的切线，线上任何一点做曲线的切线，那么那么f(x)都在切线上方。都在切线上方。(二阶条件二阶条件)：设：设D是一个非空开凸集，设是一个非空开凸集，设f在在D上二次可微，则上二次可微，则 f(x)是凸函数，当且仅当对所有是凸函数，当且仅当对所有xD,Hessian 矩阵矩阵 是是半正定矩阵半正定矩阵;2()f x注意：注意：Hesse矩阵在矩阵在D中的每一点都是正定的，则中的每一点都是正定的，则f是严格是严格凸的；可是，如果凸的；可是，如果f是严格凸的，则是严格凸的，则Hesse矩阵在矩阵在S中的每中的每一点都是半正定的。一点都是半正定的。上述定理在检验函数的凹凸性是有效的
14、，特别是当函数为上述定理在检验函数的凹凸性是有效的，特别是当函数为二次函数时，二次函数时，Hesse矩阵不依赖点矩阵不依赖点x，因此检验其凸性简，因此检验其凸性简化为检验一个单一矩阵的特征值的非负性。化为检验一个单一矩阵的特征值的非负性。例：检验函数例：检验函数f(x1,x2)=2x1+6x2-2x12-3x22+4x1x2是凸的，凹是凸的，凹的。或者两者都不是。的。或者两者都不是。解：将解：将f 改写为下面更方便的形式：改写为下面更方便的形式：11121222441(,)2,6,462xxf x xx xxx以下通过解下面的方程来计算特征值以下通过解下面的方程来计算特征值2440det()d
15、et(4)(6)1646108HI 方程的解为方程的解为12517517.Hf 和，故为负定矩阵，为凹函数 凸规划定义：凸规划定义：已知非线性规划已知非线性规划 若可行域若可行域D是凸集，且是凸集，且f(x)是定义在是定义在D上的凸函数，则该非上的凸函数，则该非线性规划称为凸规划。线性规划称为凸规划。min().()0,1,2,()0,1,2,ijf xst g ximh xjp定理：对非线性规划，如果定理：对非线性规划，如果gj(x)(i=1,2,m)是是En 上的凸函数，上的凸函数，hj(x)(j=1,2,p)为线性函数，且为线性函数，且f(x)为可行域为可行域D上的凸函数，则上的凸函数，
16、则该非线性规划问题是凸规划。该非线性规划问题是凸规划。(作业作业1)：设：设D为非空凸集，为非空凸集，f(x)连续，考虑如下问题连续，考虑如下问题(1)如果如果 f 是凸函数，则局部最优解也是全局最优解；是凸函数，则局部最优解也是全局最优解；(2)如果如果 f 是严格凸函数，则是严格凸函数，则 x*为为的全局最优解。的全局最优解。min()x Df x:考虑凸规划考虑凸规划 ,(1)x*是最优解的充要条件是对是最优解的充要条件是对xX,有有(2)若若D是开集是开集,x*是最优解的充要条件是是最优解的充要条件是min()x Xf x*()()0Tf xxx*()0.f x由定理结论由定理结论(1
17、)可知，如果某点可知，如果某点x*是最优解，则对任意是最优解，则对任意xD,向向量量x-x*与函数与函数f在点在点x*处的梯度向量处的梯度向量 所成的角度小于所成的角度小于90。.*()f x 例：考虑如下非线性规划问题：例：考虑如下非线性规划问题：22121212123min()()(5)22.23110,0f xxxxxstxxxx试验证最优性条件成立。试验证最优性条件成立。分析：题意是要求验证非线性规划的最优解分析：题意是要求验证非线性规划的最优解x*满足满足*()()0,.Tf xxxxD对任意的(1,3)(0,2)(0,0)11(,0)22x1x3(,5)2(1,3)(1,4)Tf
18、解：显然，目标函数解：显然，目标函数是凸函数是凸函数,且约束条件为线性且约束条件为线性函数函数,故此规划问题为凸规划故此规划问题为凸规划.22123()()(5)2f xxx点点x*=(1,3)T是唯一最优解是唯一最优解.由于由于f在点在点(1,3)的梯度为的梯度为从图中可以看出，向量从图中可以看出，向量与与 所成的角度小所成的角度小于等于于等于90。.(1,3)(1,4),Tf (1,4)T 12(1,3)Txx 而对点而对点(0,0)T而言，显然不而言，显然不是最优解。因为是最优解。因为(0,0)(3,10),Tf 对任意非零点对任意非零点xD,有有-3x1-10 x20,即向量即向量(x
19、1-0,x2-0)T 与与 所成角度大于所成角度大于90。,不不满足最优性条件满足最优性条件,原点不会是原点不会是最优解。为使目标函数值下最优解。为使目标函数值下降，最好的局部下降方向是降，最好的局部下降方向是(0,0)f(0,0)(3,10),Tf3(,5)2(1,3)(0,2)(0,0)11(,0)22x1x(0,0)(3,10)Tf *1*1,0,01,.nniiiiixxxf xxxxinx(1)点为局部极小解的必要条件是，*,1,0.jjiiif xixxji xxix(2)固定 令有，*10,0200.ijjiiiiif xxxxji xxxf xxx(3)如果令则有，于是，有，如
20、果思考题：思考题：如果某凸规划的可行域为如果某凸规划的可行域为D=x|x0，请讨论此凸规划问题，请讨论此凸规划问题的最优解的充要条件的形式。的最优解的充要条件的形式。无约束问题无约束问题 一阶二阶必要和充分条件一阶二阶必要和充分条件等式约束问题等式约束问题 Lagrange 乘子理论乘子理论一般约束问题一般约束问题 一阶二阶必要和充分条件一阶二阶必要和充分条件最优性条件最优性条件 二阶必要条件二阶必要条件：设：设f:RnR1在点在点x*Rn 处二阶可微，如果处二阶可微，如果x*是局部极小解是局部极小解,则则f(x*)=0,且且2f(x*)为半正定矩阵为半正定矩阵.对无约束极值问题对无约束极值问
21、题 min f(x)，x Rn （1）一阶必要条件：设一阶必要条件：设f:Rn R1在点在点x*Rn处可微，处可微，如果如果x*是局部极是局部极小点小点,则则 f(x*)=0.定义定义:设设 f:En E1在点在点x*处可微处可微,若若f(x*)=0,称称x*函数函数f的驻点的驻点.驻点驻点极小点极小点驻点驻点极大点极大点驻点驻点鞍点鞍点fOx10,(0,),()(),.nfRRpntf xtpf xpfx 定义：设：，为 维非零向量，若存在对有则称向量 是 在点处的下降方向 1()0,.nnTfEExpEf xppfx定理：设：在点处可微，若存在使得则向量 是 在点处的下降方向0,fxfxT
22、aylort 证明：由条件 在点处可微，根据 在点处的展式，对于任意的有()()()()Tf xtpf xt f xpo tp()00,0,(0,),Tf xptt由于和于是存在对任意的有()()0Tt f xpo tp()(),.f xtpf xpfx于是有即 是 在点处的下降方向()f x()f xp x()f x 对无约束极值问题对无约束极值问题 min f(x)，x Rn （1）定理定理(一阶必要条件一阶必要条件)：设：设f:Rn R1在点在点x*Rn处可微，处可微，如果如果x*是是局部极小点局部极小点,则则 f(x*)=0.*()0(),f xpf x 证明:(反证法)假设，取则有2
23、*()()()()0.TTf xpf xf xf x *,0,0,pfxt 由上一定理可知是 在点 处的下降方向，即存在对有*x这与假设 是局部最优解矛盾，证毕。*()().f xtpf x 推论：设推论：设f:Rn R1在点在点x*Rn处可微，处可微，f是是Rn上的凸函数，上的凸函数，如果如果f(x*)=0,则则x*是无约束问题的全局最优解。是无约束问题的全局最优解。*,()()()()()().TxXf xf xf xf xxxf x 证明：对由为凸函数可得，定理定理(二阶必要条件二阶必要条件)：设：设f:RnR1在点在点x*Rn 处二阶可微，处二阶可微，如果如果x*是局部极小解是局部极小
24、解,则则f(x*)=0,且且2f(x*)为半正定矩阵为半正定矩阵.*,T0,nfxfxaylortpE证明:因为 在点 处二阶可微 由 在点 处的二阶展式,对于任意的和任意的有2*22*1()()()()()2TTf xtpf xt f xpt pf xpo tp*()(),tf xtpf x当 充分小时，有于是有222*2()()20To tppf xpptp2*2*0()0,().Ttpf xpf x令即可得到即是半正定矩阵注意：该定理仅是必要的，而不是充分的。注意：该定理仅是必要的，而不是充分的。定理定理(二阶充分条件二阶充分条件I)：设设f:RnR1在点在点x*Rn 处二阶可微，如果处
25、二阶可微，如果f(x*)=0,且且2f(x*)为为正定正定矩阵矩阵,则则x*是无约束问题的是无约束问题的严格严格局部极小解局部极小解证明证明:设设 为为 的最小特征值的最小特征值.利用二阶利用二阶Taylor展式有展式有2*()f x022*()()()()()2TTTf xdf xf xddf xdod 22()2dod2222oddd222odd只要 充分小，相对于可以忽略不计，0.定理定理(二阶充分条件二阶充分条件II):设设f:EnE1在点在点x*En 的一个邻域的一个邻域 处二阶连续可微，处二阶连续可微，如果如果 f 满足满足f(x*)=0,且且2f(x)在在 内半正定内半正定,则则
26、 x*是是无约束问题的局部极小解无约束问题的局部极小解.*()Nx*()Nx 1242112(,)min()(2)(2)Txx xf xxxx例：设,求如下无约束极小化问题的最优解 3*112124(2)2(2)()()0,(2,1).4(2)Txxxf xf xxxx解：因为,令解得由于22112(2)24(),48xf x2*2*24()()48f xf x有,显然是半正定矩阵,二阶充分条件失效.*2*()()(2,1)TxNxf xx但对点 的邻域,是半正定的,故是局部最优解.思考题：考虑二次函数的无约束极小化问题思考题：考虑二次函数的无约束极小化问题1min()2nTx Rf xx Q
27、xb x,其中其中Q为为n阶对称矩阵，阶对称矩阵，b为为n维列向量。维列向量。221122()282420.f xxxxx例：试求的极小点111222*1*4081(),20,044210408240414104()()10.Txxf xx xxxAxA bf xf x 解：其中是正定矩阵，故是的最小解,等式约束极值问题等式约束极值问题min f(x)，x Rns.t.hi(x)=0,i=1,2,m 最优性条件最优性条件(必要条件必要条件):定理定理:设等式约束问题中函数设等式约束问题中函数f与与hi(x)(i=1,m)是连续可微函数是连续可微函数,x*为局部最优解且为正则点为局部最优解且为正
28、则点(即即 线性无关线性无关,则存在实数则存在实数组组 ,使得使得*1()()0.miiif xh x*()ih x*1,m如果函数如果函数f与与hi(x)(i=1,m)是二次连续可微是二次连续可微,则则 注：等式约束问题的一阶必要条件的直观的几何意义：注：等式约束问题的一阶必要条件的直观的几何意义：122212min.2xxst xx*1211,.2xx 注注1：定理中给出的一阶必要条件仅当约束函数满足一定条件时：定理中给出的一阶必要条件仅当约束函数满足一定条件时才成立，该条件称为约束规格才成立，该条件称为约束规格1222122212min(1)10.(2)40 xxxxstxx 注：该定理
29、表明等式约束极值问题的极值点处的目标函数与约束注：该定理表明等式约束极值问题的极值点处的目标函数与约束函数梯度之间通过函数梯度之间通过Lagrange乘子向量存在的关系乘子向量存在的关系,是是Lagrange乘乘子法的出发点子法的出发点.1(,)()()miiiL x Vf xh x引入拉格朗日函数引入拉格朗日函数L(x,V),其中参数向量其中参数向量 称为称为.*12,m n+p个方程解个方程解n+p个未知量可得个未知量可得L的驻点的驻点,但是否驻点就是此非规划模但是否驻点就是此非规划模型的极小解，还需要充分条件的判断；型的极小解，还需要充分条件的判断；但是对于特殊的如二次规划问题，可以通过
30、计算但是对于特殊的如二次规划问题，可以通过计算L对对X的的Hesse矩阵矩阵判定该驻点是极大值点还是极小值点判定该驻点是极大值点还是极小值点.即即定理定理:设等式约束问题中函数设等式约束问题中函数f与与hi(x)(i=1,m)是连续可微函数是连续可微函数,x*为为f的局部最优解的局部最优解,线性无关线性无关,则存在乘子则存在乘子向量向量 ,使得使得*(),1,2,ih xim*(,)0.L x*1*(,)()()0.(,)()0,1,.miiix xix vL xf xh xxL xh xim*1(,)m 221212121212122212(1)max(,)283.310(2)min.2f
31、x xxxx xxxstxxxxst xx 练习练习:求等式约束极值问题求等式约束极值问题(书书61-62页页)(充分条件充分条件):定理定理:设等式约束问题中函数设等式约束问题中函数f与与hi(x)(i=1,m)是二次连续可微是二次连续可微函数函数,*(,)0(,)0 xL xL x，*nmxRR和满足2*(,)00()0 xxyL xyyh xy，且则则x*是一个极小点是一个极小点。123122331123min(,)().3f x x xx xx xx xstxxx 考虑 1.含不等式约束的极值问题含不等式约束的极值问题min f(x)，x Rns.t.gi(x)0,i=1,2,m (3
32、)最优性条件最优性条件设设x*是问题是问题(3)的可行解的可行解,约束条件约束条件gi(x)0可分为两类可分为两类,x*点的点的：gi(x*)=0；x*点的点的：gi(x*)0.*()|()0,1,2,.iI xi g xim记点记点x*处所有起作用约束下标的集合为处所有起作用约束下标的集合为I(x*),即即,0,.,.nXExX pntxtpXpxXpfxxXpfxX定义：设为 维非零向量 若存在使则称 是点 处关于 的可行方向如果 是 在点 处的下降方向,又是点 处关于可行域 的可行方向则称 为 在点 处关于 的可行下降方向如何找到在点如何找到在点x0处的可行方向？处的可行方向？*()0(
33、)Tig xpiI xpx只要有即可保证 为点 的可行方向.*(2)(),()0.()0()0.iiiiI xg xg xxtg xtp当时 有由函数在点 的连续性,当足够小时有*()0()Tig xpiI xpx只要有即可保证 为点 的可行方向.*(1)(),()0.()()()()()iiTiiiiI xg xg xtpxTaylorg xtpg xt g xpo t 当时 有由函数在点 的展式,有*()0(),0,()0().Tiiig xpiI xtg xtpg x如果只要足够小 有如果如果x*为局部最优解为局部最优解,则在该点处不可能存在可行下降方向则在该点处不可能存在可行下降方向.
34、*()()(),()(),()0,()0()(*)()|()0,1,2,.iiTTiixf xg xiI xxg x iI xxxpf xpg xpiI xI xi g xim定理1:设 是不等式约束的极值问题的一个局部最优解,和在点 处可微在点 处连续 则在点 处不存在可行下降方向，即不存在 同时满足其中指标集p从几何意义上说,满足上式的方向,与该点目标函数梯度方向的夹角为钝角且与该点起作用约束梯度方向的夹角也为钝角.11G:,0(1,),0.TmimmiiiordanAAmnpA pimA1引理 设是 个 维向量 不存在向量使成立的充要条件是存在不全为零的非负实数,使几何意义说明如下几何意
35、义说明如下:设设A1,A2,A3是三个二维向量是三个二维向量.1A2A3AHp3A若若A1,A2,A3不在任一条直线的同一不在任一条直线的同一侧侧,就无法找到使就无法找到使AiTp0(i=1,2,3)均均满足的向量满足的向量p.这时总可以适当缩小这时总可以适当缩小或放大各向量或放大各向量Ai的长度的长度,使它们合成使它们合成为零向量为零向量,即可找到不全为零的非负即可找到不全为零的非负实数实数,使使1122330.AAA若均位于某直线若均位于某直线H的同一侧的同一侧,则总可则总可找到某一向量找到某一向量p,使使AiTp0(i=1,2,3);定理：设定理：设x*是不等式约束极值问题是不等式约束极
36、值问题(3)的可行解，的可行解，I(x*)为在为在x*起作用起作用约束的下标集合，假设约束的下标集合，假设f(x),gi(x)(i I(x*)在在x*处可微，处可微，如果如果x*是局部最优解，则对于是局部最优解，则对于i I(x*)，存在，存在*0,i使得*()()0.iii If xg x如果如果gi(x)在在x*处都可微处都可微(i=1,2,m)，则上述结论可叙述为，则上述结论可叙述为存在存在*0,1,2,iim使得*1*()()0(1)()0,0,1,2,.(2)miiiiiif xg xg xim在在x*处连续，向量组处连续，向量组 线性无关。线性无关。*()()ig x iI x*(
37、)()ig xiI x此处的此处的(1)(2)两式称为两式称为Kuhn-Tucker条件，简称条件，简称K-T条件；条件；满足满足K-T条件的点称为条件的点称为K-T点。点。*,xxp证明:设点 是不等式约束极值问题的局部最优解,根据定理1知,该点 处不存在向量使得下式成立，即*()0,()0()TTif xpg xpiI x*0*0()()(),(),iiif xg xiI xGordanA AiI x 把和看成引理中的向量故存在不全为零的数使得*0()()()0iii I xf xg x*(),0iiI x当令相应的，于是有*01()()0miiif xg x*0()()0.ig xiI
38、x又因为线性无关,故0(1,2,),iiim令0(1).用 除上式中的各式两边,即可得到式*1,2,()0,0,(2)iiiimg x对所有有于是式成立.ker(1)KuhnTuc注：在条件的式中,可以变形得到*()*()()0()iii I xif xg xiI x可表示为*()f x的非负线性组合.*()()ig xiI x由此可见,若x*是K-T点,目标函数在点x*处的负梯度30g 20g 10g f1g2gf2g3g2x1x2x1xK-T条件的几何意义 2.一般约束极值问题的一般约束极值问题的KT条件条件min f(x)，x Rns.t.gi(x)0,i=1,2,m (3)hj(x)=
39、0,j=1,2,p 最优性条件最优性条件*(),()|(),1,2,.,ijg xh xiI xjp则存在则存在*0()iuiI x及及*(1,2,.,),jvjp使得使得线性无关线性无关.如果如果x*是局部最优解是局部最优解,定理：设定理：设x*是一般约束极值问题是一般约束极值问题(3)的可行解的可行解,I(x*)为在为在x*起作用约束起作用约束的下标集合的下标集合,假设假设gi(x)(i=1,2,m)在在x*处连续处连续,f(x),gi(x)(i I(x*)在在x*处可微处可微,hj(x)(j=1,2,p)在在x*的某邻域内连续可微的某邻域内连续可微,约束规格约束规格*1()()()()0
40、.piijjji I xf xug xvh x 如果如果*()()ig x iI x在在x*也是可微的，则也是可微的，则*11*()()()0()0,(1,2,)0,(1,2,)pmiijjijiiif xug xvh xu g ximuim*1212,Lagrangempuuuvvu其中,称为广义乘子。最优性条件最优性条件前面的定理表明前面的定理表明,如果局部最优解满足约束规格如果局部最优解满足约束规格,则则K-T条件成立条件成立;如果局部最优解不满足约束规格，则如果局部最优解不满足约束规格，则K-T条件条件可能可能不存在解不存在解.Kuhn-Tucker条件是确定某点为最优解的必要条件条件
41、是确定某点为最优解的必要条件,只要是最优只要是最优解解,且此处起作用约束的梯度线性无关且此处起作用约束的梯度线性无关,就一定满足就一定满足K-T条件条件,但但一般来说它并不是充分条件一般来说它并不是充分条件.因而因而,满足这个条件的点不一定是满足这个条件的点不一定是最优点最优点.下面的定理说明下面的定理说明,对于凸规划对于凸规划,Kuhn-Tucker条件不但是最优点存条件不但是最优点存在的必要条件在的必要条件,同时也是充分条件同时也是充分条件.定理：设定理：设f(x),gi(x)(i=1,2,m),hj(x)(j=1,2,p)在在x*处连续可微，处连续可微，且且f(x),gi(x)(i=1,
42、2,m)是凸函数，是凸函数，hj(x)是线性函数，若是线性函数，若x*是非线性是非线性规划模型的规划模型的K-T点，则点，则x*是其全局极小点。是其全局极小点。最优性条件最优性条件 KT例：利用条件求带一般约束的非线性规划问题的全局最优解221231212min()(2)(3).()(2)0()210f xxxst g xxxh xxx 最优性条件最优性条件*(1)0,(2,3),0;(2)0(1,1),2(1,1).TTTxxKT：可解得，不满足不等式约束条件：可解得,故为点 二次规划及其应用二次规划及其应用二次规划是一个有二次目标函数和线性约束条件的优化问题,其数学模型如下：min().0
43、TTf Xc XX QXstAXbX1,1,1XnQn ncnAm nbm其中 是决策变量向量是实对称矩阵,是向量是阶系数矩阵 是右端常数向量.111(,),(,),(,).TmTTmmSssuuuvvv其中二次规划的K-T条件引入松弛变量S,使之成为等式S=b-AX,并分别设与条件AXb和X0对应的Lagrange乘子向量为u和v，则二次规划的K-T条件为200,0,0,0TTTQXA uvcAXSbu Sv XXSuv二次规划及其应用二次规划及其应用min().0TTf Xc XX QXstAXbX000.TTTTu Sv Xu Sv X注意，这里等价于，由于二次规划是凸规划,故点X*是最
44、优解的充要条件是存在u,v,S,X共同满足以上K-T条件.于是,原问题的最优解等价于找以上K-T条件的可行解.200,0,0,0TTTQXA uvcAXSbu Sv XXSuv0,2K-T0,0TTAbSuMqwzcvXAQwMzqw zw z 令，则条件可以改写为二次规划及其应用二次规划及其应用至此，对二次规划的求解已经转化为线性互补问题，可以用互补转轴算法找出二次规划的K-T点。例：写出二次规划的K-T条件：122212121212min32220165.0,0fxxx xxxxxstxx3 12016,1,1,512cQAb 解：本例中的，1215,K-Txxs对约束加上松弛变量原问题的
45、条件为121112121211 11 122121212622002416050,0,0,0 xxuvxxuvxxsu sv xv xx x s u v v称为互补松弛条件，即u1,s1不能同时为零，vi和xi不能同时为零。二次规划及其应用二次规划及其应用 例：考虑二次规划问题22121122121212min26222.220,0fxxxx xxxxstxxxx 解：设与约束条件x1+x22,-x1+2x22,x10,x20对应的Lagrange乘子向量分别用u=(u1,u2)T和v=(v1,v2)T表示，1212123422211(),()()6241210()()01xxf xg xgx
46、xxgxgx 由于，二次规划及其应用二次规划及其应用 于是，可得K-T条件如下：12121121221122121 1221212121212222062420(2)0(22)00,0222,0 xxuuvxxuuvu xxuxxv xv xxxxxx x u u v v 1212121 12 22,00 xxxxs su su s如果对约束条件2和-2分别引入松弛变量则有和二次规划及其应用二次规划及其应用 线性互补问题线性互补问题,ppMppqRw zR定义：设为已知的阶矩阵,为一给定向量,线性互补问题是找出可行解使得以下各式成立:0(1,2,)(1)0,0(1,2,)jjjjwMzqw z
47、jpwzjp0(,)1,2,.jjjjw zw zjp其中称约束为互补约束,称为互补变量,(,)(1)(,)(1,2,)(,)jjw zw zjpw z若是以上系统式的基可行解,且中只有一个是基变量,则称为一对互补基可行解.如何解决线性互补问题？(1)0,0(1)qwq z若则显然令即可得到系统的解；线性互补问题线性互补问题0(2)0,qz若 不完全引入人工变量 后变形为0010(1,2,)(2)0,00(1,2,)jjjjwMzzqw zjpwzzjp，010max0,1,(2).i pizqzwqz 令,即可得到系统的一个初始解00(2)(1)(,)(2)1,2,(3)1,2,(,)ssj
48、jw z zspw zzjpjs w z 定义：考虑以上系统，一可行解称为几乎互补基可行解，若满足以下条件是满足以上系统中等式的基可行解；有都不是基变量;是基变量,中有且仅有一个是基变量.线性互补问题线性互补问题例：求解以下线性互补问题：0(1,2,)0,0(1,2,)jjjjwMzqw zjpwzjp其中00112001221122212246Mq，线性互补问题线性互补问题0,z解：引入人工变量形成下表：1w2w3w4w1z2z3z4z1w2w3w4w0zRHS100001000010000100-1-1001-21-1-22122-4-122-2-6-1-1-1144044max,.iis
49、qqzwyz 和中间进行旋转 令换入基变量（）线性互补问题线性互补问题3433,.sswyzwyz第1步：由最小比值原则确定为换出变量 在行和列之间进行一次旋转，并令1w2w3w4w1z2z3z4z1w2w3w0z0zRHS100001000010-1-1-1-111012232-1-3-4-2566-408846001（）线性互补问题线性互补问题31311,.sszwyzwyz第2步：换入基变量,由最小比值原则确定为换出变量 在行和列之间进行一次旋转，并令1w2w3w4w1z2z3z4z1w2w4z0z0zRHS10000100-5/6-11/6-2/3-1/60-1/6-1/31101-1
50、/2-11/207/31-2/32/30010014/342/310/3001（）线性互补问题线性互补问题1001,.szzyzz第3步：换入基变量,由最小比值原则确定 为换出变量 在行和 列之间进行一次旋转1w2w3w4w1z2z3z4z3z2w4z0z0zRHS3/7-3/72/70100-5/14-3/7-1/14-3/14-2/7-3/14-11/145/141/710010014/342/310/3001（）-2/7-9/14-1/141/143/74/72/75/7000 线性互补问题线性互补问题12341234(,)(0,2 5,0,0,14 5,0,4 5,6 5).Tw w
