非线性规划演示文稿2

非线性规划演示文稿1第一页，共三十六页。2（优选）非线性规划第二页，共三十六页。2、多元函数y=f(X)=f(x1,x2,…,xn)：在X0附近作泰勒展开，得

第三页，共三十六页。①极值点存在的必要条件：f(x)=0，此时求出的x0

为驻点。

②极值点存在的充分条件：

第四页，共三十六页。四、凸函数与凹函数：

1、定义：y=f(x)是En中某凸集R上的函数①对[0,1]及X1、X2R，且X1≠X2

若f[X1+(1-)X2]≤f(X1)+(1-)f(X2)，则f(x)为R上的凸函数。若f[X1+(1-)X2]＜f(X1)+(1-)f(X2)，则f(x)为R上的严格凸函数。②对[0,1]及X1、X2R，且X1≠X2

若f[X1+(1-)X2]≥f(X1)+(1-)f(X2)，则f(x)为R上的凹函数。若f[X1+(1-)X2]＞f(X1)+(1-)f(X2)，则f(x)为R上的严格凹函数。yxoX1X2X1+(1-)X2y=f(x)凸函数yxoX1X2X1+(1-)X2y=f(x)凹函数yxoX1X2y=f(x)非凸、非凹函数第五页，共三十六页。2、性质：fi(X)为凸集R上的凸函数，则对ki≥0，i=1,2,…,m，有

k1f1(X)+k2f2(X)+…+kmfm(X)仍为凸函数。

3、凸函数的判定：f(X)定义在凸集R上，若f(X)有连续的二阶导数，则f(X)为凸函数H为半正定。

f(X)为严格凸函数H为正定。

4、凸函数的局部极值与全局极值的关系若目标函数在可行域中为凸函数，则其极值点为最优值点；若目标函数在可行域中为严格凸函数，则其极值点为唯一最优值点。

第六页，共三十六页。五、凸规划：

1、定义：非线性规划(p)

Minf(X)

gi(X)≥0

，i=1,2,…,m

若f(X)，-gi(X)为凸函数，则(p)称为凸规划。2、性质：①(p)的可行解集R是凸集；最优解集R*也是凸集。②(p)的任何局部最优解均是全局最优解。③若f(X)为严格凸函数时，其最优解必唯一。特例:线性函数既是凸函数又是凹函数，故L.P.为凸规划。六、寻优方法概述：

1、N.L.P.问题分类①无约束条件的NLP问题。②有约束条件的NLP问题。

2、寻优方法

①间接法(解析法)：适应于目标函数有简单明确的数学表达式。②直接法(搜索法)：目标函数复杂或无明确的数学表达式。

a.消去法(对单变量函数有效)：不断消去部分搜索区间，逐步缩小极值点存在的范围。

b.爬山法(对多变量函数有效)：根据已求得的目标值，判断前进方向，逐步改善目标值。第七页，共三十六页。9.2无约束条件下单变量函数寻优一、消去法原理：逐步缩小搜索区间，直至极值点存在的区间达到允许的误差范围为止。设要寻求f(X)的极小值点为X*，起始搜索区间为[a0,b0]。

x1、x2[a0,b0]，且x2＜x1，计算f(x1)和f(x2)，并且比较结果：f(x)xoa0b0X*x1,x2在x*的右侧x1x2f(x)xoa0b0X*x1,x2在x*的左侧x1x2f(x)xoa0b0X*x1,x2在x*的两侧x1x2①x1,x2均在x*的右侧，f(x2)＜f(x1)，去掉[x1,b0]，此时x*[a0,x1]②x1,x2均在x*的左侧，f(x2)＞f(x1)，去掉[a0,x2]，此时x*[x2,b0]③x1,x2均在x*的两侧，f(x2)＝f(x1)：

a.去掉[x1,b0]，此时x*[a0,x1]b.去掉[a0,x2]，此时x*[x2,b0]

第八页，共三十六页。二、黄金分割法(0.618法)：是一种常用的消去法与对分法、Fibonacci法比较，具有计算次数少，过程简单的特点。1、原理：LxL-xLx1x22、取点法则：Lx1x2a0b0L①f(x2)≤f(x1)，取[a1=a0,b1=x1]x’1=x2

