非线性规划模型在上一次作业中，我们对线性规划模型进行了相应的介绍及优缺点，然而在实际问题中并不是所有的问题都可以利用线性规划模型求解。

实际问题中许多都可以归结为一个非线性规划问题，即如果目标函数和约束条件中包含有非线性函数，则这样的问题称为非线性规划问题。

一般来说，解决非线性的问题要比线性的问题难得多，不像线性规划有适用于一般情况的单纯形法。

对于线性规划来说，其可行域一般是一个凸集，只要存在最优解，则其最优解一定在可行域的边界上达到；对于非线性规划，即使是存在最优解，却是可以在可行域的任一点达到，因此，对于非线性规划模型，迄今为止还没有一种适用于一般情况的求解方法，我们在本文中也只是介绍了几个比较常用的几个求解方法。

一、非线性规划的分类1无约束的非线性规划当问题没有约束条件时，即求多元函数的极值问题，一般模型为I r m i n f(X)X 一0此类问题即为无约束的非线性规划问题1.1无约束非线性规划的解法1.1.1 一般迭代法即为可行方向法。

对于问题J mnf(X)[X X O给出f (X)的极小点的初始值X(O),按某种规律计算出一系列的X(k)(k =1,2,…)，希望点阵｛X (k)｝的极限X "就是f (X)的一个极小点。

由一个解向量X(k)求出另一个新的解向量X(kI)向量是由方向和长度确定的，所以XZ I)=X k「k P k(k =12…)即求解A和P k,选择'k和P k的原则是使目标函数在点阵上的值逐步减小，即f (X0) 一f (X1) 一- f (X k) 一.检验｛X(k)｝是否收敛与最优解，及对于给定的精度；7,是否IIlf(X k JlF ；1.1.2 一维搜索法当用迭代法求函数的极小点时，常常用到一维搜索，即沿某一已知方向求目标函数的极小点。

一维搜索的方法很多，常用的有：(1)试探法(“成功一失败”，斐波那契法，0.618法等)；(2)插值法(抛物线插值法，三次插值法等)；(3)微积分中的求根法(切线法，二分法等)。

考虑一维极小化问题a¾f(t)若f (t)是[a,b]区间上的下单峰函数，我们介绍通过不断地缩短[a,b]的长度，来搜索得min f(t)的近似最优解的两个方法。

通过缩短区间 [a,b],逐步搜索得 a 空 m t in f (t)的最优解t *的近似值a-≤ιb2.1.3 梯度法选择一个使函数值下降速度最快的的方向。

