jml.optimization
Class NonlinearConjugateGradient

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

public class NonlinearConjugateGradient
extends java.lang.Object

A Java implementation for the nonlinear conjugate gradient method. 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 = NonlinearConjugateGradient.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. 25th, 2013
Author:
Mingjie Qian

Field Summary
private static double alpha
           
private static boolean converge
          If the algorithm converges or not.
private static int formula
          Formula used to calculate beta.
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 java.util.ArrayList<java.lang.Double> J
          An array holding the sequence of objective function values.
private static int k
          Iteration counter.
private static org.apache.commons.math.linear.RealMatrix p
          Decreasing step.
private static double rou
           
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 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
NonlinearConjugateGradient()
           
 
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 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.


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

rou

private static double rou

formula

private static int formula
Formula used to calculate beta. 1: FR 2: PR 3: PR+ 4: HS


J

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

Constructor Detail

NonlinearConjugateGradient

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