x’2=b1-(b1-a1)

a1b1x’1x’2②f(x2)＞f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)

x’2=x1

a1b1x’1x’2计算n个点后，总缩短率为En=n-1＜，可得试点数n。第九页，共三十六页。3、计算步骤：求函数f(x)的极值点

第一步：取初始区间[a0,b0]x1x2a0b0⑴若求f(x)的极小值点，则①f(x2)≤f(x1)，取[a1=a0,b1=x1]x’1=x2

x’2=b1-(b1-a1)②f(x2)＞f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)

x’2=x1

a1b1x’1x’2a1b1x’1x’2⑵若求f(x)的极大值点，则①f(x2)≥f(x1)，取[a1=a0,b1=x1]x’1=x2

x’2=b1-(b1-a1)②f(x2)＜f(x1)，取[a1=x2,b1=b0]x’1=a1+(b1-a1)

x’2=x1

第二步：求区间的缩短率第十页，共三十六页。例求解f(x)=-18x2+72x+28的极大值点，≤0.1，起始搜索区间为[0,3]解：①用间接法：令f’(x)=-36x+72=0，得驻点x=2

又因为f’’(x)=-36＜0，故x=2为f(x)的极大值点，fmax=100②用直接法中的黄金分割法：令n-1=，得n=1+(lg)/(lg)≈5.78442

约6步即可，计算结果见下表：kakbkf(ak)f(bk)pk=

bk-akpk/p0x1k=ak+·pkx2k=bk-·pkf(x2k)△f(x1k)0032882311.8541.14686.9＜99.62f(x)xo3x1x211.146386.9821.8540.6182.2921.85499.62＞98.4621.1462.29286.998.461.1460.3821.8541.58496.89＜99.6231.5842.29296.8998.460.7080.2362.0221.85499.62＜99.9941.8542.29299.6298.460.4380.1462.1252.02299.99＞98.7251.8542.12599.6299.720.2710.0903第十一页，共三十六页。9.3无约束条件下多变量函数寻优一、爬山法原理：通过点的直接移动，逐步改善目标函数取值，直至达到极值点为止。由以下二部分组成：①选定搜索方向；②在选定的方向上爬山搜索。二、变量轮换法(或降维法):选择与坐标轴平行的方向为搜索方向设S=f(X)=f(x1,x2,…,xn)，极值点存在的区间为

x1*[a1,b1]，x2*[a2,b2]，…

，xn*[an,bn]1、原理：①从起点X(0)出发，沿平行于x1

轴的方向P(1)进行一维搜索，求得f(X)在该方向P(1)上近似极值点X(1)；②从点X(1)出发，沿平行于x2

轴的方向P(2)进行一维搜索，求得f(X)在该方向P(2)上近似极值点X(2)；③从点X(2)出发，照此交替进行下去，直至满足给定的精度为止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜

第十二页，共三十六页。2、算法步骤：设S=f(X)=f(x1,x2)，极值点存在的区间为x1*[a1,b1]，x2*[a2,b2]

第一步：从X(0)=(x1(0),x2(0))T出发①先固定x1=x1(0):求以x2为单变量的目标函数的极值点，得X(1)=(x1(0),x2(1))T

，S(1)=f(X(1))②再固定x2=x2(1):求以x1为单变量的目标函数的极值点，得X(2)=(x1(2),x2(1))T

，S(2)=f(X(2))

此时S(2)优于S(1)，且搜索区间缩短为x1*[x1(2),b1]，x2*[x2(1),b2]

第二步：如此交替搜索，直至满足给定精度为止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜ox1X(0)X(1)X(2)X(3)X(4)x2第十三页，共三十六页。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点，=0.01解：设起始点X(0)=(0,0)T，用变量轮换法计算：①先固定x1=x1(0)=0:则f(0,x2)=x22-4x2+60，寻优得x2(1)=2

于是X(1)=(x1(0),x2(1))T=(0,2)T

，S(1)=f(X(1))=56②再固定x2=x2(1)=2:则f(x1,2)=x12-12x1+56，寻优得x1(2)=6

于是X(2)=(x1(2),x2(1))T=(6,2)T

，S(2)=f(X(2))=20

如此交替搜索，直至满足给定精度=0.01为止

