Test Matrix Downhill simplex, Levenberg-Marquardt nmsmax Solvopt LP, LCP, Indefinite QP and Nonlinear Programming Levenberg-Marquardt Line Search, Conjugate Gradient, Stepest Descent Constrained minimization/maximization Minimization functions (deriv.m, gradient.m, Newton-Raphson, Golden Section, Davidon-Fletcher-Powell, Broyden)
Octave is just beginning to have optimization routines. The ones
I use
are written for matlab but not part of matlab. If it is unconstrained
problems you are interested in then I recommend the direct search
algorithms in the Test Matrix toolbox which Nick Higham puts on his
home
page at
http://www.ma.man.ac.uk/~higham/testmat.html
The files you are interested in are called adsmax.m nmsmax.m and
mdsmax.m. These methods do not calculate gradients so they may
not be
as fast as a BFGS type method (when you know the gradient) but they
get
confused less often.
Of course is may depend on your problem. Is the function you want
to
optimize concave? If so the fastest way to get a solution is
to use
fsolve and set the gradient to zero. For a concave (convex) function
this gives the maximum (minimum).
If you are intested in constrained problems then I would use solnp from
http://dollar.biz.uiowa.edu/col/ye/matlab.html
which is quite good. It is a minimizer I believe so you'll want
to
minimize -f(x) rather in order to maximize f(x).
Heber Farnsworth
Downhill simplex, Levenberg-Marquardt
Hello,
I have a downhill simplex function (Nelder-Mead)
at http://anonimo.isr.ist.utl.pt:8080/~etienne/octave/.
It should do for
low-dimensional functions.
I also have some code for Levenberg-Marquardt like optimization,
but it isn't online. Just ask if you would like to see it.
Cheers,
Etienne
There is a function called nmsmax which uses the same algorithm as fmins
but
maximizes rather than minimizes. It is not part of Octave.
You can get it
from the Mathworks anonymous ftp site at
ftp://ftp.mathworks.com/pub/contrib/v4/optim/dsmax
More recent versions can be obtained from the authors web site as part
of a
toolbox he calls the test matrix toolbox. The web page is
http://www.ma.man.ac.uk/~higham/testmat.html
The only way in which you would need to change your code is to have
nmsmax
maximize -f(x) where f(x) is the function you want to minimize.
Last time I
checked there was also some problem with the ^ versus ~ operator used
in
that code. Running octave with the --braindead option should
take care of
it. Alternatively you can edit the code and change the one instance
of the
matlab operator to the octave one.
It is also available via
http://bedvgm.kfunigraz.ac.at:8001/alex/solvopt/
if you want to avoid
the matlab registration form.
cheers
Richard
Cyril Fischer wrote:
> > Free: Solver for local nonlinear optimization problems
> > ======================================================
> >
> > The SolvOpt toolbox (Solver for local optimization problems) is
concerned
> > with minimization or maximization of nonlinear, possibly non-smooth
> > objective functions and with the solution of nonlinear programming
problems
> > taking into account constraints by the so-called method of exact
> > penalization. This solver is available for download for free.
> >
> > http://www.mathtools.com/toolbox-solveopt.html
LP, LCP, Indefinite QP and Nonlinear Programming
I seem to recall that someone in the recent postings on the lack of
optimisation code suggested contacting Yinyu Ye, of the University
of
Iowa, College of Business Administration. I would also advocate that
those
people who are interested in (and capable of) integrating GPL optimisation
code into Octave contact Y.Ye
I noticed that the Website for the Computational Optimisation Laboratory
of which he is the Director,
http://dollar.biz.uiowa.edu/col/ye/matlab.html
contains freely distributatble source for LP, LCP, QP and SemiDefinite
Programming, either in Fortran or in C.
There are also Matlab routines at the site, for solving Linear Programs,
(constrained and unconstrained), Quadratic Programs, and NonLinear
Programs, by Sequential QP. These seem to work fine under Octave. Anyone
interested in finding a quick fix for Octave's optimisation incapacities
could start with this (freely-distributable??) archive of M-files.
David Dowey
This is a FAQ. I took from
the mathworks contrib dir a program
implementing the Levenberg-Marquardt nonlinear regression method.
I looked
around for the latest version of this software, which was modified
by three
people. I then adopted
it to Octave. I now
put it on
ftp://fly.cnuce.cnr.it/pub/software/octave/.
I'd like to publish this under the GPL. To this end,
I tried to contact
the authors. Arthur jutan responded, saying that
he has no objection as
long as authorship is acknowledged, but I didn't
manage to contact the
others. I'll try harder when I have time, but if someone
else does it, it
will be quicker.
Line Search, Conjugate Gradient, Stepest Descent
with very small modifications the following also run in Octave:
http://solon.cma.univie.ac.at/~neum/software/ls/ public domain
Matlab Line Search Routines
ELS, Efficient Line Search
ELS is an implementation of a very efficient and robust line search
that
finds along each ray x+alp*p with
g(x)^Tp<0 (where g(x) denotes the gradient of the objective function
f(x)) a step size alp>0 such that
f(x+alp*p) <= f(x) - delta (g(x)^Tp/||p||)^2
with a positive constant delta depending only on f.
Apart from the initial directional derivative g(x)^Tp, ELS only uses
function evaluations at points along the ray.
and ftp://eivind.imm.dtu.dk/pub/cyril/ non-comercial use, I believe.
Search for `conjgrad.m' `steepdes.m'
Constrained minimization/maximization
I've been using some functions developed at the U of Iowa. You
can look
at them at
http://dollar.biz.uiowa.edu/col/ye/matlab.html
They are free in some sense (you have to consult the author before
incorporating them in a commercial package). Solnp is the general
one
which I have used with fair success. Be sure to download to
documentation as well since it's not obvious.
Heber Farnsworth
I have put some minimization functions I have written on the web at
http://www.neutrino.lanl.gov/~bsapp/octave/minimization.tar.gz
Here is
a list of the functions:
deriv.m -> numerically calculates 1st,2nd,3rd or 4th derivatives
of
O(2) or O(4) of a scalar function.
gradient.m -> numerically calculates the gradient of a multi-variable
function.
nrm.m -> Newton-Raphson minimization of a scalar function.
gs.m -> Golden Section search for a minimum of a scalar function.
__quasi_func__.m -> Used internally by bfgs and dfp. This turns
the
multi-variable functions you supply bfgs and dfp into a scalar function
along some line determined by the bfgs and dfp algorithm. Then this
scalar function is minimized with nrm.m.
dfp.m -> Davidon-Fletcher-Powell minimization of a multi-variable
function.
bfgs.m -> Broyden and company minimization of a multi-variable
function.
dfp and bfgs both need some improvement. They never re-calculate
the
inverse hessian. This makes them somewhat slow when the hessian
changes
drastically. I will eventually have them do this.
They also do not
check the arguements supplied for sanity.
I hope these are useful.
Ben Sapp