水资源系统分析及应用：第四章 非线性数规划

1、第四章非线性规划 前面介绍了线性规划问题，即目标函数和约束条件都是线性函数的规划问题，但在实际工作中，还常常会遇到另一类更一般的规划问题，即目标函数和约束条件中至少有一个是非线性函数的规划问题，即非线性规划问题. 4.1 引言 事实上，客观世界中的问题许多是非线性的，给予线性大多是近似的，是在作了科学的假设和简化后得到的. 为了利用线性的知识，许多非线性问题常进行线性化处理. 但在实际问题中，有一些是不能进行线性化处理的，否则将严重影响模型对实际问题近似的可依赖型.线性规划问题在计算上常是困难的，理论上的讨论也不能像线性规划那样给出简洁的结果形式和全面透彻的结论. 这点又限制了非线性规划的应用

2、，所以，在数学建模时，要进行认真的分析，对实际问题进行合理的假设、简化，首先考虑用线性规划模型，若线性近似误差较大时，则考虑用非线性规划. 如果目标函数或约束条件中至少有一个是非线性函数时的最优化问题就叫做非线性规划问题。 与线性规划一样，非线性规划也是运筹学的一个重要分支，于 20 世纪 50 年代开始逐步形成，到20 世纪 70 年代开始处于兴旺发展时期。随着计算机技术的日益发展，很多领域越来越重视这门学科，应用非线性规划方法进行设计、管理等，非线性规划理论自身也得到了进一步的发展。非线性规划是20世纪50年代才开始形成的一门新兴学科。1951年H.W.库恩和A.W.塔克发表的关于最优性条

3、件（后来称为库恩塔克条件）的论文是非线性规划正式诞生的一个重要标志。在50年代还得出了可分离规划和二次规划的n种解法，它们大都是以G.B.丹齐克提出的解线性规划的单纯形法为基础的。50年代末到60年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。非线性规划在工程、管理、经济、科研、军事等方面都有广泛的应用，为最优设计提供了有力的工具。20世纪80年代以来，随着计算机技术的快速发展，非线性规划方法取得了长足进步，在信赖域法、稀疏拟牛顿法、并行计算、内点法和有限存储法等领域取得了丰硕的成果。 线性规划与非线性规划的区别如果线性规划的最优解存在，其最优解只能在其可行域的边界上

4、达到（特别是可行域的顶点上达到）；而非线性规划的最优解（如果最优解存在）则可能在其可行域的任意一点达到。非线性规划问题的标准形式为： 如果采用向量表示法，则线性规划的一般形式可以写成： min f(X) s.t. g(X) 0 h(X) = 0其中：g(X) = (g1(X), , gm(X)T， h(X) = (h1(X), , hl(X)T，至于求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式。 非线性规划模型按约束条件可分为以下三类： 无约束非线性规划模型： 等式约束非线性规划模型： 不等式约束非线性规划模型：1) 无约束的非线性规划问题.针对上述三类非

5、线性规划模型，其常用求解的基本思路可归纳如下： 在下降迭代算法中，搜索方向起着关键的作用，而当搜索方向确定后，步长又是决定算法好坏的重要因素. 非线性规划只含一个变量，即一维非线性规划可以用一维搜索方法求得最优解，一维搜索方法主要有进退法和黄金分割法. 二维的非线性规划也可以像解线性规划那样用图形求解. 对于二维非线性规划，使用搜索方法是要用到梯度的概念，最常用的搜索方法就是最速下降法.2) 只有等式约束的非线性规划问题通常可用消元法、拉格朗日乘子法或反函数法，将其化为无约束问题求解.3) 具有不等式约束的非线性规划问题解起来很复杂，求解这一类问题，通常将不等式化为等式约束，再将约束问题化为无

