当前位置：文档之家 › 3一维优化方法

3一维优化方法

  • 格式：ppt
  • 大小：894.50 KB
  • 文档页数：34

下载文档原格式

  / 34

合集下载

最优化方法归纳总结

最优化方法归纳总结

最优化方法归纳总结最优化方法归纳总结篇一：最优化方法综述最优化方法综述1.引论1.1应用介绍最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案。

这类问题普遍存在。

例如，工程设计中怎样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排工厂、机关、学校、商店、医院、住户和其他单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域中，诸如此类，不胜枚举。

最优化这一数学分支，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。

1.2优化的问题的基本概念工程设计问题一般都可以用数学模型来描述，即转化为数学模型。

优化设计的数学模型通常包括设计变量、目标函数和约束条件。

三个基本要素。

设计变量的个数决定了设计空间的维数。

确定设计变量的原则是：在满足设计基本要求的前提下，将那些对设计目标影响交大的而参数选为设计变量，而将那些对设计目标影响不大的参数作为设计变量，并根据具体情况，赋以定值，以减少设计变量的个数。

用来评价和追求最优化设计方案的函数就称为目标函数，目标函数的一般表达式为f?x??f?x1,x2,?xn?。

优化设计的目的，就是要求所选择的设计变量使目标函数达到最佳值。

所谓最佳值就是极大值或极小值。

在设计空间中，虽然有无数个设计点，即可能的设计方案，但是一般工程实际问题对设计变量的取值总是有一些限制的，这些限制条件显然是设计变量的函数，一般称之为优化设计问题的约束条件或约束函数。

一维搜索的最优方法(黄金分割法)

一维搜索的最优方法(黄金分割法)

( 1 )＝ ( 2 )＝0.264， f1＝－1.125
新点 ( 2 )＝a 0.618( b a )＝0.354, f 2＝f ( ( 2 ) ) ＝-1.103 (4) 比较函数值，缩短搜索区间 f1 f 2 a 0.118, b ( 2 ) 0.354 判断迭代终止条件: b - a 0.354 0.118 0.236 继续缩短
区间为[a, b] [－0. 5,0.5]，取迭代精度＝0.15。
解：(1) 在初始区间[a, b]内取点并计算函数值。
( 1 )＝b 0.618( b a )＝ 0.118, f1＝f ( ( 1 ) ) ＝－0.854 ( 2 )＝a 0.618( b a )＝0.118,
( 1 )＝b 0.618( b a ) ( 2 )＝a 0.618( b a )
计算f ( ( 1 ) )和f ( ( 2 ) )，令f ( ( 1 ) ) f1 , f ( ( 2 ) ) f 2
( 2 ) 比较函数值，缩小搜索区间 a. f1 f 2 ,则丢掉区间( ( 2 ) ,b ] 部分，取[ a , ( 2 ) ]为 新区间[ a1 , b1 ],在计算中作置换：
(2)+h (3)。计算（ ），令（ ） f3 f f
(3) (3)
(1) 若f 3 f1，则[a,b]=[(3) ,(2)]，停止计算。 (2) 若f 3 f1，则 2h h，(2) (1)，f 2 f1，
(3) (2)，f 3 f 2 (2) h (3)，计算（ ），令（ ） f3 , f f
h 2 1 2 1＝ 2＝1,
2＝ 3＝2 , 3＝ 2 h＝4

机械优化设计-第三章一维优化方法

