非线性规划的基本概念

1、第五讲第五讲 非线性规划的基本概念非线性规划的基本概念l 非非线性规划问题线性规划问题l 非非线性规划数学模型线性规划数学模型l 非线性规划的图解法非线性规划的图解法l 梯度、梯度、Hesse矩阵、矩阵、Jacobi阵阵l 凸函数和凸规划凸函数和凸规划l 解非线性规划方法概述解非线性规划方法概述l 一维最优化一维最优化 在科学管理和其他领域中，大量应用问题可以归结为线性规在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含件很难

2、用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。有自变量的非线性函数，则这样的规划问题就属于非线性规划。 非线性规划是运筹学的重要分支之一。最近非线性规划是运筹学的重要分支之一。最近3030多年来发展很多年来发展很快，不断提出各种算法，而其应用范围也越来越广泛。比如在各快，不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。广泛且不短深入的应用。 一般来说，求解非线性规划问题比线性规划问题困难得多。一般来

3、说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还没有到目前为止还没有适合于各种问题的一般算法适合于各种问题的一般算法，这是需要深入研，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。究的一个领域。我们只是对一些模型及应用作简单介绍。1 1非线性规划问题举例非线性规划问题举例例一：选例一：选址问题址问题设有设有 个市场，第个市场，第 个市场位置为

4、个市场位置为 ，它对某种货物的需要，它对某种货物的需要量为量为 。现计划建立。现计划建立 个仓库，第个仓库，第 个仓库的存储个仓库的存储容量为容量为 试确定仓库的位置，使各仓库对各市场的试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。运输量与路程乘积之和为最小。设第设第 个仓库的位置为个仓库的位置为 第第 个仓库到第个仓库到第 个市场的货物供应量为个市场的货物供应量为 则第则第 个个仓库到第仓库到第 个市场的距离为个市场的距离为jn),(jjqp), 2 , 1(njbj mi)., 2 , 1(miai i, 2 , 1),(miyxii ij)., 2 , 1, 2 , 1

