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

关于非线性规划的基本概念和基本原理27.1数学模型和基本概念非线性规划是运筹学中包含内容最多，应用最广泛的一个分支，计算远比线性规划复杂。第2页,共54页，星期六，2024年，5月3一、数学模型例某单位拟建一排厂房，厂房建筑平面如图所示。由于资金及材料的限制，围墙及隔墙的总长度不能超过80米。为使建筑面积最大，应如何选择长宽尺寸？分析：设长为米，宽为米，则有

f(x)为非线性函数第3页,共54页，星期六，2024年，5月4例设某物理过程具有如下规律用试验法。现要确定参数使所得试验点构成的曲线与理论曲线误差平方和为最小，且满足

非负。第4页,共54页，星期六，2024年，5月5非线性规划：目标函数或（和）约束条件为非线性函数的规划。分析：

f(x)为非线性函数，求最小。第5页,共54页，星期六，2024年，5月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上的实函数。或第6页,共54页，星期六，2024年，5月7二、基本概念1、全局极值和局部极值

为目标函数，为可行域。若存在，，都有，则称为该问题的全局极小点，

为全局极小值。

为目标函数，为可行域。若有，，都有，则称为该问题的严格全局极小点，

为严格全局极小值。

第7页,共54页，星期六，2024年，5月8若存在，令，都有，

则称为该问题的局部极小点，为局部极小值。

若存在，令，都有，

则称为该问题的严格局部极小点，为严格局部极小值。

相应不等式反号，得到相应极大点，极大值定义。第8页,共54页，星期六，2024年，5月9定义如果X满足（P）的约束条件

hi(X)=0(i=1,2,….m)gj(X)

0(j=1,2….l)

则称X

En

为（P）的一个可行解。记（P）的所有可行解的集合为D，D称为（P）可行域。第9页,共54页，星期六，2024年，5月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

DN(X*,)

第10页,共54页，星期六，2024年，5月11f(X)局部最优解整体最优解第11页,共54页，星期六，2024年，5月122.梯度向量

f(X)=gradf(X)=(f/x1,f/x2,…..,f/xn)T区间内连续的梯度的性质：①在某点的

f(X（0）)必与函数过该点的等值面的切平面相垂直。②梯度方向是函数值增加最快的方向（函数变化率最大的方向）负梯度方向是函数值减小最快的方向。第12页,共54页，星期六，2024年，5月13第13页,共54页，星期六，2024年，5月143、海赛(Hesse)矩阵

2f(X)=H(X)

2f/x12

2f/x1x2…..2f/x1xn

2f/x2x1

2f/x22

…..2f/x2xn……..

2f/xnx1

2f/xnx2…..2f/xn2=第14页,共54页，星期六，2024年，5月15

2f(X)是对称矩阵。（f(X)二阶偏导数连续时，混合偏导数和取导数的顺序无关）f(X)是二次函数，则可写成

