凸优化数学基础笔记（八）：一维线性搜索法

上一节关于求解最优化问题概括中可知迭代最优化算法的基本思路是从已知迭代点Xk∈Rn∈ 出发按照迭代格式Xk1XktkPk1 ,从已知迭代点来求解最优化问题其关键在于如何构造一个搜索方法Pk∈Rn∈ 和确定 一个步长的tk∈R1∈1使下一个迭代点Xk11 处的目标函数值下降即f(Xk1)f(Xk)(1)()。现在我们来讨论当搜索方向Pk已经确定的情况下如何确定步长tk ? 步长因子的选取有多种方法如取步长为常数但这样选取的步长并不最好如何选取最好步长呢实际计算通常采用一维搜索来确定最优步长。​ 对于无约束最优问题minX∈Rnf(X)(1)(1)min∈()当已知迭代点Xk和下降方向Pk 时要确定适当的步长tk使f(Xk1)f(XktkPk)(1)() 比f(Xk)() 有所下降即相当于参数变量t的函数φ(t)f(XktPk)(2)(2)()()要在区间[0,∞)[0,∞)上选取ttk使f(Xk1)f(Xk)(1)() 即φ(tk)f(XktkPk)f(Xk)φ(0)(3)(3)()()()(0)由于这种从已知点的Xk 出发沿某一个下降的搜索方向Pk 来确定步长tk的问题实质上是单变量函数关于步长变量的搜索选取故通常叫做一维搜索。按照这种方法确定的步长tk 又称为最优步长这种方法的优点是它使目标函数值在搜索方向上下降得最多。​ 今后为了简单起见我们用记号Zls(X,P)(4)(4)(,)表示从点X出发沿P方向对目标函数f(X)()作直线搜索所得到的极小值点是Z 。其中l和s 分别是Linear search(直线搜索)的缩写。在目标函数f(X)() 已确定条件下等价于如下两式{f(Xt0P)minf(XtP)φ(t)ZXtP(5)(5){(0)min()()下面我们进一步解释迭代点Xk1XktkPk1 的空间位置容易证明若从Xk出发沿Pk 方向进行一维搜索得到极小值点Xk1XktkPk1则该点处XXk11 则该点处XXk11 的梯度方向∇f(Xk1)∇(1) 与搜索方向Pk 之间应满足∇f(Xk1)TPk0(6)(6)∇(1)0事实上设φ(t)f(XktPk)()()求φ(t)() 的极值对t 求导有φ′(t)∇f(XktPk)TPk(7)(7)′()∇()令φ′(t)0′()0即可得 ∇f(XktPk)TPk0∇()0 ,所以∇f(Xk1)TPk0∇(1)0。​ 式2.5的几何意义是明限的从某一个点Xk出发沿Pk 方向对目标函数f(X)() 作直线搜索所得到的极小值点为Xk11。公式6指出梯度∇f(Xk1)∇(1) 必与搜索方向Pk 正交。又因为∇f(Xk1)∇(1) 与目标函数过点Xk11 的等值面f(X)f(Xk1)()(1) 正交所以进一步看到搜索方向Pk与这个等值面在点Xk11 处相切。1.搜索区间及其确定方法​ 设一维最优化问题为min0≤ttmaxφ(t)(8)(8)min0≤()为了求解式8我们可以引入如下的搜索区间概念。Definition 1设φ:R→R:→t∗∈[0,∞)∗∈[0,∞)(t∗∈[0,tmax])(∗∈[0,])并且φ(t∗)min0≤t≤tmaxφ(t)(9)(9)(∗)min0≤≤()若存在闭区间[a,b]⊂[0,∞)[,]⊂[0,∞)([a,b]⊂[0,tmax][,]⊂[0,]) 并且使t∗∈[a,b]∗∈[,],则称[a,b][,] 为以为优化问题式8的搜索区间*。​ 由定义简而言之一个一维最优化问题的搜索区间就是包含该问题最优解的一个闭区间。通常在进行一维搜索区间然后再在此区间中进行搜索求解。​ 下面介绍一个确定式8的搜索区间确定的简单方法。这个方法的基本思路如下先选定一个初始点t0∈[0,∞)(t0∈[0,tmax])0∈[0,∞)(0∈[0,])和初始步长h00ℎ00。然后沿着t∈[0,∞)∈[0,∞) 轴的正方向搜索前进一个步长得到新点t0h00ℎ0。若目标函数在新点处的值是下降了即φ(t0h0)φ(t0)(10)(10)(0ℎ0)(0)则下一步就从新点的处的值t0h00ℎ0出发的加大步长再向前探索。若目标函数在新点处的值上升即φ(t0h0)φ(t0)(11)(11)(0ℎ0)(0)则下一步以t00为出发点为出发点以原步长开始向t轴的负方向的同样探索。当达到目标函数上升的点时就停止搜索。这时候便得到一个搜索区间。这种以加大步长进行搜索来寻找搜索区间的方法叫做加步搜索法。其加步搜索法的步骤选取初始数据。选取初始点t0∈[0,∞)(t0∈[0,tmax])0∈[0,∞)(0∈[0,]) 计算φ0φ(t0)0(0)。给出初始步长h00ℎ00加步系数α11,令k00。比较目标函数值。令tk1tkhk1ℎ 计算φk1φ(tk1)1(1)若φk1φk1 ,转步骤3否则转步骤4。加大搜索步长。令hk1αhkℎ1ℎ。同时令ttk,tktk1,φkφk1,kk1,1,1,1 转步骤2反向搜索。若k00转换探索方向令hk−hk,ttk1ℎ−ℎ,1转步骤2。否则停止迭代令amin(t,tk1),bmax(t,tk1)(12)(12)min(,1),max(,1)输出[a,b][,]。​ 在加步搜索法中一般建议α22。若能估计式8的最优解的大体位置的话初始点t00要接近于式8的最优解。在具体运用上述的加步搜索法时有时还要考虑一些细节问题。例如当探索得到新点处的目标函数值和出发点处相同的时以及初步步长应如何选取等都需作适当处理。​ 由于以后要介绍的一些一维搜索方法主要适用于式8在搜索区间只有唯一的最优解情况下为此我们再给出下面单谷区间与单谷函数概念。​Definition 2设φ:R1→R1:1→1 闭区间[a,b]⊂R1[,]⊂1。若存在点t∗∈[a,b]∗∈[,]使得 φ(t)() 在[a,t∗][,∗] 上严格递减在[t∗,b][∗,] 上严格递增则称[a,b][,] 是函数φ(t)() 的单谷区间φ(t)()是在[a,b][,] 上单谷函数。​ 由定义2可知一个区间是某函数的单谷区间意味着在该区间中函数只有一个“凹谷”极小值。另外从定义2可知某区间上的单谷函数上不必是连续函数而凸函数在所给区间上必然是单谷函数。单谷函数和单谷区间有如下有用的性质。​定理 1设φ:R1→R1:1→1,[a,b][,]是φ(t)() 的单谷区间任取t1,t2∈[a,b]1,2∈[,] 并且t2t121。若有φ(t2)≤φ(t1)(2)≤(1)则[a,t1][,1]是φ(t)()的单谷区间。若有φ(t2)≥φ(t1)(2)≥(1)则[t2,b][2,]是φ(t)()的单谷区间。