非线性规划模型

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

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

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

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

5、)x 'f(X(k)X2，f(X(k)T'Xnf (X(k)f (X(k)f (X(k)X1'X2 ''Xnf (X(k)f (X(k)f (X(k)H(X(k)x2 x1 'x2 x2 ''X2 Xnf(X(k)f(X(k)f(X(k)Xn X1'Xn X2''Xn Xn2.1.4共轭梯度法又称共轭斜量法，仅适用于正定二次函数的极小值问题:1min f(X) XtAX BtX c2A为n n阶实对称正定阵 X,B En,c为常数从任意初始点X (1)和向量Pf(X)出发，由X(k1)XkkPk, kmin

6、f(X(k)kP(k)(f (X(k)Tp(k)(P(k)T AP(k)P(k 1)和Pf (X(k 1)kP(k)f (X(k 1) A (P(k)T(P(k)T AP(k)(k 1,2, ,n 1)可以得到一一能够证明向量一一是线性无关的,则 为 的极小点。计算步骤：且关于A是两两共轭的。从而可得到(1)对任意初始点X En和向量Pf(X )，取 k 1;(2)若f(X(k)0，即得到最优解，停止计算，否则求X(k 1)kkX kP , k minf(X(k)P(k)( f(X(k)TP(k)kP ) (P(k)TAP(k)p(k 1)f (X(k 1)kp(k)f (X(k 1) A (

7、P(k)T(P(k)T AP(k)(3 )令2.1.5(k 1,2, ,nk 1 ；返回(2)牛顿法1)对于问题：1 tTmin f (X) X 1 AX B1 X c2由f(X) AX B 0,则由最优条件 f (X) 0,当A为正定时，A 1存在，于是有X A 1B为最优解2.1.6 拟牛顿法 对于一般的二阶可微函数f(X)，在X(k)点的局部有f(X) f(X(k) f(X(k)T(X X(k)(X X(k)T 2f(X(k)(X X(k)2当2f(X(k)正定时，也可用上面的牛顿法，这就是拟牛顿法。计算步骤：(1)任取 X En，k 1;(2)计算gkf(X(k)，若gk 0,则停止计

8、算，否则计算H(xk)2f(X(k)，令 X(k 1) X k(H(Xk) 1gk ；（3）令 k k 1 ；返回（2）2有约束的非线性规划2.1非线性规划的最优性条件若X*是非线性问题中的极小点，且对点 X*有效约束的梯度线性无关,则必存在向量1 , 2丄,m使下述条件成立：m* * *f Xj gj X 0j 1* gj X*0, j 1,2,L ,m* 0, j 1,2,L ,m此条件为库恩-塔克条件（K-T条件），满足K-T条件的点也称为K-T点。K-T条件是非线性规划最重要的理论基础，是确定某点是否为最优解的 必要条件，但不一定是充要条件。对于凸规划它一定是充要条件。2.2非线性规划

9、的可行方向法由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优 解就是整个可行域上的全局最优解。非线性规划却不然，有时求出的某 个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局 最优解。假设xk非线性规划问题中的一个可行解，但不是最优解，为了进一步寻找最优解在它的可行下降方向中选取其中一个方向D k，并确定最佳 步长k，使得X k1XkkD kf Xk1XkR,k 0,1,2,L反复进行这一过程，直到得到满足精度要求为止， 向法，也称迭代法。2.3 有约束非线性规划的解法2.3.1 外点法(1)对于等式约束问题min f (X), hi (x) 0,i 1,2, m,

10、做辅助函数m P1(X,M ) f (X) M hj2(X)j1如果最优解 X 满足或近似满足 hi (X * ) 0 (j 1,2, 最优解或近似解(2)对于不等式约束问题做辅助函数mP2(X,M ) f (X ) M min 0,gj (X) 2 j1求 min P2(X,M ).X(3)对于一般问题做辅助函数P3(X,M ) f (X ) MP(X)这种方法称为可行方,m),则X就是问题的P(X)mm22M|hj2(X)|2 M min 0,gj(X)j 1 j 1求解 min P3 (X,M)X2.3.2 内点法内点法是在可行域内进行得，并一直保持在可行域内进行搜索，只适用 于不等式约束的问题辅助函数：Q(X,r) f(X) rB(X)X趋于R的边界时，使B(X)趋向于正无穷，B(X)的常用形式m imB(X) 和 B(X) - In gj(X)j i gj(X)j i求解 mi nQ(X,r)R。X |gj(X) 0, j 1,2, , mX Ro非线性规划的缺陷不足算法优点缺点梯度法计算量小，存储变量较少，初始点要求不咼初值依赖，收敛慢，