5、(njmizij ij,)()(22jijiijqypxd ,)()(min221111jijiminjijijminjijqypxzdz 目标函数为目标函数为约束条件为约束条件为 （1 1）每个仓库向各市场提供的货物量之和不能超过它的）每个仓库向各市场提供的货物量之和不能超过它的存储容量。存储容量。miazinjij, 2 , 1,1 njbzjmiij, 2 , 1,1 （2）每个市场从各仓库得到的货物量之和应等于它的）每个市场从各仓库得到的货物量之和应等于它的需要量。需要量。（3）运输量不能为负数）运输量不能为负数njmizij, 2 , 1, 2 , 1, 0 例例2. 木木梁设计问题

6、梁设计问题 把圆形木材加工成矩形横截面的木梁，要求木梁高度把圆形木材加工成矩形横截面的木梁，要求木梁高度不超过不超过 ，横截面的惯性矩（高度的平方，横截面的惯性矩（高度的平方 宽度）不小宽度）不小于于 ，而且高度介于宽度与，而且高度介于宽度与4倍宽度之间。问如何确定木倍宽度之间。问如何确定木梁尺寸可使木梁成本最小梁尺寸可使木梁成本最小.H W2x1x设矩形横截面的高度为设矩形横截面的高度为 ， 宽度宽度为为 ，则圆形木材的半径，则圆形木材的半径1x2x222122 xxr,44min22212 xxrs 目标函数为目标函数为约束条件为约束条件为 )( . 0,4 4( W)( )(212121

7、2211高度与宽度非负高度与宽度非负倍宽度之间）倍宽度之间）高度介于宽度与高度介于宽度与惯性矩不小于惯性矩不小于高度不小于高度不小于 xxxxxxWxxHHx（1）数学规划模型的一般形式：）数学规划模型的一般形式：其中其中, 简记为简记为MP(Mathematical Programming) 2 2 非线性规划问题的数学模型非线性规划问题的数学模型 qjxhpixgxfii, 1 , 0)( , 1 , 0)( s.t.)( min的实值函数，的实值函数，为为xxhxgxfxxxxjiTn)(),(),(,),(21 （2）简记形式：）简记形式：Tpxgxgxg)(,),()(1 Tqxhx

8、hxh)(,),()(1 引入引入向量函数向量函数符号：符号： qjxhpixgtsxfii, 1 , 0)( , 1 , 0)( .)( min 0)( 0)( .)( minxhxgtsxfXxxf )(min qjxhpixgRxXiin, 1, 0)(, 1, 0)(（3）数学规划问题的分类：）数学规划问题的分类： 0)( 0)( s.t.)( minxhxgxf若若 为线性函数，即为为线性函数，即为线性规划线性规划(LP)；若若 至少一个为非线性至少一个为非线性, 即为即为非线性规划非线性规划(NLP)；对于非线性规划，对于非线性规划，若没有若没有 ,即即X=Rn,称为称为 无约束非

9、线性规划无约束非线性规划或或无约束最优化问题无约束最优化问题；否则称为否则称为约束非线性规划或约束最优化问题约束非线性规划或约束最优化问题。)(),(),(xhxgxfji)(),(),(xhxgxfji)(),(xhxgji（4）可行域和可行解：）可行域和可行解： qjxhpixgRxXiin, 1, 0)(, 1, 0)(称称为为MP问题的问题的约束集约束集或或可行域可行域。若若x在在X内，称内，称x为为MP的的可行解可行解或者或者可行点可行点。 qjxhpixgtsxfii, 1 , 0)( , 1 , 0)( .)( min（5）最优解和极小点）最优解和极小点对于非线性规划（对于非线性

10、规划（MP），），若若 ，并且有，并且有Xx *Xxxfxf ),()(*极极小小值值。）的的整整体体最最优优值值或或整整体体是是（称称MP)(*xf如果有如果有*, ),()(xxXxxfxf 严严格格整整体体极极小小点点，）的的严严格格整整体体最最优优解解或或是是（称称MP*x严严格格整整体体极极小小值值。）的的严严格格整整体体最最优优值值或或是是（称称MP)(*xf定义定义:极极小小点点，）的的整整体体最最优优解解或或整整体体是是（则则称称MP*x 使使的的邻邻域域并并且且存存在在若若）对对于于非非线线性性规规划划（ )( ,MP* xxRxxNxXxnXxNxxfxf)()()(* ，

11、极极小小值值）的的局局部部最最优优值值或或局局部部是是（称称MP)(*xf如果有如果有* ,)()()(xxXxNxxfxf ，定义定义严严格格局局部部极极小小点点）的的严严格格局局部部最最优优解解或或是是（称称MP*x严严格格局局部部极极小小值值。）的的严严格格局局部部最最优优值值或或是是（MP)(*xf则称则称 x* 是是(MP)的的局部最优解或或局部极小解, 例1： 用图解法求解 min f(x)=(x12)2 +(x22)2 s.t. h(x)= x1 + x2 - 6 = 0 x1x20662233最优解 x* = ( 3，3 )T可行解 x = ( 1.5，4.5 )T最优级解即为

12、最小圆的半径：最优级解即为最小圆的半径：f(x)=(x12)2 +(x22)2 = 23 非线性规划问题的图解法 对二维最优化问题，总可以用图解法求解，而对三维或高维问题，对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。已不便在平面上作图，此法失效。x1x206622D可行域最优解最优解 x x* * = = ( 2( 2，2 )2 )T T 例2： 用图解法求解 min f(x)=(x1 - 2)2 +(x2 - 2)2 s.t. h(x)= x1 + x2 - 6 03 3 非线性规划问题的图解法非线性规划问题的图解法最优级解即为最小圆的半径：最优级

13、解即为最小圆的半径：f f( (x x)=()=(x x1 1 - 2) - 2)2 2 +( +(x x2 2 - 2) - 2)2 2 = 0 = 0 解：先画出等式约束曲线 的图形抛物线， 0,0505.12)(min212122212221xxxxxxxtsxxxf052221 xxxx1x2123456135 例3：用图解法求解 再画出不等式约束区域， 最后画出目标函数等值线， 所以 最优解最优解 x*=(4,1), 最优值最优值 min f(x)=4.4 梯度、Hesse矩阵、Jacobi阵一般形式:矩阵形式:二次型:矩阵A的正定性: 正定、半正定、负定、不定。其中AAT。二次型的

14、正定性: 正定、半正定、负定、不定。 cxbxxgxxxfiniininjjiijn 1112121, cxbAxxxfTT 21 AxxxfT21 定义：f(x) 是定义在是定义在En上的可微函数。上的可微函数。f(x) 的的n个偏导数个偏导数为分量的向量称为为分量的向量称为f(x) 的的梯度梯度. Tnxxfxxfxxfxf ,)(21 性质：设f(x) 在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质： 性质一 函数在某点的梯度不为零，则该梯度方向必与过该点的等值面垂直; 性质二 梯度方向是函数具有最大变化率的方向（负梯度方向也叫最速下降方向）。解： 由于,46211xxx

15、f 102121 xxxfxfxfP例：试求目标函数 在点 x =0,1T 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。 2221212143,xxxxxxf 则函数在 x =0,1T 处的最速下降方向是21224xxxf 24244610212121xxxxxx这个方向上的单位向量是： 551552242422xfxfe解： 由于例：试求目标函数 在点x =0,1T 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。 2221212143,xxxxxxf 新点是： 551552242422xfxfe 5511552551552101exx 52526

16、|4312221211 xxxxxxf函数值： 几个常用的梯度公式几个常用的梯度公式： AxxfAxxxfAxxfxxxfbxfxbxfCxfCxfTTT2 .0 . 0,.1 则则对对称称矩矩阵阵。则则则则即即则则常常数数 22221222222212121222122nxxfnxxxfnxxxfxnxxfxxfxxxfxnxxfxxxfxxfxfxf多元函数 f(x) 关于x的二阶导数，称为 f(x)的Hesse矩阵.当f(x)的所有二阶偏导数连续时,即 ijjixxxfxxxf 22Hesse矩阵是对称的.时，时， ; 0)(,)(2 xfbxfxbxfT );()(,)(

17、212单位阵单位阵IxfxxfxxxfT .)(,)(,212AxfAxxfAAxxxfT 对对称称几个常用Hessian公式： 向量变量值函数： nmmmnnxxgxxgxxgxxgxxgxxgxxgxxgxxgxg0201002202102012011010向量值函数g(x)在点 x0处的Jacobi矩阵Tnxgxgxgxg)(,),(),()(21 向量变量值函数的导数：Tnxxxx),(21 (1)凸函数：凸函数：）有）有，（若对若对是非空凸集，是非空凸集，设设10,:1 RSfRSn定义定义上上是是凸凸的的。在在上上的的凸凸函函数数，或或是是则则称称SSff上上是是严严格格凸凸的的。

18、在在上上的的严严格格凸凸函函数数，或或是是则则称称SSff凹凹的的。严严格格上上是是在在或或凹凹函函数数严严格格上上的的是是凸凸函函数数，称称严严格格上上的的是是若若)(S,)(S)(Sfff 5 凸函数和凸规划凸函数和凸规划Sxxxfxfxxf 212121,),()1()()1( Sxxxfxfxxf 212121,),()1()()1( 若若即是凸的也是凹的。即是凸的也是凹的。其中其中例例1,)( RRxxxfnT 是凸函数是凸函数其中其中例例nRxxxf |)( 例：正定二次函数例：正定二次函数,21)(cxbAxxxfTT 其中其中A是正定矩阵，是正定矩阵，f(x)是凸函数。是凸函数

19、。是非空凸集是非空凸集设设nRS 性质性质1:上的凸函数；上的凸函数；是是，则，则上的凸函数，上的凸函数，是是若若S0S)1(ff 上上的的凸凸函函数数。是是上上的的凸凸函函数数是是若若S,S,)2(2121ffff （2）凸函数的性质）凸函数的性质性质性质2:则集合则集合是凸函数是凸函数是非空凸集是非空凸集设设,1RcfRSn cxfSxcfHS )(|),(是凸集。是凸集。证明证明:略略.则则可可微微：是是非非空空开开凸凸集集，设设,S1RSfRn 上上的的凸凸函函数数是是）（S1fSxxxfxfxxxfT 2112121,),()()()(处处的的梯梯度度。是是函函数数在在点点）（其其中

20、中11111)(,)()(xxxfxxfxfTn 定理定理1：（一阶条件）：（一阶条件）上上的的严严格格凸凸函函数数是是）（S2f212112121, ),()()()(xxSxxxfxfxxxfT n=1时几何意义：可微函数是凸的等价于切线不在函数图像时几何意义：可微函数是凸的等价于切线不在函数图像上方。上方。 （3） 凸函数的判定凸函数的判定逆命题不成立）逆命题不成立）上的严格凸函数（此时上的严格凸函数（此时是是上是正定矩阵时上是正定矩阵时在在当当上是半正定的。上是半正定的。在在上的凸函数上的凸函数是是则则二阶连续可导二阶连续可导是非空开凸集是非空开凸集设设,)(S)( ,:,S221Sf

21、SxfxfSfRSfRn nnnnxxxfxxxfxxxfxxxfxfxf)(.)(.)(.)()(Hesse)(2121211222矩阵，矩阵，为为其中其中定理定理2：（二阶条件）：（二阶条件） , 1 0 , 1 0 . miniqjxh pixgtsxfj）（）（）（4）凸规划的定义及其性质：）凸规划的定义及其性质： , 1 0 , 1 0 qjxhpixgRxXjin）（）（简简称称凸凸规规划划。凸凸规规划划为为非非线线性性称称上上的的凸凸函函数数是是是是凸凸集集若若,MP,)(SfX凸规划定义：凸规划定义：定理定理是凸规划。是凸规划。上的凸函数，则上的凸函数，则是是并且并且皆为线性函

22、数，皆为线性函数，上的凸函数上的凸函数皆为皆为若若）（）（）（对于非线性规划对于非线性规划)( MP)(,)(g , 1 0 , 1 0 s.t. min,(MP) iXfxhRxqjxh pixgxfjnij 凸规划性质凸规划性质：定理定理凸规划的任一局部最优解都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非线性规划凸规划是以后重点讨论的一类非线性规划凸函数凸函数线性函数线性函数（1）微分学方法的局限性：）微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，

23、微分学方法不易处理。6 6 非线性规划方法概述非线性规划方法概述（2）数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列xkxk的最后一点为最优解xk有限xk无限xk收敛于最优解迭代格式迭代格式xkxk+1kx kkkxxx 1pkkkkptx kkkxxx 1称称pk为第为第k轮轮搜索方向搜索方向，tk为第为第k轮沿轮沿pk方向的方向的步长步长。产生产生tk和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。，使，使若存在若存在设设0, 0,:1 pRpRxRRfnnn), 0( ),()( txftpxf处处的的下下降降方方向向。在在点点是是函函数数则则称称向

24、向量量xxfp)(处处下下降降最最快快的的方方向向。在在就就是是可可导导，则则在在若若xxfxfxxf)()(-)( 定义定义：特殊搜索方向：特殊搜索方向下降方向下降方向，使得，使得若存在若存在设设0t, 0, pRpXxRXnnXtpx 的的可可行行方方向向。关关于于处处是是点点则则称称向向量量Xxp定义：定义：特殊搜索方向特殊搜索方向下降方向下降方向解非线性规划问题，关键在于解非线性规划问题，关键在于找到某个方向，使得在此方向找到某个方向，使得在此方向上，目标函数得到下降，同时上，目标函数得到下降，同时还是可行方向。还是可行方向。这样的方向称为这样的方向称为可行下降方向。可行下降方向。定义

25、：算法收敛、下降迭代算法定义：算法收敛、下降迭代算法集合集合S上的迭代算法：上的迭代算法：（1）初始点）初始点0 x；（2）按照某种搜索方向）按照某种搜索方向pk产生下一个迭代点产生下一个迭代点.1kkkkpxx （i）如果点列如果点列kx收敛于最优解收敛于最优解*x，则称此，则称此算法收敛算法收敛。（ii）如果如果 )()()(10kxfxfxf，则称此算法为，则称此算法为下降迭代算法下降迭代算法。.0 x.1x.2x（3）下降迭代算法步骤）下降迭代算法步骤（1）给出初始点）给出初始点0 x，令，令0 k；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向kd；（3）按照某种规

26、则确定搜索步长）按照某种规则确定搜索步长k ，使得，使得)()(kkkkxfdxf ；（4）令）令 kkkkdxx 1，1: kk；（5）判断）判断kx是否满足是否满足停止条件停止条件。是则停止，否则转第。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：)(min)(kkkkkdxfdxf 称称0)( kTkkkddxf k 为为最优步长最优步长，且有对，且有对 k的梯度的梯度（4） 终止条件终止条件)(31 kkkkxxxx )(41 kkkkxfxfxfxf11 kkxx21)()( kkxfxf（5）常用的收敛性判别准则）常用的收敛性判别准则:（）点收敛准则（）点收敛准则

27、: :( (可取可取Rn中任一种模中任一种模) )。 ) 1()(kkxx（）目标函数值准则：（）目标函数值准则：（绝对差）。（绝对差）。 )()() 1()(kkffxx（）目标函数值准则：（）目标函数值准则：（相对差）。（相对差）。 )()()()() 1()(kkkfffxxx取其中之一取其中之一,也可同时取也可同时取(1)与与(2);(1)与与(3);或或(1),(2)和和(3)等。等。（6）算法的收敛速度）算法的收敛速度则称则称 的收敛阶为的收敛阶为 。设算法所得的点列为设算法所得的点列为kx，如果，如果,|*1 xxxxkk.0, kx1.线性收敛（当线性收敛（当k充分大时）：充分

28、大时）： 2.超线性收敛：超线性收敛：3.二阶收敛：二阶收敛： （*）式中）式中 =2时成立。时成立。1|*)(*)1( xxxxkk0|lim*)(*)1( xxxxkkk 单变量单变量( (一维一维) )最优化最优化l 一维最优化问题一维最优化问题l 进退法进退法l 黄金分割法黄金分割法l 抛物线搜索法抛物线搜索法l 三次插值法三次插值法下降迭代算法下降迭代算法中最优步长的确定中最优步长的确定)(min)(kkkkkdxfdxf .kxkd.k 一维最优化问题：一维最优化问题：)(minxfRxts .解析的方法解析的方法（极值点的必要条件）极值点的必要条件）0)( xf一、一维最优化问题

29、一、一维最优化问题1. 单峰函数单峰函数定义定义：设：设)(xf是区间是区间,ba上的一元函数，上的一元函数，x是是)(xf在在,ba上的极小点，且对任意的上的极小点，且对任意的, ,2121xxbaxx 有有（a）当当xx 2时，时，; )()(21xfxf （b）当当时，时，xx 1. )()(21xfxf a.b.x.1x2x则称则称 是单峰函数。是单峰函数。)(xf.性质性质：通过计算区间：通过计算区间 a, b 内两个不同点的函数值，就可内两个不同点的函数值，就可以确定一个包含极小点的子区间。以确定一个包含极小点的子区间。定理定理 设设是区间是区间,ba上的一元函数，上的一元函数，x

30、是是)(xf在在,ba上的极小点。任取点上的极小点。任取点)(xf, ,badc 则有则有（1）如果）如果)()(dfcf ，则，则; ,bcx （2）如果）如果, )()(dfcf 则则。,dax a.b.x.cd2 搜索法求解：搜索法求解：)(min0 xx )(minmax0 xxx 或或基本过程：基本过程：给出给出a,b,使得使得x*在在a,b中。中。a,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,b的长度。的长度。当当a,b的长度小于某个预设的值，或者导数的绝的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。对值小于某个预设的正数，则迭代终止。二进退法二进退

31、法思想思想从一点出发从一点出发,按一定的步长按一定的步长, 试图确定出函数值呈现试图确定出函数值呈现“高高 - 低低 - 高高”的三点。一个方向不成功，就退回来，再沿相反方的三点。一个方向不成功，就退回来，再沿相反方向寻找。向寻找。进退法的计算步骤进退法的计算步骤,. 1)0(Rx 给给定定初初始始点点, 00 h初初始始步步长长,0hh 令令,)0()1(xx ),()1(xf计算计算. 0 k并令并令,. 2)1()4(hxx 令令),()4(xf计算计算. 1: kk令令),()(. 3)1()4(xfxf 若若，则转则转 45.否则，转否则，转,. 4)1()2(xx 令令,)4()1

32、(xx ),()()1()2(xfxf ),()()4()1(xfxf . 2,2:转转令令hh 如何确定包含极小点的一个区间？如何确定包含极小点的一个区间？, 1. 5 k若若；则转则转 6. 7否则，转否则，转,:. 6hh 令令,)4()2(xx ),()()4()2(xfxf . 2转转,. 7)2(3)xx 令令,)1()2(xx ,)4()1(xx 停停止止计计算算。例：例：)0(x)1(xhxx )1()4()2(x)1(x)4(x)3(x)2(x)1(x)0(x)1(x)4(xhh :)1(x)2(x)4(x)3(x)2(x)1(x。即即为为包包含含极极小小点点的的区区间间或或

33、区区间间,)1()3()3()1(xxxx,)1()3(xx：极小点区间极小点区间,)3()1(xx极小点区间：极小点区间：假定：已经确定了单峰区间假定：已经确定了单峰区间a,b)(min0 xx )(minmax0 xxx )(minxbxa )(1x)(2xx)(1t )(2t xx1x2ababx12新搜索区间为新搜索区间为a,x2新搜索区间为新搜索区间为x1,b三三. 黄金分割法（黄金分割法（0.618法）法）区间缩小比例的确定：区间缩小比例的确定：区间缩短比例为区间缩短比例为(x2-a)/(b-a)缩短比例为缩短比例为(b-x1)/(b-a)缩短比例缩短比例 满足：满足：每次插入搜索

34、点使得两个区间每次插入搜索点使得两个区间a,x2和和x1,b相等；相等；每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。618. 0215 缩短比例缩短比例0.618法法)(1x)(2x)(1x)(2xx1x2ababx1x2黄金分割法的计算公式的推导：黄金分割法的计算公式的推导：上单峰，上单峰，在在设设,)(11baxf.,11bax 极小点极小点假设进行假设进行次迭代前次迭代前第第 k,kkbax ,kkkkba 取取规定规定.kk , )()(kkff 和和计计算算分两种情况：分两种情况：, )()(. 1kkff 若若,1kka 则令则令;1kkbb , )()(. 2

35、kkff 若若,1kkaa 则令则令.1kkb ？与与如何确定如何确定kk kkkkab . 1比率相同，即比率相同，即每次迭代区间长度缩短每次迭代区间长度缩短. 2)0()(11 kkkkabab)1()2(）可得：）可得：）与（）与（由式（由式（21 )()(1(kkkkkkkkabaaba )3()4(件：件：要求其满足以下两个条要求其满足以下两个条kakbk ku？取值的确定取值的确定 通过确定通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。迭代的一个迭代点重合，从而减少算法的计算量。 , )()

36、()1(kkuffk 次迭代时有次迭代时有设在第设在第则有则有。,11kkkkuaba ,111k kuk 次迭代时选取次迭代时选取在第在第）有）有则由（则由（4)(1111 kkkkabau )(2kkkaba 。不必重新计算不必重新计算因此因此则则，如果令如果令112,1 kkkuu 618. 021512 。次迭代时有次迭代时有若在第若在第)()()2(kkuffk 同理可得。同理可得。3. 0.618法的算法步骤：法的算法步骤：0.,. 111 精度要求精度要求给定初始区间给定初始区间ba. 1: k令令),(382. 01111aba 令令),(618. 01111aba ).()(

37、11 ff与与并计算并计算,. 2 kkab若若停止，停止，.2kkabx 且且否则，否则，；时，转时，转当当3)()(kkff . 4)()(时，转时，转当当kkff ,. 31kka 令令,1kkbb ,1kk ),(618. 01111 kkkkaba ),(1 kf 计算计算。转转 2,. 41kkaa 令令,1kkb ,1kk ),(382. 01111 kkkkaba ),(1 kf 计算计算, 1: kk令令。转转 2, 1: kk令令确定确定a,b,计算探索点计算探索点x1=a+0.382(b-a)x2=a+0.618(b-a)()(21xx是是否否ax2是是停止，输出停止，输

38、出x1否否以以a,x2为新的搜索区间为新的搜索区间1xb是是停止，输出停止，输出x2否否以以x1,b为新的搜索区间为新的搜索区间3. 0.618法的算法框图：法的算法框图：黄金分割法的迭代效果：黄金分割法的迭代效果：第第 k 次后迭代后所得区间长度为初始区间长度的次后迭代后所得区间长度为初始区间长度的。倍倍k)215( 其它的试探点算法：其它的试探点算法：Fibonacci算法。算法。例例：5 . 0,3 , 0 12)(min 30精度精度其中单谷区间其中单谷区间求解求解 tttt 解：解：t1t2)(1t )(2t 30t 1、第一轮：、第一轮：t1=1.146, t2=1.8546648

39、. 3)(,2131. 0)(21 tt t200.52、第二轮：、第二轮：t2=1.146, t1=0.7082131. 0)(0611. 0)(21 tt t20=1.1460.53、第三轮：、第三轮：t1=0.438, t2=0.7082082. 0)(0611. 0)(12 tt b -t1=1.146-0.4380.51.8540t t2t11.1460 tt2t14、第四轮：、第四轮：t2=0.876=(1.146-0.438), t1=0.7080798. 0)(0611. 0)(21 tt b-t1=1.146-0.7080，求目标函数值的计算次，求目标函数值的计算次数数 n，

40、使，使置辨别常数置辨别常数0。计算试探点。计算试探点 计算函数值和计算函数值和 。置。置k =1。（2） 若若 ，则转（，则转（3）；）； 若若 ，则转（，则转（4）。）。,11ba / )(11abFn 11 和和 ,1111111211abFFaabFFannnn )()(11 ff和和)()(k ffk )()(k ffk （3） （5） 置置k= k+1，转（，转（2）。）。)5(),( ,(6);, 2(2.7) )b(,11111,111转转计算函数值计算函数值否则否则则转则转若若计算试探点：计算试探点：令令 kkkkkkkkkkkfnkaabba )5(),( ,(6);, 2(

41、2.8) )b( ,111111,111转转计算函数值计算函数值否则否则则转则转若若：计算计算令令 kkkkkkkkkkkkfnkaabaa （4） b, b, .b,),()( ;b,),()( )()(,1111。的的长长度度不不超超过过且且，停停止止计计算算，极极小小点点含含于于则则令令若若则则令令若若，和和计计算算函函数数值值令令 nnnnnnnnnnnnnnnnnnnnnnaaaaffbaffff （6） 思想思想在极小点附近，用二次三项式在极小点附近，用二次三项式),()(xfx 逼近目标函数逼近目标函数 处有相同的函数值，处有相同的函数值，在三点在三点与与令令)3()2()1()

42、()(xxxxfx 并并假假设设).()(),()()3()2()2()1(xfxfxfxf )1(x)2(x)3(x)(xf)(x x*x四四. 抛物线（二次）插值抛物线（二次）插值即即“两头大中间小两头大中间小”,)(2cxbxax 设设)()()1(2)1()1()1(xfcxbxax )()()2(2)2()2()2(xfcxbxax )()()3(2)3()3()3(xfcxbxax .)(cbx和和的系数的系数近函数近函数解上述方程组，可得逼解上述方程组，可得逼 的极小点，的极小点，再求函数再求函数)(x 令令cxbx2)( , 0 解得解得cbx2 如何计算函数如何计算函数?)(

43、x 。的极小点的估计值的极小点的估计值作为作为以以)(xfx )()()()()()(2)()()()()()()3()2()1()2()1()3()1()3()2()3()2()1()2()1()3()1()3()2(222222xfxxxfxxxfxxxfxxxfxxxfxx 令令x=33221123322221111111121fxfxfxxfxfxf 抛物线插值算法步骤：抛物线插值算法步骤：, ,)1()3()1(xx给定初始区间给定初始区间).()(),()()3()2()2()1(xfxfxfxf 设设。给定精度给定精度。令令 )1()0(1:xxk 。令令。设设3,2,1, )(

44、)()()2()()(2 ixfxcxbxaxii 解出解出。的极小点的极小点解出解出。系数系数cbxxcbak2)(,)( 及其及其的函数值最小的三个点的函数值最小的三个点中选择中选择和和从从)(,)3()()3()2()1(xfxxxxk。）转（转（。令令。重新标记为重新标记为左、右两点，左、右两点，21:,)3()2()1( kkxxx）。）。否则转（否则转（，则算法停止则算法停止若若3,| )()(|)1()( kkxfxf思路：思路：,0)()()()1()2()1()2()1( xfxxxxxf且有且有，的函数值的函数值、在点在点已知已知利用这两点的函数值利用这两点的函数值的极小点

45、。的极小点。内存在内存在（则区间则区间)(),.0)()2()1()2(xfxxxf 在在这这两两点点有有相相同同的的函函使使它它与与项项式式和和导导数数构构造造一一个个三三次次多多)(, )(xfx 的极小点。的极小点。的极小点近似的极小点近似并用并用逼近逼近用用数值和导数，数值和导数，)()(, )()(xfxxfx )1(x)2(x)(xf)(x *xx五五. 三次插值法三次插值法设设)1()()()()()1(2)1(3)1(dxxcxxbxxax 令令 )()()()()()()()()2()2()1()1()2()2()1()1(xfxxfxxfxxfx 则有则有 )()(2)(3

46、)()()()()()()2()1()2(2)1()2()1()2()1()2(2)1()2(3)1()2()1(xfcxxbxxaxfcxfdxxcxxbxxaxfd)2(。从而确定函数从而确定函数，的值的值求解方程组得出系数求解方程组得出系数)(,xdcba 的方法：的方法：确定函数确定函数)(x 求解满足求解满足 0)(0)(xx 的极小点的极小点 令令0)(2)(3)()1(2)1( cxxbxxax )3(。bxxax2)(6)()1( 而而解方程（解方程（3），有两种情况：），有两种情况：解得解得时，时，当当0. 1 a)4(2)1(bcxx 由（由（2）可知）可知。)1()2()

47、2()1(, 0)(,0)(xxxfxfc 。所以所以0 b的极小点。的极小点。是是即即因此因此)(,02)(xxbx 。x解得解得时，时，当当0. 2 aaacbbxx332)1( )5(acbbaacbbax322336)(22 此时有此时有式中应取式中应取则在则在为使为使)5(,0)( x aacbbxx332)1( acbbc32 )6(式可知式可知由由时，时，而当而当)6(0 a式式所所以以，)6(2)1(bcxx 一表达式。一表达式。两种情况下极小点的统两种情况下极小点的统、是是21极小点的计算公式：极小点的计算公式：令令)7()()( 3)1()2()1()2(xxxfxfs )

48、8()()()2()1(xfxfst )9()()()2()1(22xfxftw )10()2)()()(1)()1()2()2()1()2()1(wxfxfwtxfxxxx 则有则有算法步骤：算法步骤：要求要求计算计算给定初始点给定初始点, )(, )(, )(, )(,. 1)2()1()2()1()2()1(xfxfxfxfxx 。满足条件：满足条件：0)(,0)(,)2()1()1()2( xfxfxx。给定允许误差给定允许误差0,0 。和和、计算计算、按照公式按照公式xwts)10()9()8()7(. 2。否则，转否则，转；则停止计算，得到点则停止计算，得到点，若若4|. 3)1()2(xxx 。停止计算，得到点停止计算，得到点，若若。计算计算xxfxfxf | )(|)(, )(. 4。转转。则令则令，若若2)()(, )()(,0)()1()1()1(xfxfxf