非线性规划样本

非线性规划如果目标函数或约束条件中含有一个或多个是变量的非线性函数,我们称这类规划问题为非线性规划(nonlinearprogramming,可简记为NP)。一般地,解非线性规划问题要比解线性规划问题困难的多,因为它不像解线性规划问题有单纯形法这一通用的方法,非线性规划当前还没有适合于各种问题的一般算法,各个方法都有自己特定的应用范围。非线性规划的基本概念和基本原理第一节非线性规划的数学模型例:某金属制品厂要加工一批容积为1米3的长方形容器,按规格要求,上下底的材料为25元/m2,侧面的材料为40元/m2,试确定长、宽、高的尺寸,使这个容器的成本最低。设容器的长为,宽为,则高为。根据题意得:例:某公司经营两种设备,第一种设备每件售价30元,第二种设备每件售价为450元,根据统计,售出一件第一种设备所需营业时间平均为0.5小时,第二种设备为时,其中是第二种设备的售出数量,已知该公司在这段时间内的总营业时间为800小时,试决定使其营业额最大的营业计划。解:设该公司计划经营第一种设备为QUOTE件,第二种设备为QUOTE件,根据题意得:由这两个例子能够看出,这两个例子在高等数学中代表了两类不同类型的极值问题。例1是无条件极值;例2是有条件极值。如果令是n维空间上的点,则一般非线性的数学模型为:为目标函数,为约束条件,X为自变量。若某个约束条件是的不等式,不等式两边乘以”-1”。第二节极值问题设是定义在n维欧式空间空间上某一区域上的n元函数,其中。对于,如果存在某一个,使得所有与的距离小于的,(即),均满足,则称为在上的局部极小点。为局部极小值。若所有,且,有,则称为在上的严格局部极小点。为严格局部极小值。若点,对于所有的,均满足,则称为在上的全局极小点。为全局极小值。若对于所有,且,都有,则称为在上的严格全局极小点。为严格全局极小值。如果将上述不等式反向,即可得到局部极大值与全局极大值的定义。定理1:极值的必要条件设是定义在上某一区域上的函数,是内的一点,若在处可微且取得局部极值,则必有或,上式的点称为驻点,或平稳点。即在区域内部,极点必是驻点。称为在点X处的梯度。但反过来,驻点不一定是极值点。如点(0,0)是函数的驻点,但不是极值点。定理2:极值的充要条件设是定义在上某一区域上的函数,且在上二次连续可微,是内的一点,若在处满足,且对任意非零向量Y,有则称在点处取得严格局部极小值。这里是在点处的海赛矩阵。若,则在点处取得严格局部极大值。由定理2看出,驻点处的海赛矩阵是正定矩阵时,函数在点处取得极小值。驻点处的海赛矩阵是负定矩阵时,函数在点处取得极大值。定理3:设是定义在上的函数,且在点处存在二阶连续偏导数,若是的局部极小点,则,且半正定。 需要指出的是,定理2不是必要条件,定理3不是充分条件。例:对于无约束问题解:由于令,得驻点,而且,因此不是正定矩阵,但在点处取得最小值,即为严格局部极小点。例:解:由于令,得是不定的,因此不是极值点;是负定的,故是极大点。是正定的,故是严格极小点。例:解:因为,令,得是半正定矩阵,但在的任意邻域内,总能够取到,使得,即不是局部极小点。例:解:因为令,得是不定的,因此不是极值点;是负定的,故是极大点。是正定的,故是严格极小点。非线性规划的图解问题图解法能够给人以直观概念,当只有两个自变量时,非线性规划也像线性规划一样,能够利用图解法。例:用图解法求解非线性规划。若令目标函数,C为某一常数。则就代表一条曲线,称为等值线或等高线。等值线与直线AB相切,切点为。例:用图解法求解非线性规划。解:画出目标函数的等值线,它表示一族中心在(2,1)上的同心圆。画出约束区域:先画,这是一条抛物线,再画不等式,所代表的约束区域。则抛物线弧ＡＢＣＤ为约束集。由动点Ａ出发抛物线ＡＢＣＤ移动时,弧ＡＢ段,目标函数值下降,在ＢＣ段函数值上升,弧ＣＤ段,目标函数值下降,而且在Ｄ点是可行域上使目标函数值最小的点,它是全局最优点。其坐标由约束方程组可得。最优点(４,１),最优值。第三节凸函数及其性质一、凸函数凸集、凸函数是研究非线性规划问题所不可缺少的内容,有关凸集的概念参见线性规划部分,这里主要介绍凸函数的概念。定义:设是定义在n维欧式空间空间中某个凸集上的函数,若对任意一个实数以及中的任意两点和,恒有,则称是定义在凸集上的凸函数。若对任意一个实数以及、,恒有,则称是定义在凸集上的严格凸函数。若上述不等式反向,称分别为上的凹函数及严格凹函数。下面给出凸函数与凹函数的几何意义X(1)X(1)图下面的x(1)位置大小都不对即函数图形上任意两点的连线处处不在这个函数图形的下方,称它为凸函数,下凸的。线性函数既是凸函数,又是凹函数。下面介绍凸函数的性质。性质１:设是凸集上的凸函数,,且则:。性质２:设是凸集上的两个凸函数,则和函数仍是上的凸函数。性质３:设是凸集上的凸函数,对任意的实数,仍是凸集上的凸函数。由性质２、性质３可得:凸集上的有限个凸函数的正系数的线性组合,仍是凸集上的凸函数。性质４:设是定义在凸集上的凸函数,则对每一个实数,集合是凸集。集合称为实数的水平集。值得注意的是,性质４的逆命题不成立。例:当时,是上的严格凹函数,而不是凸函数。但对于一切,水平集是凸集。下面介绍凸函数的判定方法。定理:设是凸集上具有一阶连续偏导数,则是上的凸函数对于任意两点,必有不等式是严格不等式时,即得严格凸函数的充要条件。即一个可微的函数时凸函数函数图形上任意一点处的切平面位于曲面的下方。定理:设是凸集上具有二阶连续偏导数,则是上的凸函数海赛矩阵的时整个上是半正定的。的海赛矩阵是正定的,则是严格凸函数。反之不成立。凹函数和上面的结果类似,在此就不重复。例:设,其中是n阶对称矩阵,则(1)是上的凸函数为半正定矩阵。(2)是上的严格凸函数为正定矩阵。证:二次函数在上具有二阶连续偏导数,且由定理知,(1)成立。下面证(2):因为是上的严格凸函数,当且仅当,任意即等价于。因为是二次函数,为对称矩阵,因此上式等价于即,故为正定矩阵。例:证明为凹函数证:故为负定矩阵,故为严格凹函数。我们知道,一般来说,函数的局部极值并一定就是全局极值,而解非线性规划时,所求最优解必须是目标函数在某个可行域上的全部极值。但对于一类所给凸规划来说,下面将看到,其局部最优解必定是全局最优解。定理:设是凸集上的一个凸函数,则使得取得极小值的点集必是一个凸集,而且的任一局部极小值也是它在上的全局极小值。该定理说明,对于凸集上的凸函数,所有极小点位于同意凸集中,即所有极小点的集合形成一个凸集,而且局部极小值也是全局极小值。定理:设是凸集上的一阶可微凸函数,点,且为的内点,则为在上的全局极小点对于所有,有. 由定理可知,当为的内点时,上式对于任意的都成立,即它意味着,也就是,对于凸集上的凸函数,驻点就是全局极小点。 现在我们回到非线性规划中:非线性规划的数学模型为:它与线性规划类似,把满足约束条件(2)、(3)的点称为可行点(可行解)。所有可行解的集合称为可行域。若某个可行解使目标函数(1)的值最小,就称它为最优解。下面我们考虑一种比较特殊的非线性规划:其中,是凸函数,为凹函数(为凹函数),这样的非线性规划称为凸规划。能够证明,凸划的可行域是凸集。由此可知,凸规划的局部最优解就是它的全局最优解。因此,凸规划是一种较简单的非线性规划。例:求解非线性规划解:的海塞矩阵为:,由于为正定矩阵,故为严格凸函数;为半定矩阵,因此为凹函数,为线性函数,能够看作凹函数。因此,该非线性规划为凸规划。如图所示,图中A点为最优点,目标函数的最优值为。第四节下降迭代算法对于求可微函数的最优解,从理论上讲,我们是首先令函数的梯度等于零(),求得驻点,然后利用充分条件进行判别,求最优解。但在实际中,对于一般的n元函数来说,由于得到的常常是一个非线性方程组,求它的解相当困难。另外很多实际问题的目标函数对各自变量的偏导数不存在,从而无法利用上面所说求它的驻点,因此这时常常使用迭代法。所谓迭代法,就是从已知点出发,按照某种规则(即算法),求出比更好的解,(若极小化问题,QUOTE),再按照此规则求出比QUOTE更好的点QUOTE,…如此重复这个过程,便产生一个点列,在一定条件下,下降迭代算法产生的点列收敛于原问题的解。即或称该点列QUOTE收敛于。由于算法产生的点列使目标函数值逐步减小,称这一算法为下降算法。收敛速度设算法产生的点列,收敛到解,且,,若存在,及一个与迭代次数k无关的常数,使1.线性收敛:当,时称为线性收敛速度。2.超线性收敛:当,,或,时,称为超线性收敛速度3.二阶收敛:当,k充分大时有一般地认为,具有超线性收敛或二阶收敛速度的算法是比较快速的算法。不过应该认识到,对任意一个算法,收敛性和收敛速度的理论结果并不保证算法在实际应用(执行)时一定有好的实际计算效果。一方面,由于这些理论结果本身不能保证算法一定有好的特性;另一方面是它们忽略了计算过程中十分重要的舍入误差的影响。对于不同的问题,要根据具体情况来选择算法,因为我们事先并不知道最优解,迭代到什么时候停止呢?常见的准则是:迭代中我们从一点出发沿下降可行方向找一个新的、性质有所改进的点。△下降方向:设,若存在,使,则称为点下降的方向。△可行方向:设,若存在,使,称为点的可行方向。同时满足上述两个性质的方向称下降可行方向。4.1常见的搜索算法结构 在以上迭代过程中,选取搜索方向是最关键的一步,计算各种算法的区别,主要在于确定搜索方向的方法不同。 确定步长的算法也有很多种,步长的选定是由使目标函数值沿搜索方向下降最多的依据,即沿射线求的极小。即选取,使,由于这一工作是求以为变量的一元函数的极小点,故称为一维搜索或线性搜索。由此确定的步长为最佳步长。 一维搜索有一个重要性质:在搜索方向上所取得最优点处的梯度和该方向正交。即 。表述为定理如下:定理:设目标函数具有一阶连续偏导数,按下述产生:则有。由于函数在某点的梯度和该点的等值面的切线正交,on个人一维搜索的方向和其上最优点处的等值面相切。第五节一维搜索定理:设QUOTE在上单峰,QUOTE。那么1°若,则,QUOTE;如左下图2°若,则,QUOTE;如右下图一、分数法(斐波那锲法)分数法是寻找单峰函数极小点的一种方法。设在区间上只有一个极值点,则对区间内任意两点,,并计算。则必有下列两种情况之一:(1),此时必有;(2),此时必有。经过上面的讨论,我们知道,只要在区间内取两个不同的点,并算出这两点的函数值,加以比较,就能把搜索区间QUOTE缩小成QUOTE或QUOTE。如果继续缩小区间QUOTE或QUOTE,就需要在区间QUOTE或QUOTE内取一点QUOTE,并计算出QUOTE的值,并与QUOTE比较。若QUOTE,则; QUOTE,则。这样如此继续下去,就能越来越精确地估计出QUOTE的位置。当然,如果无限地搜索下去,能够精确地求出极小点QUOTE。但实际计算时只能使QUOTE包含在某个小区间内,且此时小区间的长度不超过某一给定的精度就能够了。如经过n次搜索以后,已知QUOTE位于区间QUOTE中,且QUOTE,其中QUOTE是事先给定的精度,这时区间QUOTE中的点都能够作为QUOTE的近似点。因此,现在我们关心的是:进行n次搜索后,能把区间QUOTE缩小到什么程度?或者说,计算n次函数值以后能把多长的区间缩小成长度为1的区间?用表示计算n个函数值能缩短为单位区间的最大原区间长度,显然有这是因为至少要计算两次函数值才能缩短区间,只计算零次或一次函数值是不能缩短区间长度的,故只有区间长度本身等于1时才行。现考虑计算函数值两次的情形:我们把计算函数值的点称为试算点或试点。在区间QUOTE内任取两点,计算函数值以缩短区间,缩短后的区间为QUOTE或,显然,这两个区间长度之和必大于QUOTE区间的长度。也就是说,计算两次函数值一般无法把长度大于2的区间缩短成单位区间,可是对于长度为2的区间,能够用如图的方法选取试点,图中QUOTE为任意小的正数,缩短后的区间长度我1＋QUOTE,故缩短后的区间长度近似等于1。由此得:QUOTE根据同样的方法,可得 QUOTE序列的递推公式为:利用公式可计算出QUOTE的值如下:这里的QUOTE就是一般所说的裴波那锲数。由以上讨论知,计算n次函数值所能获得的最大缩短率(缩短后的长度与原区间长度的比)为QUOTE。如,即计算20个函数值能够把原区间长度为L的区间缩短为的区间长度。现在对于寻找近似极小点来说,如果希望误差不超过QUOTE,只需将原区间QUOTE缩短为包含极小点而区间长度不超过QUOTE的区间就能够了。这时计算函数值的次数n只要满足:即可。有时给出区间缩短的绝对精度,要求。分数法求近似极小点的步骤(1)给出精度QUOTE,求出使的最小整数n,由,定出两个试点QUOTE,。(2)计算与QUOTE:若,取并令QUOTE,。若QUOTE,取,并令,。(3)计算,比较它们的大小。方法同(2)。(4)当迭代到k=n+1时,QUOTE这时无法比较函数值与QUOTE来确定最后的区间QUOTE,为此取其中是一个很小的正数,这样就能够比较与的值以确定最后区间,在与中其函数值较小者为近似极小点,相应的函数值为近似的极小值。例:试用分数发,求函数在区间上的近似极小点和近似极小值,并要求误差不超过0.2。解:不难验证,在区间上是仅有唯一的极小点的单峰函数,极小点为,极小值。下面利用分数法求解。已知,故n=7,又知,取,取,这样一直下去,最后可得:由于,因此取,取为近似极小点,近似极小值。 二、0.618法(黄金分割法)由上节讨论知,用分数法以n个试点来缩短某一区间时,区间长度的第一次缩短率为QUOTE,其后各次分别为:QUOTE,QUOTE,…,QUOTE,现将以上数列分为奇数项和偶数项,能够证明,这两个数量收敛于同一个极限:以不变的区间缩短率0.618代替分数法每次不同的缩短率,就得到黄金分割法(0.618法)。它能够看成是分数法的近似,实现起来比较容易,效果也好。具体算法如下:例:为了提高某种化工产品的质量指标,需要在制作过程中加入某种原料,已知其最佳加入量在1000克到克之间的某一点,现在经过实验的方法找到该点。按0.618法来获取该点。先做第一次试验,其加入量为:1000＋0.382(－1000)=1382g;再做第二次试验,加入量为:1000＋0.618(－1000)=1618g;比较这两次的试验结果。如果第(2)点较第(1)点效果好,则去掉1000至1382这段,然后在留下的一段中再找出第(2)点的对称点,做第三次试验,其加入量为1382＋0.618(－1382)=1764g。再比较第一次与第三次的试验结果。如果依然是第(2)点较第(3)点效果好,则去掉1764至这一段,然后在留下的一段中再找出第(4)点的对称点,做第四次试验,其加入量为1382＋0.618(1764－1382)=1528g;如果依然是第(4)点较第(2)点效果好,则去掉1618至1764这一段,对留下的1382至1618这一段中继续试验下去就能找到最优点,这样能够用最少的试验次数找到最佳加入量。例:用黄金分割法求函数在区间上的极大点,要求缩短后的长度不大于原区间长度的15%。解:已知,则因为,故原区间缩短为,令,,故原区间缩短为。令,故原区间缩短为,令,,故原区间缩短为,由于,以达到精度要求,停止迭代,得近似极大点和极大值,此题的精确最优解为。三、牛顿法(Newton)(切线法)上面我们所讨论的方法,只是对一些点的函数值的大小进行比较,而函数本身并没有得到充分利用,至于函数的一些解析性质,更是毫无利用,下面介绍的牛顿法当函数性质具有较好的解析性质时,计算效果要比分数法、0.618法更好。现在仍设QUOTE在上仅有一个极小点的单峰函数,且具有二阶导数。我们知道,如果函数QUOTE在处取极小值,则必有QUOTE,因此求此函数极小点,只需求出QUOTE在QUOTE内的零点即可。对在QUOTE点展开:取二次式(略去高阶项):QUOTE,用作为QUOTE的近似。首先求QUOTE的导数,并令其等于零。,得QUOTE,取QUOTE为新的迭代点。以上过程即Newton法。特点:二阶、局部收敛。(算法框图见下页)当QUOTE在QUOTE上仅有三阶导数,,以及,则切线法产生的点列收敛到QUOTE在QUOTE中的唯一极小点。当QUOTE是具有极小点的二次函数时,牛顿法能够一步达到极小点。当QUOTE的三阶导数在QUOTE内大于零时,迭代的初始点QUOTE应在b端点附近,QUOTE的三阶导数在QUOTE内小于零时,迭代的初始点QUOTE应在a端点附近。例:求解:,迭代公式:QUOTE取QUOTE算结果:取QUOTE计算结果如下:例:用牛顿法求在区间上的极小点。解:因为,由此可知,在上,而在上有唯一极小点。下面用牛顿法来求。,初始点选在靠近5的一端,取初始点,并取精度。,计算,,计算,,计算,,停止迭代。取。四、抛物线法(插值法):1、插值法概念假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置,可是没有函数表示式,只有若干试验点处的函数值。我们能够根据这些函数值,构成一个与原目标函数相接近的低次插值多项式,用该多项式的最优解作为原函数最优解的近似解,这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近似求解方法,称为插值方法或函数逼近法。上面的牛顿法需要计算的一阶导数、二阶导数,当QUOTE很复杂时,计算起来相当困难。抛物线法是一种多项式逼近,即用一个二次多项式来逼近所给的函数QUOTE,并用QUOTE的极小点来近似的极小点,在整个计算过程中,只需要计算QUOTE的值。其基本思想就是用二次三项式来逼近目标函数。2、插值法与试探法的区别试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的,并未考虑函数值的分布。例如:黄金分割法是按照等比例0.618缩短率确定的。而在插值法中,试验点的位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值进行大小的比较,而插值法还要利用函数值本身。因此,当函数具有较好的解析性质时,插值方法比试探方法效果更好。3、二次插值法的概念利用原目标函数上的三个插值点,构成一个二次插值多项式,用该多项式的最优解作为原函数最优解的近似解,逐步逼近原目标函数的极小点,称为二次插值方法或抛物线法。4、二次插值函数的构成设一维目标函数的搜索区间为QUOTE,取三点,其中取区间的端点,即而QUOTE为区间内的一个点,开始能够取区间的中点,即QUOTE计算函数值QUOTE过函数曲线上的三点作二次插值多项式,满足条件QUOTE解方程组,得待定系数A、B、C分别为于是函数QUOTE就是一个确定的二次多项式,称二次插值函数,如图所示,虚线部分即为二次插值函数。二次插值函数图例令插值函数QUOTE