非线性规划模型
Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】
非线性规划模型
在上一次作业中,我们对线性规划模型进行了相应的介绍及优缺点,然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题,即如果目标函数和约束条件中包含有非线性函数,则这样的问题称为非线性规划问题。一般来说,解决非线性的问题要比线性的问题难得多,不像线性规划有适用于一般情况的单纯形法。对于线性规划来说,其可行域一般是一个凸集,只要存在最优解,则其最优解一定在可行域的边界上达到;对于非线性规划,即使是存在最优解,却是可以在可行域的任一点达到,因此,对于非线性规划模型,迄今为止还没有一种适用于一般情况的求解方法,我们在本文中也只是介绍了几个比较常用的几个求解方法。
一、非线性规划的分类 1无约束的非线性规划
当问题没有约束条件时,即求多元函数的极值问题,一般模型为 此类问题即为无约束的非线性规划问题
无约束非线性规划的解法 一般迭代法
f?X???minx?R即为可行方向法。对于问题???X?0
给出f(x)的极小点的初始值X(0),按某种规律计算出一系列的X(k)(k?1,2,?),希望点阵{X(k)}的极限X?就是f(x)的一个极小点。 由一个解向量X(k)求出另一个新的解向量X(k?1)
向量是由方向和长度确定的,所以X(k?1)?Xk??kPk(k?1,2,?)
即求解?k和Pk,选择?k和Pk的原则是使目标函数在点阵上的值逐步减小,即 检验{X(k)}是否收敛与最优解,及对于给定的精度??0,是否||?f(Xk?1)||??。 一维搜索法
当用迭代法求函数的极小点时,常常用到一维搜索,即沿某一已知方向求目标函数的极小点。一维搜索的方法很多,常用的有: (1)试探法(“成功—失败”,斐波那契法,法等); (2)插值法(抛物线插值法,三次插值法等); (3)微积分中的求根法(切线法,二分法等)。 考虑一维极小化问题
若f(t)是[a,b]区间上的下单峰函数,我们介绍通过不断地缩短[a,b]的长度,来搜索得minf(t)的近似最优解的两个方法。通过缩短区间[a,b],逐步搜索得
a?t?ba?t?bminf(t)的最优解t*的近似值
(k)选择一个使函数值下降速度最快的的方向。把f(x)在X向作为搜索方向,即令Pk???f(Xk). 计算步骤:
点的方向导数最小的方
(1)选定初始点X0和给定的要求??0,k?0;
(2)若||?f(Xk)||??,则停止计算,X*?Xk,否则P(k)???f(Xk); (3)在X(k)处沿方向P(k)做一维搜索得X(k?1)?Xk??kPk,令k?k?1,返回第二步,直到求得最优解为止.可以求得: 共轭梯度法
又称共轭斜量法,仅适用于正定二次函数的极小值问题:
A为n?n阶实对称正定阵X,B?En,c为常数 从任意初始点X(1)和向量P(1)???f(X(1))出发,由 ?f(X(k?1))?A?(P(k))T???f(X)??kP,?k?(P(k))TAP(k)(k?1,2,?,n?1)(k?1)(k)和P(k?1) 可以得到——能够证明向量——是线性无关的,且关于A是两两共轭的。从而可得到——,则——为——的极小点。 计算步骤: (1)对任意初始点X(1)?En和向量P(1)???f(X(1)),取k?1; (2)若?f(X(k))?0,即得到最优解,停止计算,否则求 (3)令k?k?1;返回(2) 对于问题:
由?f(X)?AX?B?0,则由最优条件?f(X)?0,当A为正定时,A?1存在,于是有
X*??A?1B为最优解
对于一般的二阶可微函数f(X),在X(k)点的局部有
当?2f(X(k))正定时,也可用上面的牛顿法,这就是拟牛顿法。 计算步骤:
(1)任取X(1)?En,k?1;
(2)计算gk??f(X(k)),若gk?0,则停止计算,否则计算H(Xk)??2f(X(k)),令X(k?1)?Xk?(H(Xk))?1gk;
(3)令k?k?1;返回(2) 2有约束的非线性规划 非线性规划的最优性条件
若X*是非线性问题中的极小点,且对点X*有效约束的梯度线性无关,则必存在向量????,?,,?**1*2*Tm?使下述条件成立:
此条件为库恩-塔克条件(K-T条件),满足K-T条件的点也称为K-T点。
K-T条件是非线性规划最重要的理论基础,是确定某点是否为最优解的必要条件,但不一定是充要条件。对于凸规划它一定是充要条件。
非线性规划的可行方向法
由于线性规划的目标函数为线性函数,可行域为凸集,因而求出的最优解就是整个可行域上的全局最优解。非线性规划却不然,有时求出的某个解虽是一部分可行域上的极值点,但并不一定是整个可行域上的全局最优解。
假设X?k?非线性规划问题中的一个可行解,但不是最优解,为了进一步寻找最优解在它的可行下降方向中选取其中一个方向D?k?,并确定最佳步长
?k,使得
反复进行这一过程,直到得到满足精度要求为止,这种方法称为可行方向法,也称迭代法。
非线性规划模型
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)
![](/skin/haowen/images/icon_star.png)