机械优化设计-第三章一维优化方法
23
机械优化设计
• 第四次缩小区间： 第四次缩小区间： • 令 x2=x1=0.764, , f2=f1=0.282 • x1=0.472+0.382*(0.944-0.472)=0.652, f1=0.223 • 由于f1<f2, 故新区间 由于f 故新区间[a,b]=[a, x2]=[0.472, 0.764] • 因为 b-a=0.764-0.472=0.292>0.2, 应继续缩小区间。 , 应继续缩小区间。 第五次缩小区间： 第五次缩小区间： f2=f1=0.223 令 x2=x1=0.652, x1=0.472+0.382*(0.764-0.472)=0.584, f1=0.262 由于f 故新区间[a,b]=[x1,b]=[0.584, 0.764] 由于f1>f2, 故新区间 因为 b-a=0.764-0.584=0.18<0.2, 停止迭代。 程序演示 , 停止迭代。 极小点与极小值： 极小点与极小值： x*=0.5*(0.584+0.764)=0.674,
x2 = a + 0.618(b − a), y2 = f ( x2 )
f
b = x2 , x2 = x1, y2 = y1
x1 = a + 0.382(b − a), y1 = f ( x1 )
y1 < y2
否
是
y1 y2
x
b
a = x1 , x1 = x2 , y1 = y2
x2 = a + 0.618(b − a), y2 = f ( x2 )
7
机械优化设计
h0
x2
机械优化设计
2.前进搜索 加大步长 h＝2 h ，产生新点x3= x2+ 2h0 ； （a）如y2<y3，则函数在[x1，x3]内 必有极小点，令a= x1，b= x3搜索 区间为[a，b] ； （b）如y2>y3， 令x1=x2 ，y1=y2 ； x2=x3 ，y2=y3 ； h=2h 重新构造新点x3=x2+h，并比较y2、 y3的大小，直到y2<y3。

优化设计的问题

优化设计的问题
外点法：
混合法： 增广拉格朗日乘子法的原问题、新目标函数构造如下所示：
3.6多目标函数的优化方法
比之单目标函数通过比较函数值大小的优化方法，多目标函 数的优化问题要复杂得多，求解难度也较大。目前仍没有最 好的普适的多目标函数优化方法，实际运用中应根据具体的 优化问题，有选择地采用下面介绍的各类方法。 1.统一目标法
引入案例 外啮合齿轮泵的齿轮设计
案例：对处于不同应用环境下的外啮合齿轮泵，其 设计的侧重点是不同的，现在输出压力、输出流量、转
速分别为 25 MPa、100 L/min和 1500 rad/min的情况下，
要求确定一台具有流量均匀性好、体积小、寿命长的外 啮合齿轮泵齿轮的几何设计参数。
3.1 优化设计概述
其优化模型为：
2.主要目标法
在每个实际的具体优化问题中，其实各分目标函数的重要 程度肯定是不一样的，例如对于在性能和利润的两目标函 数的优化问题中，性能指标想当然要比利润指标重要，没 有优良的性能，产品卖不出去，又何来利润。也就是说多 目标函数优化问题的各个分目标函数是有主次之分的。
3.3 一维探索优化方法
• 一、探索区间的确定 • 一维问题的探索方向是确定的，因此，一维探索实际就是
求可性域内的最优步长 (k )，使目标函数达到极小。 • 首先要确定出包含最优点的可性域 [s ,e ] ，主要有外
推法和进退法。
1.外推法
2.进退法
1.Fibonacci法
3）按照下面的迭代公式进入下一轮的迭代，并进行完全雷 同于第2)步的判断和操作。
例3-8 解：
三、二阶梯度法 二阶梯度法又叫牛顿法。
图 3-14 二阶梯度法的求优过程
四、共轭梯度法
图 3-15 同心椭圆族属性和共轭梯度法的探索路线

一维优化方法

一维优化方法

