西北农林科技大学运筹学课件非线性规划教程文件

1、第六章西北农林科技大学运筹学课件非线性规划第六章一、基本概念一、基本概念2二维问题的图解000505) 1()2()(min212122212221xxxxxxxxxxf考虑非线性规划问题BACD05x1x2第六章一、基本概念一、基本概念3几个定义)()(,)()(,),(*21XfXfXXXXXfXfXXxxxXn定义1 局部极小值(严格局部极小值)定义1 全局极小值(严格全局极小值)()(,)()(,),(*21XfXfRXXXXfXfRXxxxXn第六章一、基本概念一、基本概念4多元函数极值点存在的条件0)(,)(,)()(*2*1*Tnxxfxxfxxfxf 1)必要条件 梯度2)充分

2、条件 海赛矩阵严格局部极小点正定且*2*22*21*21*221*212*2*2*)()()()()()()(, 0)(xxxfxxxfxxxfxxxfxxxfxxfxfxfnnnn 函数在函数在某点的梯度，垂直于过该点的等值面的切平面。某点的梯度，垂直于过该点的等值面的切平面。 梯度方向是函数值增加最快的方向。梯度方向是函数值增加最快的方向。 满足梯度为零的点称为驻点。满足梯度为零的点称为驻点。l若海赛矩阵是正定的，则驻点是极小点；若海赛矩阵是正定的，则驻点是极小点；l若海赛矩阵是负定的，则驻点是极大点；若海赛矩阵是负定的，则驻点是极大点；l若海赛矩阵是不定的，则驻点不是极值点；若海赛矩阵是

3、不定的，则驻点不是极值点；l若海赛矩阵是半定的，须视高阶导数的性质而定若海赛矩阵是半定的，须视高阶导数的性质而定 。第六章1223231423131)(minxxxxXf04)(211xxXf04)(2222xxxXf0)(Xf令42024202例 利用极值条件求解下列问题：解：4-004驻点处的海赛矩阵：一、基本概念一、基本概念4004400442002)(212xxXf4004极小点极小点极大点极大点不定不定不定不定第六章一、基本概念一、基本概念)(min)()()()()(kkkkkdXfdXf)()()1(kkkkdXX5下降迭代算法l 选取某一初始点X(1),令k=0l 确定一个有利

4、搜索方向d(k)l 确定最优步长K，得一新点X(k+1)l 检验X(k+1) 是否为极小点，若是，停止计算。否则令kk1返回第2步继续迭代。)()()1()()1(kkkkkXXXXX )1(kf)()1()()1()(kkkkkfffff第六章二、一维搜索二、一维搜索x xy ya ab bb b1 1a a1 10 0XXxyabb1a10X 一维搜索方法的斐波那契法与黄金分割法的寻优途径不是直接找出最优点，而是不断缩小最优点所处区域，直到符合精度为止。这两种方法的主要特点为：适于单峰（谷）函数；压缩峰（谷）点所处的区域第六章二、一维搜索二、一维搜索10.618法(黄金分割法) 在区间a1

5、,b1上选取t1和t1 计算f(t1),f(t1)比较函数值的大小，缩短区间。 置换区间端点。 判断精度（bk+1-ak+1)/(b1-a1)0，k=1 确定有利得搜索方向d(k)为X(k)点的负梯度方向 判断精度 确定最优步长 求出新点.令kk1返回第2步)()()()()(0)()()()(-(min)()()()()()()()()()()()()()1(kkTkkTkkkkkkkkkkxfxHxfxfxfxfxfxfxfxfxfxf)()()(kkxfd22221)()()()()()()()(nkkkxxfxxfxxfxfxfdkkk)()()()1(kkkkxfxx三、无约束极值问

6、题三、无约束极值问题1梯度法（最速下降法）第六章1111001022)()()()(1100)(11)(221241)()()()0 , 0(22)(min)1(1)1()2(111)1()1()1()1()1()1()1(212121)1(22212121dXXdXfXfdXXfdXfxxxxxXfxXfXfXxxxxxxXfT例例 给定初始条件，求下列问题的最小值。给定初始条件，求下列问题的最小值。解：解：三、无约束极值问题三、无约束极值问题第六章2828.0)(2 .02 .0)(2 .18 .05/10210)()()()(111111)(11)()3()3()2(2)2()3(122

7、)2()2()2()2()2()2()2(XfXfdXXdXfXfdXXfdXf三、无约束极值问题三、无约束极值问题第六章 给定初始点X(1)，允许误差0，k=1 确定搜索方向d(k)： 判断精度 确定最优步长 求出新点.令kk1返回第2步0)()()(d()(min)()()()()()()()()1(kkkkkkkkXfXfXdXfXdXfXf)()()(1)()(kkkxfxHd)(kd)()()()1(kkkkxdXX三、无约束极值问题三、无约束极值问题2牛顿法第六章2224)(11(2224)(221241)()()()0 , 0(22)(min11)1(212121)1(22212

8、121）（）（）：XHXfXXHxxxxxXfxXfXfXxxxxxxXfT112224)()(1)1(1)1()1(（XfXHd三、无约束极值问题三、无约束极值问题例例 给定初始点求下列函数极值给定初始点求下列函数极值第六章 2/312/3100102525)()()()(2/32/31002/31)1(1)1()2(111)1()1()1()1()1(dXXdXfXfdXd三、无约束极值问题三、无约束极值问题第六章), 2 , 1(0), 2 , 1(0)(0)()()(*1*1*ljljXgXgXhXfjjjljjjmiii 库恩塔克条件是确定能够非线性规划问题中某点为库恩塔克条件是确定

9、能够非线性规划问题中某点为最优点的一阶必要条件。但对于凸规划，库恩塔克条件最优点的一阶必要条件。但对于凸规划，库恩塔克条件是充要条件。是充要条件。 对非线性规划数学模型对非线性规划数学模型 minf(x) minf(x) H Hi i(X)= 0 (i=1,2,m)(X)= 0 (i=1,2,m) g gj j(X)0 (j=1,2,l)(X)0 (j=1,2,l) 若若X X* *是局部（或全局）极小点，则一定存在向量是局部（或全局）极小点，则一定存在向量* *=(=(1 1* *，2 2* *，m m* *) )T T 及及* *=(=(1 1* *， 2 2* *， l l* *) )T

10、 T，使，使得下述条件成立：得下述条件成立：四、约束极值问题四、约束极值问题1库恩库恩塔克条件塔克条件第六章求下列非线性规划问题的库恩塔克点0-3-60-510-10-22)(min21222121222121xxxxxxxxxxXf解：设K-T点为X*21*122)(xxXg10221024)(2121*xxxxXf13)(*2Xg四、约束极值问题四、约束极值问题第六章NoImage000)36(0)5(021022032102421212222112212121121xxxxxxxxxx故根据故根据K-TK-T点有点有，舍去。得到的解不满足条件不是可行点。点。是可行点。点不是可行点。代入原

11、问题约束中，该0, 00, 0)4(0,520)3(0, 1, 2, 10)2(, 5, 00) 1 (2121221212122121TKxxxxK-TK-T点的分析：点的分析：四、约束极值问题四、约束极值问题第六章lijkklijkkXgrXfrXpXgrXfrXp11)(lg()(),()(1)(),( 通过构造罚函数把约束问题转化为一系列的无约束问题，进而用无约束最优化方法求解。外点法 构造罚函数构造罚函数), 2 , 1(0)(), 2 , 1(0)()(minljXgmiXhXfji四、约束极值问题四、约束极值问题1罚函数法（外点法）第六章 算法步骤 给定初始点x(0),初始罚因子

12、M10，放大系数C1,允许误差0,令k=1 求解罚函数p(X,Mk)的无约束极小 以X(k-1)为始点，求解min p(X,Mk),得其极小点X(k) 判断精度 在X(k)点，若罚项0，允许误差0,令k=1 求解罚函数p(X,rk)的无约束极小 以X(k-1)为始点，求解min p(X,rk),得其极小点X(k) 判断精度 在X(k)点，若罚项,停止计算。否则，令rk+1=Crk,k=k+1四、约束极值问题四、约束极值问题第六章例例 用内点法求解非线性规划用内点法求解非线性规划0210200)()(2)(11211221221221212212212112211xrxrrxrxrxxrxxrx

13、xxpxxxxxrxrxxxxpkkkkkkkkk0110121)ln()ln(),()(,)()(min221212211112212112221121xxrxpxrxxxrxpxxxrxxrXpxXgxxXgxxXfkkkkk四、约束极值问题四、约束极值问题第六章四、约束极值问题四、约束极值问题16)811(,481102,221211221kkkkkrrxrxrxxxxrKrkx1x2p(x)f(x)120.78078 2.6096 1.5470 3.3904 210.50000 1.2500 2.0377 1.7500 30.50.30902 0.5955 1.6765 0.9045 40.10.08