非线性规划模型.doc

(完整word)非线性规划模型非线性规划模型在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法.对于线性规划来说，其可行域一般是一个凸集,只要存在最优解，则其最优解一定在可行域的边界上达到;对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到,因此，对于非线性规划模型,迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。一、非线性规划的分类1无约束的非线性规划当问题没有约束条件时，即求多元函数的极值问题，一般模型为此类问题即为无约束的非线性规划问题1。1无约束非线性规划的解法 1。1。1一般迭代法即为可行方向法.对于问题给出的极小点的初始值，按某种规律计算出一系列的，希望点阵的极限就是的一个极小点。由一个解向量求出另一个新的解向量向量是由方向和长度确定的，所以即求解和，选择和的原则是使目标函数在点阵上的值逐步减小，即 检验是否收敛与最优解，及对于给定的精度，是否。 1。1。2一维搜索法当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多,常用的有:（1）试探法(“成功失败”，斐波那契法,0。618法等)；（2)插值法(抛物线插值法，三次插值法等）；（3)微积分中的求根法(切线法，二分法等）.考虑一维极小化问题若是区间上的下单峰函数，我们介绍通过不断地缩短的长度，来搜索得的近似最优解的两个方法。通过缩短区间，逐步搜索得的最优解的近似值 2。1.3梯度法选择一个使函数值下降速度最快的的方向.把在点的方向导数最小的方向作为搜索方向,即令.计算步骤： （1)选定初始点和给定的要求,； （2）若，则停止计算，否则； （3)在处沿方向做一维搜索得，返回第二步，直到求得最优解为止.可以求得: 2.1。4共轭梯度法又称共轭斜量法，仅适用于正定二次函数的极小值问题：A为阶实对称正定阵从任意初始点和向量出发，由和可以得到-能够证明向量是线性无关的,且关于A是两两共轭的。从而可得到-，则为的极小点。计算步骤:（1）对任意初始点和向量,取（2)若,即得到最优解，停止计算,否则求（3）令；返回（2） 2.1.5牛顿法对于问题：由则由最优条件当A为正定时，存在,于是有为最优解 2。1.6拟牛顿法对于一般的二阶可微函数，在点的局部有当正定时，也可用上面的牛顿法，这就是拟牛顿法.计算步骤：（1） 任取，（2）计算，若，则停止计算,否则计算，令；（3）令;返回（2）2有约束的非线性规划2.1非线性规划的最优性条件若是非线性问题中的极小点，且对点有效约束的梯度线性无关，则必存在向量使下述条件成立:此条件为库恩-塔克条件（K-T条件），满足KT条件的点也称为KT点。K-T条件是非线性规划最重要的理论基础，是确定某点是否为最优解的必要条件，但不一定是充要条件.对于凸规划它一定是充要条件.2。2非线性规划的可行方向法由于线性规划的目标函数为线性函数,可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解.非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点,但并不一定是整个可行域上的全局最优解。假设非线性规划问题中的一个可行解，但不是最优解，为了进一步寻找最优解在它的可行下降方向中选取其中一个方向，并确定最佳步长，使得反复进行这一过程,直到得到满足精度要求为止，这种方法称为可行方向法，也称迭代法。 2。3有约束非线性规划的解法 2。3。1外点法 （1)对于等式约束问题做辅助函数如果最优解满足或近似满足则就是问题的最优解或近似解 （2)对于不等式约束问题做辅助函数求. (3）对于一般问题做辅助函数求解 2.3.2内点法 内点法是在可行域内进行得，并一直保持在可行域内进行搜索，只适用于不等式约束的问题辅助函数:X趋于R的边界时，使趋向于正无穷，的常用形式求解二 非线性规划的缺陷不足算法优点缺点梯度法计算量小，存储变量较少，初始点要求不高初值依赖,收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，越接近极值点时,收敛熟读越慢，后期宜选用收敛快的算法牛顿法收敛速度很快当维数较高时，计算的工作量很大，初值依赖，当初值选择不好时,有可能计算出现异常,导致迭代无法进行，该法需要修正拟牛顿法收敛速度快,避免牛顿矩阵求逆运算，算法更稳定初值依赖程度相对牛顿法减弱,但仍然存在 专业知识分享