jml.optimization
Class LBFGSOnSimplex

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

public class LBFGSOnSimplex
extends java.lang.Object

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

A simple example:

W = repmat(zeros(nFea, 1), new int[]{1, K});
A = X.transpose().multiply(W);
V = sigmoid(A);
G = X.multiply(V.subtract(Y)).scalarMultiply(1.0 / nSample);
fval = -sum(sum(times(Y, log(plus(V, eps))))).getEntry(0, 0) / nSample;

boolean flags[] = null;
while (true) {
  flags = LBFGSOnSimplex.run(G, fval, epsilon, W);
  if (flags[0])
    break;
  A = X.transpose().multiply(W);
  V = sigmoid(A);
  fval = -sum(sum(times(Y, log(plus(V, eps))))).getEntry(0, 0) / nSample;
  if (flags[1])
    G = rdivide(X.multiply(V.subtract(Y)), nSample);
}

Version:
1.0 Feb. 26th, 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 org.apache.commons.math.linear.RealMatrix G_z
           
private static boolean gradientRequired
          If gradient is required for the next step.
private static double H
           
private static int i
           
private static org.apache.commons.math.linear.RealMatrix I_z
           
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_z
           
private static org.apache.commons.math.linear.RealMatrix PG_z
           
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 double tol
          Tolerance of convergence.
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 org.apache.commons.math.linear.RealMatrix z
           
private static org.apache.commons.math.linear.RealMatrix z_t
           
 
Constructor Summary
LBFGSOnSimplex()
           
 
Method Summary
static void main(java.lang.String[] args)
           
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.


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.


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

z

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

z_t

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

p_z

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

I_z

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

G_z

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

PG_z

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

i

private static int i

tol

private static double tol
Tolerance of convergence.


J

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

Constructor Detail

LBFGSOnSimplex

public LBFGSOnSimplex()
Method Detail

main

public static void main(java.lang.String[] args)
Parameters:
args -

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
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 of two elements: {converge, gradientRequired}