四非线性规划

《四非线性规划》由会员分享，可在线阅读，更多相关《四非线性规划（35页珍藏版）》请在金锄头文库上搜索。

1、四*、非线性规划 n第7章 无约束问题 n第8章 约束极值问题清华大学出版社清华大学出版社1 引 言v在科学管理和其他领域中，很多实际问题可归结为线性规划问题。但也有很多问题，其目标函数和(或)约束条件很难用线性函数表达。如果目标函数或约束条件中含有非线性函数，就称这种问题为非线性规划问题。v解这类问题需要用非线性规划方法。目前，非线性规划已成为运筹学一个重要分支，在最优设计、管理科学、系统控制等许多领域得到越来越广泛的应用。v一般说来，由于非线性函数的复杂性，解非线性规划问题要比解线性规划问题困难得多。而且，也不像线性规划那样有单纯形法等通用方法。非线性规划目前还没有适于各种问题的一般性算法

2、，各个方法都有自己特定的适用范围。清华大学出版社清华大学出版社2第7章 无约束问题n第1节 基本概念n第2节 一维搜索n第3节 无约束极值问题的解法清华大学出版社清华大学出版社3第1节 基本概念v1.1 引言1. 问题的提出 例例1 某公司经营两种产品，第一种产品每件售价30元，第二种产品每件售价450元。根据统计，售出一件第一种产品所需要的服务时间平均是0.5小时，第二种产品是(2+0.25x2)小时，其中x2是第二种产品的售出数量。已知该公司在这段时间内的总服务时间为800小时，试决定使其营业额最大的营业计划。设该公司计划经营第一种产品x1件，第二种产品x2件。根据题意，其营业额为由于服务

3、时间的限制，该计划必须满足此外，这个问题还应满足 ，得到本问题数学模型为：清华大学出版社清华大学出版社4第1节 基本概念例例2 为了进行多属性问题(假设有n个属性)的综合评价，需要确定每个属 性的相对重要性，即求它们的权重。为此将各属性的重要性进行两两比 较，从而得出如下判断矩阵其中元素是第i个属性的重要性与第j个属性的重要性之比。为了使 在最小二乘意义上能最好反映判断矩阵的估计，由，可得 现需从判断矩阵求出各属性的权重清华大学出版社清华大学出版社5第1节 基本概念2非线性规划问题的数学模型非线性规划的数学模型常表示成以下形式其中自变量是n维欧氏空间中的向量(点)；为目标函数，和为约束条件。

4、清华大学出版社清华大学出版社6第1节 基本概念由于当需使目标函数极大化时，只需使其负值极小化即可。因而仅考虑目标函数极小化，这无损于一般性。若某约束条件是“”不等式时，仅需用“-1”乘该约束的两端，即可将这个约束变为“”的形式。由于等式约束等价于下述两个不等式约束：因而，也可将非线性规划的数学模型写成以下形式清华大学出版社清华大学出版社7第1节 基本概念3非线性规划问题的图示 图示法可以给人以直观概念，当只有两个自变量时，非线性规划问题也可像线性规划那样用图示法来表示(如图6-1所示)。考虑非线性规划问题若令其目标函数其中c为某一常数，则(6-8)式代表目标函数值等于c的点的集合，它一般为一条

5、曲线或一张曲面，通常称其为等值线或等值面。对于这个例子来说，若令目标函数(6-6)式分别等于2和4，就得到相应的两条圆形等值线(图6-1)。由图可见，等值线f(X)=2和约束条件直线AB 相切，切点D即为此问题的最优解：最优解：x1*=x2*=3，其目标函数值f(X*)=2。清华大学出版社清华大学出版社8第1节 基本概念图6-1在这个例子中，约束条件(6-7)式对最优解是有影响的。现若以代替约束条件(6-7)式，则非线性规划问题(6-6)式、(6-9)式的最优解是x1=x2=2，即图6-1中的C点(这时f(X)=0)。由于最优点位于可行域的内部，故对这个问题的最优解来说，约束(6-9)式事实上

