chokkan / liblbfgs Goto Github PK
View Code? Open in Web Editor NEWlibLBFGS: a library of Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS)
Home Page: http://www.chokkan.org/software/liblbfgs/
License: MIT License
libLBFGS: a library of Limited-memory Broyden-Fletcher-Goldfarb-Shanno (L-BFGS)
Home Page: http://www.chokkan.org/software/liblbfgs/
License: MIT License
libLBFGS: C library of limited-memory BFGS (L-BFGS) Copyright (c) 1990, Jorge Nocedal Copyright (c) 2007-2010, Naoaki Okazaki ========================================================================= 1. Introduction ========================================================================= libLBFGS is a C port of the 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 method solves the unconstrainted minimization problem: minimize F(x), x = (x1, x2, ..., xN), only if the objective function F(x) and its gradient G(x) are computable. Refer to the libLBFGS web site for more information. http://www.chokkan.org/software/liblbfgs/ ========================================================================= 2. How to build ========================================================================= [Microsoft Visual Studio 2008] Open the solution file "lbfgs.sln" and build it. [GCC] On top of a compiler and GNU Make, you will also need to install libtool and automake to build. On Debian distributions, this can be installed with: sudo apt install libtool automake $ ./autogen.sh $ ./configure $ make $ make install # To install libLBFGS library and header. ========================================================================= 3. Note on SSE/SSE2 optimization ========================================================================= This library has SSE/SSE2 optimization routines for vector arithmetic operations on Intel/AMD processors. The SSE2 routine is for 64 bit double values, and the SSE routine is for 32 bit float values. Since the default parameters in libLBFGS are tuned for double precision values, it may need to modify these parameters to use the SSE optimization routines. To use the SSE2 optimization routine, specify --enable-sse2 option to the configure script. $ ./configure --enable-sse2 To build libLBFGS with SSE2 optimization enabled on Microsoft Visual Studio 2005, define USE_SSE and __SSE2__ symbols. Make sure to run libLBFGS on processors where SSE2 instrunctions are available. The library does not check the existence of SSE2 instructions. To package maintainers, Please do not enable SSE/SSE2 optimization routine. The library built with SSE/SSE2 optimization will crash without any notice when necessary SSE/SSE2 instructions are unavailable on CPUs. ========================================================================= 4. License ========================================================================= libLBFGS is distributed under the term of the MIT license. Please refer to COPYING file in the distribution. $Id$
When trying the sample code https://github.com/chokkan/liblbfgs/blob/master/sample/sample.cpp, the code will crash when using N = 80601.
Please let me know if you are able to reproduce.
I'm using Visual Studio 2010 to build lbfgs.sln, but it then report the bug,
"Unable to start program ./liblbfgs-master/Debug/lbfgs_debug.lib The specified file is an unrecognized or unsupported binary format".
How can I solve this?
Thank you for the very excellent L-BFGS implementation.
Do you have any plan to implement L-BFGS-B the solver ?(http://users.iems.northwestern.edu/~nocedal/lbfgsb.html)
The information was given by Norman Goldstein.
On my Fedora 19 linux box, I had to do the following
before configuring for SSE2
export CFLAGS=-msse2
export CPPFLAGS=-DHAVE_EMMINTRIN_H
To debug with gdb without artefacts, I changed the configure script as follows
enableval=$enable_debug; CFLAGS="-DDEBUG -O0 -ggdb ${CFLAGS}"
The main thing is using -O0, otherwise I get funny results when debugging.
I am running on Fedora 18, x86, 32-bit
I tried to use LBFGS_FLOAT=32 (i.e., float instead of double), to save memory in a large optimization task.
But it always aborts with LBFGSERR_ROUNDING_ERROR. I've tried this on different optimization problems. This error happens in later iterations, closer to convergence. Is there any way to prevent that error? I tried increasing xtol, but it doesn't help.
One way would be to fiddle with convergence criteria to declare it converged earlier, but I'd rather not do that.
Occasionally, during the running of the optimization, I will need to change the variables (x) that are passed in the interface of the evaluate() routine. This "change of variables" does not affect the value of objective function (F), only how F is parametrized. For example, if F involves a unit vector (x,y), I may use just x to describe the unit vector; but, should x become too large, I will start using y, instead. One way to do this, is to restart L-BFGS with the new parametrization, but this is not the most efficient approach. How much work is involved to have a routine that efficiently updates the L-BFGS data structures for a new x supplied by the user?
When I downloaded the project zip and went to install, I discovered there was no configure script! Running "autoreconf --force --install" fixed this as far as I can tell. It's easy enough to rebuild the configure script, but that step should at least be in the installation instructions.
I noticed that when a callback function returns non-zero value, the value is used as a return value of lbfgs()
.
Lines 495 to 500 in 5ad02fb
But this behavior is not documented, e.g. at
Lines 403 to 404 in 5ad02fb
or
Lines 461 to 465 in 5ad02fb
The current situation is not desirable as a user might write a callback function that returns a value that is not intended to be used as the return value of lbfgs()
.
I think it's better to either:
As for code block line 1000-1006 in lbfgs.c
/*
If an unusual termination is to occur then let
stp be the lowest point obtained so far.
*/
if ((brackt && ((*stp <= stmin || stmax <= *stp) || param->max_linesearch <= count + 1 || uinfo != 0)) || (brackt && (stmax - stmin <= param->xtol * stmax))) {
*stp = stx;
}
This code block may cause misleading error information. For example, if the max_linesearch is achieved, the *stp is set as stx at line 1005. However, the error at line 1023-1025 can be catched firstly in this case, thus the returned error is LBFGSERR_ROUNDING_ERROR instead of LBFGSERR_MAXIMUMLINESEARCH. I wonder if there is a possibility for this to happen.
will it work on new versions of Microsoft Visual Studio
There is a bug in the default linesearch (#0), which is revealed after iteration 4 when minimizing the standard Rosenbrock function with gtol = 0.1. I compared the code carefully with Jorge Nocedal's original to track it down. The bug is on line 1178 in lbfgs.c (commit 7fc7876). The "else-if" condition should be (u) < (v)
instead of a < 0
and the line along with surrounding lines should read:
if (r < 0. && gamma != 0.) { \
(cm) = (v) - r * d; \
} else if ((u) < (v)) { \
(cm) = (xmax); \
} else { \
(cm) = (xmin); \
}
As a result of the error the linesearch and whole optimization finishes prematurely. I can (and shall) provide more details shortly.
Here are two routines for the LBFGS project, to be incorporated as seen fit by the project maintainers.
-- Converts LBFGS error codes to short strings.
-- Pretty-prints the LBFGS parameters
//*******************************************************************
// Copyright 2013 Norman J. Goldstein
//
// License:
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Lesser General Public License as
// published by the Free Software Foundation, either version 3 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 Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this program. If not, see
// http://www.gnu.org/licenses/.
//
// Author: Norman J. Goldstein ([email protected],
// [email protected])
const char* LBFGS_ERR_str( int val )
{
switch( val )
{
case LBFGS_CONVERGENCE:
{
return "CONVERGENCE";
}
case LBFGS_STOP:
{
return "STOP";
}
case LBFGS_ALREADY_MINIMIZED:
{
return "ALREADY_MINIMIZED";
}
case LBFGSERR_UNKNOWNERROR:
{
return "UNKNOWNERROR";
}
case LBFGSERR_LOGICERROR:
{
return "LOGICERROR";
}
case LBFGSERR_OUTOFMEMORY:
{
return "OUTOFMEMORY";
}
case LBFGSERR_CANCELED:
{
return "CANCELED";
}
case LBFGSERR_INVALID_N:
{
return "INVALID_N";
}
case LBFGSERR_INVALID_N_SSE:
{
return "INVALID_N_SSE";
}
case LBFGSERR_INVALID_X_SSE:
{
return "INVALID_X_SSE";
}
case LBFGSERR_INVALID_EPSILON:
{
return "INVALID_EPSILON";
}
case LBFGSERR_INVALID_TESTPERIOD:
{
return "INVALID_TESTPERIOD";
}
case LBFGSERR_INVALID_DELTA:
{
return "INVALID_DELTA";
}
case LBFGSERR_INVALID_LINESEARCH:
{
return "INVALID_LINESEARCH";
}
case LBFGSERR_INVALID_MINSTEP:
{
return "INVALID_MINSTEP";
}
case LBFGSERR_INVALID_MAXSTEP:
{
return "INVALID_MAXSTEP";
}
case LBFGSERR_INVALID_FTOL:
{
return "INVALID_FTOL";
}
case LBFGSERR_INVALID_WOLFE:
{
return "INVALID_WOLFE";
}
case LBFGSERR_INVALID_GTOL:
{
return "INVALID_GTOL";
}
case LBFGSERR_INVALID_XTOL:
{
return "INVALID_XTOL";
}
case LBFGSERR_INVALID_MAXLINESEARCH:
{
return "INVALID_MAXLINESEARCH";
}
case LBFGSERR_INVALID_ORTHANTWISE:
{
return "INVALID_ORTHANTWISE";
}
case LBFGSERR_INVALID_ORTHANTWISE_START:
{
return "INVALID_ORTHANTWISE_START";
}
case LBFGSERR_INVALID_ORTHANTWISE_END:
{
return "INVALID_ORTHANTWISE_END";
}
case LBFGSERR_OUTOFINTERVAL:
{
return "OUTOFINTERVAL";
}
case LBFGSERR_INCORRECT_TMINMAX:
{
return "INCORRECT_TMINMAX";
}
case LBFGSERR_ROUNDING_ERROR:
{
return "ROUNDING_ERROR";
}
case LBFGSERR_MINIMUMSTEP:
{
return "MINIMUMSTEP";
}
case LBFGSERR_MAXIMUMSTEP:
{
return "MAXIMUMSTEP";
}
case LBFGSERR_MAXIMUMLINESEARCH:
{
return "MAXIMUMLINESEARCH";
}
case LBFGSERR_MAXIMUMITERATION:
{
return "MAXIMUMITERATION";
}
case LBFGSERR_WIDTHTOOSMALL:
{
return "WIDTHTOOSMALL";
}
case LBFGSERR_INVALIDPARAMETERS:
{
return "INVALIDPARAMETERS";
}
case LBFGSERR_INCREASEGRADIENT:
{
return "INCREASEGRADIENT";
}
default:
{
return "Not a valid LBFGS error code";
}
}
}
using namespace std;
ostream& operator<<( ostream& os,
const lbfgs_parameter_t& params )
{
POUT(m);
POUT(epsilon);
POUT(past);
POUT(delta);
POUT(max_iterations);
POUT(linesearch);
POUT(max_linesearch);
POUT(min_step);
POUT(max_step);
POUT(ftol);
POUT(wolfe);
POUT(gtol);
POUT(xtol);
POUT(orthantwise_c);
POUT(orthantwise_start);
POUT(orthantwise_end);
return os;
}// operator<<
Do you have interest in supporting other SIMD types? I'm particularly interested in AVX, for modern x86 processors, and NEON, for ARM processors.
I would be willing to implement this, if it's something you want. It would be useful to me, and the amount of code for each one looks small.
Another possibility is to create an implementation using the portable vector extension in clang and gcc (not VisualStudio though). You can write a single implementation that automatically works on all architectures and uses whatever vector instructions are available.
According to the description, delta
defaults to 0, however, it is initialized to 1e-5 here.
There don't seem to be any unit tests. Hook up googletest and add some tests that are run with make check
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.