package dragon.ml.seqmodel.crf;
/* RISO: an implementation of distributed belief networks.
* Copyright (C) 1999, Robert Dodier.
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA, 02111-1307, USA,
* or visit the GNU web site, www.gnu.org.
*/
/** <p> This class contains code for the limited-memory Broyden-Fletcher-Goldfarb-Shanno
* (LBFGS) algorithm for large-scale multidimensional unconstrained minimization problems.
* This file is a translation of Fortran code written by Jorge Nocedal.
* The only modification to the algorithm is the addition of a cache to
* store the result of the most recent line search. See <tt>solution_cache</tt> below.
*
* LBFGS is distributed as part of the RISO project. Following is a message from Jorge Nocedal:
* <pre>
* From: Jorge Nocedal [mailto:nocedal@dario.ece.nwu.edu]
* Sent: Friday, August 17, 2001 9:09 AM
* To: Robert Dodier
* Subject: Re: Commercial licensing terms for LBFGS?
*
* Robert:
* The code L-BFGS (for unconstrained problems) is in the public domain.
* It can be used in any commercial application.
*
* The code L-BFGS-B (for bound constrained problems) belongs to
* ACM. You need to contact them for a commercial license. It is
* algorithm 778.
*
* Jorge
* </pre>
*
* <p> This code is derived from the Fortran program <code>lbfgs.f</code>.
* The Java translation was effected mostly mechanically, with some
* manual clean-up; in particular, array indices start at 0 instead of 1.
* Most of the comments from the Fortran code have been pasted in here
* as well.</p>
*
* <p> Here's some information on the original LBFGS Fortran source code,
* available at <a href="http://www.netlib.org/opt/lbfgs_um.shar" rel='nofollow' onclick='return false;'>
* http://www.netlib.org/opt/lbfgs_um.shar</a>. This info is taken
* verbatim from the Netlib blurb on the Fortran source.</p>
*
* <pre>
* file opt/lbfgs_um.shar
* for unconstrained optimization problems
* alg limited memory BFGS method
* by J. Nocedal
* contact nocedal@eecs.nwu.edu
* ref D. C. Liu and J. Nocedal, ``On the limited memory BFGS method for
* , large scale optimization methods'' Mathematical Programming 45
* , (1989), pp. 503-528.
* , (Postscript file of this paper is available via anonymous ftp
* , to eecs.nwu.edu in the directory pub/lbfgs/lbfgs_um.)
* </pre>
*
* @author Jorge Nocedal: original Fortran version, including comments
* (July 1990). Robert Dodier: Java translation, August 1997.
*/
public class LBFGS
{
/** Specialized exception class for LBFGS; contains the
* <code>iflag</code> value returned by <code>lbfgs</code>.
*/
public static class ExceptionWithIflag extends Exception
{
private static final long serialVersionUID = 1L;
public int iflag;
public ExceptionWithIflag( int i, String s ) { super(s); iflag = i; }
public String toString() { return getMessage()+" (iflag == "+iflag+")"; }
}
/** Controls the accuracy of the line search <code>mcsrch</code>. If the
* function and gradient evaluations are inexpensive with respect
* to the cost of the iteration (which is sometimes the case when
* solving very large problems) it may be advantageous to set <code>gtol</code>
* to a small value. A typical small value is 0.1. Restriction:
* <code>gtol</code> should be greater than 1e-4.
*/
public static double gtol = 0.9;
/** Specify lower bound for the step in the line search.
* The default value is 1e-20. This value need not be modified unless
* the exponent is too large for the machine being used, or unless
* the problem is extremely badly scaled (in which case the exponent
* should be increased).
*/
public static double stpmin = 1e-20;
/** Specify upper bound for the step in the line search.
* The default value is 1e20. This value need not be modified unless
* the exponent is too large for the machine being used, or unless
* the problem is extremely badly scaled (in which case the exponent
* should be increased).
*/
public static double stpmax = 1e20;
/** The solution vector as it was at the end of the most recently
* completed line search. This will usually be different from the
* return value of the parameter <tt>x</tt> of <tt>lbfgs</tt>, which
* is modified by line-search steps. A caller which wants to stop the
* optimization iterations before <tt>LBFGS.lbfgs</tt> automatically stops
* (by reaching a very small gradient) should copy this vector instead
* of using <tt>x</tt>. When <tt>LBFGS.lbfgs</tt> automatically stops,
* then <tt>x</tt> and <tt>solution_cache</tt> are the same.
*/
public static double[] solution_cache = null;
private static double gnorm = 0, stp1 = 0, ftol = 0, stp[] = new double[1], ys = 0, yy = 0, sq = 0, yr = 0, beta = 0, xnorm = 0;
private static int iter = 0, nfun = 0, point = 0, ispt = 0, iypt = 0, maxfev = 0, info[] = new int[1], bound = 0, npt = 0, cp = 0, i = 0, nfev[] = new int[1], inmc = 0, iycn = 0, iscn = 0;
private static boolean finish = false;
private static double[] w = null;
/** This method returns the total number of evaluations of the objective
* function since the last time LBFGS was restarted. The total number of function
* evaluations increases by the number of evaluations required for the
* line search; the total is only increased after a successful line search.
*/
public static int nfevaluations() { return nfun; }
/** This subroutine solves the unconstrained minimization problem
* <pre>
* min f(x), x = (x1,x2,...,x_n),
* </pre>
* using the limited-memory BFGS method. The routine is especially
* effective on problems involving a large number of variables. In
* a typical iteration of this method an approximation <code>Hk</code> to the
* inverse of the Hessian is obtained by applying <code>m</code> BFGS updates to
* a diagonal matrix <code>Hk0</code>, using information from the previous M steps.
* The user specifies the number <code>m</code>, which determines the amount of
* storage required by the routine. The user may also provide the
* diagonal matrices <code>Hk0</code> if not satisfied with the default choice.
* The algorithm is described in "On the limited memory BFGS method
* for large scale optimization", by D. Liu and J. Nocedal,
* Mathematical Programming B 45 (1989) 503-528.
*
* The user is required to calculate the function value <code>f</code> and its
* gradient <code>g</code>. In order to allow the user complete control over
* these computations, reverse communication is used. The routine
* must be called repeatedly under the control of the parameter
* <code>iflag</code>.
*
* The steplength is determined at each iteration by means of the
* line search routine <code>mcsrch</code>, which is a slight modification of
* the routine <code>CSRCH</code> written by More' and Thuente.
*
* The only variables that are machine-dependent are <code>xtol</code>,
* <code>stpmin</code> and <code>stpmax<