非线性规划模型

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

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

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

4、间 a,b ，逐步搜索得 a <<min f (t) 的最优解 t *的近似值a 咗辿选择一个使函数值下降速度最快的的方向。把作为搜索方向，即令 Pk = -f(X k).f(x) 在 X(k) 点的方向导数最小的方向计算步骤：(1) 选定初始点 X0 和给定的要求； 0，k = 0 ； 假设f (X k)|卜：；，那么停止计算，X* = Xk,否那么Pk) - f (X k)；(3)在Xk)处沿方向Pk)做一维搜索得Xi1=XkP,令k=kT,返回第 二步，直到求得最优解为止 . 可以求得：2.1.4 共轭梯度法又称共轭斜量法，仅适用于正定二次函数的极小值问题：A为n n阶实对称

5、正定阵X,B? En,c为常数从任意初始点X(i)和向量P二ff(X)出发，由if(X (k 鋼 A (P 鋼T(p(k)T AP)PC1)_If (X* d)p .-kPk), -k 二 和(k =1,2, , n-1)可以得到一一能够证明向量一一是线性无关的，那么 且关于A是两两共轭的。从而可得到 为的极小点。计算步骤:(1 )对任意初始点X(i). E和向量P(i)-f (X)，取k = 1;(2)假设f(X (k) =0，即得到最优解，停止计算，否那么求(3)令 k 二 k ? 1 ；返回(2)对于问题:由I f(X)二AX, B=0,那么由最优条件'、f(X)=0,当A为正定

6、时，A存在，于是有X = -A B为最优解对于一般的二阶可微函数f(X)，在Xk)点的局部有当12f(X (k)正定时，也可用上面的牛顿法，这就是拟牛顿法。计算步骤：(1) 任取 X(1) ? En，k 二 1;(2) 计算 gk八f(X (k)，假设 gk =0,那么停止计算，否那么计算 H(Xk)八2f(X (k)，令 X(k1) =Xk-(H(X k)'g k ；(3) 令 k =k 1 ;返回(2)2有约束的非线性规划2.1非线性规划的最优性条件假设X*是非线性问题中的极小点，且对点 X*有效约束的梯度线性无关，那么必存在向量* = (丫； , ？；，川,休T使下述条件成立：此

7、条件为库恩 -塔克条件( K-T 条件)，满足 K-T 条件的点也称为 K-T 点。K-T 条件是非线性规划最重要的理论根底，是确定某点是否为最优解的必要条件，但不一定是充要条件。对于凸规划它一定是充要条件。2.2 非线性规划的可行方向法由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优 解就是整个 可行域上的全局最优解。非线性规划却不然，有时求出的某 个解虽是一局部可行域 上的极值点，但并不一定是整个可行域上的全局 最优解。假设xk非线性规划问题中的一个可行解，但不是最优解，为了进一步寻找最优解在它的可行下降方向中选取其中一个方向D k，并确定最正确步长 k，使得反复进行这一过程

8、，直到得到满足精度要求为止，这种方法称为可行方 向法，也称 迭代法。2.3 有约束非线性规划的解法2.3.1 外点法(1) 对于等式约束问题做辅助函数如果最优解X 满足或近似满足此(用)=0(j -1,2/ ,m ),那么X就是问题的最优解或近似解(2) 对于不等式约束问题做辅助函数求 min P2(X,M ).X(3) 对于一般问题做辅助函数 求解 min P3(X, M)X内点法内点法是在可行域内进行得，并一直保持在可行域内进行搜索，只适用于不等式约束的问题辅助函数：X趋于R的边界时，使B(X)趋向于正无穷，B(X)的常用形式求解mi n Q(X,r)R 二X | g(X) ? 0, j = 1,2, ,m?非线性规划的缺陷缺乏算法优点缺点梯度法计算量小，存储变量较少，初始点要求不咼初值依赖，收敛慢，最速下降法适用 于寻 优过程的前期迭代或作为间插步 骤，越接 近极值点时，收敛熟读越慢，