• 最优化设计的目的： • 机械设计师追求其设计的方案是 • 尺寸最小（材料消耗最少或重量最轻） • 成本最低（ 运输、资源分配、安排生产等
） • 性能最好（零件、部件、产品） • 每一产品设计、制造过程中，都含有很多因素
如何优化。 • 因此，最优化理论和技术必将在社会的诸多方
面起着越来越大的作用。
在连续变量优化方法中，又可分为：
2020/3/24
1. 非线性无约束优化方法 1) 直接算法 2) 梯度算法
2. 非线性约束优化方法 1) 直接算法 2) 间接算法
•
直接搜索法：通过函数值的计算和
比较，确定搜索的方向和步长。如：黄
金分割法、二次插值、复合形法等。
•
间接搜索法：利用函数的一阶或二
阶偏导数矩阵确定搜索方向和步长。如
XDRn
s.t.
gu(X)0
u1,2,..p.
hv(X)0
v1,2,..q.
最优方案 最优值
X* [x1*, x2*,...x, x*]T
F (X*)
2020/3/24
• 例:某车间生产甲、乙两种产品。生产甲种产 品每件需要用材料9kg、3个工时、4kw电， 可获利60元。生产乙种产品每件需要用材料 4kg、10个工时、5kw电，可获利120元。若 每天能供应材料360kg、有300个工时、能 供200kw电，问每天生产甲、乙两种产品各 多少件，才能够获得最大的利润。
获得足够精度的近似解时就截断计算。
• 一、迭代过程:从一个选定的初始点X出发,沿某 种优化方法所规定的方向S,确定适当的步长a. 产生一个新的设计点.
•
•
即 : X (k 1 )X (k)(k)S(k)
• 满足

凸优化之无约束优化（一维搜索方法：二分法、牛顿法、割线法）

凸优化之无约束优化（一维搜索方法：二分法、牛顿法、割线法）

凸优化之⽆约束优化（⼀维搜索⽅法：⼆分法、⽜顿法、割线法）1、⼆分法（⼀阶导）⼆分法是利⽤⽬标函数的⼀阶导数来连续压缩区间的⽅法，因此这⾥除了要求 f 在 [a0,b0] 为单峰函数外，还要去 f(x) 连续可微。

（1）确定初始区间的中点 x(0)=(a0+b0)/2 。

然后计算 f(x) 在 x(0) 处的⼀阶导数 f'(x(0))，如果 f'(x(0)) >0 , 说明极⼩点位于 x(0)的左侧，也就是所，极⼩点所在的区间压缩为[a0,x(0)]；反之，如果 f'(x(0)) <0，说明极⼩点位于x(0)的右侧，极⼩点所在的区间压缩为[x(0)，b0]；如果f'(x(0)) = 0，说明就是函数 f(x) 的极⼩点。

（2）根据新的区间构造x(1)，以此来推，直到f'(x(k)) = 0，停⽌。

可见经过N步迭代之后，整个区间的总压缩⽐为（1/2）N，这⽐黄⾦分割法和斐波那契数列法的总压缩⽐要⼩。

1 #ifndef _BINARYSECTION_H_2#define _BINARYSECTION_H_34 typedef float (* PtrOneVarFunc)(float x);5void BinarySectionMethod(float a, float b, PtrOneVarFunc fi, float epsilon);67#endif1 #include<iostream>2 #include<cmath>3 #include "BinarySection.h"45using namespace std;67void BinarySectionMethod(float a, float b, PtrOneVarFunc tangent, float epsilon)8 {9float a0,b0,middle;10int k;11 k = 1;12 a0 = a;13 b0 = b;14 middle = ( a0 + b0 )/2;1516while( abs(tangent(middle)) - epsilon > 0 )17 {18 #ifdef _DEBUG19 cout<<k++<<"th iteration:x="<<middle<<",f'("<<middle<<")="<<tangent(middle)<<endl;20#endif2122if( tangent(middle) > 0)23 {24 b0 = middle;25 }26else27 {28 a0 = middle;29 }30 middle =( a0+b0)/2;31 }3233 cout<<k<<"th iteration:x="<<middle<<",f'("<<middle<<")="<<tangent(middle)<<endl;34 }1 #include<iostream>2 #include "BinarySection.h"345float TangentFunctionofOneVariable(float x)6 {7return14*x-5;//7*x*x-5*x+2;8 }910int main()11 {12 BinarySectionMethod(-50, 50, TangentFunctionofOneVariable, 0.001);13return0;14 }1th iteration:x=0,f'(0)=-52th iteration:x=25,f'(25)=3453th iteration:x=12.5,f'(12.5)=1704th iteration:x=6.25,f'(6.25)=82.55th iteration:x=3.125,f'(3.125)=38.756th iteration:x=1.5625,f'(1.5625)=16.8757th iteration:x=0.78125,f'(0.78125)=5.93758th iteration:x=0.390625,f'(0.390625)=0.468759th iteration:x=0.195312,f'(0.195312)=-2.2656210th iteration:x=0.292969,f'(0.292969)=-0.89843811th iteration:x=0.341797,f'(0.341797)=-0.21484412th iteration:x=0.366211,f'(0.366211)=0.12695313th iteration:x=0.354004,f'(0.354004)=-0.043945314th iteration:x=0.360107,f'(0.360107)=0.041503915th iteration:x=0.357056,f'(0.357056)=-0.001220716th iteration:x=0.358582,f'(0.358582)=0.020141617th iteration:x=0.357819,f'(0.357819)=0.0094604518th iteration:x=0.357437,f'(0.357437)=0.0041198719th iteration:x=0.357246,f'(0.357246)=0.0014495820th iteration:x=0.357151,f'(0.357151)=0.0001144412、⽜顿法（⼆阶导）前提：f 在 [a0,b0] 为单峰函数，且[a0,b0] 在极⼩点附近，不能离的太远否则可能⽆法收敛。