把f(x)在X (IO点的方向导数最小的方向作为搜索方向，即令 P k——∖f (X k).计算步骤：(1) 选定初始点 X 0和给定的要求；∙0，k=0 ；(2) 若 |八 f(X k)* ;,则停止计算，X^X k,否则 P(k)=-V f(X k)；(3)在X (k)处沿方向P (I)做一维搜索得x (jI)=X k…k P k,令k = kT ,返回 第二步，直到求得最优解为止.可以求得：、_ Vf(X(I))¼ V f (X (I)) ^Vf(X (I))T.H(X (I)^V f(X (I)).2.1.4共轭梯度法又称共轭斜量法，仅适用于正定二次函数的极小值问题：1min f(X) = X TAX B TX C2A 为n n 阶实对称正定阵 X,B ∙ E n,c 为常数从任意初始点X (I)和向量P(I)= -f (X ⑴)出发，由(f (X (I))δχ所(X(I))…<f(X (I)))TCX nCX 2「济(X (I)) 商(X(I))…CF(X(I))I、 JCX 1ZVJ% EX n Cf(X (I)) 商(X (I))…Gr(X (I))cx 2^x 1- CX 2CX 2 ,≡CX 2C X n-Cf(X (I)) 伊(X (I))… GF(X (I)) CX n CX I~!CX^X 2'EXnEX nH(X (I))二If(X (I)) =(k “2 ,n -1)可以得到一一能够证明向量一一是线性无关的，且关于 A 是两两共轭的。

从而可得到则 为 的极小点。

计算步骤:(1)对任意初始点X(I)∙E n和向量P ⑴-f (X ⑴)，取k = 1;(2)若If (X (I)) =0,即得到最优解，停止计算，否则求(k =1,2,…,n -1)(3)令 k =k 1 ；返回(2)2.1.5 牛顿法对于问题：1 min f(X) X TAX B TX C2由I f(X)=AX ∙B=0,则由最优条件'f(X) =0,当A 为正定时，Ad 存在，于是有X^ -A 4B 为最优解2.1.6 拟牛顿法对于一般的二阶可微函数f (X),在X (I)点的局部有f(X) ： f(X (I)Γ If(X (I))T(X _ X (I)) ∙ 1(X _ X (I))TI 2f(X (I))(^X (I))2当√f(X Ck))正定时，也可用上面的牛顿法，这就是拟牛顿法。

X (k D =X k kP k k= min f (x (k)kP (k ))=Cf(X (k )))T p (k )(P (G )T AP (k)和 P (k I)-f (x (k I)) —P (k「kVf(X (k I)) A (P (Io )T(P (k))TAP(k)X (k 1) = X k kP k, k= min f(X (I) kP (I))=" f(X )) P (P (I))TAP(I)P (k D一屮x (k1))「k P (k)「kU(X (II))A (P (I))T(P (I))TAP(I)计算步骤：(1)任取 X(I)∙E n，k =1;(2)计算g1.八f(X(k)),若g k =0 ,则停止计算，否则计算H(X k)八2f(X(k))，令 X(k I)=X k-(H(X k))S k ；(3)令 k =k 1 ；返回(2)2有约束的非线性规划2.1非线性规划的最优性条件… * *若X是非线性问题中的极小点，且对点 X有效约束的梯度线性无关，则必存在向量r =(丫；异；川I,Y m T使下述条件成立：「mH(X h—z Y浮gj(X"=0Ag j X* =0, j =1,2V* ≥0, j =1,2^∣,mI此条件为库恩-塔克条件(K-T条件)，满足K-T条件的点也称为K-T点。

K-T条件是非线性规划最重要的理论基础，是确定某点是否为最优解的必要条件，但不一定是充要条件。

对于凸规划它一定是充要条件。

2.2非线性规划的可行方向法由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域上的全局最优解。

非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的全局最优解。

假设X k非线性规划问题中的一个可行解，但不是最优解，为了进一步寻找最优解在它的可行下降方向中选取其中一个方向 D k,并确定最佳步长,k,使得[χ(k4τ)= χ(k)十打D(k)w R,k=0,1,2,川.f X k 1： f X k反复进行这一过程，直到得到满足精度要求为止，这种方法称为可行方向法，也称迭代法。

2.3有约束非线性规划的解法2.3.1 外点法(1)对于等式约束问题p^min f (X), Jh(X)=O,i =1,2,…m,做辅助函数mR(X,M) = f (X) +M W h f(X)j4如果最优解X ”满足或近似满足h i(X*) =0 (j =d,2,…,m),则X ”就是问题的最优解或近似解(2)对于不等式约束问题做辅助函数mF2(X,M) = f(X) M' [min{0g(X)}]2j^求mjn P2(X,M ).(3)对于一般问题做辅助函数P3(X,M) = f(X) MP(X)m mP(X)=M' ∣h j2(X) I2M^ [min{0g(X)}]2j j m求解min P3 (X, M)X2.3.2 内点法内点法是在可行域内进行得，并一直保持在可行域内进行搜索，只适用于不等式约束的问题辅助函数：Q(X,r) = f(X) rB(X)X趋于R的边界时，使B(X)趋向于正无穷，B(X)的常用形式mIB(X)八一1Ug j(X)m和B(X)-'I n[g j(X)]j^求解 min Q(X,r)X巩R0 ={X Ig j(X) 0, j =1,2, ,m}•非线性规划的缺陷不足。