6、约束问题，用线性逼近的方法将非线性规划问题化为线性规划问题. 如果采用向量表示法，则线性规划的一般形式可以写成： min f(X) s.t. g(X) 0 h(X) = 0其中：g(X) = (g1(X), , gm(X)T， h(X) = (h1(X), , hl(X)T，至于求目标函数的最大值或约束条件为小于等于零的情况，都可通过取其相反数化为上述一般形式。 4.2 引例 引例 4.2.1 项目投资问题。有一投资者有资金 5000 美元和两个可能的投资项目，令 xj（j = 1, 2）表示他分配到投资项目 j 的资金（以千美元为单位）。从历史资料分析，投资项目 1 和 2 分别有预计的年收

7、益 20% 和 16%，同时与项目 1 和 2 有关的总的风险损失由总收益的方差来衡量，由式 2x12 + x22 + (x1+x2)2 给出，即风险损失随着总投资和单项投资的增加而增加。投资者希望使期望的收益为最大，同时使风险损失为最小，应怎样进行投资？ 建立模型：maxZ = 20 x1 + 16x2 2x12 + x22 + (x1 + x2)2 s.t. x1 + x2 5 x1, x2 0其中非负常数 反映风险损失和收益之间的权衡。 当 = 0 时，他将资金全部投到最大期望收益的项目，属冒险型； 当 时，期望回收的目标收益可以忽略不计，他主要考虑使风险损失为最小。 引例4.2.2 生

8、产计划问题。Carron（卡隆）化学公式年轻工程师 R 和 D 合成了一种轰动一时的新肥料，只用两种可互相替换的基本原料来制造。公司想利用这个机会生产尽可能多的这种新肥料，公司目前有资金 40000 美元，可购买单价分别为 8000 美元和 5000 美元的原料。当用数量为 x1 和 x2 两种原料合成时，肥料的数量Q 由下式给出：Q = 4x1 + 2x2 0.5x12 0.25x22 试确定购买原料的计划。 建立模型： max Q = 4x1 + 2x2 0.5x12 0.25x22 s.t. 8x1 + 5x2 40 x1, x2 0 引例4.2.3 供应与选址问题。某公司有 6 个建筑

9、工地要开工，每个工地的位置（用平面坐标系 a，b 表示，距离单位：千米）及水泥日用量 d（吨）由下表给出。目前有两个临时料场位于 A(5, 1)，B(2, 7)，日储量各有 20 吨。假设从料场到工地之间均有直线道路相连。123456a1.258.750.55.7537.25b1.250.754.7556.57.25d3547611 (1) 试制定每天的供应计划，即从 A，B 两料场分别向各工地运送多少吨水泥，使总的吨千米数最小。 (2) 为了进一步减少吨千米数，打算舍弃两个临时料场，改建两个新的，日储量各为 20吨，问应建在何处，节省的吨千米数有多大？ 建立模型：记工地的位置为 (ai，bi

10、)，水泥日用量为 di，i =1, , 6；料场位置为 (xj，yj)，日储量为 ej，j =1, 2；从料场 j 向工地 i 的运送量为 Xij。于是 当使用临时料场时，决策变量为：Xij（此时，x1 = 5，x2 = 2，y1 = 1，y2 = 7）； 当不使用临时料场时，决策变量为：Xij，xj，yj。下面通过实例归纳出非线性规划数学模型的一般形式，介绍有关非线性规划的基本概念。例1 （投资决策问题）某企业有n 个项目可供选择投资，并且至少要对其中一个项目投资。已知该企业拥有总资金 A元，投资于第i(i=1,2,3，n) 个项目需花资金a 元，并预计可收益 bi元。试选择最佳投资方案。解

11、 设投资决策变量为则投资总额为 ，投资总收益为 。因为该公司至少要对一个项目投资，并且总的投资金额不能超过总资金A ，故有限制条件另外， 由于 只取值0或1，所以还有最佳投资方案应是投资额最小而总收益最大的方案，所以这个最佳投资决策问题归结为总资金以及决策变量（取0或1）的限制条件下，极大化总收益和总投资之比。因此，其数学模型为：s.t.上面例题是在一组等式或不等式的约束下，求一个函数的最大值（或最小值）问题，其中目标函数或约束条件中至少有一个非线性函数，这类问题称之为非线性规划问题，简记为（NP）。可概括为一般形式其中 称为模型（NP）的决策变量， f称为目标函数， 和 称为约束函数。另外，

12、 称为等式约束， 称为不等式约束。对于一个实际问题，在把它归结成非线性规划问题时，一般要注意如下几点：（i）确定供选方案：首先要收集同问题有关的资料和数据，在全面熟悉问题的基础上，确认什么是问题的可供选择的方案，并用一组变量来表示它们。（ii）提出追求目标：经过资料分析，根据实际需要和可能，提出要追求极小化或极大化的目标。并且，运用各种科学和技术原理，把它表示成数学关系式。（iii）给出价值标准：在提出要追求的目标之后，要确立所考虑目标的“好”或“坏”的价值标准，并用某种数量形式来描述它。（iv）寻求限制条件：由于所追求的目标一般都要在一定的条件下取得极小化或极大化效果，因此还需要寻找出问题的

13、所有限制条件，这些条件通常用变量之间的一些不等式或等式来表示。例1 农业生产计划问题 某村计划在100公顷土地上种植A、B、C 三种农作物，可提供的劳力、粪肥和化肥等资源的数量，种植每公顷农作物所需这三种资源的数量以及获得的利润如表（1-1）所示：1.1 最优化问题的一般模型 33000 330063000资源 1800 30030900C 1200 40025600B 1500 35035450A利润（元）化肥（千克）粪肥（吨）用工其中一个劳动力干一天为1个工。试确定三种农作物的种植面积，使利润最大。下面分析怎样建立数学模型。设农作物A、B、C 的种植面积分别为 公顷，则总利润的表达式为：确

14、定种植面积时，资源限制有4种：1、土地限制，总的种植面积为100公顷，即2、劳力限制，种植三种农作物用工之和不能超过允许值63000个，即3、粪肥限制，即4、化肥限制，即此外，种植面积不能为负数，即因此，该问题的数学模型为：其中，max是maximize的简写，读作“极大化”，s.t.是subject to 的简写，读作“受限制于”或“约束条件是”。（1）称为目标函数，（2）（6）称为约束条件。例2 选址问题设有n个市场，第j个市场的位置 ，对某种货物的需要量 现计划建立m个货栈，第i个货栈的容量为试确定货栈的位置，是使个货栈到各市场的运输量与路程乘积之和最小。现在建立数学模型。设第i个货栈的

15、位置为：一般定义为：我们的目标函数是使运输量与路程乘积之和最小，如果距离按第一式定义，就是使最小。约束条件是：1. 每个货栈向各市场提供的货物量之和不能超过它的容量；2.每个市场得到的货物量之和等于它的需要量；3. 运输量不能为负数。因此，该问题的数学模型如下：最优化问题的数学一般形式为：其中要求连续可微。x称为决策变量，f(x)为目标函数，为约束函数，(1.1.1)min和s.t. 分别是英语单词minimize(极小化)和subject to (受约束)的缩写。 注意：最优化模型有不同的形式，但经过适当的变换都可以转换成上述的一般形式。目标函数 约束条件为等式约束，为不等式约束。4.3主要

16、内容非线性规划理论方面应用方面算法方面互补稳定灵敏对偶问题最优性条件无约束问题直接法有约束问题间接法 最优化问题分类1. 根据有无约束条件：2. 根据决策变量的取值是离散的或连续的：一般模型Min f(X)s.t. hi(X) = 0 (i=1,2,.m) （P） gj(X) 0 (j=1,2.l) X En f(X) hi(X) gj(X) 为En上的实函数。几个概念定义1 如果X满足（P）的约束条件 hi(X)=0 (i=1,2,.m) gj(X) 0 (j=1,2.l) 则称X En 为（P）的一个可行解。记（P）的所有可行解的集合为D，D称为（P）可行域。几个概念定义2 X*称为（P）

17、的一个（整体）最优解，如果X* D，满足 f(X) f(X*)， X D。 几个概念定义3 X*称为（P）的一个（局部）最优解，如果X* D，且存在一个X*的邻域N(X* ,)= X En X- X* 0满足 f(X) f(X*)， X D N(X* ,) f(X)局部最优解整体最优解模型分类Min f(X)s.t. hi(X)=0 (i=1,2,.m) （P） gj(X) 0 (j=1,2.l) X En f(X) hi(X) gj(X) 为En上的实函数。模型分类1 如果 f(X) hi(X) gj(X) 中至少有一个函数不是线性（仿射）函数，则称（P）为非线性问题。 如果 f(X) hi

18、(X) gj(X) 都是线性（仿射）函数，则称（P）为线性问题。模型分类2若m=l=0 ，则称（P）为无约束问题。 （P1） Min f(X) X En 模型分类2若m0，l=0 ，则称（P）为带等式约束问题。 （P2） Min f(X) s.t. hi(X)=0 (i=1,2,.m) X En 模型分类2若m=0，l 0 ，则称（P）为带不等式约束问题。 （P3） Min f(X) s.t. gj(X) 0 (j=1,2.l) X En 模型分类2若m 0，l 0 ，则称（P）为一般问题。 （P） Min f(X) s.t. hi(X)=0 (i=1,2,.m) gj(X) 0 (j=1,2

19、.l) X En 凸函数的概念凸集概念： 设D是n维线性空间En的一个点集，若D中的任意两点x(1),x(2)的连线上的一切点x仍在D中，则称D为凸集。即：若D中的任意两点x(1),x(2) D，存在01 使得x= x(1)+(1- )x(2) D,则称D为凸集称为的凸组合.例1. 集合例2. 集合为凸集.例3. 集合为凸集.其中,d是给定的非零向量,为定点.为凸集,其中,p为n维列向量, 为实数.凸集的性质:设 A 和 B为中两个凸集,是实数,则1. 为凸集.2.为凸集.3.为凸集.4.为凸集. 凸集的另一个重要性质是分离定理. 在最优化理论中,有些重要结论可用凸集分离定理来证明. 所谓集合

20、的分离,是指对于两个集合存在一个一个超平面如果超平面的方程为那么对应于H某一边的点x,定义2.1.6 为给后面证明凸集分离定理做准备,我们先给出闭凸集的一个显然的性质.定理2.1.2定理2.1.3 下面利用定理2.1.2证明点与凸集的分离定理.为此先给出点与闭凸集分离的一种形式.定理2.1.4推论定理 2.1.5下面: 用 表示闭包，用 表示集合 S 的闭包。凸函数的概念定义：定义在凸集DEn上的函数f(X)如果对任意两点x(1),x(2) D，均有0 0( 0 )则称H(X)在X* 点正定(半正定).如果 为 上的凸函数,则称 为 上的凹函数.例2.2.1 一元函数 是 上的凸函数.2.2.

21、2 凸函数的性质利用凸函数的定义不难验证下面的一些性质定理 2.2.1 设 是定义在 上的凸函数, 实数则也是定义在 上的凸函数. 定理2.2.3 设 是 中一个非空凸集, 是定义在 上的凸函数, 是一个实数,则水平集是凸集 定理2.2.2 设 是定义在凸集 上的凸函数,则 也是定义在 上的凸函数. 定理2.2.4 设 是 中一个非空凸集, 是定义在 上的凸函数,则 在 上的局部极小点是整体极小点,且极小点的集合为凸集.定理2.2.5 是一个凸函数, ,在处取有限值，则在沿任何方向的右侧导数及左侧导数都存在 定理2.2.6 设 是 中非空凸集, 是定义在 上的凸函数,则 在 上的局部极小点,且

22、极小点的集合为凸集.2.2.3 凸函数的判别 利用凸函数的定义及其有关性质可以判别一个函数是否为凸函数,但有时计算比较复杂,使用很不方便,因此需要一些研究凸函数的判别问题.在介绍可微函数的充要条件之前,先给出下列定义. 定义2.2.3 设函数 存在一阶便导数, ,则称向量为 在点处的梯度为 在点处的Hessian矩阵 定义2.2.4 设函数 存在二阶偏导数, ,则称矩阵海赛(Hesse)矩阵 xxf(X) = H(X)2f/x12 2f/x1x2 . 2f/x1xn2f/x2x1 2f/x22 . 2f/x2xn.2f/xnx1 2f/xnx2 . 2f/xn2= 定理2.2.7 设 是 中非

23、空开凸集, 是定义在 上可微函数,则 为凸函数的充要条件是对任意两点 ,都有 而 为严格凸函数的充要条件是对任意的互不相同的 ,成立 定理2.2.8 设 是 中非空开凸集, 是定义在 上的 二次可微函数,则 为凸函数 的充要条件是在每一点 处 Hessian矩阵半正定. 定理2.2.9 设 是 中非空开凸集, 是定义在 上的 二次可微函数, 如果每一点 处,Hessian矩阵正定,则 为严格凸函数. 定理2.2.9的证明可仿照定理2.2.8.值得注意,逆定理并不成立.若 是定义在 上的严格凸函数,则在每一点 处,Hessian 矩阵是半正定的. 利用以上几个定理容易判别一个可微函数 是否为凸函

24、数,特别是对于二次函数,用上述定理判别是很方便的. 例2.2.2 给定二次函数2 最优性条件最优性条件的研究是非线性规划理论研究的一个中心问题。为什么要研究最优性条件？本质上把可行解集合的范围缩小。它是许多算法设计的基础。3、最优性条件3.1 无约束问题的极值问题考虑非线性规划问题: 其中 是定义在 上的实函数.这个问题是求 在 维欧氏空间中的极小点,称为无约束极值问题.这是一个古典的极值问题,在微积分学中已经有所研究,那里给出了定义在几何空间上的实函数极值存在条件,这一节只是把已有理论在 维欧氏空间中加以推广.3.1.1 无约束极值问题 3.1.2 必要条件 定理3.1.1 设函数 在点 可

25、微,如果存在方向 ,使 ,则存在数 ,使得对每个 ,有 为研究函数 的极值条件,先介绍一个定理,它在后面的证明中将要多次用到. 定理3.1.2 设函数 在点 可微,若 是局部极小点,则梯度 定理3.1.3 设函数 在点 两次可微,若 是局部极小点,则梯度 ,并且Hessian矩阵 是半正定的. 3.1.3 充分条件 下面给出局部极小点的充分条件： 定理3.1.4 设 在点 处两次可微,若梯度 ,且Hessian矩阵 正定,则 是局部极小点. 3.1.4 充要条件 前面几个定理分别给出无约束极值的必要条件和充分条件,这些条件都不是充要条件,而且利用这些条件只能研究局部极小点.下面在函数凸性的假设

26、下,给出整体极小点的充要条件. 定理3.1.5 设 是定义在 上的可微凸函数, ,则 为整体极小点的充要条件是 . 例3.1.1 利用极值条件解下列问题: 例3.1.2 利用极值条件解下列问题:3.2 约束极值问题的最优性条件 3.2.1 约束极值问题 有约束的极值问题一般表示为 其中 称为不等式约束, 称为等式约束.集合(3.2.1)(3.2.2) 称为可行集或可行域. 由于在约束极值问题中,自变量的取值问题中,自变量的取值受到限制 , 目标函数在无约束情况下的平稳点(驻点)很可能不在可行域内 , 因此一般不能用无约束处理约束问题. 3.2.2 可行方向与下降方向 为增加直观性,下面先给出最

27、优性的几何条件,然后在给出它们的代数表示.为此引入可行方向与下降方向的概念. 先定义下降方向： 定义3.2.1 设 是定义在 上的实函数, , 是非零向量.若存在数 ,使得对每个 ,都有 则称 为函数 在 处的下降方向. 如果 是可微函数,且 ,根据定理3.1.1,显然 为 在 处的下降方向.这时记作这个集合在下面的讨论中将要用到. 下面定义可行域 的可行方向. 定义3.2.2 设集合 , , 是非零向量,若存在数 ,使得对每一个 ,都有则称 为集合 在 的可行方向.其中“ ”表示闭包， 即 的闭包。(3.2.3) 集合 在 处所有可行方向组成的集合称为在 处的可行方向锥。 由可行方向和下降方

28、向的定义可知，如果 是 在 上的局部极小点，则在 处的可行方向一定不是下降方向。 定理3.2.1 考虑问题设 是 中的非空集合， ， 在 处可微。如果 是局部最优解，则 。 其中 和 分别又式(3.2.3)和(3.2.4)定义。(3.2.4) 3.2.3 不等式约束问题的一阶最优性条件 考虑非线性规划问题:这个问题的可行域 为把最优性的几何条件用代数来表示, 我们引入起作用约束的概念. 问题(3.2.3)的约束条件,在点 处呈现两种情形: 有些约束,它们的下标集用 表示,成立等式,即 (3.2.3)(3.2.8)(3.2.9)取代定理3.2.1中的可行方向锥 . 定理3.2.2 设 , 和 在

29、 可微, 在 连续.如果 是问题(3.2.3)的局部最优解,则 定理3.2.3 (Fritz John条件) 设 , , , 在 处可微, 在 处连续,如果 是 (3.2.3)的局部最优解,则存在不全为零的非负数 , ,使得 例3.2.1 已知 是下列问题的最优解:验证在 满足Fritz John条件. 例3.2.2 给定非线性规划问题:验证在点 ,Fritz John条件成立.定理 （Kuhn-Tucker必要条件） 设f(X)和每个gj(X)在X*D点可微，每个hi(X)在X*D点连续可微,又设gj(X)( j J(X*)和hi(X) 线性无关,如果X* 为(P)的局部最优解,一定存在(u

30、1,u2,ul) 0和(v1,v2,vm),使得 f(X*)+ujgj(X* ) + vihi(X* ) =0gj(X* ) 0 uj gj(X* ) =0 j=1,2.lhi(X* ) =0 i=1,2.m定理 （ Kuhn-Tucker充分条件） 设f(X)和每个gj(X)都是En中的凸函数，每个gj(X) 都是线性函数，如果存在（u1,u2,ul) 0,和(v1,v2,vm),使得 f(X*)+ujgj(X* ) + vihi(X* ) =0gj(X* ) 0 uj gj(X* ) =0 j=1,2.lhi(X* ) =0 i=1,2.m则X* 为（P）的一个最优解。 例3.2.3 给定

31、非线性规划问题:验证下列两点是否为K-T点. 例3.2.4 给定非线性规划问题:求满足K-T条件的点 定理3.2.5 设在问题(3.2.3)中, 是凸函数, 是凹函数, 为可行域, , , 和 在点 可微, 在点 连续,且在 处K-T条件成立,则 为整体最优解.4、一维搜索 从这一节开始, 我们来研究非线性规划的具体算法.这里主要讨论一维搜索, 它是后面各章将要介绍的各种计算过程的重要组成部分.在实际应用中,一维搜索不仅需要大量时机,而且它的选择是否恰当对一些算法的计算效果有重要影响. 4.1 一维搜索概念 4.1.1 什么是一维搜索 在许多迭代下降算法中,具有一个共同点,这就是得到点 后,需

32、要按某种规则确定一个方向 ,再从 出发,沿方向 在直线(或射线)上求目标函数的极小点,从而得到 的后点 .重复以上做法,直至求得问题的解.这里所谓求目标函数在直线上的极小点,称为一维搜索,或称为线搜索. 一维搜索可归结为单变量函数的极小化问题. 设目标函数为 ,过点 沿方向 的直线可用点集来表示,记作(4.1.1)求 在直线 上的极小点转化为求一元函数(4.1.2)的极小点. 如果 的极小点为 ,通常称 为沿方向 的步长因子,或简称为步长,那么函数 在直线 上的极小点就是(4.1.3) 一维搜索的方法很多,归纳起来,大体可分成两类: 一类是试探法.采用这类方法,需要按某种方式找试探点,通过一系

33、列试探点来确定极小点. 另一类是函数逼近法,或称插值法. 这类方法是用某种较简单的曲线逼近本来的函数曲线, 通过求逼近函数的极小点来估计目标函数的极小点. 这两类方法一般只能求得极小点的近似值. 在一维搜索中,可能出现这样情形:在直线上存在多个极小点.这时可采取不同策略.可以选择第一个极小点,也可以从中选择最小点,甚至还可以从这若干个极小点中任意选择一个,只要这点的函数值不超过在点 的目标函数值即可. 4.2 试探法 4.2.1 0.618法(黄金分割法) 0.618法使用于单峰函数, 为阐述0.618法的原理, 需要引入单峰函数的概念. 定义4.2.1 设 是定义在闭区间 上的一元实函数,

34、是 在 上的极小点,并且对任意的 , ,有则称 是在闭区间 上的单峰函数. 单峰函数具有一个很有用的性质:通过计算区间 内二个不同点处的函数值,就能确定一个包含极小点的子区间. 定理4.2.1 设 是区间 上的单峰函数, , 则对每一个 ,有 . 0.618法的基本思想是,根据上述定理,通过取试探点使包含极小点的区间(不确定区间)不断缩短,当区间长度小到一定程度时,区间上各点的函数值均接近极小值,因此任意一点都可作为极小点的近似. 综上所述,运用0.618法,初始搜索区间记作 ,第1次迭代取两个试探点 ,以后每次迭代中,只需按照公式新计算一点.详细计算步骤如下: 1.置初始区间 及精度要求 ,

35、计算试探点 ,计算函数值 .计算公式是:令 . 2.若 ,则停止计算.否则,当 时,转步3.;当 时,转步4. 3.置 计算函数值 ,转步5.计算函数值 ,转步5. 4.置 5.置 ,返回步2. 例4.2.1 用0.618法解下列问题:初始区间 ,精度 前面已经指出,0.618法使用于单峰函数.但是,在实际问题中,目标函数在其定义域内不一定是单峰的,因此需要先确定单峰区间,然后再使用0.618法的计算公式.在现有的0.618法的程序中,一般具有这种功能. 4.2.2 Fibonacci法 这种方法与0.618法类似,也是用于单峰函数,在计算过程中,也是第1次迭代需要计算两个试探点,以后每次迭代

36、只需新算一点,另一点取自上次迭代.Fibonacci法与0.618法的主要区别之一在于区间长度缩短比率不是常数,而是所谓的Fibonacci数确定. 定义4.2.2 设有数列 ,满足条件:则称 为Fibonacci数列. 根据定义4.2.2,可将Fibonacci数列表如表4-2: Fibonacci法在迭代中计算试探点的公式:(4.2.12)(4.2.13)其中 是计算函数值的次数(不包括初始区间端点的计算),需要事先给定.关于确定 的方法,将在后面给出.需要事先知道计算函数值的次数,这是Fibonacci法的一个特点. 容易验证,利用公式(4.2.12)和(4.2.13)计算试探点时,第

37、次迭代区间长度的缩短率恰为 . Fibonacci法计算步骤如下: 1.给定初始区间 和最终区间长度 .求计算函数值的次数 ,使置辨别常数 .计算试探点 :计算函数值 .置 . 2.若 ,则转步3.; 若 ,则转步4. 3.令 计算试探点 :若 , 则转步6.;否则,计算函数值 ,转步5. 4.令 计算 : 若 , 则转步6.;否则,计算函数值 ,转步5. 5.置 ,转步2. 6.令 计算 . 停止计算,极小点含于 . 例4.2.2 用Fibonacci法求解例4.2.1初始区间 ,精度 5、惩罚函数法 本节介绍另一类约束最优化方法惩罚函数法.这类方法的基本思想是,借助惩罚函数把约束问题转化为

38、无约束问题,进而用无约束最优化方法来求解,5.1 外点法 5.1.1 罚函数的概念 本节考虑约束问题(5.1.1)其中 是 上的连续函数,研究这类问题的求解方法. 由于上述问题的约束非线性,不能用消元法将次问题化为无约束问题,因此在求解时必须同时照顾到即使目标函数值下降又要满足约束条件这两个方面.实现这一点的一种途径是由目标函数和约束函数组成辅助函数,把原来的约束问题转化为极小化辅助函数的无约束问题. 比如,对于等式约束问题 可定义辅助函数(5.1.2)(5.1.3)参数 是很大的正数.这样就能够把(5.1.2)转化为无约束问题(5.1.4)显然,(5.1.4)的最优解必使得 接近零,因为如若

39、不然,(5.1.3)的第2项将是很大的正数,现行点必不是极小点.由此可见,求解问题(5.1.4)能够得到问题(5.1.2)的近似解. 对于不等式约束问题(5.1.5)辅助函数的形式与等式约束情形不同,但构造辅助函数的基本思想是一致的,这就是在可行点辅助函数值等于原来的目标函数值,在不可行点,辅助函数值等于原来的目标函数值加上一个很大的正数.根据这样的原则,对于不等式约会素问题(5.1.5), 我们定义函数(5.1.6)其中 是很大的正数. 当 为可行点时, 当 不是可行点时,这样,可将(5.1.5)转化为无约束问题(5.1.7)通过(5.1.7)求得(5.1.5)的近似解. 我们把上述思想加以

40、推广,对于一般情形(5.1.1),可定义函数(5.1.8)其中 具有下列性质:(5.1.9) 是满足下列条件的连续函数:函数 的典型取法如其中 ,均为给定常数.通常取作 . 这样,把约束问题(5.1.1)转化为无约束问题(5.1.10)其中 是很大的正数, 是连续函数. 根据定义,当 为可行点时, ,从而有 当 不是可行点时,在 处, 是很大的正数,它的存在是对点脱离可行域的一种惩罚,其作用是在极小化过程中迫使迭代点靠近可行域.因此,求解问题(5.1.10)能够得到约束问题(5.1.1)的近似解,而且 越大,近似程度越好.通常将 称为罚项, 称为罚因子, 称为罚函数. 例5.1.1 考虑下列问

41、题:令(5.1.11) 例5.1.2 求解下列非线性规划问题: 5.1.2 外点法计算步骤 实际计算中,罚因子 的选择十分重要.如果 过大,则给罚函数的极小化增加计算上的困难;如果 太小,则罚函数的极小点远离约束问题的最优解,计算效率很差.因此,一般策略是取一个趋向无穷大的严格递增正数列 ,从某个 开始,对每个 ,求解(5.1.5)从而得到一个极小点的序列 , 在适当的条件下, 这个学列将收敛于约束问题的最优解. 如此通过求解一系列无约束问题来获得约束问题最优解的方法称为序列无约束极小化方法, 简称为SUMT方法. 外点法计算步骤如下: 1.给定初始点 ,初始罚因子 ,放大系数 ,允许误差 2

42、.以 为 初点,求解无约束问题设其极小点为 . 3.若 ，则停止计算，得到点 ；否则 ，令 5.2 内点法 5.2.1 内点法的基本思想 内点法在迭代中总是从内点出发，并保持在可行域内部进行搜索。因此，这种方法适用于下列只有不等式约束的问题：(5.2.1)其中 是连续函数。现将可行域记作(5.2.2)(5.2.3) 保持迭代点含于可行域内部的方法是定义障碍函数其中 是连续函数，当点 趋向可行域边界时， 。两种最重要的形式是及(5.2.4)(5.2.5) 是很小的正数。这样，当 趋向边界时，函数 否则，由于 很小，则函数 的取值近似 。因此，我们通过求借下列问题得到(5.2.1)的近似解：由于

43、的存在，在可行域边界形成“围墙”，因此(5.2.6)的解 必包含于可行域的内部。 (5.2.6)仍是约束问题，看起来踏的约束条件比原来的约束问题还要复杂。但是，由于函数 的阻挡作用是自动实现的，因此从计算的观点看，(5.2.6)可当作无约束问题来处理。(5.2.6) 5.2.2 内点法计算步骤 根据障碍函数 的定义，显然， 取值越小，(5.2.6)的最优解越接近(5.2.1)的最优解。但是，这里存在与外点类似的问题，如果 太小，则将给(5.2.6)的计算带来很大困难. 因此，仍采取序列无约束极小化方法(SUMT)，取一个严格单调且趋于零的罚因子(障碍因子)数列 ，对每一个 ，从内部出发，求解问

44、题(5.2.7) 内点法计算步骤如下: 1.给定初始内点 ,允许误差 ,初始参数 ,缩 2.以 为初始点,求解下列问题:其中 由式(5.2.4)定义.设求得的极小点为 . 3.若 ，则停止计算，得到点 ；否则，令 例5.2.1 用内点法求解下列问题： 5.3 乘子法 5.3.1 乘子法的基本思想 我们首先考虑只有等式约束的问题:(5.3.1)其中 是二次连续可微函数, . 运用乘子法实现需要定义增广Lagrange函数(乘子罚函数):(5.3.2)其中 5.3.2 等式约束问题乘子法计算步骤 乘子法的计算步骤如下: 1.给定初始点 ,乘子向量初始估计 ,参数 ,允许误差 2.以 为初点,解无约

45、束问题得解 . 3.若 ,则停止计算,得到点 ;否则,进行步4. 4.若则置 ,转步5.;否则,进行步5. 5.用公式(5.3.19)计算 ,置 ,转步2. 例5.3.1 用乘子法求解下列问题: 对于此例,增广Lagrange函数我们取罚因子 , 令Lagrange乘子的初始估计 ,由此出发求最优乘子及问题的最优解. 5.3.3 不等式约束问题的乘子法 我们先考虑只有不等式约束的问题(5.3.20) 为利用关于等式约束问题所得到的结果 , 引入变量 , 把(5.3.20)化为等式约束问题:这样,可定义增广Lagrange函数从而把问题(5.3.20)转化为求解(5.3.21)我们将 关于 求极

46、小,由此解出 ,并代入(5.3.21),将其化为只关于 求极小的问题.为此求解(5.3.22)用配方法将 化为(5.3.23)为使 关于 取极小, 取值如下: 综上两种情形,即(5.3.24)将上式代入(5.3.23),由此定义增广Lagrange函数(5.3.25)将问题(5.3.20)转化为求解无约束问题(5.3.26) 对于既含有不等式约束有含有等式约束的问题应定义增广Lagrange函数(5.3.28)(5.3.27)在迭代中,与只有等式约束问题类似,也是取定充分大的参数 ,并通过修正第 次迭代中的乘子 ,得到第 次迭代中的乘子 ,修正公式如下:(5.3.29)计算步骤与等式约束情形相

47、同. 例5.3.2 用乘子法求解下列问题:6、使用导数的最优化方法 本节和下一节讨论无约束问题最优化方法.我们把无约束问题的算法大致分成两类:其中之一,在计算过程中要用到目标函数的导数,凡属这类算法在本节介绍;另一类只用到目标函数值,不必计算导数,通常称为直接方法. 一般来说,无约束问题的求解通过一系列一维搜索来实现.因此,怎样选择搜索方向是解无约束问题的核心问题,搜索方向的不同选择,形成不同的最优化方法.6.1 最速下降法 6.1.1 最速下降方向 考虑无约束问题(6.1.2)其中函数 具有一阶连续偏导数. 人们在处理这类问题时,总希望从某一点出发,选择一个目标函数值下降最快的方向,以利于尽

48、快达到极小点.正是基于这样一种愿望,早在1847年法国著名数学家Cauchy提出了最速下降法.后来,Curry等人作了进一步的研究.现在最速下降法已经成为众所周知的一种最基本的算法,它对其他算法的研究也很有启发作用,因此在最优化方法中占有重要地位.下面我们先来讨论怎样选择最速下降方向. 我们知道,函数 在点 处沿方向 的变化率可用方向导数来表达,对于可微函数,方向导数等于梯度与方向的内积,即(6.1.2)因此,求函数 在点 处的下降最快的方向,可归结为求解下列非线性规划:(6.1.3)根据Schwartz不等式,有去掉绝对值符号,可以得到(6.1.4)由上式可知,当(6.1.5)时等号成立.因

49、此,在点 处沿(6.1.5)所定义的方向变化率最小,即负梯度方向为最速下降方向. 这里要特别指出,在不同尺度下最速下降方向是不同的.前面定义的最速下降方向,是在向量 的殴氏范数 不大于1的限制得到的,属于殴氏度量意义下的最速下降方向.如果改用其他度量,比如,设 为对称正定矩阵,在向量 的 范数 不大于1的限制下,极小化 ,则得到的最速下降方向与前者不同. 6.1.2 最速下降算法 最速下降法的迭代公式是(6.1.6)其中 是从 出发的搜索方向,这里取在点 处的最速下降方向,即 是从 出发沿方向 进行一维搜索的步长,即 满足(6.1.11) 计算步骤如下: 1.给定初点 ,允许误差 ,置 . 2

50、.计算搜索方向 3.若 ,则停止计算;否则,从 出发,沿 进行一维搜索,求 ,使 4.令 ,置 ,转步2. 例6.1.1 用最速下降法解下列问题:6.2 牛顿法 6.2.1 牛顿法 设 是两次可微实函数, .又设 是 的极小点的一个估计,我们把 在 展成Taylor级数,并取两阶近似:其中 是 在 处的Hessian矩阵.为求 的平稳点,令即(6.2.1)设 可逆,有(6.2.1)得到牛顿法的迭代公式(6.2.2)其中 是Hessian矩阵 的逆矩阵. 这样, 知道 后,算出在这一点处目标函数的梯度和Hessian矩阵的逆,代人(6.2.2),便得到后继点 ,用 代替 ,再用(6.2.2)计算

51、,又得到 的后继点.依此类推,产生序列 .在适当的条件下,这个序列收敛. 定理6.2.1 设 为二次连续可微函数, , 满足 ,且 存在.又设初点 充分接近 ,使得存在 ,满足 ,且对每一个成立 (6.2.3) (6.2.4)则牛顿法产生的序列收敛于 . 例6.2.1 用牛顿法解下列问题: 我们取初点 实际上,当牛顿法收敛时,有下列关系: (6.2.8)其中 是某个常数.因此,牛顿法至少两阶收敛.可见牛顿法的收敛速率是很快的. 特别地,对于二次凸函数,用牛顿法求解,经一次迭代即达极小点. 设有二次凸函数(6.2.9)其中，A 是对称正定矩阵. 我们先用极值条件求解.令得到最优解 下面用牛顿法求

52、解. 任取初始点 , 根据牛顿法的迭代公式(6.2.2),则有显然, .即1次迭代达到极小点.不一定是下降方向,经迭代,目标函数值可能上升.此外,即使目标函数值下降,得到的点 也不一定是沿牛顿方向的最好点或极小点.因此,人们对牛顿法进行修正,提出了阻尼牛顿法. 值得注意,当初始点远离极小点时,牛顿法可能不收敛.原因之一,牛顿方向 6.2.2 阻尼牛顿法 阻尼牛顿法与原始牛顿法的区别在于增加了沿牛顿方向的一维搜索,其迭代公式是(6.2.6)其中 为牛顿方向, 是由一维搜索得到的步长,即满足 阻尼牛顿法的计算步骤如下: 1.给定初始点 ,允许误差 ,置 . 2.计算 3.若 ,则停止迭代;否则,令

53、 4.从 出发,沿方向 作一维搜索:令 . 5.置 ,转步2. 由于阻尼牛顿法含有一维搜索,因此每次迭代目标函数值一般有所下降(决不会上升).可以证明,阻尼牛顿法在适当的条件下具有全局收敛性,且为两阶收敛.6.3 共轭梯度法 共轭梯度法最初由Hesteness和Stiefel于1952年为求解线性方程组而提出.后来,人们把这种方法用于求解无约束最优化问题,使之成为一种重要的最优化方法. 下面,重点介绍Fletcher-Reeves共轭梯度法,简称FR法. 共轭梯度法的基本思想是把共轭性与最速下降方法相结合,利用已知点处的梯度构造一组共轭方向,并沿这组方向进行搜索,求出目标函数的极小点. 下面先

54、讨论对于凸函数的共轭梯度法,然后再把这种方法推广到极小化一般函数的情形. 考虑如下问题：其中 , 是对称正定矩阵, 是常数. 具体求解方法如下: 首先,任意给定一个初始点 ,计算出目标函数 在这点的梯度,若 ,则停止计算;否则,令(6.3.12)沿方向 搜索,得到点 .计算在 处的梯度,若 ,则利用 和 构造第2个搜索方向 ,再沿 搜索. 一般地,若已知点 和搜索方向 ,则从 出发,沿 进行搜索,得到(6.3.14)其中步长 满足我们可以求出 的显式表达.令求 的极小点,令(6.3.15)根据二次函数的梯度的表达式,(6.3.15)即(6.3.16)由(6.3.16)得到(6.3.17) 计算

55、 在 处的梯度.若 ,则停止计算;否则,用共轭.按此设想,令(6.3.18)上式两端左乘 ,并令由此得到(6.3.19) 再从 出发,沿方向 搜索.综上分析，在第个搜索方向取负梯度的前提下, 重复使用公式(6.3.14),(6.3.17),(6.3.18)和(6.3.19),就能伴随计算点的增加,构造出一组搜索方向.下面将要证明,这组方向是关于 共轭的.因此,上述方法具有二次终止性. 定理6.3.3 对于正定二次函数(6.3.12),具有精确一维搜索的Fletcher-Reeves法在 次一维搜索后即终止，并且对所有 ,下列关系成立: 例6.3.1 考虑下列问题： 取初始点和初始搜索方向分别为

56、 在FR法中，初始搜索方向必须取最速下降方向，这一点绝不可忽视。 对于二次凸函数，FR法的计算步骤如下： 1. 给定初始点 , 置 . 2.计算 ,若 ,则停止计算,得点 ;否则,进行下一步. 3.构造搜索方向,令其中,当 时, ,当 时,按公式 计算因子 . 4.令其中按公式(6.3.17)计算步长 5.若 ,则停止计算,得点 ;否则,置 ,返回步2. 例6.3.2 用FR法求解下列问题:取初始点 .6.4 拟牛顿法 6.4.1 拟牛顿条件 前面介绍了牛顿法,它的突出优点是收敛很快.但是,运用牛顿法需要计算导数,而且目标函数的Hessian矩阵可能非正定.为了克服牛顿法的缺点,人们提出了拟牛

57、顿法.它的基本思想是用不包含导数的矩阵近似牛顿法中的Hessian矩阵的逆矩阵. 由于构造近似矩阵的方法不同,因而出现不同的拟牛顿法.经理论证明和实践检验,拟牛顿法已经成为一类公认的比较有效的算法. 下面分析怎样构造近似矩阵并用它取代牛顿法中的Hessian矩阵的逆. 前面已经给出牛顿发的迭代公式,即(6.4.1)其中 是在点 处的牛顿方向:(6.4.2) 是从 出发沿牛顿方向搜索的最优步长. 为构造 的近似矩阵 ,先分析 与一阶导数的关系. 设在第 次迭代后,得到点 ,我们将目标函数 在点 展成Taylor级数,并取二阶近似,得到由此可知,在 附近有令 ,则记作(6.4.3)(6.4.4)则

58、有(6.4.5)又设Hessian矩阵 可逆,则(6.4.6)这样,计算出 后,可以根据(6.4.6)估计在 处的Hessian矩阵的逆.因此,为了用不包含二阶导数的矩阵 取代牛顿法中的Hessian矩阵 的逆矩阵,有理由令 满足(6.4.7)式(6.4.7)有时称为拟牛顿条件.下面就来怎样确定满足这个条件的矩阵 . 6.4.3 变尺度法（DFP算法） 著名的 DFP 方法是 Davidon 首先提出, 后来又被 Fletcher 和 Powell 改进的算法,又称为变尺度法.在这种方法中,定义校正矩阵为(6.4.16) 容易验证,这样定义校正矩阵 ,得到的矩阵(6.4.17)满足拟牛顿条件(

59、6.4.7).(6.4.17)称为DFP公式. DFP方法计算步骤如下: 1.给定初始点 ,允许误差 . 2.置 (单位矩阵),计算出在 处的梯度 3.令 4.从 出发,沿方向 搜索,求步长 ,使它满足令 5. 检验是否满足收敛准则,若则停止迭代,得到点 ;否则,进行步6. 6.若 ,则令 ,返回步2.;否则,进行步7. 7.令利用公式(6.4.17)计算 置 ,返回步3. 例6.4.1 用DFP方法求解下列问题: 初始点及初始矩阵分别取为 例7（石油最优储存方法）有一石油运输公司，为了减少开支，希望作了节省石油的存储空间.但要求存储的石油能满足客户的要求.为简化问题，假设只经营两种油，各种符

60、号表示的意义如表4所示.其中供给率指石油公司供给客户的速度.带不等式约束问题-拉格朗日法表4 各种符号表示意义表第i种油的存储量第i种油的价格第i种油的供给率第i种油的每单位的存储费用第i种油的每单位的存储空间总存储公式由历史数据得到的经验公式为 :且提供数据如表5所示：表5 数据表已知总存储空间代入数据后得到的模型为：模型求解：拉格朗日函数的形式为： 即:对 求各个变量的偏导数，并令它们等于零，得: 解这个线性方程组得：从而可得最小值是 . 带不等式约束问题的最优性条件（P3） Min f(X) s.t. gj(X) 0 (j=1,2.l) X En 令X* D，记J（X*）= j gj(X