非线性规划 (2)课件.ppt

第六章关于非线性规划(2)第1页，此课件共41页哦第六章一、基本概念一、基本概念一般形式1非线性规划的数学模型第2页，此课件共41页哦第六章一、基本概念一、基本概念2二维问题的图解考虑非线性规划问题BACD05x1x2第3页，此课件共41页哦第六章一、基本概念一、基本概念3几个定义定义1 局部极小值(严格局部极小值)定义2 全局极小值(严格全局极小值)第4页，此课件共41页哦第六章一、基本概念一、基本概念4多元函数极值点存在的条件 1)必要条件 梯度函数在函数在某点的梯度，垂直于过该点的等值面的切平面。某点的梯度，垂直于过该点的等值面的切平面。梯度方向是函数值增加最快的方向。梯度方向是函数值增加最快的方向。满足梯度为零的点称为驻点。满足梯度为零的点称为驻点。第5页，此课件共41页哦第六章一、基本概念一、基本概念4多元函数极值点存在的条件2)充分条件 海赛矩阵l若若A A为实数，则为实二次型；为实数，则为实二次型；l若若X0X0，实二次型总为正（负），则称正（负）定；，实二次型总为正（负），则称正（负）定；l不定不定l半正（负）定。半正（负）定。lAA正、负、不定、半正、半负定正、负、不定、半正、半负定二次型二次型第6页，此课件共41页哦第六章一、基本概念一、基本概念4多元函数极值点存在的条件2)充分条件 海赛矩阵l若海赛矩阵是正定的，则驻点是极小点；若海赛矩阵是正定的，则驻点是极小点；l若海赛矩阵是负定的，则驻点是极大点；若海赛矩阵是负定的，则驻点是极大点；l若海赛矩阵是不定的，则驻点不是极值点；若海赛矩阵是不定的，则驻点不是极值点；l若海赛矩阵是半定的，须视高阶导数的性质而定若海赛矩阵是半定的，须视高阶导数的性质而定 。第7页，此课件共41页哦第六章例 利用极值条件求解下列问题：解：驻点处的海赛矩阵：一、基本概念一、基本概念极小点极小点极大点极大点不定不定不定不定第8页，此课件共41页哦第六章一、基本概念一、基本概念5下降迭代算法l选取某一初始点X(1),令k=0l确定一个有利搜索方向d(k)l确定最优步长K，得一新点X(k+1)l检验X(k+1)是否为极小点，若是，停止计算。否则令kk1返回第2步继续迭代。第9页，此课件共41页哦第六章二、一维搜索二、一维搜索x xy ya ab bb b1 1a a1 10 0XXxyabb1a10X 一维搜索方法的斐波那契法与黄金分割法的寻优途径不是直接找出最优点，而是不断缩小最优点所处区域，直到符合精度为止。这两种方法的主要特点为：适于单峰（谷）函数；压缩峰（谷）点所处的区域第10页，此课件共41页哦第六章二、一维搜索二、一维搜索x xy ya ab bb b1 1a a1 10 0XXxyabb1a10X第11页，此课件共41页哦第六章二、一维搜索二、一维搜索10.618法(黄金分割法)在区间a,b上选取a1和b1计算f(a1),f(b1)比较函数值的大小，缩短区间。置换区间端点。判断精度（bk-ak)/(b-a)=0.618K0，k=0确定有利得搜索方向d(k)为X(k)点的负梯度方向判断精度确定最优步长求出新点.令kk1返回第2步三、无约束极值问题三、无约束极值问题第17页，此课件共41页哦第六章例例 给定初始条件，求下列问题的最小值。给定初始条件，求下列问题的最小值。解：解：三、无约束极值问题三、无约束极值问题第18页，此课件共41页哦第六章三、无约束极值问题三、无约束极值问题第19页，此课件共41页哦第六章给定初始点X(1)，允许误差0，k=1确定搜索方向d(k)：判断精度确定最优步长求出新点.令kk1返回第2步三、无约束极值问题三、无约束极值问题2牛顿法第20页，此课件共41页哦第六章三、无约束极值问题三、无约束极值问题例例 给定初始点求下列函数极值给定初始点求下列函数极值第21页，此课件共41页哦第六章三、无约束极值问题三、无约束极值问题第22页，此课件共41页哦第六章四、约束极值问题四、约束极值问题1.起作用约束起作用约束2.可行方向可行方向3.下降方向下降方向4.可行下降方向可行下降方向第23页，此课件共41页哦第六章 库恩塔克条件是确定能够非线性规划问题中某点为最优点的库恩塔克条件是确定能够非线性规划问题中某点为最优点的一阶必要条件。但对于凸规划，库恩塔克条件是充要条件。一阶必要条件。但对于凸规划，库恩塔克条件是充要条件。对非线性规划数学模型对非线性规划数学模型 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 T，使得下述条件成立：，使得下述条件成立：四、约束极值问题四、约束极值问题5库恩库恩塔克条件塔克条件第24页，此课件共41页哦第六章求下列非线性规划问题的库恩塔克点解：设K-T点为X*四、约束极值问题四、约束极值问题第25页，此课件共41页哦第六章故根据故根据K-TK-T点有点有K-TK-T点的分析：点的分析：四、约束极值问题四、约束极值问题第26页，此课件共41页哦第六章 通过构造罚函数把约束问题转化为一系列的无约束问题，进而用无约束最优化方法求解。外点法构造罚函数构造罚函数四、约束极值问题四、约束极值问题6罚函数法（外点法）第27页，此课件共41页哦第六章算法步骤给定初始点x(0),初始罚因子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四、约束极值问题四、约束极值问题第32页，此课件共41页哦第六章例例 用内点法求解非线性规划用内点法求解非线性规划四、约束极值问题四、约束极值问题第33页，此课件共41页哦第六章四、约束极值问题四、约束极值问题Krkx1x2p(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.08541 0.1073 0.6554 0.1927 50.010.00981 0.0101 0.1120 0.0199 60.0010.00100 0.0010 0.0158 0.0020 70.00010.00010 0.0001 0.0020 0.0002 第34页，此课件共41页哦第六章 将非线性规划问题中的目标函数合约束条件近似为线性规划，将非线性规划问题中的目标函数合约束条件近似为线性规划，并对变量的取值范围加以限制，从而得到一近似线性规划，再用单并对变量的取值范围加以限制，从而得到一近似线性规划，再用单纯形求解之，把符合原始约束的最优解作为原非线性规划的解的近纯形求解之，把符合原始约束的最优解作为原非线性规划的解的近似。似。非线性规划模型非线性规划模型3.近似规划近似规划近似规划的基本思想近似规划的基本思想四、约束极值问题四、约束极值问题第35页，此课件共41页哦第六章给定初始可行点X(k)，步长限制j(1)，步长缩小系数，允许误差，令k=1在X(k)处，将f(X)、hi(X)、gj(X)一阶泰勒展开增加步长限制条件，求解近似线性规划问题检验问题的解是否满足原来的约束判断精度近似规划原理与算法步骤近似规划原理与算法步骤四、约束极值问题四、约束极值问题第36页，此课件共41页哦第六章用近似规划法求解下列问题用近似规划法求解下列问题近似规划法计算举例近似规划法计算举例四、约束极值问题四、约束极值问题第37页，此课件共41页哦第六章近似规划法计算举例近似规划法计算举例解：在解：在X X(1)(1)处将函数线性化处将函数线性化四、约束极值问题四、约束极值问题第38页，此课件共41页哦第六章步长限制步长限制近似线性规划问题近似线性规划问题单纯形法求解线性规划问题单纯形法求解线性规划问题经检验，该解不满足原来约束经检验，该解不满足原来约束四、约束极值问题四、约束极值问题第39页，此课件共41页哦第六章经检验该点是原问题的最小点经检验该点是原问题的最小点近似规划法计算举例近似规划法计算举例减少步长限制，减少步长限制，=0.5新的线性规划问题新的线性规划问题第二次迭代：第二次迭代：单纯形法求解线性规划问题单纯形法求解线性规划问题四、约束极值问题四、约束极值问题第40页，此课件共41页哦第六章感谢大家观看第41页，此课件共41页哦