view release on metacpan or  search on metacpan

lbfgs.c  view on Meta::CPAN

/*
 *      Limited memory BFGS (L-BFGS).
 *
 * Copyright (c) 1990, Jorge Nocedal
 * Copyright (c) 2007, Naoaki Okazaki
 * All rights reserved.
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

/* $Id: lbfgs.c 56 2007-12-16 08:01:47Z naoaki $ */

/*
This library is a C port of the FORTRAN implementation of Limited-memory
Broyden-Fletcher-Goldfarb-Shanno (L-BFGS) method written by Jorge Nocedal.
The original FORTRAN source code is available at:
http://www.ece.northwestern.edu/~nocedal/lbfgs.html

The L-BFGS algorithm is described in:
	- Jorge Nocedal.
	  Updating Quasi-Newton Matrices with Limited Storage.
	  <i>Mathematics of Computation</i>, Vol. 35, No. 151, pp. 773--782, 1980.
	- Dong C. Liu and Jorge Nocedal.
	  On the limited memory BFGS method for large scale optimization.
	  <i>Mathematical Programming</i> B, Vol. 45, No. 3, pp. 503-528, 1989.

The line search algorithms used in this implementation are described in:
	- John E. Dennis and Robert B. Schnabel.
	  <i>Numerical Methods for Unconstrained Optimization and Nonlinear
	  Equations</i>, Englewood Cliffs, 1983.
	- Jorge J. More and David J. Thuente.
	  Line search algorithm with guaranteed sufficient decrease.
	  <i>ACM Transactions on Mathematical Software (TOMS)</i>, Vol. 20, No. 3,
	  pp. 286-307, 1994.

This library also implements Orthant-Wise Limited-memory Quasi-Newton (OW-LQN)
method presented in:
	- Galen Andrew and Jianfeng Gao.
	  Scalable training of L1-regularized log-linear models.
	  In <i>Proceedings of the 24th International Conference on Machine
	  Learning (ICML 2007)</i>, pp. 33-40, 2007.

I would like to thank the original author, Jorge Nocedal, who has been
distributing the effieicnt and explanatory implementation in an open source
licence.
*/

#ifdef	HAVE_CONFIG_H
#include <config.h>
#endif/*HAVE_CONFIG_H*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#include <lbfgs.h>

#ifdef	_MSC_VER
#define	inline	__inline
typedef unsigned int uint32_t;
#endif/*_MSC_VER*/

/* this block is added by laye */
#ifndef _MSC_VER
#include <stdint.h>
#endif/*_MSC_VER*/

#if	defined(USE_SSE) && defined(__SSE__) && LBFGS_FLOAT == 32
/* Use SSE optimization for 32bit float precision. */
#include "arithmetic_sse_float.h"

#elif	defined(USE_SSE) && defined(__SSE__) && LBFGS_FLOAT == 64
/* Use SSE2 optimization for 64bit double precision. */
#include "arithmetic_sse_double.h"

#else
/* No CPU specific optimization. */
#include "arithmetic_ansi.h"

#endif

#define min2(a, b)		((a) <= (b) ? (a) : (b))
#define max2(a, b)		((a) >= (b) ? (a) : (b))
#define	max3(a, b, c)	max2(max2((a), (b)), (c));

struct tag_iteration_data {
	lbfgsfloatval_t alpha;
	lbfgsfloatval_t *s;		/* [n] */
	lbfgsfloatval_t *y;		/* [n] */
	lbfgsfloatval_t ys;		/* vecdot(y, s) */
};
typedef struct tag_iteration_data iteration_data_t;

static const lbfgs_parameter_t _defparam = {
	6, 1e-5, 0, 20,
	1e-20, 1e20, 1e-4, 0.9, 1.0e-16,
	0.0,
};

/* Forward function declarations. */

static int line_search_backtracking(
	int n,