jml.optimization
Class BoundConstrainedPLBFGS

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

public class BoundConstrainedPLBFGS
extends java.lang.Object

A Java implementation for the projected limited-memory BFGS algorithm with bound 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 = LBFGS.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 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 org.apache.commons.math.linear.RealMatrix PG
          Current projected gradient.
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
           
 
Constructor Summary
BoundConstrainedPLBFGS()
           
 
Method Summary
private static org.apache.commons.math.linear.RealMatrix project(org.apache.commons.math.linear.RealMatrix A, double l, double u)
          Projection on a box region [l, u].
private static org.apache.commons.math.linear.RealMatrix project(org.apache.commons.math.linear.RealMatrix A, org.apache.commons.math.linear.RealMatrix L, org.apache.commons.math.linear.RealMatrix U)
          Projection on a box region [L_{ij}, U_{ij}] for each element.
static boolean[] run(org.apache.commons.math.linear.RealMatrix Grad_t, double fval_t, double l, double u, double epsilon, org.apache.commons.math.linear.RealMatrix X_t)
          Main entry for the LBFGS algorithm with bound constraints.
static boolean[] run(org.apache.commons.math.linear.RealMatrix Grad_t, double fval_t, org.apache.commons.math.linear.RealMatrix L, org.apache.commons.math.linear.RealMatrix U, double epsilon, org.apache.commons.math.linear.RealMatrix X_t)
          Main entry for the LBFGS algorithm with bound constraints.
 
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.


PG

private static org.apache.commons.math.linear.RealMatrix PG
Current projected 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.


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

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

BoundConstrainedPLBFGS

public BoundConstrainedPLBFGS()
Method Detail

run

public static boolean[] run(org.apache.commons.math.linear.RealMatrix Grad_t,
                            double fval_t,
                            double l,
                            double u,
                            double epsilon,
                            org.apache.commons.math.linear.RealMatrix X_t)
Main entry for the LBFGS algorithm with bound constraints. 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
l - lower bound
u - upper bound
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}

run

public static boolean[] run(org.apache.commons.math.linear.RealMatrix Grad_t,
                            double fval_t,
                            org.apache.commons.math.linear.RealMatrix L,
                            org.apache.commons.math.linear.RealMatrix U,
                            double epsilon,
                            org.apache.commons.math.linear.RealMatrix X_t)
Main entry for the LBFGS algorithm with bound constraints. 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
L - lower bound matrix
U - upper bound matrix
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}

project

private static org.apache.commons.math.linear.RealMatrix project(org.apache.commons.math.linear.RealMatrix A,
                                                                 double l,
                                                                 double u)
Projection on a box region [l, u].

Parameters:
A - a matrix to be projected
l - lower bound
u - upper bound
Returns:
a matrix projected on a box region [l, u]

project

private static org.apache.commons.math.linear.RealMatrix project(org.apache.commons.math.linear.RealMatrix A,
                                                                 org.apache.commons.math.linear.RealMatrix L,
                                                                 org.apache.commons.math.linear.RealMatrix U)
Projection on a box region [L_{ij}, U_{ij}] for each element.

Parameters:
A - a matrix to be projected
L - lower bound matrix
U - upper bound matrix
Returns:
a matrix projected on a box region [L_{ij}, U_{ij}] for each element