|f(X(k))

-f(X(k-1))|＜0.01或

|S(k)-S(k-1)|＜0.01

最后得极小点X*=(8,6)T，f(X*)=8ox1X(0)X(1)X(2)X(3)X(4)x2计算结果见下表：第十四页，共三十六页。k固定的xi单变量的目标函数f(xj)求得极点xj目标值S(k)|S(k)-S(k-1)|12345678x1=x1(0)=0x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.88x2=x2(7)=5.94f(0,x2)=x22-4x2+60f(x1,2)=x12-12x1+56f(6,x2)=x22-10x2+36f(x1,5)=x12-15x1+65f(7.5,x2)=x22–11.5x2+41.25f(x1,5.75)=x12–15.75x1+70.06f(7.88,x2)=x22–11.88x2+43.27f(x1,5.94)=x12–15.94x1+71.50x2=x2(1)=2x1=x1(2)=6x2=x2(3)=5x1=x1(4)=7.5x2=x2(5)=5.75x1=x1(6)=7.875x2=x2(7)=5.94x1=x1(8)=7.975620118.758.18758.04698.01178.00293692.250.56250.14060.03520.0088ox1X(0)X(1)X(2)X(3)X(4)x2缺点：①很大程度上取决于目标函数性质。目标函数等高线的性质很重要。②道路迂回曲折，多次变换方向，在极点附近，目标值改进更小，收敛速度慢。故不是一个有利方向。第十五页，共三十六页。三、一阶梯度法(最速下降或上升法):选择负梯度方向为搜索方向设求S=f(X)=f(x1,x2,…,xn)的极值点。

1、原理：①从起点X(0)出发，沿某个有利方向P(0)进行一维搜索，求得f(X)在P(0)方向近似极小点X(1)；②从点X(1)出发，沿某个新有利方向P(1)进行一维搜索，求得f(X)在P(1)方向近似极小点X(2)；③从点X(2)出发，照此进行下去，直至满足给定的精度为止

|f(X(k))

-f(X(k-1))|＜或

|S(k)-S(k-1)|＜

2、算法步骤：设求S=f(X)=f(x1,x2)的极值点。第一步：从给定起点X(0)

出发

第二步：从点X(1)出发，照此进行下去，直至满足给定的精度为止

|f(X(k+1))

-f(X(k))|＜或

||G(k)||＜第十六页，共三十六页。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点，=0.1解:①②从点X(1)出发，照此进行下去，直至满足给定的精度=0.1为止

|f(X(k+1))

-f(X(k))|＜0.1或

||G(k)||＜0.1

第十七页，共三十六页。计算结果见下表：缺点：①搜索效果比变量轮换法快，但愈接近极值点，步长愈小，目标值改进愈小。当遇到强交互作用时，不是有效的方法;

当遇到山脊时，会慢慢爬行。②在远离极点时，收敛速度较快;

在极点附近，收敛速度不快。k01234507.636.817.957.827.9903.055.115.565.875.93-102.21-1.490.33-0.220.05-4-5.53-0.60-0.82-0.09-0.1210.775.591.600.890.240.13-0.930.37-0.930.37-0.930.37-0.37-0.93-0.37-0.93-0.37-0.9288.222.211.220.330.180.056015.749.158.178.038.003744.266.590.980.140.026ox1x(0)x(1)x(2)X(3)x2第十八页，共三十六页。四、共轭梯度法:选择共轭方向为搜索方向㈠问题的提出：在极值点附近，如何加快收敛速度，须对函数在极值点附近的性质进行研究。

设有n维目标函数S=f(X)=f(x1,x2,…,xn),在极值点X*附近展开成泰勒级数：

特别：对二元二次函数，可证明：在极值点附近，其等高线可近似视为同心椭园族，而同心椭园族的任意两根平行切线的切点连线必通过椭园中心。

ox1X(0)P(0)X’(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)与P(0)共轭故：在极值点附近，沿搜索方向P(0)上巳得到一个切点X(1)，则只要得出通过极值点的连线方向

P(1),在此方向上寻优,可一步直达极值点。而这个连线方向P(1)是上一次搜索方向P(0)的共轭方向。第十九页，共三十六页。㈡共轭方向的定义：

