非线性规划样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
非线性规划
如果目标函数或约束条件中含有一个或多个是变量的非线性函数, 我们称这类规划问题为非线性规划( nonlinear programming, 可简记为NP) 。
一般地, 解非线性规划问题要比解线性规划问题困难的多, 因为它不像解线性规划问题有单纯形法这一通用的方法, 非线性规划当前还没有适合于各种问题的一般算法, 各个方法都有自己特定的应用范围。
非线性规划的基本概念和基本原理
第一节 非线性规划的数学模型
例: 某金属制品厂要加工一批容积为1米3的长方形容器, 按规格要求, 上下底的材料为25元/m2, 侧面的材料为40元/m2, 试确定长、 宽、 高的尺寸, 使这个容器的成本最低。
设容器的长为, 宽为, 则高为。
根据题意得:

例: 某公司经营两种设备, 第一种设备每件售价30元, 第二种设备每件售价为450元, 根据统计, 售出一件第一种设备所需营业时间平均为0.5小时, 第二种设备为时, 其中是第二种设备的售出数量, 已知该公司在这段时间内的总营业时间为800小时, 试决定使其营业额最大的营业计划。
解: 设该公司计划经营第一种设备为件, 第二种设备为件, 根据题意得:

由这两个例子能够看出, 这两个例子在高等数学中代表了两类不同类型的极值问题。例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) 位置大小都不对

即函数图形上任意两点的连线处处不在这个函数图形的下方, 称它为凸函数, 下凸的。
线性函数既是凸函数, 又是凹函数。

下面介绍凸函数的性质。
性质１: 设是凸集上的凸函数, , 且则: 。
性质２: 设是凸集上的两个凸函数, 则和函数仍是上的凸函数。
性质３: 设是凸集上的凸函数, 对任意的实数, 仍是凸集上的凸函数。

由性质２、 性质３可得:
凸集上的有限个凸函数的正系数的线性组合, 仍是凸集上的凸函数。
性质４: 设是定义在凸集上的凸函数, 则对每一个实数, 集合是凸集。集合称为实数的水平集。
值得注意的是, 性质４的逆命题不成立。
例: 当时, 是上的严格凹函数, 而不是凸函数。
但对于一切, 水平集是凸集。
下面介绍凸函数的判定方法。
定理: 设是凸集上具有一阶连续偏导数, 则是上的凸函数对于任意两点, 必有
不等式是严格不等式时, 即得严格凸函数的充要条件。
即一个可微的函数时凸函数函数图形上任意一点处的切平面位于曲面的下方。
定理: 设是凸集上具有二阶连续偏导数, 则是上的凸函数海赛矩阵的时整个上是半正定的。
的海赛矩阵是正定的, 则是严格凸函数。反之不成立。
凹函数和上面的结果类似, 在此就不重复。
例: 设, 其中是n阶对称矩阵, 则
( 1) 是上的凸函数为半正定矩阵。
( 2) 是上的严格凸函数为正定矩阵。
证: 二次函数在上具有二阶连续偏导数, 且
由定理知, ( 1) 成立。
下面证( 2) :因为是上的严格凸函数, 当且仅当
, 任意
即等价于。
因为是二次函数, 为对称矩阵, 因此上式等价于
即, 故为正定矩阵。
例: 证明为凹函数
证:

故为负定矩阵, 故为严格凹函数。
我们知道, 一般来说, 函数的局部极值并一定就是全局极值, 而解非线性规划时, 所求最优解必须是目标函数在某个可行域上的全部极值。但对于一类所给凸规划来说, 下面将看到, 其局部最优解必定是全局最优解。
定理: 设是凸集上的一个凸函数, 则使得取得极小值的点集必是一个凸集, 而且的任一局部极小值也是它在上的全局极小值。
该定理说明, 对于凸集上的凸函数, 所有极小点位于同意凸集中, 即所有极小点的集合形成一个凸集, 而且局部极小值也是全局极小值。
定理: 设是凸集上的一阶可微凸函数, 点, 且为的内点, 则为在上的全局极小点对于所有,有.
由定理可知, 当为的内点时, 上式对于任意的都成立, 即它意味着, 也就是, 对于凸集上的凸函数, 驻点就是全局极小点。
现在我们回到非线性规划中:
非线性规划的数学模型为:

