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