yosanchan / lip-bfgs Goto Github PK

LIP-BFGS stands for Limited-memory Interior-Point Broyden-Fletcher-Goldfarb-Shanno algorithm; and is simply a an interior-point (IP) method which uses the limited-memory BFGS (L-BFGS) algorithm.

LIP-BFGS was written in Matlab by Jesse Lu in the fall of 2011.

1. LIP-BFGS can handle large problems (x with millions of elements).
2. LIP-BFGS is easy to modify. The algorithm and implementation are simple and well-documented.
3. LIP-BFGS is free. Free as in public domain (see License), you can use it in any way you like.

To install LIP-BFGS, simply extract all files to a directory.

To use LIP-BFGS, simply open matlab within the directory, and run the example program from the Matlab command line. The test_all program can also be run from the Matlab command line.

All Matlab functions are well documented. To start, try typing help lip_bfgs from the Matlab command line.

To understand the algorithm, look at theory.pdf.

LIP-BFGS is designed to minimize an objective function with linear equality constraints and simple bounds on the variables:

minimize f(x)
subject to  Ax - b = 0
            l <= x <= u.

In particular, LIP-BFGS is geared towards problems where the size of x is large (i.e. > 1 million elements).

LIP-BFGS only requires the following input parameters:

1. x, a vector of length n. The initial value for the optimization.
2. g(x), the gradient of the design objective, f(x). A function which returns a vector of length n.
3. A and b, the matrix and vector defining the equality constraint. A must be of size p by n and b must be of length p.
4. l and u, the bound constraints on x. Both must be real-valued and of length n.

LIP-BFGS still works with complex-valued x, g(x), A, and b; however, the bounds on x, l and u, only apply to the real-part of x and therefore must be real-valued. Lastly, f(x) is required to return a real-valued scalar as well.

LIP-BFGS is public domain. Feel free to use and modify as you like.