非线性规划模型
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，使得
反复进行这一过程，直到得到满足精度要求为止，这种方法称为可行方向法，也称迭代法。
非线性规划模型
