非线性优化问题

第三专题非线性优化问题1、非线性优化模型的建立2、非线性优化模型的寻优非线性优化模型的建立确定决策变量确定目标（决策准则）确定约束条件实例分析（1）投资决策问题（P88)（2）曲线拟合问题在实验数据处理或统计资料分析中，常常遇到这样的问题：如何利用有关变量的实验数据（资料）去确定这些变量间的函数关系。例如，已知某物体的温度与时间之间有如下形式的经验函数关系：其中是待定参数。通过测试获得n组温度与时间之间的实验数据，试确定参数使理论曲线尽可能地与n个测试点拟合。(,),1,2,,iitinttcetcct321)(123,,ccc123,,ccc非线性规划问题的共同特征都是求一个目标函数在一组约束条件下的极值问题。在目标函数或约束条件中，至少有一个是变量的非线性函数。非线性规划问题一般形式：向量形式：121212min(,,,)..(,,,)0,1,2,,(,,,)0,1,2,,ninjnfxxxstgxxximhxxxjl11211min()..()0,1,2,,()0,1,2,,(,,,),:,::ijTnnnnnijfxstgximhxjlxxxxRfRRgRRhRR其中且和。非线性优化问题的寻优相关概念及理论一维最优化方法多维无约束最优化方法多维有约束最优化方法非线性规划的相关概念及理论一阶导数、二阶导数和n元函数的Taylor公式112121:,,()(,,,)(1,2,,)()()()()(,,,)nnTniTnfRRxRfxfxxxxxinxfxfxfxfxfxxxxfx定义设如果在点处关于自变量的各分量的偏导数都存在，则称函数在点处一阶可导(可微），并且称向量是在点处的一阶导数或梯度。1212222212112222221222212:,,()(,,,)(,1,2,,)nnTnijnnnfRRxRfxfxxxxxijnxxfxfxfxfxxxxxxfxfxfxfxxxxxxfxxx定义设如果在点处关于自变量的各分量的二阶偏导数都存在，则称函数在点处二阶可导，并且称矩阵（）（）（）（）（）（）（）222nnfxfxxxxfx（）（）是在点处的二阶导数或Hesse矩阵。122123:,,Taylor1()()()()()()2=(,,,)()()()(nnTTTnTfRRxRfxfxfxxfxfxxxfxxoxxxxxxxxfxfxfxfxx定义设如果在点处的某邻域具有二阶连续偏导数，则在点处二阶展式：其中。若记，略去高阶小量后，得到在点处的线性逼近（函数）和二次逼近（函数）：2)1()()()()+()()()2TTxfxfxfxxxxxfxxx定义4设函数xfnRD定义在凸集上，若对任意的,,Dyx及任意的1,0都有：yfxfyxf11则称函数xf为凸集D上的凸函数．定义5严格凸函数注：将上述定义中的不等式反向，可以得到凹函数的定义．凸函数例1：设,12xxf试证明xf在,上是严格凸函数．证明:设,,Ryx且1,0,yx都有：yfxfyxf1122211111yxyx012yx因此xf在,上是严格凸函数．例2：试证线性函数是nnTxcxcxcxcxf2211证明:设,1,0,,RyxnR上的凸函数．则yxcyxfT11yfxfycxcTT11所以xcT是凸函数．类似可以证明xcT是凹函数．凸函数的几何性质对一元函数,xf在几何上211xfxf10表示连接2211,,,xfxxfx的线段．211xxf表示在点211xx处的函数值．所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方．凸函数的性质（１）设（２）设xfxf21,函数，xf是凸集nRD上的凸函数，实数,0k则xkf也是D上的凸函数．是凸集nRD上的凸实数,0,则xfxf21也是D上的凸函数．（３）设xf是凸集nRD上的凸函数，是实数，则水平集,fSxfDxx,是凸集．下面的图形给出了凸函数xyy24243,yxxyxf的等值线的图形，可以看出水平集是凸集凸函数的判定定理1设xfnRD上，,,Dyx令,1,0,1tyttxft则:(1)xf是定义在凸集是凸集D上的凸函数的充要条件是对任意的,,Dyx一元函数t为1,0上的凸函数.(2)设,,,yxDyx若t在1,0上为严格凸函数，则xf在D上为严格凸函数．该定理的几何意义是：凸函数上任意两点之间的部分是一段向下凸的弧．一阶条件定理2.1设在凸集nRD上xf可微，则：xf在D上为凸函数的充要条件是对任意的,,Dyx都有：xyxfxfyfT定理2.2严格凸函数(充要条件)二阶条件定理3设在开凸集nRD内xf二阶可微，则(1)xf是D内的凸函数的充要条件为，在D内任一点x处，xf的海色矩阵xG半正定,22221222222122122122122nnnnnxfxxfxxfxxfxfxxfxxfxxfxfxfxG其中：二阶条件定理3设在开凸集nRD内xf(2)若在D内xG正定,则xf在D内二阶可微，则是严格凸函数．注:反之不成立．例：4xxf显然是严格凸的，但在点0x处xG不是正定的凸规划定义6设nRD为凸集，xf为D上的凸函数，则称规划问题xfDxmin为凸规划问题．定理4(1)凸规划问题的任一局部极小点x是整体极小点，全体极小点组成凸集．(2)若xf是凸集nRD上的严格凸函数，且凸规划问题xfDxmin整体极小点存在，则整体极小点是唯一的．非线性规划的最优性条件最优性条件：是指非线性规划模型的最优解所要满足的必要和充分条件。无约束最优性条件约束最优性条件min()fxmin()..()0,1,2,,()0,1,2,,ijfxstgxiphxjq无约束最优性条件1:,()00()()()0()()000,nnnTTTfRRxRPRfxPPfxfxfxTaylortfxtPfxtfxPtPfxPt定理设在处可微，若存在使，则称向量是函数在处的下降方向。证明因为在处可微，故由在处的展式，对于任意的，有由于，，从而存在对于(0,)()0()0()(),(0,)TttfxPtPfxtPfxtPfx任意的，有从而有故是函数在处的下降方向。一（单）元函数的最优性条件（１）若（２）*x为fx的局部极小点，则*0;fx若**0,0,fxfx则*x为fx的严格局部极小点；若（３）*x为fx的局部极小点，则：**0,0.fxfx多元函数的一阶必要条件（P106-107)定理1:若*x为xf的局部极小点，且在*xN内xf一阶连续可导，则.0**xfg注:(1)仅仅是必要条件，而非充分条件．(2)满足0**xfg的点称为驻点．驻点分为：极小点，极大点，鞍点．多元函数的二阶充分条件定理2:若在*xN内xf二阶连续可导，且***,0xGGg正定,则*x为严格局部极小点．注:如果*G负定,则*x为严格局部极大点．二阶必要条件和充要条件定理3:若*x为xf的局部极小点，且在*xN内xf二阶连续可导，则**,0Gg半正定．定理4:设xf在nR上是凸函数且有一阶连续偏导数，则*x为xf的整体极小点的充要条件是.0*g例1：利用极值条件解下列问题：12232313131minxxxxxf解：222221121xxxfxxf令,0xf即：020122221xxx得到驻点：(1)(2)(3)(4)1111,,,0202xxxx函数xf的海色阵：22002212xxxf由此，在点(1)(2)(3)(4),,,xxxx处的海色阵依次为：2(1)2(2)20200202fxfx2(3)2(4)20200202fxfx由于矩阵2(1)2(4),fxfx不定，则(1)(4),xx不是极小点．2(3)fx负定，则(3)x不是极小点，实际上它是极大点．2(2)fx正定，则(2)x是局部极小点．约束最优性条件(p133-p136)min()..()0,1,2,,()0,1,2,,()0,1,2,,;()0,1,2,,1,2,,,1,2,,ijnijfxstgxiphxjqDxRgxiphxjqJqIp一般约束问题的最优性（*)令可行域定义1:有效约束：若(*)中的一个可行点*x使得某个不等式约束0igx变成等式，即则称为关于的有效(积极）约束．非有效约束：若对*0,kgx则0kgx称为关于的非有效(无效）约束．有效集：***0iIIxigx定义2:锥：nR的子集，如果它关于正的数乘运算是封闭的．如果锥也是凸集，则称为凸锥．凸锥关于加法和正的数乘运算是封闭的．*0igx0igx*x*x一阶必要条件定理3.5:(Kuhn-Tucker一阶必要条件)(1951)设*,()ifxgxiI在可微，*x******iijjjJiIfxgxhx*********()()()(),()0()(),jijijxhxjJxgxiIhxjJxiIjJ点处连续。在点处连续可微,且线性无关。若是问题（*)的局部最优解，则存在和使得*(\)igxiII在（K-T条件）一阶必要条件定理1‘:(Kuhn-Tucker一阶必要条件)**0iigxIi*********,()()()(),()0()(),ijijijfxgxiIxhxjJxgxiIhxjJxiIjJ设在点处可微,在点处连续可微,且线性无关。若是问题（*)的局部最优解，则存在和使得*****iijjiIjJfxgxhx（互补松弛条件）*********min()..()0,1,2,,0()min()..()0,1,2,,()iiiiiIjjfxstgxipxiIfxgxfxsthxjqxjJ不等式约束问题若是不等式约束问题的局部最优解，则存在使得等式约束问题若是等式约束问题的局部最优解，则存在使***jjjJfxhx得例2：验证是否满足Kuhn-Tucker条件：22212312123222123min32..00003fxxxxstxxxxxxxx试验证最优点Tx1,1,1*为KT点．x解：*1ITxf4,2,6