jml.optimization
Class LBFGS

java.lang.Object
  extended by jml.optimization.LBFGS

public class LBFGS
extends java.lang.Object

A Java implementation for the limited-memory BFGS algorithm. It is a general algorithm interface, only gradient and objective function value are needed to compute outside the class.

A simple example:

double epsilon = ...; // Convergence tolerance
RealMatrix W = ...; // Initial matrix (vector) you want to optimize
RealMatrix G = ...; // Gradient at the initial matrix (vector) you want to optimize
double fval = ...; // Initial objective function value

boolean flags[] = null;
while (true) {
  flags = LBFGS.run(G, fval, epsilon, W); // Update W in place
  if (flags[0]) // flags[0] indicates if L-BFGS converges
    break;
  fval = ...; // Compute the new objective function value at the updated W
  if (flags[1]) // flags[1] indicates if gradient at the updated W is required
    G = ...; // Compute the gradient at the new W
}

Version:
1.0 Jan. 11th, 2013
Author:
Mingjie Qian

Field Summary
private static double alpha
           
private static double beta
           
private static boolean converge
          If the algorithm converges or not.
private static double fval
          The last objective function value.
private static org.apache.commons.math.linear.RealMatrix G
          Current gradient.
private static org.apache.commons.math.linear.RealMatrix G_pre
          Last gradient.
private static boolean gradientRequired
          If gradient is required for the next step.
private static double H
           
private static java.util.ArrayList<java.lang.Double> J
          An array holding the sequence of objective function values.
private static int k
          Iteration counter.
private static int m
           
private static org.apache.commons.math.linear.RealMatrix p
          Decreasing step.
private static double rou_k
           
private static java.util.LinkedList<java.lang.Double> rou_ks
           
private static org.apache.commons.math.linear.RealMatrix s_k
           
private static java.util.LinkedList<org.apache.commons.math.linear.RealMatrix> s_ks
           
private static int state
          State for the automata machine.
private static double t
          Step length for backtracking line search.
private static org.apache.commons.math.linear.RealMatrix X
          Current matrix variable that we want to optimize.
private static org.apache.commons.math.linear.RealMatrix X_pre
          Last matrix variable that we want to optimize.
private static org.apache.commons.math.linear.RealMatrix y_k
           
private static java.util.LinkedList<org.apache.commons.math.linear.RealMatrix> y_ks
           
private static double z
          A temporary variable holding the inner product of the decreasing step p and the gradient G, it should be always non-positive.
 
Constructor Summary
LBFGS()
           
 
Method Summary
static boolean[] run(org.apache.commons.math.linear.RealMatrix Grad_t, double fval_t, double epsilon, org.apache.commons.math.linear.RealMatrix X_t)
          Main entry for the LBFGS algorithm.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

G

private static org.apache.commons.math.linear.RealMatrix G
Current gradient.


G_pre

private static org.apache.commons.math.linear.RealMatrix G_pre
Last gradient.


X

private static org.apache.commons.math.linear.RealMatrix X
Current matrix variable that we want to optimize.


X_pre

private static org.apache.commons.math.linear.RealMatrix X_pre
Last matrix variable that we want to optimize.


p

private static org.apache.commons.math.linear.RealMatrix p
Decreasing step.


fval

private static double fval
The last objective function value.


gradientRequired

private static boolean gradientRequired
If gradient is required for the next step.


converge

private static boolean converge
If the algorithm converges or not.


state

private static int state
State for the automata machine. 0: Initialization 1: Before backtracking line search 2: Backtracking line search 3: After backtracking line search 4: Convergence


t

private static double t
Step length for backtracking line search.


z

private static double z
A temporary variable holding the inner product of the decreasing step p and the gradient G, it should be always non-positive.


k

private static int k
Iteration counter.


alpha

private static double alpha

beta

private static double beta

m

private static int m

H

private static double H

s_k

private static org.apache.commons.math.linear.RealMatrix s_k

y_k

private static org.apache.commons.math.linear.RealMatrix y_k

rou_k

private static double rou_k

s_ks

private static java.util.LinkedList<org.apache.commons.math.linear.RealMatrix> s_ks

y_ks

private static java.util.LinkedList<org.apache.commons.math.linear.RealMatrix> y_ks

rou_ks

private static java.util.LinkedList<java.lang.Double> rou_ks

J

private static java.util.ArrayList<java.lang.Double> J
An array holding the sequence of objective function values.

Constructor Detail

LBFGS

public LBFGS()
Method Detail

run

public static boolean[] run(org.apache.commons.math.linear.RealMatrix Grad_t,
                            double fval_t,
                            double epsilon,
                            org.apache.commons.math.linear.RealMatrix X_t)
Main entry for the LBFGS algorithm. The matrix variable to be optimized will be updated in place to a better solution point with lower objective function value.

Parameters:
Grad_t - gradient at original X_t, required on the first revocation
fval_t - objective function value on original X_t
epsilon - convergence precision
X_t - current matrix variable to be optimized, will be updated in place to a better solution point with lower objective function value
Returns:
a boolean array with two elements: {converge, gradientRequired}