1、定义：设X,Y是n维向量空间En中两个向量，A为n×n对称正定矩阵，若XTAY=0，则称向量X与Y对于矩阵A共轭。特例：若A=I，得XTY=0，则称向量X与Y正交。

2、几何意义：共轭方向是通过极值点的方向。㈢寻优原理：设n元函数S=f(X)=f(x1,x2,…,xn),在极值点X*附近可用一个二次函数逼近其中H为n×n对称正定矩阵第二十页，共三十六页。特别：对二元二次函数S=f(X)=f(x1，x2)①从某点X(0)出发,以P(0)方向搜索,使f(X)达到极小值点X(1),

则:X(1)必为该点处等高线的切点,P(0)为切线方向，且点X(1)的梯度方向f(X(1))为该等高线的法线方向，这两个方向正交。②从另一点X’(0)出发,仍以P(0)方向搜索,使f(X)达到另一个极小值点X(2),

则:X(2)也必为该点处等高线的切点,P(0)为切线方向，且点X(2)的梯度方向f(X(2))为该等高线的法线方向，这两个方向正交。ox1X(0)P(0)X’(0)X(2)X(1)x2P(0)P(1)=X(2)-X(1)P(1)与P(0)共轭故:对二元二次函数,只须搜索两个方向P(0)和P(1)就可达到极值点X*。一般:对n元二次函数,可用不超过n次搜索就可达到极值点X*。而n元非二次函数在极值点附近可用二次函数逼近。第二十一页，共三十六页。㈣寻优步骤：例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点。解①ox1X(0)P(0)X(1)x2第二十二页，共三十六页。②即ox1X(0)P(0)X(1)x2P(1)与P(0)共轭X(2)对二元二次函数,只须两次搜索就可达到极值点X*,一般:对n元二次函数,可用不超过n次搜索就可达到极值点X*。而n元非二次函数在极值点附近可用二次函数逼近。第二十三页，共三十六页。㈤适用于一般目标函数的共轭梯度法：

1、共轭方向的计算问题：须用到目标函数的海赛矩阵H(二阶偏导数矩阵)，若目标函数为二次函数时，H容易求出；若目标函数为高次或高维函数时，H难以求出，此时共轭方向难以求出。

2、共轭方向的计算方法：F-R法，由Fletcher和Reeves提出，可避免海赛矩阵H的计算，方便地确定共轭方向，简单有效。第二十四页，共三十六页。

3、搜索过程：①从X(0)出发：②从X(1)出发：第二十五页，共三十六页。③从X(2)出发：4、搜索方法:①若目标函数为n元二次函数，则理论上最多经n次迭代可达极小点，实际由于舍入误差，须n次以上的迭代。②若目标函数为n元非二次函数，但共轭方向只有n个，迭代n次以后应重新开始迭代，减少误差积累。一般，在开始阶段(二次型较弱)用一阶梯度法，接近极点(二次型较强)

用共轭梯度法。

一般有：第二十六页，共三十六页。例求S=f(x)=x12+x22-x1x2-10x1-4x2+60的极小值点。解:①②第二十七页，共三十六页。9.4有约束条件下多变量函数寻优一、具有等式约束的极值问题：

1、消元法：n元非线性规划

S=f(X)=f(x1,x2,…,xn)s.t.gk(X)=0,k=1,2,…,m,m<n

若可从m个s.t.中解出m个变量xi=h(xm+1,xm+2,…,xm),i=1,2,…,m,

代入目标函数中消去m个变量，则问题变为一个求n-m个变量函数的无约束条件的极值问题。例：求解Mins.t.第二十八页，共三十六页。

2、拉格朗日(Lagrangian)乘子法：n元非线性规划

S=f(X)=f(x1,x2,…,xn)s.t.gk(X)=0,k=1,2,…,m

例：求解Mins.t.则L(X,)有极值的必要条件为：

求出的解就是f(X)的驻点。

令

第二十九页，共三十六页。

其中，拉格朗日乘子k的经济意义：

影子价格---单位资源的目标增量

S=f(X)=f(x1,x2,…,xn)s.t.gk(X)=bk,k=1,2,…,m

知k是约束式gk每变化一个单位,引起目标f值的变化率。

⑴若目标f为效用函数极大化，b为预算约束，