非线性规划的基本概念

第五讲非线性规划的基本概念非线性规划问题非线性规划数学模型非线性规划的图解法梯度、Hesse矩阵、Jacobi阵凸函数和凸规划解非线性规划方法概述一维最优化在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。非线性规划是运筹学的重要分支之一。最近30多年来发展很快，不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。1非线性规划问题举例例一：选址问题设有个市场，第个市场位置为，它对某种货物的需要量为。现计划建立个仓库，第个仓库的存储容量为试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。设第个仓库的位置为第个仓库到第个市场的货物供应量为则第个仓库到第个市场的距离为jn),(jjqp),,2,1(njbjmi).,,2,1(miaii,,,2,1),,(miyxiiij).,,2,1,,,2,1(njmizijij,)()(22jijiijqypxd,)()(min221111jijiminjijijminjijqypxzdz目标函数为约束条件为（1）每个仓库向各市场提供的货物量之和不能超过它的存储容量。miazinjij,,2,1,1njbzjmiij,,2,1,1（2）每个市场从各仓库得到的货物量之和应等于它的需要量。（3）运输量不能为负数njmizij,,2,1,,,2,1,0例2.木梁设计问题把圆形木材加工成矩形横截面的木梁，要求木梁高度不超过，横截面的惯性矩（高度的平方宽度）不小于，而且高度介于宽度与4倍宽度之间。问如何确定木梁尺寸可使木梁成本最小.HW2x1x设矩形横截面的高度为，宽度为，则圆形木材的半径1x2x222122xxr而木梁长度无法改变，因此成本只与圆形木材的横截面积有关。,44min22212xxrs目标函数为约束条件为)(.0,44(W)()(2121212211高度与宽度非负倍宽度之间）高度介于宽度与惯性矩不小于高度不小于xxxxxxWxxHHx（1）数学规划模型的一般形式：其中,简记为MP(MathematicalProgramming)2非线性规划问题的数学模型qjxhpixgxfii,,1,0)(,,1,0)(s.t.)(min的实值函数，为xxhxgxfxxxxjiTn)(),(),(,),,,(21（2）简记形式：Tpxgxgxg))(,),(()(1Tqxhxhxh))(,),(()(1引入向量函数符号：qjxhpixgtsxfii,,1,0)(,,1,0)(..)(min0)(0)(..)(minxhxgtsxfXxxf)(minqjxhpixgRxXiin,,1,0)(,,1,0)(（3）数学规划问题的分类：0)(0)(s.t.)(minxhxgxf若为线性函数，即为线性规划(LP)；若至少一个为非线性,即为非线性规划(NLP)；对于非线性规划，若没有,即X=Rn,称为无约束非线性规划或无约束最优化问题；否则称为约束非线性规划或约束最优化问题。)(),(),(xhxgxfji)(),(),(xhxgxfji)(),(xhxgji（4）可行域和可行解：qjxhpixgRxXiin,,1,0)(,,1,0)(称为MP问题的约束集或可行域。若x在X内，称x为MP的可行解或者可行点。qjxhpixgtsxfii,,1,0)(,,1,0)(..)(min（5）最优解和极小点对于非线性规划（MP），若，并且有Xx*Xxxfxf),()(*极小值。）的整体最优值或整体是（称MP)(*xf如果有**,),()(xxXxxfxf严格整体极小点，）的严格整体最优解或是（称MP*x严格整体极小值。）的严格整体最优值或是（称MP)(*xf定义:极小点，）的整体最优解或整体是（则称MP*x使的邻域并且存在若）对于非线性规划（)(,,MP****xxRxxNxXxnXxNxxfxf)()()(**，极小值）的局部最优值或局部是（称MP)(*xf如果有***,)()()(xxXxNxxfxf，定义严格局部极小点）的严格局部最优解或是（称MP*x严格局部极小值。）的严格局部最优值或是（MP)(*xf则称x*是(MP)的局部最优解或局部极小解,例1：用图解法求解minf(x)=(x1－2)2+(x2－2)2s.t.h(x)=x1+x2-6=0x1x20662233最优解x*=(3，3)T可行解x=(1.5，4.5)T最优级解即为最小圆的半径：f(x)=(x1－2)2+(x2－2)2=23非线性规划问题的图解法对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。x1x206622D可行域最优解x*=(2，2)T例2：用图解法求解minf(x)=(x1-2)2+(x2-2)2s.t.h(x)=x1+x2-6≤03非线性规划问题的图解法最优级解即为最小圆的半径：f(x)=(x1-2)2+(x2-2)2=0•解：①先画出等式约束曲线的图形——抛物线，0,0505.12)(min212122212221xxxxxxxtsxxxf052221xxxx1x2123456135•例3：用图解法求解•②再画出不等式约束区域，•③最后画出目标函数等值线，•所以最优解x*=(4,1),最优值minf(x)=4.4梯度、Hesse矩阵、Jacobi阵•(1)二次函数一般形式:矩阵形式:二次型:矩阵A的正定性:正定、半正定、负定、不定。其中A＝AT。二次型的正定性:正定、半正定、负定、不定。cxbxxgxxxfiniininjjiijn1112121,,,cxbAxxxfTT21AxxxfT21（2）梯度定义：f(x)是定义在En上的可微函数。f(x)的n个偏导数为分量的向量称为f(x)的梯度.Tnxxfxxfxxfxf,,)(21性质：设f(x)在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质：性质一函数在某点的梯度不为零，则该梯度方向必与过该点的等值面垂直;性质二梯度方向是函数具有最大变化率的方向（负梯度方向也叫最速下降方向）。解：由于,46211xxxf102121xxxfxfxfP例：试求目标函数在点x=[0,1]T处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。2221212143,xxxxxxf则函数在x=[0,1]T处的最速下降方向是21224xxxf24244610212121xxxxxx这个方向上的单位向量是：551552242422xfxfe解：由于例：试求目标函数在点x=[0,1]T处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。2221212143,xxxxxxf新点是：551552242422xfxfe5511552551552101exx52526|4312221211xxxxxxf函数值：•几个常用的梯度公式：AxxfAxxxfAxxfxxxfbxfxbxfCxfCxfTTT2.4.2.3..20.0,.1则对称矩阵。则则即则常数（3）Hesse矩阵22221222222212121222122nxxfnxxxfnxxxfxnxxfxxfxxxfxnxxfxxxfxxfxfxf多元函数f(x)关于x的二阶导数，称为f(x)的Hesse矩阵.当f(x)的所有二阶偏导数连续时,即ijjixxxfxxxf22Hesse矩阵是对称的.时，;0)(,)(2xfbxfxbxfT);()(,)(212单位阵IxfxxfxxxfT.)(,)(,212AxfAxxfAAxxxfT对称•几个常用Hessian公式：（4）Jacobi矩阵•向量变量值函数：nmmmnnxxgxxgxxgxxgxxgxxgxxgxxgxxgxg0201002202102012011010向量值函数g(x)在点x0处的Jacobi矩阵Tnxgxgxgxg))(,),(),(()(21•向量变量值函数的导数：Tnxxxx),,,(21(1)凸函数：）有，（若对是非空凸集，设10,:1RSfRSn定义上是凸的。在上的凸函数，或是则称SSff上是严格凸的。在上的严格凸函数，或是则称SSff凹的。严格上是在或凹函数严格上的是凸函数，称严格上的是若)(S,)(S)(Sfff5凸函数和凸规划Sxxxfxfxxf212121,),()1()())1((Sxxxfxfxxf212121,),()1()())1((若即是凸的也是凹的。其中例1,,,)(RRxxxfnT是凸函数其中例nRxxxf||||)(例：正定二次函数,21)(cxbAxxxfTT其中A是正定矩阵，f(x)是凸函数。参见P104例。是非空凸集设nRS性质1:上的凸函数；是，则上的凸函数，是若S0S)1(ff上的凸函数。是上的凸函数是若S,S,)2(2121ffff（2）凸函数的性质性质2:则集合是凸函数是非空凸集设,,,1RcfRSncxfSxcfHS)(|),(是凸集。证明:略.则可微：是非空开凸集，设,S1RSfRn上的凸函数是）（S1fSxxxfxfxxxfT2112121,),()()()(处的梯度。是函数在点）（其中11111)(,)()(xxxfxxfxfTn定理1：（一阶条件）上的严格凸函数是）（S2f212112121,,),()()()(xxSxxxfxfxxxfTn=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。（3）凸函数的判定逆命题不成立）上的严格凸函数（此时是上是正定矩阵时在当上是半正定的。在上的凸函数是则二阶连续可导是非空开凸集设,)(S)(,:,S221SfSxfxfSfRSfRn