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

非线性规划第1页，本讲稿共70页1.非线性规划模型：非线性规划模型：数学规划模型的一般形式：数学规划模型的一般形式：其中其中,x=(x1,x2,xn)T，f(x),gi(x),hj(x)为为x的实值函数的实值函数简记为简记为MP(Mathematical Programming)退 出前一页后一页2.1 基本概念基本概念第2页，本讲稿共70页可行域和可行解：可行域和可行解：称称为为MP问题的约束集或可行域。问题的约束集或可行域。若若x在在X内，称内，称x为为MP的可行解或者可行点。的可行解或者可行点。退 出前一页后一页第3页，本讲稿共70页简记形式：简记形式：引入向量函数符号：引入向量函数符号：退 出前一页后一页第4页，本讲稿共70页数学规划问题的分类：数学规划问题的分类：若若f(x),gi(x),hj(x)为线性函数，即为为线性函数，即为线性规划线性规划(LP)；若若f(x),gi(x),hj(x)至少一个为非线性，即为至少一个为非线性，即为非线性规划非线性规划(NLP)；对于非线性规划，对于非线性规划，若没有若没有gi(x),hj(x)即即X=Rn,称为称为无约束非线性无约束非线性规划规划或或无约束最优化问题无约束最优化问题；否则称为；否则称为约束非线性规划或约束最优约束非线性规划或约束最优化问题化问题。退 出前一页后一页第5页，本讲稿共70页最优解和极小点最优解和极小点 对于数学规划（对于数学规划（MP），若），若 ，并且有，并且有如果有如果有定义定义:退 出前一页后一页第6页，本讲稿共70页如果有如果有定义定义退 出前一页后一页第7页，本讲稿共70页例例退 出前一页后一页第8页，本讲稿共70页三角形表示的是可行域。三角形表示的是可行域。同心圆表示的是目标函数的等值线。同心圆表示的是目标函数的等值线。最优解为（最优解为（1/2，1/2）最优值为最优值为1/2问题：问题：(1/2,1/2)是整体的还是局部的？是严格的还是非是整体的还是局部的？是严格的还是非严格的？严格的？1/21/2退 出前一页后一页第9页，本讲稿共70页2.非线性规划方法概述非线性规划方法概述微分学方法的局限性：微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处实际的问题可能含有不等式约束，微分学方法不易处理。理。退 出前一页后一页第10页，本讲稿共70页数值方法的基本思路：数值方法的基本思路：迭代迭代给定初始点给定初始点x0根据根据x0,依次迭代产生点列依次迭代产生点列xkxk的最后一点为最优解的最后一点为最优解xk有限有限xk无限无限xk收敛于最优解收敛于最优解退 出前一页后一页第11页，本讲稿共70页迭代格式迭代格式xkxk+1pk称称pk为第为第k轮轮搜索方向搜索方向，tk为第为第k轮沿轮沿pk方向的方向的步长步长。产生产生tk和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。退 出前一页后一页第12页，本讲稿共70页定义：下降方向定义：下降方向退 出前一页后一页第13页，本讲稿共70页定义定义解非线性规划问题，关键在于找到某解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数个方向，使得在此方向上，目标函数得到下降，同时还是可行方向。得到下降，同时还是可行方向。这样的方向称为这样的方向称为可行下降方向。可行下降方向。退 出前一页后一页第14页，本讲稿共70页1.凸函数及其性质：凸函数及其性质：定义定义退 出前一页后一页2.2 凸函数和凸规划凸函数和凸规划第15页，本讲稿共70页退 出前一页后一页第16页，本讲稿共70页定理定理:关于凸函数的一些结论关于凸函数的一些结论定理定理:是凸集。是凸集。函数函数f在集合在集合S上关于上关于c的水平集的水平集退 出前一页后一页第17页，本讲稿共70页定理定理?还有什么方法判断一个函数是凸函数呢？还有什么方法判断一个函数是凸函数呢？退 出前一页后一页第18页，本讲稿共70页退 出前一页后一页第19页，本讲稿共70页2.凸规划及其性质：凸规划及其性质：凸规划定义：凸规划定义：退 出前一页后一页第20页，本讲稿共70页凸规划性质：凸规划性质：凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非线性规划凸规划是以后重点讨论的一类非线性规划凸函数凸函数线线性性函函数数退 出前一页后一页第21页，本讲稿共70页解：解：（1）目标函数是不是凸函数？）目标函数是不是凸函数？（2）gi(x)是不是凸函数？是不是凸函数？退 出前一页后一页第22页，本讲稿共70页t为实数为实数一维搜索问题指目标函数为单变量的非线性规划问题。又称线性一维搜索问题指目标函数为单变量的非线性规划问题。又称线性搜索问题。其模型为：搜索问题。其模型为：什么叫一维搜索问题？什么叫一维搜索问题？或或一般一维搜索问题一般一维搜索问题有效一维搜索问题有效一维搜索问题退 出前一页后一页2.3一维搜索方法一维搜索方法第23页，本讲稿共70页一维搜索问题的算法分类：一维搜索问题的算法分类：精确一维搜索（最优一维搜索）精确一维搜索（最优一维搜索）非精确一维搜索（可接受一维搜索）非精确一维搜索（可接受一维搜索）本节内容：本节内容：两种精确一维搜索方法：两种精确一维搜索方法：0.618法，法，Newton法。法。两种非精确一维搜索方法：两种非精确一维搜索方法：Goldstein法法,Armijo法。法。退 出前一页后一页第24页，本讲稿共70页1.0.618法（近似黄金分割法）法（近似黄金分割法）问题：问题：凸函数是不是单谷函数？严格凸函数是不是单谷函凸函数是不是单谷函数？严格凸函数是不是单谷函数？单谷函数是不是凸函数？数？单谷函数是不是凸函数？单谷函数单谷函数退 出前一页后一页第25页，本讲稿共70页搜索法求解：搜索法求解：或或基本过程：基本过程：给出给出a,b,使得使得t*在在a,b中。中。a,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,b的长度。的长度。当当a,b的长度小于某个预设的值，或者导数的绝对的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。值小于某个预设的正数，则迭代终止。退 出前一页后一页第26页，本讲稿共70页假定：已经确定了单谷区间假定：已经确定了单谷区间a,bt1t2ababt1t2新搜索区间为新搜索区间为a,t2新搜索区间为新搜索区间为t1,b退 出前一页后一页第27页，本讲稿共70页区间缩小比例的确定：区间缩小比例的确定：区间缩短比例为区间缩短比例为(t2-a)/(b-a)缩短比例为缩短比例为(b-t1)/(b-a)缩短比例缩短比例 满足：满足：每次插入搜索点使得两个区间每次插入搜索点使得两个区间a,t2和和t1,b相等；相等；每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。0.618法法t1t2ababt1t2退 出前一页后一页第28页，本讲稿共70页确定确定a,b,计算探索点计算探索点t1=a+0.382(b-a)t2=a+0.618(b-a)0.618法解题步骤：法解题步骤：是是否否是是停止，输出停止，输出t1否否以以a,t2为新的搜索区间为新的搜索区间是是停止，输出停止，输出t2否否以以t1,b为新的搜索区间为新的搜索区间退 出前一页后一页第29页，本讲稿共70页例：例：解：解：t1t230t1.第一轮：第一轮：t1=1.146,t2=1.854t200.5退 出前一页后一页第30页，本讲稿共70页2.第二轮：第二轮：t2=1.146,t1=0.708t20=1.1460.53.第三轮：第三轮：t1=0.438,t2=0.708b-t1=1.146-0.4380.51.8540tt2t11.4160tt2t1退 出前一页后一页第31页，本讲稿共70页4.第四轮：第四轮：t2=0.876,t1=0.708b-t1=1.146-0.7080.5输出：输出：t*=t2=0.876为最优解，最优值为为最优解，最优值为-0.0798课下练习：参阅课下练习：参阅110页表格仔细分析上述迭代过程，体会页表格仔细分析上述迭代过程，体会0.618法法的实质。的实质。01.416tt1t2退 出前一页后一页第32页，本讲稿共70页2.Newton法法Newton法基本思想：法基本思想：用探索点用探索点tk处的二阶处的二阶Taylor展开式近似代替目标函展开式近似代替目标函数，以展开式的最小点为新的探索点。数，以展开式的最小点为新的探索点。退 出前一页后一页第33页，本讲稿共70页解题步骤：解题步骤：给定初始点给定初始点t1和精度和精度是是是是停止，输出停止，输出t1是是否否停止，解题失败停止，解题失败否否停止，输出停止，输出t2否否退 出前一页后一页第34页，本讲稿共70页例：例：解：解：取取t1=1,计算：计算：迭代过程如下表：迭代过程如下表：1.1370.11630.11693-0.00106141.3258-0.5178-0.5708220.785411退 出前一页后一页第35页，本讲稿共70页3.非精确一维搜索法非精确一维搜索法数值方法的关键是从一个点迭代到下一个点。数值方法的关键是从一个点迭代到下一个点。确定下一个点的关键是确定搜索方向和步长确定下一个点的关键是确定搜索方向和步长如果已经确定了搜索方向如果已经确定了搜索方向pk,则只要确定一个最佳的步长则只要确定一个最佳的步长即可。即可。所谓的最佳步长即是在所谓的最佳步长即是在pk方向上走一个最好的长度使方向上走一个最好的长度使得目标函数下降的最多，即下述的最优化问题：得目标函数下降的最多，即下述的最优化问题：这样的最优化问题不需要太高的精度，只要满足某些这样的最优化问题不需要太高的精度，只要满足某些更宽松的精度要求即可。更宽松的精度要求即可。这样的搜索方法称之为这样的搜索方法称之为非精确一维搜索方法非精确一维搜索方法退 出前一页后一页第36页，本讲稿共70页Goldstein法原理：法原理：yt0bcdaY=(0)+(0)tY=(0)+m2(0)tY=(0)+m1(0)t退 出前一页后一页第37页，本讲稿共70页是是Goldstein算法算法确定确定m1,m2,t0,a=0,b=+(t0)(0)+m1 (0)t0(t0)(0)+m2(0)t0是是停止停止,输出输出t0否否a=a,b=t0,t1=(a+b)/2否否a=t0,b=b,t1=(a+b)/2(若若b=+,则则t1=a)退 出前一页后一页第38页，本讲稿共70页Armijo法原理：法原理：yt0tkMtk退 出前一页后一页第39页，本讲稿共70页本节课讨论本节课讨论n元函数的无约束非线性规划问题：元函数的无约束非线性规划问题：求解此类模型求解此类模型(UMP)的方法称为的方法称为无约束最优化方法无约束最优化方法。无约束最优化方法通常有两类：无约束最优化方法通常有两类：解析法：解析法：要使用导数的方法；要使用导数的方法；直接法：直接法：无须考虑函数是否可导，直接使用函数值。无须考虑函数是否可导，直接使用函数值。退 出前一页后一页2.4无约束最优化方法无约束最优化方法第40页，本讲稿共70页本节课内容：本节课内容：无约束问题的最优性条件无约束问题的最优性条件最速下降法（一种解析法）最速下降法（一种解析法）退 出前一页后一页第41页，本讲稿共70页1.无约束问题的最优性条件无约束问题的最优性条件定理定理1定理定理2梯度为梯度为0的点称为函数的的点称为函数的驻点。驻点。驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极驻点可能是极小点，也可能是极大点，也可能即不是极大也不是极小，这时称为函数的小，这时称为函数的鞍点。鞍点。定理定理2说明：说明：UMP问题的局部最优解必是目标函数的驻点。问题的局部最优解必是目标函数的驻点。注：注：退 出前一页后一页第42页，本讲稿共70页定理定理3定理定理4退 出前一页后一页第43页，本讲稿共70页例例解：解：1.先求出目标函数的全部驻点；先求出目标函数的全部驻点；2.利用充分条件判断驻点是不是最优点。利用充分条件判断驻点是不是最优点。退 出前一页后一页第44页，本讲稿共70页关于梯度的复习：关于梯度的复习：梯度是一个向量。梯度是一个向量。n元函数元函数f(x1,x2,xn)在某点在某点x处的梯度为：处的梯度为：梯度的方向与函数梯度的方向与函数f的等值线的一个法线方向相同，从较低的等的等值线的一个法线方向相同，从较低的等值线指向较高的等值线。值线指向较高的等值线。梯度的方向就是函数梯度的方向就是函数f的值增加最快的方向，其相反方的值增加最快的方向，其相反方向就是函数值降低最快的方向。向就是函数值降低最快的方向。2.最速下降法最速下降法退 出前一页后一页第45页，本讲稿共70页最速下降法又称为最速下降法又称为梯度法梯度法，由，由Cauchy于于1847年给出。年给出。最速下降法解决的是最速下降法解决的是具有连续可微的目标函数具有连续可微的目标函数的的UMP问问题。题。最速下降法的基本思想：从当前点最速下降法的基本思想：从当前点xk出发寻找使得目标函出发寻找使得目标函数下降最快的方向，即数下降最快的方向，即负梯度方向负梯度方向。退 出前一页后一页第46页，本讲稿共70页最速下降法计算步骤：最速下降法计算步骤：选区初始点选区初始点x0和精度和精度计算计算是是否否停止，输出停止，输出x0求求p0=计算计算t0,使使计算计算x1=x0+t0 p0退 出前一页后一页第47页，本讲稿共70页例例解：解：退 出前一页后一页第48页，本讲稿共70页说明：说明：观察观察P119的图，可以发现的图，可以发现x1 x0垂直于目标函数的等值线垂直于目标函数的等值线（图中的虚线）在（图中的虚线）在x0的切线；的切线；最速下降方法相邻的两个搜索方向是相互垂直的，即最速下降方法相邻的两个搜索方向是相互垂直的，即x1 x0垂直垂直x1 x2；最速下降法解决最速下降法解决UMP的缺陷：迭代点越靠近最优解则的缺陷：迭代点越靠近最优解则目标函数下降的速度越慢；目标函数下降的速度越慢；优点：迭代点列总是收敛的，而且计算过程简单。优点：迭代点列总是收敛的，而且计算过程简单。退 出前一页后一页第49页，本讲稿共70页本节课讨论约束非线性规划问题本节课讨论约束非线性规划问题MP其中其中,x=(x1,x2,xn)T，f(x),gi(x),hj(x)为为x的实值函数的实值函数求解此类模型求解此类模型(MP)的方法称为的方法称为约束最优化方法约束最优化方法。退 出前一页后一页2.5约束最优化方法约束最优化方法第50页，本讲稿共70页本节课内容：本节课内容：约束问题的最优性条件约束问题的最优性条件惩罚函数法惩罚函数法退 出前一页后一页第51页，本讲稿共70页1.约束最优化问题的最优性条件约束最优化问题的最优性条件对于对于 MP问题：问题：退 出前一页后一页第52页，本讲稿共70页若若x*有变化，则约束条件可能没有破坏有变化，则约束条件可能没有破坏若若x*有变化，则约束条件一定被破坏有变化，则约束条件一定被破坏令令J表示表示MP的全部等式约束的下标集合，即的全部等式约束的下标集合，即J=1,2q,I表示表示MP的全部不等式约束的下标集合，即的全部不等式约束的下标集合，即I=1,2px*的积极约束的下标集合的积极约束的下标集合退 出前一页后一页第53页，本讲稿共70页定理定理1对于对于若若x*是局部最优解是局部最优解,则则退 出前一页后一页第54页，本讲稿共70页定理定理1的说明：的说明：2、称下述表达式为、称下述表达式为MP的的Kuhn-Tucker条件，简称条件，简称K-T条件条件满足满足K-T条件的点称为条件的点称为MP的的K-T点，定理点，定理1说明说明MP的局部最优解一定的局部最优解一定是是MP的的K-T点。点。为了求出为了求出MP的最优解，可以先找出的最优解，可以先找出MP的的K-T点，再做进一步点，再做进一步的判断。的判断。退 出前一页后一页第55页，本讲稿共70页3、定理、定理1的实例说明的实例说明定理定理1表明：若表明：若(x1,x2)T是局部最优解，是局部最优解，g1和和g2为积极约束，则：为积极约束，则：退 出前一页后一页第56页，本讲稿共70页4.定理定理1的特例的特例1退 出前一页后一页第57页，本讲稿共70页5.定理定理1的特例的特例2退 出前一页后一页第58页，本讲稿共70页6.定理定理1的改进：的改进：对于对于若若x*是局部最优解是局部最优解,则则互补松紧条件互补松紧条件退 出前一页后一页第59页，本讲稿共70页7.实例说明改实例说明改进后的定理进后的定理1：定理定理1改进后表明：若改进后表明：若(x1,x2)T是局部最优解，则：是局部最优解，则：退 出前一页后一页第60页，本讲稿共70页互补松紧条件互补松紧条件退 出前一页后一页第61页，本讲稿共70页定理定理2对于对于注：定理注：定理2表明，在凸性条件下，表明，在凸性条件下，K-T点是整体最优解。点是整体最优解。退 出前一页后一页第62页，本讲稿共70页例：例：写出写出K-T条件条件;求出相应的求出相应的K-T点点;判断判断K-T点是不是问点是不是问题的最优解题的最优解解：解：由于全部函数都是连续可微的，所以应用以下由于全部函数都是连续可微的，所以应用以下K-T条件条件退 出前一页后一页第63页，本讲稿共70页首先写出原首先写出原MP问题的问题的K-T条件：条件：根据定理根据定理1,K-T点还应该满足原问题的约束条件点还应该满足原问题的约束条件互补松紧条件互补松紧条件退 出前一页后一页第64页，本讲稿共70页利用互补松紧条件，可以求出利用互补松紧条件，可以求出K-T点：点：利用定理利用定理2，由于全部函数都连续可微，并且，由于全部函数都连续可微，并且f和和g都是凸函数，都是凸函数，h是线性函数，所以是线性函数，所以K-T点就是整体最优解。点就是整体最优解。退 出前一页后一页第65页，本讲稿共70页2.惩罚函数法惩罚函数法惩罚函数法的基本思想：利用原问题的中的约束函数惩罚函数法的基本思想：利用原问题的中的约束函数构造适当的惩罚函数，并和原问题的目标函数相加，得构造适当的惩罚函数，并和原问题的目标函数相加，得到带参数的增广目标函数，从而将原问题题转换为一系到带参数的增广目标函数，从而将原问题题转换为一系列无约束非线性规划问题。列无约束非线性规划问题。惩罚函数法的分类：罚函数法（外部惩罚法），障碍惩罚函数法的分类：罚函数法（外部惩罚法），障碍函数法（内部惩罚法）函数法（内部惩罚法）退 出前一页后一页第66页，本讲稿共70页(1)罚函数法罚函数法罚函数法基本原理：罚函数法基本原理：考虑：考虑：构造惩罚函数：构造惩罚函数：很大的正数很大的正数无约束最优化问题无约束最优化问题min F(x)=f(x)+p(x)的最优解必定是的最优解必定是原问题的最优解。原问题的最优解。退 出前一页后一页第67页，本讲稿共70页可选的惩罚函数：可选的惩罚函数：惩罚函数法的经济解释：惩罚函数法的经济解释：f(x)为产品成本，约束条件为产品质量约束；为产品成本，约束条件为产品质量约束；如果违反质量约束，就给予一定的惩罚如果违反质量约束，就给予一定的惩罚p(x)；追求的目标就是成本追求的目标就是成本f(x)和惩罚量和惩罚量p(x)的总和最小（即的总和最小（即构造的无约束最优化问题）；构造的无约束最优化问题）；如果惩罚条件很苛刻，最好的结果就是不违反质量约束如果惩罚条件很苛刻，最好的结果就是不违反质量约束（无约束最优化问题的最优解为（无约束最优化问题的最优解为MP的最优解）的最优解）退 出前一页后一页第68页，本讲稿共70页(2)障碍函数法障碍函数法障碍函数法基本原理：障碍函数法基本原理：构造一个新的目标函数，它在可行区域的边界筑起一道构造一个新的目标函数，它在可行区域的边界筑起一道墙；墙；当迭代点靠近边界时，新的目标函数迅速增加；迭当迭代点靠近边界时，新的目标函数迅速增加；迭代点被档在可行区域的内部；代点被档在可行区域的内部；迭代得到的点列就只可能在可行区域的内部。迭代得到的点列就只可能在可行区域的内部。退 出前一页后一页第69页，本讲稿共70页可选的惩罚函数：可选的惩罚函数：考虑：考虑：构造最优化问题：构造最优化问题：或：或：当当x靠近边界时，至少有一个靠近边界时，至少有一个gi(x)趋近于零，则趋近于零，则F(x)将无限将无限增大，从而使得迭代点保持在可行区域的内部。增大，从而使得迭代点保持在可行区域的内部。退 出前一页后一页第70页，本讲稿共70页