它与线性规划类似, 把满足约束条件( 2) 、 ( 3) 的点称为可行点( 可行解) 。
所有可行解的集合称为可行域。若某个可行解使目标函数( 1) 的值最小, 就称它为最优解。
下面我们考虑一种比较特殊的非线性规划:

其中, 是凸函数, 为凹函数( 为凹函数) , 这样的非线性规划称为凸规划。能够证明, 凸划的可行域是凸集。
由此可知, 凸规划的局部最优解就是它的全局最优解。因此, 凸规划是一种较简单的非线性规划。
例: 求解非线性规划

解: 的海塞矩阵为:
,
由于为正定矩阵, 故为严格凸函数; 为半定矩阵, 因此为凹函数, 为线性函数, 能够看作凹函数。
因此, 该非线性规划为凸规划。
如图所示, 图中A点为最优点, 目标函数的最优值为。

第四节 下降迭代算法
对于求可微函数的最优解, 从理论上讲, 我们是首先令函数的梯度等于零( ) , 求得驻点, 然后利用充分条件进行判别, 求最优解。
但在实际中, 对于一般的n元函数来说, 由于得到的常常是一个非线性方程组, 求它的解相当困难。另外很多实际问题的目标函数对各自变量的偏导数不存在, 从而无法利用上面所说求它的驻点, 因此这时常常使用迭代法。
所谓迭代法, 就是从已知点出发, 按照某种规则( 即算法) , 求出比更好的解, (若极小化问题, ), 再按照此规则求出比更好的点, …如此重复这个过程, 便产生一个点列, 在一定条件下, 下降迭代算法产生的点列收敛于原问题的解。即或
称该点列收敛于。
由于算法产生的点列使目标函数值逐步减小, 称这一算法为下降算法。
收敛速度
设算法产生的点列,收敛到解, 且, , 若存在, 及一个与迭代次数k无关的常数, 使
1.线性收敛: 当, 时称为线性收敛速度。
2.超线性收敛: 当 , , 或, 时, 称为超线性收敛速度
3.二阶收敛: 当, k充分大时有
一般地认为, 具有超线性收敛或二阶收敛速度的算法是比较快速的算法。不过应该认识到, 对任意一个算法, 收敛性和收敛速度的理论结果并不保证算法在实际应用( 执行) 时一定有好的实际计算效果。一方面, 由于这些理论结果本身不能保证算法一定有好的特性; 另一方面是它们忽略了计算过程中十分重要的舍入误差的影响。
对于不同的问题, 要根据具体情况来选择算法, 因为我们事先并不知道最优解, 迭代到什么时候停止呢? 常见的准则是:

迭代中我们从一点出发沿下降可行方向找一个新的、 性质有所改进的点。
△下降方向 :
设, 若存在, 使, 则称为点下降的方向。
△可行方向: 设, 若存在, 使, 称为点的可行方向。
同时满足上述两个性质的方向称下降可行方向。
4.1 常见的搜索算法结构

在以上迭代过程中, 选取搜索方向是最关键的一步, 计算各种算法的区别, 主要在于确定搜索方向的方法不同。
确定步长的算法也有很多种, 步长的选定是由使目标函数值沿搜索方向下降最多的依据, 即沿射线求的极小。
即选取, 使, 由于这一工作是求以为变量的一元函数的极小点, 故称为一维搜索或线性搜索。由此确定的步长为最佳步长。
一维搜索有一个重要性质: 在搜索方向上所取得最优点处的梯度和该方向正交。
即 。
表述为定理如下:
定理: 设目标函数具有一阶连续偏导数, 按下述产生:

则有 。
由于函数在某点的梯度和该点的等值面的切线正交, on个人一维搜索的方向和其上最优点处的等值面相切。

第五节 一维搜索
定理: 设在上单峰, 。那么
1°若, 则, ; 如左下图
2°若, 则, ; 如右下图

一、 分数法( 斐波那锲法)
分数法是寻找单峰函数极小点的一种方法。
设在区间上只有一个极值点, 则对区间内任意两点, , 并计算。则必有下列两种情况之一:
( 1) , 此时必有;
( 2) , 此时必有。