6、是不起作用的。在求这个问题的最优解时，可不考虑约束条件(6-9)式，就相当于没有这个约束一样。由第一章知道，如果线性规划问题的最优解存在，其最优解只能在其可行域的边界上达到(特别是在可行域的顶点上达到)；而非线性规划问题的最优解(如果最优解存在)则可能在其可行域中的任意一点达到。清华大学出版社清华大学出版社9第1节 基本概念v1.2 极值问题极值问题1局部极值和全局极值 由于线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是在整个可行域上的全局最优解。非线性规划却不然，有时求出的某个解虽是一部分可行域上的极值点，但却并不一定是整个可行域上的全局最优解。清华大学出版社清华大学出版社

7、10第1节 基本概念设f(X)为定义在n维欧式空间En的某一区域R上的n元函数，其中。对于，如果存在某个，使所有与的距离小于的(即且)均满足不等式，则称为在R上的局部极小点局部极小点(或相对极小点)，为局部极小值局部极小值。若对于所有且与的距离小于的，则称为在R上的严格局格极小点严格局格极小点，为严格局部极小值严格局部极小值。 若点，而对于所有都有，则称为在R上的全局极小点全局极小点，为全局极小值全局极小值。若对于所有且，都有，则称为在R上的严格全局极小点，严格全局极小点，为严格全局极小值。严格全局极小值。清华大学出版社清华大学出版社11第1节 基本概念2极值点存在的条件定理定理1 (一阶必要

8、条件)设R是n维欧式空间En上的某一开集，f(X)在R上有一阶连续偏导数，且在点取得局部极值，则必有或上式中为函数f(X)在点X*处的梯度。清华大学出版社清华大学出版社12第1节 基本概念2极值点存在的条件定理定理2 (二阶必要条件)设R是n维欧式空间En上的某一开集，f(X)在R上有二阶连续偏导数，且在点取得局部极小值，则X*为驻点，即梯度且二阶Hesse阵 半正定清华大学出版社清华大学出版社13第1节 基本概念定理定理3(二阶充分条件)设R是n维欧式空间En上的某一开集，f(X)在R上有二阶连续偏导数，若，且对任何非零向量有则X*为f(X)的严格局部极小点。此处H(X*)为f(X)在点X*

9、处的海赛海赛(Hesse)矩阵：矩阵：清华大学出版社清华大学出版社14第2节 下降迭代算法v为了求某可微函数(假定无约束)的最优解，根据前面的叙述，可如下进行：v令该函数的梯度等于零，由此求得平稳点；v然后用充分条件进行判别，求出所要的解。v对某些较简单的函数，这样做有时是可行的；v但对一般n元函数f(X)来说，由条件f(X)=0得到的常是一个非线性方程组，解它相当困难。对于不可微函数，当然谈不上使用这样的方法。为此，常直接使用迭代法。清华大学出版社清华大学出版社15第2节 下降迭代算法迭代法的基本思想：迭代法的基本思想：为了求函数f(X)的最优解，首先给定一个初始估计，然后按某种规划(即算法

10、)找出比更好的解对极小化问题，对极大化问题，再按此种规则找出比更好的解，。如此即可得到一个解的序列。若这个解序列有极限，即则称它收敛于X*。若算法是有效的，则它产生的解的序列将收敛于该问题的最优解。但由于计算机只能进行有限次迭代，一般很难得到准确解，而只能得到近似解。当达到满足的精度要求后，即可停止迭代。清华大学出版社清华大学出版社16第2节 下降迭代算法现假定已迭代到点(见图6-5)，若从出发沿任何方向移动都不能使目标函数值下降，则是一局部极小点，迭代停止。若从出发至少存在一个方向可使目标函数值有所下降，则可选定能使目标函数值下降的某方向，沿这个方向迈进适当的一步，得到下一个迭代点 ，并使。

