2022年非线性规划模型 .pdf

《2022年非线性规划模型 .pdf》由会员分享，可在线阅读，更多相关《2022年非线性规划模型 .pdf（5页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、非线性规划模型在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。 对于线性规划来说， 其可行域一般是一个凸集， 只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍

2、了几个比较常用的几个求解方法。一、非线性规划的分类1 无约束的非线性规划当问题没有约束条件时，即求多元函数的极值问题，一般模型为此类问题即为无约束的非线性规划问题1.1 无约束非线性规划的解法 1.1.1一般迭代法即为可行方向法。对于问题min0 x RfXX给出)(xf的极小点的初始值)0(X，按某种规律计算出一系列的),2 ,1()(kXk，希望点阵)(kX的极限 X 就是)(xf的一个极小点。由一个解向量)(kX求出另一个新的解向量)1(kX向量是由方向和长度确定的，所以),2, 1()1(kPXXkkkk即求解k和kP ，选择k和kP 的原则是使目标函数在点阵上的值逐步减小，即检验)(

3、kX是否收敛与最优解，及对于给定的精度0，是否|)(|1kXf。 1.1.2一维搜索法当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 点。一维搜索的方法很多，常用的有：（1）试探法（ “成功失败”，斐波那契法， 0.618 法等） ；（2）插值法（抛物线插值法，三次插值法等）；（3）微积分中的求根法（切线法，二分法等）。考虑一维极小化问题若)(tf是,

4、ba区间上的下单峰函数，我们介绍通过不断地缩短,ba的长度，来搜索得)(mintfbta的近似最优解的两个方法。通过缩短区间,ba，逐步搜索得)(mintfbta的最优解*t的近似值选择一个使函数值下降速度最快的的方向。把)(xf在)(kX点的方向导数最小的方向作为搜索方向，即令)(kkXfP. 计算步骤：（1）选定初始点0X 和给定的要求0，0k；（2）若|)(|kXf，则停止计算，kXX*，否则)()(kkXfP；（3）在)(kX处沿方向)(kP做一维搜索得1,)1(kkPXXkkkk令，返回第二步，直到求得最优解为止 . 可以求得：2.1.4 共轭梯度法又称共轭斜量法，仅适用于正定二次函

5、数的极小值问题：A 为nn阶实对称正定阵为常数cEBXn,从任意初始点)1(X和向量)()1()1(XfP出发，由和)1, 2, 1()()()(,)()()()()1()()1()1(nkAPPPAXfPXfPkTkTkkkkkkk可以得到能够证明向量是线性无关的，且关于A 是两两共轭的。从而可得到，则为的极小点。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 计算步骤：（1）对任意初始点nEX)1(和向量)()1()1(Xf

6、P，取; 1k（2）若0)()(kXf，即得到最优解，停止计算，否则求（3）令1kk；返回（ 2）对于问题：由,0)(BAXXf则由最优条件,0)(Xf当 A 为正定时，1A存在，于是有BAX1*为最优解对于一般的二阶可微函数)(Xf，在)(kX点的局部有当)()(2kXf正定时，也可用上面的牛顿法，这就是拟牛顿法。计算步骤：（1）任取nEX)1(，; 1k（2）计算)()(kkXfg，若0kg，则停止计算，否则计算)()()(2kkXfXH，令kkkkgXHXX1)1()(；（3）令1kk；返回（ 2）2 有约束的非线性规划2.1 非线性规划的最优性条件若*X 是非线性问题中的极小点， 且对

7、点*X 有效约束的梯度线性无关， 则必存在向量*12,Tm使下述条件成立：此条件为库恩 - 塔克条件（ K-T 条件） ，满足 K-T 条件的点也称为 K-T 点。K-T 条件是非线性规划最重要的理论基础，是确定某点是否为最优解的必要条件，但不一定是充要条件。对于凸规划它一定是充要条件。2.2 非线性规划的可行方向法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就

8、是整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局最优解。假设kX非线性规划问题中的一个可行解，但不是最优解， 为了进一步寻找最优解在它的可行下降方向中选取其中一个方向kD，并确定最佳步长k，使得反复进行这一过程，直到得到满足精度要求为止，这种方法称为可行方向法，也称迭代法。 2.3有约束非线性规划的解法 2.3.1外点法（1）对于等式约束问题做辅助函数如果最优解 X 满足或近似满足,),2, 1(0)(*mjXhi则 X 就是问题的最优解或近似解（2）对于不等式约束问题做辅助函数求),(min2MXPX. （3）对于一般问

9、题做辅助函数求解),(min3MXPX 2.3.2内点法内点法是在可行域内进行得，并一直保持在可行域内进行搜索，只适用于不等式约束的问题辅助函数：X趋于 R的边界时，使)(XB趋向于正无穷，)(XB的常用形式求解,2, 1,0)(|),(min00mjXgXRrXQjRX名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - - - - 二非线性规划的缺陷不足算法优点缺点梯度法计算量小，存储变量较少, 初始点要求不高初值依赖，收敛慢，最速下降法适用于寻优过程的前期迭代或作为间插步骤，越接近极值点时， 收敛熟读越慢，后期宜选用收敛快的算法牛顿法收敛速度很快当维数较高时，计算的工作量很大，初值依赖，当初值选择不好时，有可能计算出现异常，导致迭代无法进行，该法需要修正拟牛顿法收敛速度快，避免牛顿矩阵求逆运算，算法更稳定初值依赖程度相对牛顿法减弱，但仍然存在名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -