博客

最近工作需要用到ceres，代码里面都直接给出了结果及很简单说明，在编程的过程中为了多了解一些，顺便网络查询了一些背景理论以及阅读一些数值优化方法的教材，随手记录了一下学习笔记，现计划分几篇分享到微信公众号。

无约束最优化方法

最小二乘法优化方法整个理论体系被包含在无约束最优化方法之中，目的是研究在无约束情况下如何求最优解的问题，采用迭代法求解本质是确定一个迭代差值dx，使


目标/代价函数


f(x+dx


)下降，定义g(x)和G(x)分别为目标函数f(x)的一阶及二阶导数。

对于局部最优解：

1. • 
     
     一阶必要条件：一阶导数g(x*)=0
     
     

   • 
     
     二阶必要条件：二阶导数G(x*)半正定
     
     

     
     半正定：对于非0向量d满足d’*G*d >=0
     

   • 
     
     二阶充分条件
     
     

     • 
       
       g(x*)=0，且
       
       

     • 
       
       
       
       G(x*)正定：对于非0向量d满足d’*G*d >0
       
       

       • 
         证明：
         

       
       Taylor展开： f(x + alpha*d) = f(x) + 0.5 * alpha^2 * d’ * G(x) * d + o(||alpha * d||^2)，当d’ * G(x*) * d > 0, f(x + alpha*d) > f(x) ,即 f(x) 为严格局部极小值；
       

     • 
       下降方向d的约束
       

       
       由一般性Taylor展开：f(x + alpha*d) = f(x) + alpha * g'(x) * d + o(
       

       
       ||alpha * d)||^2)，在步长alpha大于0情况下，要使f下降，则必须满足：
       
       g'(x) * d  < 0
       
       ;
       

       
       
       
       

   
   上面的alpha和d的求解方法最常见分为最速下降法和牛顿法：
   

   • 
     最速下降法
     

     • 
       Taylor展开，只保留一阶项，忽略二阶及高阶项
       

       • 
         f(x+a*d) = f(x) + a * d’ * g(x) ，d为下降方向，a为步长，大于0的标量；
         
         
         

     • 
       d取负梯度方向，即d = -g(k)，此时目标函数最速下降（下降方向d与梯度方向相反，下降最快）；
       

     • 
       当求出d之后，采用精确线性搜索求出a，固定d之后再次优化得到a；
       

     • 
       举例:
       

       
       优化函数：f(x)=0.5 * x1^2 + 2.5 * x2^2,
       

       
       其中x=(x1,x2)’，
       

       
       当初始值x0 =(5,1),则在x0处的梯度d为(5,5)’，按照精确线性搜索min f(x0 – alpha * d)，可求alpha = 0.3，即下一步迭代x1 = x0 + alpha * d = (3.333,-0.667)’,按照上面的步骤持续迭代，直到梯度足够小（接近为0）停止迭代。
       

   • 
     牛顿法
     

     
     Taylor展开，保留二阶，忽略高阶项：f(x+h) = f(x) + h’ * g(x) + 0.5 * h’ * G * h；
     
     定义：min(q(h)) = min (f(x+h))，对h求导，令q'(h) = 0，即
     
     
     g + 0.5 * h’ * (G’ + G) = 0，由于G为f(x)的hessian矩阵，G为对称矩阵，即有
     
     
     G * h = -g
     
     
     ,若G正定，由 h’ * G * h = -h’ * g  > 0，下降方向h显然满足f下降条件，当G’G非奇异时，h = -inv(G’G) * g，这种直接求逆的做法效率很低，一般会使用矩阵分解（如QR分解）来求h，在求出h之后，再迭代f(x+h)，由于牛顿法每次迭代都需要二阶导数，效率很会很低，实际的工程一般是采用近似G的做法，下面的最小二乘法会有说明。
     
     

     
     
     
     
     最小二乘法优化问题
     
     
     
     
     

     
     
     
     
     
     

     1. 定义如上式，r为残差函数，有一个或以上为非线性函数，上式为非线性最小二乘问题反之为线性最小二乘优化问题，由1节 将优化函数taylor展开之后牛顿法优化方程：
        
        G * h = -g
        
        ，此方程为解决最小二乘优化问题基本方程。
        
        

        • 
          求g
          
          
          ，链式法则
          

     
     

     
     
     背景求导知识（分子阈）：
     
     
     
     
     
     
     
     
     
     
     
     
     

     • 求G

       公式推起来特别繁琐，直接给出结论了:
       
       

       G = g’ * g + S，

       即解最小二乘问题牛顿方程为：

       
       
       
       (g’ * g + S)* h = -g’ * r
       
       
       , 当S为0时转换为线性最小二乘问题。
       
       
       

       
       
       
       

       (未完待续)