ConstrainedOptPack::MatrixSymPosDefLBFGS Class Reference

Implementation of limited Memory BFGS matrix for arbitrary vector spaces. More...

#include <ConstrainedOptPack_MatrixSymPosDefLBFGS.hpp>


Detailed Description

Implementation of limited Memory BFGS matrix for arbitrary vector spaces.

The function set_num_updates_stored() must be called first to set the maximum number of the most recent updates that can be stored. The storage requirements for this class are O( n*m + m*m ) which is O(n*m) when n >> m which is expected (where n is the dimension of the vector space and m is the maximum number of updates stored).

This implementation is based on:

Byrd, Nocedal, and Schnabel, "Representations of quasi-Newton matrices and their use in limited memory methods", Mathematical Programming, 63 (1994)

Consider BFGS updates of the form:

 ( B^{k-1}, s^{k-1}, y^{k-1} ) -> B^{k}
 
 where:
 
 B^{k} = B^{k-1} - ( (B*s)*(B*s)' / (s'*B*s) )^{k-1} + ( (y*y') / (s'*y) )^{k-1}
 
 B <: R^(n x n)
 s <: R^(n)
 y <: R^(n)
 
Now let us consider limited memory updating. For this implementation we set:
 Bo = ( 1 / gamma_k ) * I
 
 where:
               / (s^{k-1}'*y^{k-1})/(y^{k-1}'*y^{k-1})           :  if auto_rescaling() == true
     gamma_k = |
             \  1/alpha from last call to init_identity(n,alpha) :  otherwise
 
 
Now let us define the matrices S and Y that store the update vectors s^{i} and y^{i} for i = 1 ... m_bar:
 S = [ s^{1}, s^{2},...,s^{m_bar} ] <: R^(n x m)
 Y = [ y^{1}, y^{2},...,y^{m_bar} ] <: R^(n x m)
  
Here we are only storing the m_bar <= m most recent update vectors and their ordering is significant. The columns S(:,m_bar) and Y(:,m_bar) contain the most recent update vectors. This is all client needs to know in order to reconstruct the updates themselves.

This class allows matrix-vector products x = B*y and the inverse matrix-vector products x = inv(B)*y to be performed at a cost of about O(n*m_bar^2).

Definition at line 97 of file ConstrainedOptPack_MatrixSymPosDefLBFGS.hpp.


The documentation for this class was generated from the following file:
Generated on Wed May 12 21:57:14 2010 for MOOCHO (Single Doxygen Collection) by  doxygen 1.4.7