《最优化方法》课程教学资源（PPT课件）第三章 线性搜索（刘二永）

第三章 线性搜索

第三章 线 性 搜 索

可题描述 已知x,并且求出了x处的可行下降方向p, 从x出发,沿方向P求目标函数的最优解, min f(x+pk)=min o(a C>0 a>0 或者选取a>0使得 2=m0+y

问题描述 已知 , k x 并且求出了 k x 处的可行下降方向 , k p 从 k x 出发，沿方向 k p 求目标函数的最优解， 或者选取 (  ) ()  0  0 min min   f xk + pk =  0 k 使得： = min   0 ( + ) k = 0 T k k k   f x p p

设其最优解为αk(叫精确步长因子), 于是得到一个新点:x41=xk+aP 所以线性搜索是求解一元函数o(a) 的最优化问题(也叫维最优化问题) 我们来求解 asks

设其最优解为  k （叫精确步长因子）， k k k k x = x + p +1 所以线性搜索是求解一元函数 () 的最优化问题（也叫一维最优化问题）。 我们来求解： 于是得到一个新点： f (x) axb min

一般地,线性搜索算法分成两个阶段 第一阶段确定包含理想的步长因子 (或问题最优解)的搜索区间 第二阶段采用某种分割技术或 插值方法缩小这个区间

一般地，线性搜索算法分成两个阶段： 第一阶段确定包含理想的步长因子 （或问题最优解）的搜索区间； 第二阶段采用某种分割技术或 插值方法缩小这个区间

进退法(寻找下单峰区间) 在线搜索之前,必须先知道一个f(x)的下 单峰区间。我们将求出f(x)的一个形如p6 形式的下单峰区间。 因为我们关心的问题是minf(x+p)=mmoa) 我们的目的是找出两个点x<x2,使得 f(x)≤f(x)f(x)≤f(0

进退法（寻找下单峰区间） 在线搜索之前，必须先知道一个 ( ) ( ); ( ) (0) 1 2 1 f x  f x f x  f f (x) 单峰区间。 的下 我们将求出 f (x) 的一个形如 0,b 形式的下单峰区间。 因为我们关心的问题是： (  ) ()  0  0 min min   f xk + pk = 我们的目的是找出两个点 , 1 2 x  x 使得：

给定初始点xn=0.初始步长△x>0,x,=xn+Ax 下面分两种情况讨论 (1)f(x)≤f(x0) x1对应着图上用红线标出的一部分

0 x 给定初始点 0, x0 = 初始步长 x  x = x + x 1 0 0, （１） ( ) ( ) 1 0 f x  f x 1 x 对应着图上用红线标出的一部分 下面分两种情况讨论：

(1)f(x)≤f(x) △ 2△ 此时x取值小,我们加大步长向右搜索, 取Ax=2△x,x2=x1+Ax 若f(x)≤f(x2),则我们要找的区间即为[xn,x

0 x 此时 1 x 我们加大步长向右搜索， x = x x = x +x 2 1 2 , 若 ( ) ( ), 1 2 f x  f x   0 2 x , x （１） ( ) ( ) 1 0 f x  f x x 1 x 2x 2 x 取值小， 取 则我们要找的区间即为

(1)f(x)≤f(x) △ 2△ 若f(x)>f(x2),则我们取的步长偏小 Yx=x Ax=2Ax.x=x,+Ax 继续往下判断,直到满足f(x)≤f(z)

0 x （１） ( ) ( ) 1 0 f x  f x x 1 x 2x 2 x 若 继续往下判断，直到满足 ( ) ( ), 1 2 f x  f x 则我们取的步长偏小。 令 x = x x = x x = x +x 1 2 2 1 , 2 , ( ) ( ). 1 2 f x  f x 2 x 1 x

(2)f(x)>f(x) 此时x取值大,我们缩小步长向左搜索, 取Ax=Ax/2,x2=x,x1=x,-△x 若f(x)≤f(x)则我们要找的区间即为[xn,x] 否则继续缩小区间,直到满足f(x)≤f(x

0 x 此时 1 x 我们缩小步长向左搜索， x = x x = x x = x −x 2 1 1 2 / 2, , 若 ( ) ( ), 1 0 f x  f x   0 2 x , x （２） ( ) ( ) 1 0 f x  f x 1 x 2 x 取值大， 取 则我们要找的区间即为 1 x 否则继续缩小区间，直到满足 ( ) ( ). 1 0 f x  f x

算法3.1进退法 给定初始点x=0,初始步长△0) step1计算(x),转Step2 step2x=x+Ax,计算/(x) 若f(x)≤/(x),则转Step3酒则转Step5。 Step3 令Ax=2Ax,x2=x+Ax,计算/(2) 若fx)≤f(x)则得区间,x为初始区间,停 若f(x)>f(x)则转Step4

算法3.1 进退法 Step1 给定初始点 0, x0 = 初始步长 x( 0) 计算 ( ), 0 f x 转Step２ Step2 , 1 0 x = x + x 计算 ( ), 1 f x 若 ( ) ( ), 1 0 f x  f x 则转 Step３；否则转Step５。 Step3 令 2 , , 2 1 x = x x = x +x 计算 ( ). 2 f x 若 ( ) ( ), 1 2 f x  f x 则得区间   0 2 x , x 为初始区间，停； 若 ( ) ( ), 1 2 f x  f x 则转 Step4