经过上面的讨论, 我们知道, 只要在区间内取两个不同的点, 并算出这两点的函数值, 加以比较, 就能把搜索区间缩小成或。
如果继续缩小区间 或, 就需要在区间 或内取一点, 并计算出的值, 并与比较。
若 , 则 ;
, 则 。
这样如此继续下去, 就能越来越精确地估计出的位置。当然, 如果无限地搜索下去, 能够精确地求出极小点。但实际计算时只能使包含在某个小区间内, 且此时小区间的长度不超过某一给定的精度就能够了。如经过n次搜索以后, 已知位于区间中, 且, 其中是事先给定的精度, 这时区间中的点都能够作为的近似点。
因此, 现在我们关心的是: 进行n次搜索后, 能把区间缩小到什么程度? 或者说, 计算n次函数值以后能把多长的区间缩小成长度为1的区间?
用表示计算n个函数值能缩短为单位区间的最大原区间长度, 显然有
这是因为至少要计算两次函数值才能缩短区间, 只计算零次或一次函数值是不能缩短区间长度的, 故只有区间长度本身等于1时才行。
现考虑计算函数值两次的情形: 我们把计算函数值的点称为试算点或试点。
在区间内任取两点, 计算函数值以缩短区间, 缩短后的区间为或, 显然, 这两个区间长度之和必大于区间的长度。也就是说, 计算两次函数值一般无法把长度大于2的区间缩短成单位区间, 可是对于长度为2的区间, 能够用如图的方法选取试点, 图中为任意小的正数, 缩短后的区间长度我1＋:, 故缩短后的区间长度近似等于1。由此得:

根据同样的方法, 可得

序列的递推公式为:

利用公式可计算出的值如下:

这里的就是一般所说的裴波那锲数。
由以上讨论知, 计算n次函数值所能获得的最大缩短率( 缩短后的长度与原区间长度的比) 为。
如, 即计算20个函数值能够把原区间长度为L的区间缩短为的区间长度。
现在对于寻找近似极小点来说, 如果希望误差不超过, 只需将原区间缩短为包含极小点而区间长度不超过的区间就能够了。这时计算函数值的次数n只要满足:
即可。有时给出区间缩短的绝对精度, 要求。

分数法求近似极小点的步骤
( 1) 给出精度, 求出使的最小整数n,
由, 定出两个试点, 。
( 2) 计算与:
若, 取
并令, 。
若, 取,
并令, 。
( 3) 计算, 比较它们的大小。方法同( 2) 。
( 4) 当迭代到k=n+1时,

这时无法比较函数值与 来确定最后的区间, 为此取

其中是一个很小的正数, 这样就能够比较与的值以确定最后区间, 在与中其函数值较小者为近似极小点, 相应的函数值为近似的极小值。
例: 试用分数发, 求函数在区间上的近似极小点和近似极小值, 并要求误差不超过0.2。
解: 不难验证, 在区间上是仅有唯一的极小点的单峰函数, 极小点为, 极小值。下面利用分数法求解。
已知, 故n=7, 又知,
取,

取, 这样一直下去, 最后可得:
由于, 因此取, 取为近似极小点, 近似极小值。

二、 0.618法( 黄金分割法)

由上节讨论知, 用分数法以n个试点来缩短某一区间时, 区间长度的第一次缩短率为, 其后各次分别为: , , …, , 现将以上数列分为奇数项和偶数项, 能够证明, 这两个数量收敛于同一个极限:

以不变的区间缩短率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法更好。
现在仍设在上仅有一个极小点的单峰函数, 且具有二阶导数。
我们知道, 如果函数在处取极小值, 则必有, 因此求此函数极小点, 只需求出在内的零点即可。
对在点展开:

取二次式( 略去高阶项) :
, 用作为的近似。
首先求的导数, 并令其等于零。
,
得 , 取为新的迭代点。
以上过程即Newton法。
特点: 二阶、 局部收敛。 ( 算法框图见下页)

当在上仅有三阶导数, , 以及, 则切线法产生的点列收敛到在中的唯一极小点。
当是具有极小点的二次函数时, 牛顿法能够一步达到极小点。
当的三阶导数在内大于零时, 迭代的初始点应在b端点附近, 的三阶导数在内小于零时, 迭代的初始点应在a端点附近。
例: 求
解: ,
迭代公式:
取算结果:

取计算结果如下:

例: 用牛顿法求在区间上的极小点。
解: 因为, 由此可知, 在上, 而在上有唯一极小点。
下面用牛顿法来求。
, 初始点选在靠近5的一端, 取初始点, 并取精度。
, 计算, , 计算, ,
计算
, , 停止迭代。
取。
四、 抛物线法( 插值法) :
1、 插值法概念
假定我们给定的问题是在某一确定区间内寻求函数的极小点的位置, 可是没有函数表示式, 只有若干试验点处的函数值。我们能够根据这些函数值, 构成一个与原目标函数相接近的低次插值多项式, 用该多项式的最优解作为原函数最优解的近似解, 这种方法是用低次插值多项式逐步逼近原目标函数的极小点的近似求解方法, 称为插值方法或函数逼近法。
上面的牛顿法需要计算的一阶导数、 二阶导数, 当很复杂时, 计算起来相当困难。抛物线法是一种多项式逼近, 即用一个二次多项式来逼近所给的函数, 并用的极小点来近似的极小点, 在整个计算过程中, 只需要计算的值。其基本思想就是用二次三项式来逼近目标函数。
2、 插值法与试探法的区别
试验点位置的确定方法不同。在试探法中试验点的位置是由某种给定的规律确定的, 并未考虑函数值的分布。例如: 黄金分割法是按照等比例0.618缩短率确定的。而在插值法中, 试验点的位置是按函数值近似分布的极小点确定的。试探法仅仅利用了试验点函数值进行大小的比较, 而插值法还要利用函数值本身。因此, 当函数具有较好的解析性质时, 插值方法比试探方法效果更好。
3、 二次插值法的概念
利用原目标函数上的三个插值点, 构成一个二次插值多项式, 用该多项式的最优解作为原函数最优解的近似解, 逐步逼近原目标函数的极小点, 称为二次插值方法或抛物线法。
4、 二次插值函数的构成
设一维目标函数的搜索区间为, 取三点, 其中取区间的端点, 即

而为区间内的一个点, 开始能够取区间的中点, 即

计算函数值
过函数曲线上的三点作二次插值多项式 , 满足条件

解方程组, 得待定系数A、 B、 C分别为

于是函数就是一个确定的二次多项式, 称二次插值函数, 如图所示, 虚线部分即为二次插值函数。
二次插值函数图例

令插值函数的一阶导数为0, 即

得极小点为, 代入A、 B得:

令, 则。
注意: 若, 则,
即。
说明三个插值点位于同一条直线上, 因此说明区间已经很小, 插值点非常接近, 故可将输出作为最优解。
5、 区间的缩短
为求得满足收敛精度要求的最优点, 往往需要多次进行插值计算, 搜索区间不断缩短, 使不断逼近原函数的极小点。
第一次区间缩短的方法是, 计算点的函数值, 比较与, 取其中较小者所对应的点作为新的, 以此点的左右两邻点作为新的和, 得到缩短后的新区间, 如图所示。
新区间三个字太大了

以后, 根据相对于的位置, 并比较与, 区间的缩短能够分为以下四种情况。

区间缩短流程图:

6、 终止准则

当满足给定精度时, 计算终止, 并令

7、 二次插值算法流程图

五、 外推内插法
设在上仅有一个单峰函数。
其基本原理和步骤:
1、 给定初始区间, 初始点及初始步长。
2、 用加步长的外推法缩短初始区间。

( 3) 在之间内插一个点, 再一次缩短并最后确定极值点存在的区间。在三个点上述之间, 因为步长逐次加倍, 故有, 于是之间内插一点, 令, 这样得到等间距的四个点。比较上述四个函数值, 令其函数值最小的为的左、 右邻点分别为。直到得到了尽可能小的极值点存在的区间, 而且符合, 然后利用抛物线法求解极小点。
例: 用一次外推内插法, 然后用抛物线法求的近似极小点, 给定初始点, 初始步长, 初始区间。
解: 外推内插法寻找尽可能小的极小点存在区间,
从以上计算得三个点, 其函数值满足两头大, 中间小, 即, 极小点在区间上, 故舍去初始区间的其它部分。
在中插入一点。,
由于, 故取的左右邻点三点, 其函数值恰好两头大, 中间小, 这样得到了尽可能小的极小点在区间。
令,
。
根据抛物线法得极小点的计算公式: , 因为中, 目标函数值最小的是, 故选取及其左右邻点为三个新的初始点, 继续迭代。
, 则, 计算得: , 因为迭代结果相同, 因此已达最优。