[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Contribution to the optimization toolbox
From: |
Jaroslav Hajek |
Subject: |
Re: Contribution to the optimization toolbox |
Date: |
Fri, 4 Sep 2009 14:53:47 +0200 |
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
- Contribution to the optimization toolbox, Leonardo Martins, 2009/09/03
- Re: Contribution to the optimization toolbox, Michael Creel, 2009/09/04
- Re: Contribution to the optimization toolbox, Jaroslav Hajek, 2009/09/04
- Re: Contribution to the optimization toolbox, Michael Creel, 2009/09/04
- Re: Contribution to the optimization toolbox,
Jaroslav Hajek <=
- Re: Contribution to the optimization toolbox, Leonardo Martins, 2009/09/04
- Re: Contribution to the optimization toolbox, John W. Eaton, 2009/09/04
- Re: Contribution to the optimization toolbox, Michael D Godfrey, 2009/09/04
- Re: Contribution to the optimization toolbox, Søren Hauberg, 2009/09/04
- Re: Contribution to the optimization toolbox, Michael Creel, 2009/09/07
- Re: Contribution to the optimization toolbox, Michael Creel, 2009/09/07
- Re: Contribution to the optimization toolbox, Michael D Godfrey, 2009/09/07
- Re: Contribution to the optimization toolbox, Michael Creel, 2009/09/04
- Re: Contribution to the optimization toolbox, Jaroslav Hajek, 2009/09/06
- Re: Contribution to the optimization toolbox, Michael Creel, 2009/09/07