无约束优化问题——线搜索

时间:2024-04-10 22:46:11

   注明:本文的向量均取为列向量。

   本文尝试通过线搜素的方法解决无约束优化问题 。

   线搜索方法是在每一步迭代中先计算一个线性方向p_k,然后决定一个步长alpha_k。具体迭代点变化如下所示:

                                                  无约束优化问题——线搜索

    因此,线搜索方法的关键在于怎样确定搜索方向以及每一次迭代的步长应取多大。

    对于搜索方向p_k,一个最基本的要求就是该方向为所优化的函数的下降方向,从数学角度来说,该方向必须要满足

p_k'*df_k<0(其中'为转置,df为导数)。因此,搜索方向经常有如下形式:

                                                  无约束优化问题——线搜索

     其中,B_k是一个对称非奇异矩阵。当B_k为单位矩阵时,线搜索方向即最速下降方向;当B_k取为f的黑塞矩阵时,线搜索方向即为牛顿方向;当B_k是一个近似的黑塞矩阵时,线搜索方向是拟牛顿方向。因为有如下式子:

                                              无约束优化问题——线搜索

     所以,该搜索方向是下降方向。

     接下来,讨论如何确定搜索方向p_k和步长alpha_k以保证在初始点较远时,该算法依然能保证收敛。

     步长确定

     在确定步长的过程中存在一个矛盾,我们希望选择一个能使f达到充分下降的步长,但与此同时,我们又不想在选择的过程中浪费太多时间。传统的线搜索算法是通过计算一系列候选步长alpha,当这些值满足一些确定条件时停止。线搜索方法通常有两步:第一是计算一个可接受的步长区间,第二是在这个区间里通过对分或插值的方法计算一个可接受的步长。

    步长alpha_k需要满足的一个最基本的条件是f(x_k+alpha_k*p_k)<f(x_k)。显然,这样的步长并没有考虑到收敛速度的问题,f在该步长下是不充分下降的。为了使f达到充分下降,接下来介绍几个充分下降条件。

     wolfe 条件

      一个比较通用的不精准线搜索条件是步长alpha_k应该满足使得目标函数f充分下降,应满足如下不等式:

                                                   无约束优化问题——线搜索

       其中常数项c1取值为(0,1),通常取为c1=1e-4。换句话说,f的下降量需与alpha_k和p_k'df成正比。该不等式也称为Armijo条件。该条件在alpha充分小时即可成立,因此不能保证算法的效率。为了排除不可接受的小步长,引出了第二个条件,curvature条件:

                                                    无约束优化问题——线搜索

       其中c2取值为(c1,1),通常取c2=0.9。

       这两个条件统称为wolf条件,即

                                     无约束优化问题——线搜索

        Goldstein条件

        与wolf条件一样,Goldstein条件确保了步长为充分下降,并且足够大。形式如下:

                                                  无约束优化问题——线搜索

      其中0<c<0.5。

      回溯线搜索

      如果采用回溯的方法来确定步长,即先选择一个足够大的步长alpha_0,然后逐步缩小步长,即可保证所选步长不会太小,这样就可忽略curvature条件。算法如下:

                                                     无约束优化问题——线搜索

       在计算过程中,初始步长alpha为1(牛顿和拟牛顿算法),其它的算法各有不同的值。在每一步迭代中,rho的取值可发生变化,事实上,我们只需要确保对于常数0<rho_lo<rho_hi<1,rho在[rho_lo,rho_hi]之间。

       基于wolfe条件的线搜索算法

       该算法有两步。第一,给定一个初始步长alpha_1,增大步长直到找到另外一个可接受的步长或者包含所需步长的区间。第二步涉及到一个zoom算法,该算法能依次缩短区间直到找到一个可接受的步长。

                                           无约束优化问题——线搜索

                                                   无约束优化问题——线搜索

        编程求解

                                                            无约束优化问题——线搜索