最优化方法及其应用

最简单的最优化问题实际上在高等数学 中已遇到，这就是所谓函数极值，我们习惯 上又称之为经典极值问题．
例1.1 对边长为a的正方形铁板，在四
个 角处剪去相等的正方形以制成方形无盖 水槽，问如何剪法使水槽的容积最大？
一 最优化问题总论
解 设剪去的正方形边长为x，由题意易知，与
此相应的水槽容积为
f (x) (a 2x)2 x
小 点（无约束或约束极小点）的过程比喻为向“山” 的顶峰攀登的过程，始终保持向“高”的方向前 进，直至达到“山顶”．当然“山顶”可以理解
为目 标函数的极大值，也可以理解为极小值，前者称 为上升算法，后者称为下降算法．这两种算法都 有一个共同的特点，就是每前进一步都应该使目 标函数有所改善，同时还要为下一步移动的搜索 方向提供有f用(X的0 ) 信f息(X．1) 如果是f (下Xk 降) 算f (法Xk，1) 则序列
一 最优化问题总论
例1.3 某单位拟建一排四间的停车房，平 面位置如图1.1所示．由于资金及材料的 限制，围墙和隔墙的总长度不能超过 40m，为使车房面积最大，应如何选择 长、宽尺寸？
x1
x2
一 最优化问题总论
解 设四间车房长为 x1，宽为 x2．由题意可
知面积为 f (x1, x2 ) x1 x2 且变量 x1 ，x2 ，应满足
(1.2)
X0
一 最优化问题总论
Xk1 Xk tk Pk， k 0，1，2，
式中,
X
k
——前一次已取得的迭代点，在 开始计算时为迭代初始点 X0；
X k1 ——新的迭代点；
Pk ——第k次迭代计算的搜索方向；
t k ——第k次迭代计算的步长因子．
一 最优化问题总论
按照式（1.2）进行一系列迭代计算所根据 的思想是所谓的“爬山法”，就是将寻求函数极

优化1-一维优化问题

返回( 1 )重新开始。
例1 用进退法确定函数
f ( a ) a2 7a 10 的一维优化初始搜索区间[a,b]。
设初始点0 0,初始步长h 1。
解：按顺序进行计算，有
a. 1 0 0 2 1 h 1
b. 比较 f2 f1
3 2 h 2
c. 比较 f2 f3 h 21 2
f1 f (1 ) 0
2＝
＝4
3
,
f2 f (2 ) 2
3＝2 h＝8 f3 f (3 ) 18
e. 此时有 f1 f2，f2 f3 ,故a=1 2,b 3 .即初始搜索
区间为[2,8].
§2 黄金分割法（0.618法）
一、基本原理
基本思路：逐步缩小搜索区间，直至最小点存在的区 间达到允许的误差范围为止。
(3) (2)，f3 f2 (2) h (3)，计算（ f ( 3 )），令（ f ） (3) f3 ,
返回( 1 )重新开始。
进退试算法步骤
step4. 若在步2中，f2 f1，后退运算
以(1)为起始点，步长反号，反方向搜索。
-h
h; (1) (3), (2) (1), f2
f1 f1
一、一维搜索的概念
迭代计算的基本格式
X X S (k1)
(k)
(k) (k)
显然，搜索方向S（k)和步长因子（k)构成了每一次迭代
的修正量，它们是决定最优化算法好坏的重要因素。
假定给定了搜索方向S（k)，从点X（k)出发沿S（k)方向
进行搜索，要确定步长（k)，使得 f ( X (k1) ) f ( X (k ) （k) S（k) ) f ( X (k ) )
1＝2＝1, 2＝3＝2, 3＝2 h＝4

优化设计第2章 优化设计

x1 d , x2 l
X [d l ]T [ x1 x2 ]T
目标函数的极小化： 约束条件：
1 1 min f ( X ) V d 2l x12 x2 0.785 x12 x2 4 4
g1 ( X ) 8.33l d 3 8.33x2 x13 0 g 2 ( X ) 6.25 d 3 6.25 x13 0
f ( X ( k 1) ) f ( X ( k ) ) 2
（2-8）
3 5 式中， 2 —— 给定的计算精度，一般可取 10 10 。
（３）函数梯度充分小准则 目标函数在迭代点的梯度已达到充分小，即
f ( X ( k 1) ) 3
（2-9）
3 —— 给定的计算精度，一般可取 103 。 式中，
这一迭代过程用数学式子表达，得数值迭代法的基本迭代格式为：
X ( k 1) X ( k ) ( K ) S ( k ) f ( X ( k 1) ) f ( X ( k ) ) gu ( X ( k 1) ) 0 (u 1, 2, , m) (k 0,1, 2, )
(k )
一维搜索方法一般分两步进行：
■ 首先在方向 S ( k ) 上确定一个包含函数极小点的初始区间，即
确定函数的搜索区间，该区间必须是单峰区间；
■ 然后采用缩小区间或插值逼近的方法得到最优步长，即求出
该搜索区间内的最优步长和一维极小点。 一维搜索方法主要有： 分数法 黄金分割法（0.618法） 二次插值 三次插值法等 本节介绍最常用的黄金分割法和二次插值法。
2.迭代计算的终止准则
目前，通常采用的迭代终止准则有以下几种：
● 点距足够小准则 ● 函数下降量足够小准则 ● 函数梯度充分小准则

机械优化设计课件第三章-刘宇


厦门大学物理与机电工程学院
13
区间消去法原理
基本思想
搜索区间确定之后，采用区间消去法逐步缩短搜索区间，从而找 到极小点的数值近似解 在搜索区间[a, b]内任取两点a1和b1，且a1 < b1 ，计算其函数值得如 下结论 （1）f(a1 )<f(b1)，由于函数为单谷，所以极小点必在区间[a, b1]内 （2） f(a1 )>f(b1)，同理，极小点必在区间[a1, b]内 （3） f(a1 )=f(b1)，极小点在区间 极小点在区间[a1, b1]内
（1）选定初始点a1，初始步长h=h0，计算y1=f(α1)和y2=f(α1+h) （2）比较y1和y2 （a）如果y1>y2，转（3）向前探测 （b）如果y1<y2，h=-h0，将α1和α2，y1和y2的值互换。转（3）向后探测 （c）如果y1=y2，极小点在 极小点在α1和α1+h之间 （3）产生新的探测点α3= α2+h，y3=f(α3)
相同点：两种方法都是利用区间消去法原理将初始搜索区间不断 缩短，求得极小值的数值近似解 不同点：表现在试验点（插入点）位置的确定方法不同 试探法：试验点是按照某种个特定的规律确定；不考虑函数值的 试探法 试验点是按照某种个特定的规律确定 不考虑函数值的 分布 插值法：试验点是按照函数值近似分布的极小点确定；利用了函 数值本身及其导数信息；效果更好
第三章 一维搜索方法
主讲人：刘宇
2014/11/12
厦门大学物理与机电工程学院
1
本章内容
一、一维搜索的概念 维搜索的概念 二、搜索区间的确定与区间消去法原理 三 一维搜索的试探方法 三、 维搜索的试探方法—黄金分割法 四、一维搜索的插值方法
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

f (b)
bx
p(x) A(x a)3 B(x a)2 C(x a) D p/ (x) 3A(x a)2 2B(x a) C
2020/11/27
21
三）插值多项式系数
A
(b
a)[
f
/ (b)
f / (a)] (b a)3
2[
f
(a)
f
(b)]
B
3[
f
(b)
f
(a)] (b a)[ (b a)2
解：
kh 0.1
1 0.2
x1 y1 09
x2 y2 0.1 8.203
x3 y3 0.3 6.681
2 0.4 0.1 8.203 0.3 6.681 0.7 4.429
3 0.8 0.3 6.681 0.7 4.429 1.5 7.125
可得初始搜索区间 a, b 0.3, 1.5.
2020/11/27
3A
应取“+” 号
故有
xp a B
B2 3AC a
3A
B
C B2 3AC
2020/11/27
23
五）缩短区间的方法
a
xp
b
* 1）当 f '(xp ) 0,则b xp;
2）当 f '(xp ) 0,则a xp.
六）终止准则
f / (xp )
2020/11/27
24
七）迭代步骤 输入a,b,ε
f3
x1
x
p
x2
x3
2020/11/27
15
二）二次插值曲线的极小点 插值多项式： p(x) ax2 bx c
1）求驻点 dp 2ax b 0 dx
2）求系数a和b
xp
b 2a
ax12 bx1 c f1 ax22 bx2 c f2 ax32 bx3 c f3
a f1(x2 x3) f2(x3 x1) f3(x1 x2) (x1 x2 )(x2 x3)(x3 x1) b f1(x22 x32 ) f2 (x32 x12 ) f3(x12 x22 ) (x1 x2 )(x2 x3)(x3 x1)
求出a、b后得
xp
1 2
f1(x22 x32 ) f2 (x32 x12 ) f3(x12 x22 ) f1(x2 x3) f2 (x3 x1) f3(x1 x2 )
2020/11/27
16
三）区间的缩短
输入
x1, x2 , x3
xP 否
否
xp<x2
是
xp>x2
是 x1, xP , x2, x3
f2 f1 f3 f1 这表明此时三个插值点共线。 x2 x1 x3 x1
f2
f3
f1
x1
x2
x3
ⅱ) (xP x1)(x3 xP ) 0
f1
x1
2020/11/27
f2
f3
x2 x3
20
§3-5 三次两点插值法
一）插值条件
根据两点处的目标函数值和一阶导数插值。
f
f (a) a
二）插值多项式
b xp, f (b) f (xp ), f (b) f (xp )
计算 f (x*p ), f (x*p )
否
f (x*p ) 0 是
否
f (x*p )
x xp , f f (xp )
是
结束
2020/11/27
25
2
2020/11/27
12
②关于缩小区间总次数的证明
证： 0.618 k (b a)
0.618k
ba k ln 0.618 ln
ba
即
k
ln[
ln
/(b a)] 0.618
(或k
lg[ /(b a)])
lg 0.618
2020/11/27
13
二)迭代步骤
f
给定 a,b,
x1 a 0.382 (b a), y1 f (x1)
x2 a 0.618(b a), y2 f (x2 )
是
y1 y2 否 a x1, x1 x2 , y1 y2
b x2, x2 x1, y2 y1 x1 a 0.382(b a), y1 f (x1)
x2 a 0.618(b a), y2 f (x2 )
f
否
ba
1.8 12.096
1.6 8.488
1.2 4.584
x3 y3
1.6 8.488 1.2 4.584 0.4 5.992
可得初始搜索区间 a, b 0.4, 1.6.
2020/11/27
8
§3-3 格点法
一）基本思路
先将搜索区间分成若干等分，计算出当中的n个等分 点的目标函数值. 再通过比较,找出其中的最小点，则该 点的两个邻近点围成缩短了的新区间。
一）基本思路
—试探后作前进或后退计算。
f
f
x1 x2 x3
x
x1 x2 x3
前进计算
2020/11/27
x1 x2 x
x3 x2 x1 x3 x2 x1
后退计算
5
二) 迭代步骤
给定x1、h0 h=h0
初始进退距
f
y1 y2 y3
h= -h
x3=x1 y3=y1
y1=f(x1)、x2=x1+h、y2=f(x2)
F* 2
2020/11/27
3
三）一维搜索的步骤
1)确定一个包含最优点的初始搜索区间
特点：高--低--高
f
2)将含最优点的区间不断缩小
o
a
bx
当该区间的长度小于预先给定的一个很小的正数 ，
则可认为该区间中的某点(如中点)是最优点。
* 区间缩短率：
新区间长度
原区间长度
2020/11/27
4
§3-2 确定初始搜索区间的进退算法
f
a
2020/11/27
xmx1 m xm1 b
x
9
二）每轮迭代区间的缩短率
2
n 1
三）特点
1）思路简单，编程容易，宜于离散型优化问题； 2）计算量大，不宜用于高维优化问题。
2020 金 分 割 法
一）基本思路
将区间按一定的比例缩小，且正常迭代时 每缩短一次区间只需计算一次函数值。
7
3 2.用进退法确定函数f (x) 3x3 8x 9的一维优化初始区间,给定 初始点x1 1.8, 初始进退距h0 0.1.
解：
kh
x1
y1
0.1 1.8 12.096 1
-0.2 1.9 14.377
2 -0.4 1.8 12.096
3 -0.8 1.6 8.488
x2
y2
1.9 14.377
1）取下降步长：
X (0) 0 0T , S(0) 1 1T
F x12 x22 8x1 12x2 52
2 2 20 52
--能使目标函数值下降的步长；
上例中，
F (0) 52, 取 3, 得F (1) 10 F (0) ,
故 3是下降步长.
2）取最优步长：
上例中，
令 dF 4 20 0,得 5是最优步长. d
第三章 一维搜索方法
1）确定初始搜索区间的进退算法； 2）格点法； 3）黄金分割法； 4）二次插值法； 5）三次两点插值法。
2020/11/27
1
§3-1 问题的提出
一）一维问题是多维问题的基础 X (k1) X (k) S (k)
* X (在k) 上次迭代中已求得， S (由k) 某种逻辑方式（如负梯度方向、共轭方
计算 f (a), f (b), f (a), f (b)
计算A，B，C，D
A=0
否
A>0
是 xp a C /(2B)
是 xp a (B B2 3AC ) /(3A)
否
xp a (B B2 3AC ) /(3A)
a xp, f (a) f (xp ), f (a) f (xp )
1） 0.618
2）缩短区间的总次数
k ln[ /(b a)]
ln 0.618
为预先给定的误差限。
2020/11/27
11
*①关于 0.618的证明
证：
1
l
l
f
l
(1 )l
(1 )l
2
(1 )l l
1
令 1 2 得：
2 1 0
a
x1 x2
(1 )l l
l
bx
其正根为：
5 1 0.618033988
f
/ (b)
2
f
/ (a)]
C f / (a)
D f (a)
2020/11/27
22
四）插值函数的极小点
由 p/ (x) 3A(x a)2 2B(x a) C 0
得
2B 4B2 12 AC B B2 3AC
xa
6A
3A
* 如何选取？
因有极小，其二阶导数应大于0：
p'' (x) 6 A(x a) 2B 0 xa B
结束
2020/11/27
本书认 为是由于 区间缩到 很小时因 计算机舍 入误差引 起，可取 中间点输 出。
19
ⅰ)A=0
f1(x2 x3 ) f2 (x3 x1) f3 (x1 x2 ) 0
f1[( x2 x1) (x3 x1)] f2 (x3 x1) f3(x1 x2 ) 0
x1, x2, xP , x3
x4=0.5(x1+x2)