f(X)＝1/2XTAX+BTX+C则2f(X)＝A（与X的位置无关）第15页,共54页，星期六，2024年，5月164、正定矩阵、负定、半定、不定正定：特征值>0；各阶主子式>0(Ai>0)半正定：特征值≥0；detA=0,Ai≥0负定：特征值<0；Ai<0(i为奇）,Ai>0(i为偶）半负定：特征值≤0；detA=0，Ai≤0(i为奇）,Ai≥0(i为偶）不定：特征值有>

0及<

0；除了上述情况外即为不定。第16页,共54页，星期六，2024年，5月17例：判定正定性解：第17页,共54页，星期六，2024年，5月18例：判定正定性解：第18页,共54页，星期六，2024年，5月19作业：P2004.4（1）第19页,共54页，星期六，2024年，5月207.2无约束问题的极值条件例求解如下非线性规划问题o2626第20页,共54页，星期六，2024年，5月21分析：

非线性规划的最优解可能在可行域的任一点达到。o2266第21页,共54页，星期六，2024年，5月22若H(x)为正定，该驻点X*是严格局部极小值点；若H(x)为负定，该驻点X*是严格局部极大值点；若H(x)为半正定（半负定），则进一步观察它在该点某邻域内的情况，可能是可能不是；如果H(x)不定的，该驻点X*就不是f(X)极值点。一、用海赛矩阵判断驻点的性质第22页,共54页，星期六，2024年，5月23二、极值点的必要条件和充分条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？本质上把可行解集合的范围缩小。它是许多算法设计的基础。第23页,共54页，星期六，2024年，5月24无约束问题的最优性条件（P1）Minf(X)X

En

定理3（一阶必要条件）

设f(X)在X*点可微，则X*为（P1）的一个局部极值点，一定有

f(X*)=gradf(X*)=0（X*称为驻点）第24页,共54页，星期六，2024年，5月25无约束问题的最优性条件（P1）Minf(X)X

En

定理4（二阶必要条件）

设f(X)在X*点二阶可微，如果X*为（P1）的一个局部极小点，则有

f(X*)=0和H（X*

）为半正定。第25页,共54页，星期六，2024年，5月26无约束问题的最优性条件（P1）Minf(X)X

En

定理5（二阶充分条件）

设f(X)在X*点二阶可微，如果

f(X*)=0和H(X*)为正定，则X*为(P1)的一个严格局部极小点。第26页,共54页，星期六，2024年，5月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)=020102222第27页,共54页，星期六，2024年，5月28H(X)=2f(X)=020102222各阶主子式：4>0,=40>04

0010020102222

=24>0H(X)正定，X*=(1,1,-2)，f(X*)=0第28页,共54页，星期六，2024年，5月29例利用极值条件解无约束非线性规划问题解因为

，

令即求得到4个驻点：

，和不是极小点；

是极小点。第29页,共54页，星期六，2024年，5月30凸集概念：

设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凸函数与凸规划第30页,共54页，星期六，2024年，5月31一、凸函数的定义几何解释第31页,共54页，星期六，2024年，5月32f(X)X第32页,共54页，星期六，2024年，5月33f(X)Xf(X1)f(X2)X1X2第33页,共54页，星期六，2024年，5月34f(X)X

f(x1)

+(1-

)f(x2)f(X1)f(X2)X1X2

x1+(1-

)x2f(x1+(1-

)x2)第34页,共54页，星期六，2024年，5月35f(X)X

f(x1)

+(1-

)f(x2)f(X1)f(X2)X1X2

x1+(1-

)x2f(x1+(1-

)x2)任意两点的函数值的连线上的点都在曲线的上方第35页,共54页，星期六，2024年，5月36线性函数既是凸函数,又是凹函数。如果-f(X)为R上的(严格)凸函数,则f(X)为R上的(严格)凹函数.第36页,共54页，星期六，2024年，5月37二．凸函数的性质

性质1设都是定义在凸集R上的凸函数，那么仍是在凸集R上的凸函数。性质2设是定义在凸集S上的凸函数，那么对任意实数，集合是S的凸子集。性质3f(x)是凸集R上凸函数，则f(x)在R上局部极小点就是全局极小点，且极小点的集合是凸集。

第37页,共54页，星期六，2024年，5月38三、凸函数的判别第38页,共54页，星期六，2024年，5月39例第39页,共54页，星期六，2024年，5月40作业：P2004.6（1）（2）第40页,共54页，星期六，2024年，5月41定理6（充要条件）：若是二阶连续可微的凸函数，则是全局极小点。类似地，若二阶连续可微的严格凸函数，则是惟一全局极小点。四、凸函数极值点的充要条件第41页,共54页，星期六，2024年，5月42解无约束问题的算法：求f(X)的驻点X*，若是凸函数，得到最优解。否则，转下一步。在驻点X*处，计算H(x)。根据H(x)来判断该驻点X*是否是极值点。第42页,共54页，星期六，2024年，5月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-2第43页,共54页，星期六，2024年，5月44H(X)=xxf(X)=各阶主子式：-2<0,=4>0-2

00-2=-6<0-2000-2101-2-2000-2101-2

H(X)负定，f(X)

是凹函数X*=(1/2,2/3,4/3)为极大值点。f(X*)=f(1/2,2/3,4/3)=19/12第44页,共54页，星期六，2024年，5月45

五、凸规划下述问题为凸规划.求凸函数f(x)在凸集R上的极小点的问题，称为凸规划。第45页,共54页，星期六，2024年，5月46性质：1、凸规划的局部极小点就是全局极小点。2、极小点的集合是凸集。3、若目标函数为严格凸函数，若存在极小点，则极小点必定唯一。凸规划