Re: Contribution to the optimization toolbox

[Jaroslav Hajek]

On Tue, Sep 8, 2009 at 11:10 AM, Michael Creel<address@hidden> wrote:
> On Mon, Sep 7, 2009 at 6:42 PM, Jaroslav Hajek <address@hidden> wrote:
>> On Mon, Sep 7, 2009 at 5:36 PM, Michael Creel<address@hidden> wrote:
>>> On Mon, Sep 7, 2009 at 3:28 PM, John W. Eaton <address@hidden> wrote:
>>>> On  7-Sep-2009, Michael Creel wrote:
>>>>
>>>> | I'm trying to
>>>> | compile a checkout of the development version to see if I can
>>>> | replicate your results, but it crashes with
>>>> | In file included from ./txt-eng-ft.h:28,
>>>> |                  from ./gl-render.h:43,
>>>> |                  from ./DLD-FUNCTIONS/fltk_backend.cc:60:
>>>> | /usr/include/ft2build.h:56:38: error: freetype/config/ftheader.h: No
>>>> | such file or directory
>>>>
>>>> I'd say fix this problem first.  Why is freetype/config/ftheader.h
>>>> missing?  Note that Octave is not including this file directly, it is
>>>> included from /usr/include/ft2build.h, so I think there is some
>>>> problem with your installation of FreeType.  Look at the
>>>> /usr/include/ft2build.h file to see if there are some clues there.
>>>>
>>>> jwe
>>>>
>>>
>>> Hmm, the fltk stuff is pretty new for me. I'm running Kubuntu 9.04,
>>> and freetype, etc., come from the provided packages. My first problem
>>> is that I don't have a clear idea of what libraries (or more usefully
>>> for me, Debian package names) are required.  Perhaps I'm missing a
>>> needed package. I can compile 3.2.x release candidates without
>>> problems, including with the fltk backend. There doesn't seem to be a
>>> switch to disable compilation of the fltk backend in the development
>>> version. Is there some way to do that?
>>> Michael
>>>
>>>
>>
>> First, make sure you have all the -devel packages installed; there is
>> sometimes a missing dependency between those.
>> Can you locate the header <somepath>/freetype/config/ftheader.h? If
>> yes, just add -I<somepath> to CXXFLAGS.
>>
>
> John and Jaroslav - thanks for the tips, I just had to make a symlink
> to put a directory in the place it was expected to be. The development
> version is now working fine for me. With the development version, I
> checked the little test script included below, and got the results
>
> octave:3> compare
> Results using analytic gradient
> ans =
>
>   0.018180   0.999000   0.093864   0.997000
>
> Results using numeric gradient
> ans =
>
>   0.025299   0.999000   0.061082   1.000000
>
>
> The recent change in the initial trust region setting has helped
> fminunc. In my results, bfgsmin is still faster than fminunc, and
> there is no difference for me in the performance of fminunc using
> Octave 3.2.2 versus the checkout of development sources. Perhaps I am
> using GradObj incorrectly, because for fminunc the numeric gradient is
> faster than the analytic gradient.
>

Yes, you are. optimset does not affect some global state; it just
constructs an option structure to be passed to fminunc. Note also that
the optim package contained an old simplistic "optimset" replacement
that shadowed Octave's version, I fixed that in SVN now.

Here's an improved script:

################## Last version of test code #######################3
1;
# in the calls to the minimization functions, use "objective" if you
# want analytic gradient, otherwise, use "objective2"

# example obj. fn.: with gradient
function [obj_value, g] = objective(x)
       [obj_value, g] = rosenbrock(x);
endfunction

# example obj. fn.: no gradient
function obj_value = objective2(x)
       obj_value = rosenbrock(x);
endfunction


dim = 5;
replications = 100;
results = zeros(replications,6);
ub = 2;
lb = 0;
control = {100,0};  # set the second number to 1,2,3 for increasing
levels of bfgsmin verbosity

opt = optimset("GradObj", "on");
for i = 1:replications
       x = (ub-lb).*rand(dim,1) + lb;
       tic;
       [theta, obj_value, convergence] = bfgsmin("objective", {x}, control);
       results(i,1) = toc;
       results(i,2) = norm(theta - ones(dim,1));
       results(i,3) = obj_value;

       tic;
       [theta, obj_value] = fminunc("objective", x, opt);
       results(i,4) = toc;
       results(i,5) = norm(theta - ones(dim,1));
       results(i,6) = obj_value;
       fprintf (stderr, "\r%d/%d", i, replications);
endfor
fputs (stderr, "\n");
printf("Results using analytic gradient\n");
mean(results)
median(results)

With a freshly installed package from SVN, I get:

octave:2> compare
100/100
Results using analytic gradient
ans =

   1.6776e-02   6.0941e-08   3.9499e-17   3.0260e-02   2.4907e-08   2.2290e-15

ans =

   1.6358e-02   2.2588e-08   1.9674e-18   2.9318e-02   1.1927e-08   5.1035e-16

The results are comparable, and now I confirm that bfgsmin is faster.
I think the problem previously was that I did not install it;
therefore, Octave extensively checked its date stamp while executing.

I tried also dim = 10:

octave:3> compare
100/100
Results using analytic gradient
ans =

   2.4335e-02   5.6294e-08   1.1550e-16   5.4346e-02   8.5339e-08   2.5899e-14

ans =

   2.3675e-02   3.0352e-08   3.2202e-17   5.3850e-02   3.6230e-08   1.1496e-14


dim = 50:
octave:4> compare
100/100
Results using analytic gradient
ans =

   7.5409e-02   3.5230e-01   6.6630e+00   2.7084e-01   1.4943e-05   1.2621e-10

ans =

   7.6525e-02   2.7970e-04   2.5038e-07   2.7125e-01   9.5309e-06   2.5546e-11

dim = 100:
octave:5> compare
100/100
Results using analytic gradient
ans =

   1.2308e-01   3.6788e+00   1.1264e+02   4.0221e-01   5.5711e-02   1.3950e-03

ans =

   1.2242e-01   3.6939e+00   9.5687e+01   4.0261e-01   3.9672e-02   3.8998e-04

apparently fminunc favors accuracy more than bfgsmin; this is
particularly visible for the higher dimensions;
its time consumption also grows more rapidly.
Obviously, both functions' results deteriorate significantly as the
problem's dimensionality increases, but probably the rosenbrock
problem gets quite difficult in higher dimensions.

In any case, now I have more toys to play with :)

best regards

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