非线性规划的基本概念和基本原理

1第七章非线性规划的基本概念和基本原理27.1数学模型和基本概念非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划复杂。3一、数学模型例某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？1x2x0,8052)(max212121xxxxxxxf分析：设长为米，宽为米，则有1x2xf(x)为非线性函数4例设某物理过程具有如下规律用试验法。现要确定参数使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足非负。txexxt321)(mittii,,2,1,)(值时的求得,,,321xxx321,1xxx5非线性规划：目标函数或（和）约束条件为非线性函数的规划。01)]()([)(min32112213xxxexxtxfmitxii分析：f(x)为非线性函数，求最小。6一般模型Minf(X)s.t.hi(X)=0(i=1,2,….m)（P）gj(X)0(j=1,2….l)XEnf(X)hi(X)gj(X)为En上的实函数。或约束条件目标函数)2(l,,2,1,j0(x)g)1(f(x)minj7二、基本概念1、全局极值和局部极值为目标函数，为可行域。若存在，，都有，则称为该问题的全局极小点，为全局极小值。)(XfSSX*SX*()()fXfX*X)(*Xf为目标函数，为可行域。若有，，都有，则称为该问题的严格全局极小点，为严格全局极小值。)(XfS**,XXSXSX)()(*XfXf*X)(*Xf8若存在，令，都有，则称为该问题的局部极小点，为局部极小值。0,*SX}0,|{*XXXN)(*XNSX)()(*XfXf*X)(*Xf若存在，令，都有，则称为该问题的严格局部极小点，为严格局部极小值。0,*SX}0,|{*XXXN**),(XXXNSX)()(*XfXf*X)(*Xf相应不等式反号，得到相应极大点，极大值定义。9定义如果X满足（P）的约束条件hi(X)=0(i=1,2,….m)gj(X)0(j=1,2….l)则称XEn为（P）的一个可行解。记（P）的所有可行解的集合为D，D称为（P）可行域。10定义X*称为（P）的一个（整体）最优解，如果X*D，满足f(X)f(X*)，XD。定义X*称为（P）的一个（局部）最优解，如果X*D，且存在一个X*的邻域N(X*,)=XEnX-X*,0满足f(X)f(X*)，XDN(X*,)11f(X)局部最优解整体最优解122.梯度向量f(X)=gradf(X)=(f/x1,f/x2,…..,f/xn)T区间内连续的梯度的性质：①在某点的f(X（0）)必与函数过该点的等值面的切平面相垂直。②梯度方向是函数值增加最快的方向（函数变化率最大的方向）负梯度方向是函数值减小最快的方向。13.,.,0)(*但驻点不一定是极值点驻点在区域内部极值点必为称为平稳点或驻点的点满足xf143、海赛(Hesse)矩阵2f(X)=H(X)2f/x122f/x1x2…..2f/x1xn2f/x2x12f/x22…..2f/x2xn……..2f/xnx12f/xnx2…..2f/xn2=152f(X)是对称矩阵。（f(X)二阶偏导数连续时，混合偏导数和取导数的顺序无关）f(X)是二次函数，则可写成f(X)＝1/2XTAX+BTX+C则2f(X)＝A（与X的位置无关）164、正定矩阵、负定、半定、不定正定：特征值0；各阶主子式0(Ai0)半正定：特征值≥0；detA=0,Ai≥0负定：特征值0；Ai0(i为奇）,Ai0(i为偶）半负定：特征值≤0；detA=0，Ai≤0(i为奇）,Ai≥0(i为偶）不定：特征值有0及0；除了上述情况外即为不定。17例：判定正定性402062225A031301110B0511a0266225080402062225A负定A解：18例：判定正定性402062225A031301110B011b010110不定B解：19作业：P2004.4（1）207.2无约束问题的极值条件例求解如下非线性规划问题06)2()2()(min212221xxxxxf解.2)()(min,3,),()(,)(**2*1xfxfxxDDcxfxf最小值得到最优解点在点等值线与直线相切于常数即的等值线作o261x262x)3,3(D21分析：hxxx12()60,若非线性规划的最优解可能在可行域的任一点达到。o22661x2x06)2()2()(min212221xxxxxfxxfxhxxfx***12*2,2,()0,,()0,min().最优解位于可行域内部此时事实上不起约束作用直接由求得22o若H(x)为正定，该驻点X*是严格局部极小值点；o若H(x)为负定，该驻点X*是严格局部极大值点；o若H(x)为半正定（半负定），则进一步观察它在该点某邻域内的情况，可能是可能不是；o如果H(x)不定的，该驻点X*就不是f(X)极值点。一、用海赛矩阵判断驻点的性质23二、极值点的必要条件和充分条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？o本质上把可行解集合的范围缩小。o它是许多算法设计的基础。24无约束问题的最优性条件（P1）Minf(X)XEn定理3（一阶必要条件）设f(X)在X*点可微，则X*为（P1）的一个局部极值点，一定有f(X*)=gradf(X*)=0（X*称为驻点）25无约束问题的最优性条件（P1）Minf(X)XEn定理4（二阶必要条件）设f(X)在X*点二阶可微，如果X*为（P1）的一个局部极小点，则有f(X*)=0和H（X*）为半正定。26无约束问题的最优性条件（P1）Minf(X)XEn定理5（二阶充分条件）设f(X)在X*点二阶可微，如果f(X*)=0和H(X*)为正定，则X*为(P1)的一个严格局部极小点。27例Minf(X)=2x12+5x22+x32+2x2x3+2x1x3-6x2+3XE3解：f(X)=（4x1+2x3,10x2+2x3–6,2x1+2x2+2x3）=0驻点x*=(1,1,-2)H(X)=2f(X)=402010222228H(X)=2f(X)=4020102222各阶主子式：40,=400400104020102222=240H(X)正定，X*=(1,1,-2)，f(X*)=029例利用极值条件解无约束非线性规划问题解因为，令即求得到4个驻点：1211xxf22222xxxf0)(Xf020122221xxx011X212X013X214X22002)(212xxXf2002)(12Xf2002)(22Xf2002)(32Xf2002)(42Xf43131)(min1223231xxxxXf，和不是极小点；1X4X是极小点。2X3X30凸集概念：设D是n维线性空间En的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。即：若D中的任意两点x(1),x(2)∈D，任意01使得x=x(1)+(1-)x(2)∈D,则称D为凸集7.3凸函数与凸规划31一、凸函数的定义.)()()1()())1(()1,0(,,)2()1()2()1()2()1(上的凸函数为则称若及为凸集设RXfXfXfXXfRXXR.)()()1()())1(()2()1()2()1(上的严格凸函数为则称若RXfXfXfXXf.)()()1()())1(()2()1()2()1(上的凹函数为则称若RXfXfXfXXf.)()()1()())1(()2()1()2()1(上的严格凹函数为则称若RXfXfXfXXf几何解释32f(X)X33f(X)Xf(X1)f(X2)X1X234f(X)Xf(x1)+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)35f(X)Xf(x1)+(1-)f(x2)f(X1)f(X2)X1X2x1+(1-)x2f(x1+(1-)x2)任意两点的函数值的连线上的点都在曲线的上方36非凸非凹函数)1(x)2(xox)(xfx))1(()2()1(xxf)()1()()2()1(xfxf凹函数)1(x)2(xo)(xf线性函数既是凸函数,又是凹函数。如果-f(X)为R上的(严格)凸函数,则f(X)为R上的(严格)凹函数.37二．凸函数的性质性质1设都是定义在凸集R上的凸函数，那么仍是在凸集R上的凸函数。),,1()(kiXfi0ikiiiXfXf1)()(性质2设是定义在凸集S上的凸函数，那么对任意实数，集合是S的凸子集。)(Xf})(|{XfSXS性质3f(x)是凸集R上凸函数，则f(x)在R上局部极小点就是全局极小点，且极小点的集合是凸集。38三、凸函数的判别TRfxRfxRXXRXXfXfXfXXX(1)(2)(1)(2)(2)(1)(1)(2)(1)(1),(),(),,,()()()()一阶条件设为开凸集在上有一阶连续偏导数则在上为凸函数的充要条件是对任意恒有若为严格不等式，为严格凸函数的充要条件。.)()(.)()()(,)(,)2(上为严格凸函数在正定则若上处处半正定在的海赛矩阵凸函数的充要条件是上为在则上有二阶连续偏导数在为开凸集设二阶条件RXfXHRXHXfRxfRxfR39例.10223)(222121的凸性判别函数xxxxXf.)(4006)(222122212212为严格凸函数正定用二阶条件解XfxfxxfxxfxfXH40作业：P2004.6（1）（2）41定理6（充要条件）：若是二阶连续可微的凸函数，则是全局极小点。类似地，若二阶连续可微的严格凸函数，则是惟一全局极小点。四、凸函数极值点的充要条件)(Xf*X0)(*Xf)(Xf*X证nRX，0)(*Xf，得0)(*XXXfT因为)(Xf是凸函数，由凸函数判别一阶条件知，)()()()()(****XfXXXfXfXfT即*X是全局极小点。42解无约束问题的算法：求f(X)的驻点X*，若是凸函数，得到最优解。否则，转下一步。在驻点X*处，计算H(x)。根据H(x)来判断该驻点X*是否是极值点。43例求极值f(X)=x1+2x3+x2x3-x12-x22-x32XE3解：f(X)=(1-2x1,x3-2x2,2+x2-2x3)=0驻点x*=(1/2,2/3,4/3)H(X)=xxf(X)=-2000-2101-244H(X)=xxf(X)=各阶主子式：-20,=40-200-2=-60-2000-2101-2-2000-2101-2H(X)负定，f(X)是凹函数X*=(1/2,2/3,4/3)为极大值点。f(X*)=f(1/2,2/3,4/3)=19/1245五、凸规划下述问题为凸规划..)(,)(,,1,0)()(min为凹函数为凸