凸优化数学基础笔记八一维线性搜索法 由上一节关于求解最优化问题概括中可知迭代最优化算法的基本思路是从已知迭代点\(\mathbf{X}_k\in{R^n}\)出发按照迭代格式\(\mathbf{X}_{k1}\mathbf{X}_kt_k\mathbf{P}_k\),从已知迭代点来求解最优化问题其关键在于如何构造一个搜索方法\(\mathbf{P}_k\in{R^n}\)和确定 一个步长的\(t_k\in{R^1}\)使下一个迭代点\(\mathbf{X}_{k1}\)处的目标函数值下降即\(f(\mathbf{X}_{k1})f(\mathbf{X}_k)\)。现在我们来讨论当搜索方向\(\mathbf{P}_k\)已经确定的情况下如何确定步长\(t_k\)? 步长因子的选取有多种方法如取步长为常数但这样选取的步长并不最好如何选取最好步长呢实际计算通常采用一维搜索来确定最优步长。 对于无约束最优问题\[\min_{\mathbf{X}\in{R}^n}f(\mathbf{X}) \tag{1} \]当已知迭代点\(\mathbf{X}_k\)和下降方向\(\mathbf{P}_k\)时要确定适当的步长\(t_k\)使\(f(X_{k1})f(\mathbf{X}_kt_k\mathbf{P}_k)\)比\(f(\mathbf{X}_k)\)有所下降即相当于参数变量\(t\)的函数\[\varphi(t)f(\mathbf{X}_kt\mathbf{P}_k)\tag{2} \]要在区间\([0,\infty)\)上选取\(tt_k\)使\(f(\mathbf{X}_{k1})f(\mathbf{X}_k)\)即\[\varphi(t_k)f(\mathbf{X}_kt_k\mathbf{P}_k)f(\mathbf{X}_k)\varphi{(0)} \tag{3} \]由于这种从已知点的\(\mathbf{X}_k\)出发沿某一个下降的搜索方向\(\mathbf{P}_k\)来确定步长\(t_k\)的问题实质上是单变量函数关于步长变量的搜索选取故通常叫做一维搜索。按照这种方法确定的步长\(t_k\)又称为最优步长这种方法的优点是它使目标函数值在搜索方向上下降得最多。 今后为了简单起见我们用记号\[Zl_s(\mathbf{X},\mathbf{P}) \tag{4} \]表示从点\(\mathbf{X}\)出发沿\(\mathbf{P}\)方向对目标函数\(f(\mathbf{X})\)作直线搜索所得到的极小值点是\(\mathbf{Z}\)。其中\(l\)和\(s\)分别是Linear search(直线搜索)的缩写。在目标函数\(f(\mathbf{X})\)已确定条件下等价于如下两式\[\begin{cases} f(\mathbf{X}t_0\mathbf{P})\min{f(\mathbf{X}t\mathbf{P})}\varphi(t)\\ \mathbf{Z}\mathbf{X}t\mathbf{P} \end{cases} \tag{5} \]下面我们进一步解释迭代点\(\mathbf{X}_{k1}\mathbf{X}_kt_k\mathbf{P}_k\)的空间位置容易证明若从\(\mathbf{X}_k\)出发沿\(\mathbf{P}_k\)方向进行一维搜索得到极小值点\(\mathbf{X}_{k1}\mathbf{X}_kt_k\mathbf{P}_k\)则该点处\(\mathbf{X}\mathbf{X}_{k1}\)则该点处\(\mathbf{X}\mathbf{X}_{k1}\)的梯度方向\(\nabla{f(\mathbf{X}_{k1})}\)与搜索方向\(\mathbf{P}_k\)之间应满足\[\nabla{f(\mathbf{X}_{k1})}^T\mathbf{P}_k0 \tag{6} \]事实上设\(\varphi(t)f(\mathbf{X}_kt\mathbf{P}_k)\)求\(\varphi(t)\)的极值对\(t\)求导有\[\varphi^{\prime}(t)\nabla{f(\mathbf{X}_kt\mathbf{P}_k)}^T\mathbf{P}_k \tag{7} \]令\(\varphi^{\prime}(t)0\)即可得\(\nabla f(\mathbf{X}_kt\mathbf{P}_k)^T\mathbf{P}_k0\),所以\(\nabla{f(\mathbf{X}_{k1})}^T\mathbf{P}_k0\)。 式2.5的几何意义是明限的从某一个点\(\mathbf{X}_k\)出发沿\(\mathbf{P}_k\)方向对目标函数\(f(\mathbf{X})\)作直线搜索所得到的极小值点为\(\mathbf{X}_{k1}\)。公式6指出梯度\(\nabla{f(\mathbf{X}_{k1})}\)必与搜索方向\(\mathbf{P}_k\)正交。又因为\(\nabla{f(\mathbf{X}_{k1})}\)与目标函数过点\(\mathbf{X}_{k1}\)的等值面\(f(\mathbf{X})f(\mathbf{X}_{k1})\)正交所以进一步看到搜索方向\(\mathbf{P}_k\)与这个等值面在点\(\mathbf{X}_{k1}\)处相切。1.搜索区间及其确定方法 设一维最优化问题为\[\min_{0\leq{t}t_{max}} \varphi(t) \tag{8} \]为了求解式8我们可以引入如下的搜索区间概念。Definition 1设\(\varphi:R\rightarrow{R}\)\(t^*\in[0,\infty)\)\((t^*\in[0,t_{max}])\)并且\[\varphi(t^*)\min_{0\leq{t}\leq{t_{max}}}{\varphi(t)} \tag{9} \]若存在闭区间\([a,b]\subset[0,\infty)\)(\([a,b]\subset{[0,t_{max}]}\)) 并且使\(t^{*}\in[a,b]\),则称\([a,b]\)为以为优化问题式8的搜索区间*。 由定义简而言之一个一维最优化问题的搜索区间就是包含该问题最优解的一个闭区间。通常在进行一维搜索区间然后再在此区间中进行搜索求解。 下面介绍一个确定式8的搜索区间确定的简单方法。这个方法的基本思路如下先选定一个初始点\(t_0\in[0,\infty)(t_0\in[0,t_{max}])\)和初始步长\(h_00\)。然后沿着\(t\in[0,\infty)\)轴的正方向搜索前进一个步长得到新点\(t_0h_0\)。若目标函数在新点处的值是下降了即\[\varphi(t_0h_0)\varphi({t_0}) \tag{10} \]则下一步就从新点的处的值\(t_0h_0\)出发的加大步长再向前探索。若目标函数在新点处的值上升即\[\varphi{(t_0h_0)}\varphi(t_0) \tag{11} \]则下一步以\(t_0\)为出发点为出发点以原步长开始向\(t\)轴的负方向的同样探索。当达到目标函数上升的点时就停止搜索。这时候便得到一个搜索区间。这种以加大步长进行搜索来寻找搜索区间的方法叫做加步搜索法。其加步搜索法的步骤选取初始数据。选取初始点\(t_0\in[0,\infty)(t_0\in[0,t_{max}])\)计算\(\varphi_0\varphi(t_0)\)。给出初始步长\(h_00\)加步系数\(\alpha1\),令\(k0\)。比较目标函数值。令\(t_{k1}t_kh_k\)计算\(\varphi_{k1}\varphi(t_{k1})\)若\(\varphi_{k1}\varphi_{k}\),转步骤3否则转步骤4。加大搜索步长。令\(h_{k1}\alpha h_k\)。同时令\(tt_k,t_kt_{k1},\varphi_k\varphi_{k1},kk1\)转步骤2反向搜索。若\(k0\)转换探索方向令\(h_k-h_k,tt_{k1}\)转步骤2。否则停止迭代令\[a\min({t,t_{k1}}),b\max{(t,t_{k1})} \tag{12} \]输出\([a,b]\)。 在加步搜索法中一般建议\(\alpha2\)。若能估计式8的最优解的大体位置的话初始点\(t_0\)要接近于式8的最优解。在具体运用上述的加步搜索法时有时还要考虑一些细节问题。例如当探索得到新点处的目标函数值和出发点处相同的时以及初步步长应如何选取等都需作适当处理。 由于以后要介绍的一些一维搜索方法主要适用于式8在搜索区间只有唯一的最优解情况下为此我们再给出下面单谷区间与单谷函数概念。Definition 2设\(\varphi:\mathbf{R}^1\rightarrow{\mathbf{R}^1}\)闭区间\([a,b]\subset\mathbf{R}^1\)。若存在点\(t^*\in[a,b]\)使得\(\varphi(t)\)在\([a,t^*]\)上严格递减在\([t^*,b]\)上严格递增则称\([a,b]\)是函数\(\varphi(t)\)的单谷区间\(\varphi(t)\)是在\([a,b]\)上单谷函数。 由定义2可知一个区间是某函数的单谷区间意味着在该区间中函数只有一个“凹谷”极小值。另外从定义2可知某区间上的单谷函数上不必是连续函数而凸函数在所给区间上必然是单谷函数。单谷函数和单谷区间有如下有用的性质。定理 1设\(\varphi:\mathbf{R}^1\rightarrow\mathbf{R}^1\),\([a,b]\)是\(\varphi(t)\)的单谷区间任取\(t_1,t_2\in[a,b]\)并且\(t_2t_1\)。若有\(\varphi(t_2)\leq\varphi(t_1)\)则\([a,t_1]\)是\(\varphi(t)\)的单谷区间。若有\(\varphi(t_2)\geq\varphi(t_1)\)则\([t_2,b]\)是\(\varphi(t)\)的单谷区间。 上述定理说明经过函数值的比较可以把单谷区间缩短为一个较小的单谷区间。换句话说利用这个定理可以把搜索区间无限缩小从而求到极小点。以下介绍的几种一维搜索方法都是利用这个定理通过不断的搜索区间来求得一维最优化问题的近似最优解。