Re: Contribution to the optimization toolbox

[Michael Creel]

On Fri, Sep 4, 2009 at 10:33 AM, Jaroslav Hajek <address@hidden> wrote:
>
> Regarding the status of Octave core, it currently includes
> fzero (1d nonlinear equation),
> fsolve (n-d nonl. eqn.), fminunc (n-d unc. min.)
>
> lsqnonneg (least squares with non-negative variables)
> glpk (linear programming, wrapper over GNU GLPK),
> qp (quadratic programming)
> sqp (general nonlinear programming)
>
> what logically belongs amongst the first four, and is missing, is
> fminbnd - 1d minimization solver. It should probably implement Brent's
> or any similar method combining golden section search with inverse
> interpolation (quadratic or higher), and should be patterned after
> fzero, including the optimget/optimset support. I intend to eventually
> do that myself, but I would be grateful for any help. Of course, the
> 1D algorithm is relatively simple and well-known, but it could be a
> good start for you.
>
> qp and sqp are more elaborate. qp could probably benefit from the QR
> and Cholesky updating classes recently introduced into Octave, to
> avoid matrix factorizations in each step. I guess that would be a big
> project, though.
>
> regarding the optim package of OctaveForge, as Michael said, there is
> currently no organization or development direction; it's just a
> collection of optimization codes from various authors. You can
> contribute virtually anything here now. In the future, I'd like to
> make the package more orthogonal to Octave core and reuse some of its
> mechanisms, in particular optimget/optimset.
>
> In any case, if you'd like to contribute to Octave, it's vital you
> start working with the development sources.
>
> if you have further questions, don't suppress them :)
>
> regards
>
> --
> RNDr. Jaroslav Hajek
> computing expert & GNU Octave developer
> Aeronautical Research and Test Institute (VZLU)
> Prague, Czech Republic
> url: www.highegg.matfyz.cz
>
>

With regard to optimization using Octave, there is a certain overlap
between Octave core and the optim toolbox. Likewise, algorithms appear
in both, but there is little standardized testing to make sure that
methods work well, or to figure out which of a set of algorithms works
best for a given type or problem.

To illustrate what I mean, I checked bfgsmin (in optim toolbox) and
fminunc (using Octave 3.2.3 release candidate. The test code runs 1000
replications of minimization of the Rosenbrock function (in optim
toolbox), using a random start vector. The test code is

################# test code #############################
dim = 5;
replications = 1000;
results = zeros(replications,4);
ub = 2;
lb = 0;
control = {100,0};

for i = 1:replications
        x = (ub-lb).*rand(dim,1) + lb;
        tic;
        [theta, obj_value, convergence] = bfgsmin("rosenbrock", {x}, control);
        results(i,1) = toc;
        results(i,2) = norm(theta-ones(dim,1)) < 1e-5;

        tic;
        [theta, obj_value] = fminunc("rosenbrock", x);
        results(i,3) = toc;
        results(i,4) = norm(theta-ones(dim,1)) < 1e-5;
endfor

mean(results)
#################  end test code #############################


When I run this, I get
octave:1> compare
ans =

   0.024725   0.999000   0.069155   0.972000

octave:2>

This means that bfgsmin is on average more than twice as fast as
fminunc (to be expected, perhaps, because the first is written as an
.oct function, the second is not). More importantly, bfgsmin gets the
right answer 99.9% of the time, while fminunc finds the right answer
97.2% of the time. I use the default tolerances of both methods here,
perhaps performance could be improved with a little tuning.

So, this is just to highlight the fact that there is a certain
proliferation of methods and a lack of a testbed to guide users in the
choice of algorithms. I'm sorry that I can't take on the job, but
perhaps some new and energetic users might be able to.

Michael