非线性规划模型

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

2、 我们在本文中也只是介绍了几个比较常用的几个求解方法。一、非线性规划的分类 1无约束的非线性规划 当问题没有约束条件时，即求多元函数的极值问题，一般模型为mminf(x)X _0此类问题即为无约束的非线性规划问题1.1无约束非线性规划的解法1.1.1 一般迭代法即为可行方向法。对于问题J噱f(X )X 二0给出f(x)的极小点的初始值X(0)，按某种规律计算出一系列的 x(k)(k =1,2,)， 希望点阵X (k)的极限X "就是f (x)的一个极小点。由一个解向量X(k)求出另一个新的解向量X(k1)向量是由方向和长度确定的，所以X(kF =xkkPk(k =1,2,)即求解和P

3、k，选择和Pk的原则是使目标函数在点阵上的值逐步减小，即f (X0) 一 f (X1) 一 - f (X k) 一 .检验X(k)是否收敛与最优解，及对于给定的精度；7,是否IP f(Xk d)|p：1.1.2 一维搜索法当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。一维搜索的方法很多，常用的有：(1) 试探法(“成功一失败”，斐波那契法，0.618法等)；(2) 插值法(抛物线插值法，三次插值法等)；(3) 微积分中的求根法(切线法，二分法等)。考虑一维极小化问题 f(t)若f (t)是a,b区间上的下单峰函数，我们介绍通过不断地缩短a,b的长度，来搜索得

4、min f(t)的近似最优解的两个方法。通过缩短区间a,b，逐步搜索得a空mtin f (t)的最优解t*的近似值a色也2.1.3梯度法选择一个使函数值下降速度最快的的方向。把f(x)在X(k)点的方向导数最小的方向作为搜索方向，即令 Pkf(Xk).计算步骤：(1) 选定初始点X °和给定的要求； 0，k = 0 ；(2) 若f(Xk)* ;，则停止计算，X* =Xk，否则 P(k) =-Vf(Xk)；(3) 在X(k)处沿方向P(k)做一维搜索得X(j1) =XkkPk,令k = kT，返回第二步，直到求得最优解为止可以求得：、_ Vf(X(k)Vf(X(k)k、f(X(k)T

5、H(X(k)"f(X(k).严(X (k)CX1所(x(k)吋(X(k) T ,r)cXnCX2Fcf (X(k)商(x(k)厅(x(k)1CX1%&ncf (X(k)商(x(k)打(x(k)&2殂-cx2cx2acx2cxn-cf (X(k)伊(X(k)行(x(k)CXnGX1 _!cxncx2 'CXnCXnH(X(k)二lf(X(k)=2.1.4共轭梯度法又称共轭斜量法，仅适用于正定二次函数的极小值问题：1min f(X) = XtAX BtX c2A为n n阶实对称正定阵 X,B En,c为常数从任意初始点x(1)和向量P=-f (X)出发，由X(k

6、1)= xk kPk Jk = min f(X kP(k)=C f(X(k)Tp(k)(p(k)T Ap(k)和 P(k1) f(x(k1)kP(kk v f(X(k 1) A (P(k)T(p(k)T ap (k)(k =1,2, ,n -1)可以得到一一能够证明向量一一是线性无关的, 则 为 的极小点。且关于A是两两共轭的。从而可得到计算步骤:(1)对任意初始点 X En和向量P-、f(X)，取k =1;(2)若f(X(k) =0，即得到最优解，停止计算，否则求X (k 1)=Xk kPk, k = min f(X(k) kP(k) =" f(X ) P(p(k)T AP(k)P

7、(k D一屮x(k1)kP(k)kU(X(k1)A(P(k)T(p(k)TAp(k)(k =1,2,n -1)(3)令 k = k 1 ；返回(2)2.1.5牛顿法对于问题：1 min f(X) XtAX BtX c2由l f(X)二AX，B=0,则由最优条件、f(X)=0,当A为正定时，A，存在，于是有X -a4b为最优解2.1.6拟牛顿法对于一般的二阶可微函数f (X)，在X(k)点的局部有f(X) ： f(x(k)厂 I f (X(k)T(X -x(k) 2(X _X(k)Tl 2f(x(k)(X _x(k)2当i2f(x(k)正定时，也可用上面的牛顿法，这就是拟牛顿法。计算步骤：(1)

8、 任取 x(1) En，k =1;(2) 计算gk八f(X(k)，若gk =0,则停止计算，否则计算H(Xk)八2f(X(k)，令 X(k1) =Xk (H(Xk)gk ；(3) 令 k =k 1 ；返回(2)2有约束的非线性规划 2.1非线性规划的最优性条件 * *若X是非线性问题中的极小点，且对点 X有效约束的梯度线性无关，则必存在向量r =(丫；异；川沁；T使下述条件成立：mVf(X： Y洱gj(X“=0>gj X* =0, j =1,2,川,m強0, j =1,2,川,mI此条件为库恩-塔克条件(K-T条件)，满足K-T条件的点也称为K-T点。 K-T条件是非线性规划最重要的理论

9、基础，是确定某点是否为最优解的必 要条件，但不一定是充要条件。对于凸规划它一定是充要条件。2.2非线性规划的可行方向法由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优 解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某 个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局 最优解。假设Xk非线性规划问题中的一个可行解，但不是最优解，为了进一步寻找最优解在它的可行下降方向中选取其中一个方向D k，并确定最佳步长k，使得X（k41）=）十打 D（k）乏 Rf x k 1:： f X k ,k=0,1,2,川. 反复进行这一过程，直到得到满足精度要求为止，这种方法

10、称为可行方 向法，也称迭代法。2.3有约束非线性规划的解法2.3.1夕卜点法(1) 对于等式约束问题'min f (X),h(x) =0,i =1,2,m,做辅助函数mR(X,M) = f (X) +MW hf(X)j4如果最优解X ”满足或近似满足hi(X*) =0 (j -1,2 ,m),则X”就是问题的最优解或近似解(2) 对于不等式约束问题做辅助函数mF2(X,M)二 f(X) M' min0g(X)2求 min P2(X,M ).(3) 对于一般问题做辅助函数P3(X,M)二 f(X) MP(X)mmP(X)二 M' |hj2(X)|2 M min0g(X)2

11、jj m求解 min P3 (X, M)X2.3.2内点法内点法是在可行域内进行得，并一直保持在可行域内进行搜索，只适用 于不等式约束的问题辅助函数：Q(X,r)二 f(X) rB(X)X趋于R的边界时，使B(X)趋向于正无穷，B(X)的常用形式m 1B(X)八一1 z(x)m和B(X)=八1 ngj(X)j求解 min Q(X,r)X巩R0 =X | g j (X)0, j =1,2,m非线性规划的缺陷不足算法优点缺点梯度法计算量小，存储变量较少，初始点要求不咼初值依赖，收敛慢，最速下降法适用 于寻优过程的前期迭代或作为间插步 骤，越接近极值点时，收敛熟读越慢， 后期宜选用收敛快的算法牛顿法收敛速度很快当维数较高时，计算-0/(*1冷勺工作量很大，初值依赖，当初值选择 不好时，有可能计算出现异常，导致 迭代无法进行，该法需要修正拟牛顿法收敛速度快，避免牛顿矩阵求 逆运算，算法更稳定初值依赖程度相对牛顿法减弱，但仍然存在文明施工 依据业主、监理有关要求，落实施工组织文件，明确各工序管理、材料管理、机械