最优化理论与算法(第二章) 联系客服

发布时间 : 星期五 文章最优化理论与算法(第二章)更新完毕开始阅读a7d1d02de2bd960590c6773b

第二章 一维搜索

§2.1. 引言

一、精确与非精确一维搜索

如前所述,最优化算法的迭代格式为:

xk?1?xk??kdk

因而算法的关键就是选择合适的搜索方向,然后再确定步长因子?k。若设

?(?)?f(xk??dk)

现在的问题是从xk出发,沿dk方向搜索,希望找到?k,使得?(?k)??(0),这就是所谓的一维搜索或称为线搜索(line search)问题。

⑴ 若求得的?k,使目标函数沿方向dk达到最小,即使得

f(xk??kdk)?minf(xk??dk)

??0或 ?(?k)?min?(?),

??0则称为最优一维搜索,或精确一维搜索。相应的?k称为最优步长因子。 ⑵ 如果选取?k,使目标函数获得可以接受的改善,即

f(xk)?f(xk??kdk)?0,

则称之为近似一维搜索,或非精确一维搜索。

注:精确搜索与非精确搜索在最优化算法中均广泛应用,它们存在各自的优缺点。

二、一维搜索的基本框架

一维搜索实际上是一元函数的极值问题,其基本的解决框架是: ⑴ 确定包含最优解的初始搜索区间;

⑵ 采用某些区间分割技术或插值方法不断缩小搜索区间,最后得到解。

注:值得注意的是,这样得到的解大多数情况下均为近似解。因此,即便采用精确一维搜索策略,只要应用了数值方法,最终得到的结果都不一定是真正数学意义上的最佳步长因子。

初始搜索区间的确定

1

定义2.1 设?:R?R,?*?[0,??)是函数?(?)的最小值点,即?(?)?min?(?)。若存在闭

??0*区间[a,b]?[0,??),使 ?*?[a,b],则称[a,b]为一维极小化问题min?(?)的搜索区间。

??0确定初始搜索区间的进退法

基本思想:从一点出发,按一定步长探测,试图找到函数值呈高-低-高变化的三点。具体地,从初始点?0出发,取初始步长为h0。若?(?0?h0)??(?0),则下一步从新点?0?h0出发,加大步长,再向前搜索。若?(?0?h0)??(?0),则下一步仍从?0出发,沿反方向搜索,直到?(?)上升,即?(?)??(?0)为止。

在确定了初始搜索区间后,剩下就是采用具体的一维搜索方法确定出?。后面将分别介绍几种常用的一维搜索方法,这些方法主要是针对所谓单峰函数设计的。

单峰函数的定义

定义2.2 设?:R?R,[a,b]?R。若存在?*?[a,b],使得函数?(?)在[a,?*]上单调下降,而在[?*,b]上单调上升,则称[a,b]是函数?(?)的单峰区间,?(?)是[a,b]上的单峰函数(准确地说应是单谷函数)。

单峰函数还可以等价地定义如下

定义2.3 如果存在唯一的??[a,b],使得对于任意的?1,?2?[a,b]且?1??2,有

⑴ 若?2??*,则?(?1)??(?2); ⑵ 若?1??*,则?(?1)??(?2)。

则称?(?)是[a,b]上的单峰函数。

下面定理表明,对单峰函数,可以通过简单地比较函数值,缩小搜索区间。 定理2.4 设?(?)是[a,b]上的一个单峰函数,?1,?2?[a,b],且?1??2。

⑴ 若?(?1)??(?2),则[a,?2]是?(?)的单峰区间; ⑵ 若?(?1)??(?2),则[?1,b]是?(?)的单峰区间。

证明:略

2

**§2.2. 精确一维搜索的收敛理论

一、基于精确一维搜索的极小化算法

无约束最优化问题算法的基本框架:

⑴ 给出初始点x0?Rn,允许误差??0,置k:?0 ⑵ 计算下降方向dk

⑶ 利用一维搜索,确定步长因子?k,使f(xk??kdk)?minf(xk??dk)

??0⑷ 令xk?1?xk??kdk,若?f(xk?1)??,则停止,输出最优解x*?xk?1。 否则,置k:?k?1,转⑵。

在上面算法中,采用了精确一维搜索。下面证明基于精确一维搜索的极小化算法的收敛性。

二、算法收敛性

2定理2.5 设?k是minf(xk??dk)的解,若?f(xk??dk)?M (???0),则有:

??0f(xk)?f(xk??kdk)?证明:由定理假设,有

12?f(xk)cos2dk,??f(xk) 2Mf(xk??dk)?f(xk)???f(xk)dk?令 ???Tdk?f(xk)T?22Mdk2,(???0)

Mdk2T(若要??0,则必须dk, ?f(xk)?0,即dk与??f(xk)成锐角)

f(xk)?f(xk??kdk)?f(xk)?f(xk??dk)???d?f(xk)?T?f(xk))21(dk1???f(xk)2Mdk22M2T(dk?f(xk))2Tk?22Mdk2?f(xk)2dk2?12?f(xk)cos2dk,??f(xk), 2M定理证毕。

注:⑴ 由证明过程可以看出,dk必须和??f(xk)成锐角。

⑵ 给出了精确搜索前提下,每步迭代所得改进量的估计式,显然与dk有关。 定理2.6 设f(x)是开集D?R上的连续可微函数,若某一极小化算法满足:

n 3

f(xk?1)?f(xk),?f(xk)Tdk?0,?k

又设x?D是序列?xk?的聚点,K1是满足limxk?x的指标集。假定存在M?0,使得?k?K1,

x?K1有dk?M,又设d是序列{dk}的任意聚点,则

?f(x)Td?0

进一步,若f(x)在D上二次连续可微,则还有

dT?2f(x)Td?0。

证明:设K2?K1是满足 d?limdk 的指标集,下面用反证法证明。若定理结论不成立,

k?K2即 ?f(x)Td?0, 由于 ?f(xk)Tdk?0,

注意到k?K2时, ?xk?K?x,?dk?K?d

22则有 ?f(x)Td?0,

因而必有 ?f(x)Td????0。 (﹡)

于是存在x的邻域N(x)和指标集K3?K2,使得当x?N(x),k?K3时,有

?f(x)Tdk???2?0, (由(﹡)式可得)

?是一个充分小的正数,使得对所有0?????,及所有k?K3,都有 设?xk??dk?N(x), (由xk?x,dk有界可得)

则 f(x)?f(x0)? ??[f(xk?0?k?1)?f(xk)]?k?K3?[f(xk?K3k?1)?f(xk)]

k?K3?[f(x?k?dk)?f(xk)]???f(xk??k??dk)T??dk (0??k?1) ?? ?????, (?)??2k?K3T与f(x)?f(x0)为有限值矛盾,故必有?f(x)d?0。 同样地,若 d?f(x)d?0

T2 4