Re: Contribution to the optimization toolbox

[Jaroslav Hajek]

On Fri, Sep 4, 2009 at 1:24 PM, Michael Creel<address@hidden> wrote:
> 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.
>

Here is what I get testing your script, using optim-1.0.6 and
development octave.

ans =

   0.131749   0.999000   0.055406   0.970000

Since the 5D Rosenbrock function has two local optima, I'm not exactly
surprised about the 3% failures for fminunc.
I'd rather say it's interesting that bfgsmin is always successful,
despite the local optimum.

Another interesting thing is that I got the times reversed. Maybe you
used a newer version of bfgsmin?

Does it do any checking against local optima?
Also, I think bfgsmin somehow attempts to auto-discover the analytic
gradient, doesn't it? If so, does it happen in this case?

Interesting stuff starts to happen if I shift the optimum of the
objective so that x_opt(1) = 100:

ans =

   0.515509   0.010000   0.191053   0.060000


Clearly, neither code reacts well. Hmmm. Perhaps I can improve fminunc
a bit in this regard.

> 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.
>

Choice of algorithms is always an art. So far fminunc got very little
testing, but I hope to put some into it as soon as I get the chance.


-- 
RNDr. Jaroslav Hajek
computing expert & GNU Octave developer
Aeronautical Research and Test Institute (VZLU)
Prague, Czech Republic
url: www.highegg.matfyz.cz