11、这相当于在射线上选定新点其中，称为搜索方向；称为步长或步长因子。图6-5 清华大学出版社清华大学出版社17第2节 下降迭代算法下降迭代算法的步骤：下降迭代算法的步骤：(1) 选定某一初始点，并令(2) 确定搜索方向(3) 从出发，沿方向求步长，以产生下一个迭代点(4) 检查得到的新点是否为极小点或近似极小点。，转回(2)继续进行迭代。在以上步骤中，选取搜索方向是最关键的一步，各种算法的区分，主要在于确定搜索方向的方法不同。 若是，则停止迭代。否则，令清华大学出版社清华大学出版社18第2节 下降迭代算法确定步长的的方法。)，这样做不能保证目标函数值下降。 (3)第三种方法是基于沿搜索方向使目标函

12、数值下降最多，即沿射线求目标函数f(X)的极小：由于这项工作是求以为变量的一元函数的极小点，故常称这一过程为一维搜索或线搜索，确定的步长为最佳步长。 (1) 令它等于某一常数(例如令(2) 第二种称为可接受点算法，只要能使目标函数值下降，可任意选取步长清华大学出版社清华大学出版社19第2节 下降迭代算法vfminunc函数vMATLAB求解无约束优化问题的主要函数vx = fminunc(fun, x0)vx, fval = fminunc(fun, x0)vx, fval, exitFlag, output, grad, hessian =fminunc(fun, x0, options)v

13、fun：目标函数；x0：初始解；options：参数设置vx：最优解；fval：最优点函数值vexitFlag：函数结束信息voutput：函数基本信息，包括迭代次数、目标最大计算次数、使用的算法、计算规模等vgrad：最优点的导数；hessian：最优点二阶导数第2节 下降迭代算法例：求Banana function的极小值点极小值点为极小值点为(1,1)(1,1)，对应的函数值为，对应的函数值为0 0第2节 下降迭代算法function f=BanaFun(x)% 不含导数解析式f=100*(x(2)-x(1)2)2+(1-x(1)2;function f,g=BanaFunWithGra

14、d(x)% 含导数解析式f=100*(x(2)-x(1)2)2+(1-x(1)2;g=100*(4*x(1)3-4*x(1)*x(2)+2*x(1)-2 100*(2*x(2)-2*x(1)2)第2节 下降迭代算法x=-1.9 2;x, fval=fminunc(BanaFuncWithGrad, x)x = -0.9634 0.9372fval=3.8632x, fval=fminunc(BanaFunc, x)x = -1.2553 1.5640fval=5.1002第3节 无约束极值问题的解法 v本节研究无约束极值问题: min f(X) XEn (6-40)前面曾指出，在求解上述问题时

15、常使用迭代法。迭代法可大体分为两类。o一类要用到函数的一阶导数和(或)二阶导数，由于用到了函数的解析性质，故称为解析法；o另一类在迭代过程中仅用到函数值，而不要求函数的解析性质，这类方法称为直接法。一般说来，直接法的收敛速度较慢，只是在变量较少时才适用。但是直接法的迭代步骤简单，特别是当目标函数的解析表达式十分复杂，甚至写不出具体表达式时，它们的导数很难求得，或者根本不存在，这时解析法就无能为力了。本节仅介绍几种常用的基本方法，其中前三种属解析法，后面一种属直接法。清华大学出版社清华大学出版社243.1 梯度法(最速下降法)v1. 梯度法的基本原理假定无约束极值问题(6-40)式中的目标函数f

16、(X)有一阶连续偏导数，具有极小点X*。以表示极小点的第k次近似，为了求其第k+1次近似点，我们在点沿方向做射线射线现将 f(X) 在点处展成泰勒级数其中对于充分小的，只要即可保证。这时若取就能使目标函数值得到改善。清华大学出版社清华大学出版社253.1 梯度法(最速下降法)现考查不同的方向。假定的模一定(且不为零)，并设 (否则，是平稳点)，使式(6-41)成立的有无限多个。为了使目标函数值能得到尽量大的改善，必须寻求使取最小值的。由线性代数知道式中为向量与的夹角。当与反向时，这时(6-41)式成立，而且其左端取最小值。我们称方向为负梯度方向，负梯度方向，它是使函数值下降最快的方向(在的某一

17、小范围内)。清华大学出版社清华大学出版社263.1 梯度法(最速下降法)为了得到下一个近似极小点，在选定了搜索方向之后，还要确定步长 。当采用可接受点算法时，就是取某一进行试算，看是否满足不等式 若上述不等式成立，就可以迭代下去。否则，缩小使满足不等式(6-43)式。由于采用负梯度方向，满足(6-43)式的总是存在的。另一种方法是通过在负梯度方向的一维搜索，来确定使f(X)最小的k，这种梯度法就是所谓最速下降法。清华大学出版社清华大学出版社273.1 梯度法(最速下降法)2. 计算步骤(1) 给定初始近似点及精度，若，则即为近似极小点。，求步长，并计算 求步长可用一维搜索法、微分法或试算法。

18、若求最佳步长，则应使用前两种方法。(3) 一般地，设已迭代到点，若，则即为所求的近似解；若，则求步长，并确定下一个近似点如此继续，直至达到要求的精度为止。(2) 若清华大学出版社清华大学出版社283.1 梯度法(最速下降法)若具有二阶连续偏导数，在作的泰勒展开：对求导并令其等于零，则得近似最佳步长可见近似最佳步长不只与梯度有关，而且也与海赛矩阵H有关。确定步长 也可不用公式(6-45)，而采用任一种一维搜索法。的模规格化为1，在这种情况下同时，式(6-45)变为有时，将搜索方向清华大学出版社清华大学出版社293.2 变尺度法v变尺度法是近30多年来发展起来的，它是求解无约束极值问题的一种有效方

19、法。由于它既避免了计算二阶导数矩阵及其求逆过程，又比梯度法的收敛速度快，特别是对高维问题具有显著的优越性，因而使变尺度法获得了很高的声誉，至今仍被公认为求解无约束极值问题最有效的算法之一。清华大学出版社清华大学出版社303.2 变尺度法变尺度法的计算步骤：(1) 给定初始点X(0)、初始矩阵H(0) ，计算g(0)，令k=0(2) 令p(k)=-H(k)g(k)(3) 由一维搜索(如0.618法)确定步长ak(4) 令x(k+1)=x(k)+akp(k)(5) 若|g(k+1)|误差限e，则x*=x(k+1)即为最优解，算法终止；否则令s(k)=x(k+1)-x(k),y(k)=g(k+1)-

20、g(k)(6) 由修正公式得到H(k+1)，令k=k+1转(2)清华大学出版社清华大学出版社313.2 变尺度法DFP修正公式：清华大学出版社清华大学出版社32BFGS修正公式： BFGS在理论上已证明具有全局收敛性，而DFP法尚未证明具有此性质。总体上来说，BGFS优于DFP3.2 变尺度法例：例：利用变尺度法求Banana函数的极小值点解：解：使用fminunc函数，将HessUpdate参数设置为dfp或bgfs即可options=optimset(HessUpdate, dfp)x, fval = fminunc(BanaFunWithGrad, x, options)x = 1.00

21、00 1.0000 fval = 1.2756e-09 options=optimset(HessUpdate, bgfs) x, fval = fminunc(BanaFunWithGrad, x, options)x = 0.9999 0.9998 fval = 1.1747e-08清华大学出版社清华大学出版社33第4节 直接算法v直接算法可以归为经验算法，不如迭代法有效v基本原则简明，有一定的技术实用性v单纯形法利用变换单纯形来求出极小点，是最常用的一种直接算法。v在单纯形法基础上，对非线性问题，1964年提出了改进的可变多面体算法vfminsearch函数利用此算法求解无约束优化问题x, fval = fminsearch(fun, x0, options)x, fval, exitflag, output = fminsearch()第4节 直接算法v例：例：利用fminsearch求Banana函数的极小值点vx0=-1.9 2;vx, fval = fminsearch(BanaFun, x0)x = 1.0000 1.0000fval = 4.0686e-10