非线性规划模型

《非线性规划模型》由会员分享，可在线阅读，更多相关《非线性规划模型（9页珍藏版）》请在装配图网上搜索。

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

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

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

4、a,b的长度，来搜索得min f (t)的近似最优解的两个方法。通过缩短区间a,b，逐步搜 atb索得min f (t)的最优解t*的近似值at 0， k = ；(2)若 II Vf (Xk )|，则停止计算，X * = Xk，否则 P (k)二-Vf (Xk)；(3)在X (k)处沿方向P (k)做一维搜索得X (k+1)二Xk +X Pk,令k = k +1，返 k回第二步，直到求得最优解为止.可以求得：Vf (X(k)T Vf (X(k)Vf (X(k)T H(X(k)Vf (X(k)Vf (X (k)二(df (X (k)dxn12df (X (k)dxdf (X (k) df (X

5、(k)dxdxdf (X (k)df (X (k)dx，dx2ndf (X (k)H (X (k)=dx dx21df (X (k)dx dxn1df (X (k)df (X (k) dx dxdx dxn 2 n ndf (X (k)df (X (k)dx dx，dx dx2 2 2 n共轭梯度法又称共轭斜量法，仅适用于正定二次函数的极小值问题:1 minf (X)二 XtAX + BtX + c2A为n x n阶实对称正定阵X, B e En, c为常数从任意初始点X和向量P(1) =-Vf (X)出发，由X(k+1) = Xk + 九 Pk,九=min f (X(k)+ 九 P(k)=k

6、k”(Vf (X( k)tP( k)(P(k)T AP(k)P(k+1) = Vf (X (k+1) +卩 P(k),卩 和kk Vf (X (k+1) - A - (P(k)T(P (k) T AP (k)(k = 1,2,n 1)可以得到一一能够证明向量一一是线性无关的，且关于A是两两共轭的。从而可得到一,则为的极小点。计算步骤:(1)对任意初始点Xe En和向量P= Vf (X)，取k = 1;(2)若Vf (X (k) = 0，即得到最优解，停止计算，否则求X (k+1)=Xk + 九 Pk,九=minf (X(k)+ 九 P(k)=kkk(Vf (X (k )tP (k)(P(k)T

7、 AP(k)P (k+1) = Vf ( X (k+1) + P P (k), Pkk Vf (X (k+1) - A - (P(k)T(P (k) T AP (k)(k = 1,2,n 1)(3)令 k = k +1；返回(2)2.1.5 牛顿法 对于问题:min f (X)=1 XtAX + BtX + c2由Vf (X) = AX + B = 0,则由最优条件Vf (X) = 0,当A为正定时，A-1存在，于是有X * = A-1B为最优解2.1.6 拟牛顿法对于一般的二阶可微函数f (X)，在X(k)点的局部有f (X)沁 f (X(k) + Vf (X(k)T(X - X(k) +1

8、(X - X(k)T v2f (X(k)(X - X(k)2当V 2 f ( X (k)正定时，也可用上面的牛顿法，这就是拟牛顿法。计算步骤：(1) 任取 X (1) G En，k = 1；(2) 计算g = Vf (X(k)，若g = 0，则停止计算，否则计算kkH(Xk) = V2f (X(k)，令 X(k+1)= Xk - (H(Xk)-1 gk(3) 令k = k +1；返回(2)2 有约束的非线性规划2.1 非线性规划的最优性条件若 X *是非线性问题中的极小点，且对点 X *有效约束的梯度线性无关，则必存在向量r* =C*, Y *, Y *使下述条件成立：1 2 mVf（X *）

9、-兰 Y * V g （X * ）= 0 j jY *Vg（X* ）= 0, j = 1,2, ,m jjY * 0, j = 12 ,mjJ 此条件为库恩-塔克条件(K-T条.件)，满足K-T条件的点也称为K-T 点。K-T 条件是非线性规划最重要的理论基础，是确定某点是否为最优 解的必要条件，但不一定是充要条件。对于凸规划它一定是充要条件。2.2 非线性规划的可行方向法 由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的 最优解就是整个可行域上的全局最优解。非线性规划却不然，有时求出 的某个解虽是一部分可行域上的极值点，但并不一定是整个可行域上的 全局最优解。假设X (k)非线性规

10、划问题中的一个可行解，但不是最优解，为了进步寻找最优解在它的可行下降方向中选取其中一个方向D(k)，并确定最佳步长九，使得kX (k +1)= X (k)+ 九 D (k) E R f(X(k+1) 0, j = 1,2, m0j二非线性规划的缺陷不足算法优点缺点梯度法计算量小，存储变量较 少，初始点要求不咼初值依赖，收敛慢，最速下降法 适用于寻优过程的前期迭代或作为间 插步骤，越接近极值点时，收敛熟读 越慢，后期宜选用收敛快的算法牛顿法收敛速度很快当维数较咼时，计算-的工作量很大，初值依 赖，当初值选择不好时，有可能计算 出现异常，导致迭代无法进行，该法 需要修正拟牛顿法收敛速度快，避免牛顿矩 阵求逆运算，算法更稳定初值依赖程度相对牛顿法减弱，但仍然存在