Antonio Coppola edited Introduction.tex  over 9 years ago

Commit id: 22cc8e739a689ea576ca10afd959bc433f0cdf5b

deletions | additions      

       

The Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) algorithm \cite{Liu_Nocedal_1989} is employed for solving high-dimensional minimization problems in scenarios where both the objective function and its gradient can be computed analytically. The L-BFGS algorithm belongs to the class of quasi-Newton optimization routines, which solve the given minimization problem by computing approximations to the Hessian matrix of the objective function. At each iteration, quasi-Newton algorithms locally model $f$ at the point $x^k$ using a quadratic approximation:  \[  Q(x) = f(x^k) + (x - x^k)^T g^k + \frac{1}{2} (x - x^k)^T \mathbf(B_k) \mathbf{B_k}  (x - x^k) \]  A search direction can then be found by computing the vector $x^*$ that minimizes $Q(x)$. Assuming that Hessian is positive-definite, this is $x^* = x^k - \mathbf{H_k} g^k$. The next search point is then found along the ray defined by $ x^k - \alpha \mathbf{H_k} g^k$.  \subsection{The OWL-QN Algorithm}