Thread Subject: why lsqnonlin so slow even given the initial guess from the optimal results?

Hi,

Can anybody help to explain it? I use lsqnonlin to solve a nonlinear system to find the optimal parameters. The number of parameters is large. once i get the optimal results (it took me around 7-8 hours), i substitute the results into those parameters as the new initial guess. then i redo it. i hope to see the same results very soon this time but it seems still running very slowly.

I would like to know usually how long I need to wait? If the first time is 8 hours, the second time should be around 4 hours or less?

My question may seem naive but I really appreciate your response. Thanks!

Amber

Yao Li wrote:
> Hi,
>
> Can anybody help to explain it? I use lsqnonlin to solve a nonlinear
> system to find the optimal parameters. The number of parameters is
> large. once i get the optimal results (it took me around 7-8 hours),
> i substitute the results into those parameters as the new initial
> guess. then i redo it. i hope to see the same results very soon this
> time but it seems still running very slowly.
>
> I would like to know usually how long I need to wait? If the first
> time is 8 hours, the second time should be around 4 hours or less?
>
> My question may seem naive but I really appreciate your response.
> Thanks!

lsqnonlin() doesn't "know" you gave it a previous set of found optimal
parameters; for all it knows it's got a set that aren't any closer (or
as close even) to the optimal solution as the previous case (which
again, it doesn't know anything about, anyway).

Don't think there's much you can rely on wrt solution time a priori.

--

On 26 Sep, 23:13, "Yao Li" <yaoam...@gmail.com> wrote:
> Hi,
>
> Can anybody help to explain it? I use lsqnonlin to solve a nonlinear system to find the optimal parameters. The number of parameters is large. once i get the optimal results (it took me around 7-8 hours), i substitute the results into those parameters as the new initial guess. then i redo it. i hope to see the same results very soon this time but it seems still running very slowly.
>
> I would like to know usually how long I need to wait? If the first time is 8 hours, the second time should be around 4 hours or less?

There are several factors that influence these types of methods:

1) The cost / time of computing whatever function you optimize
2) The search for a minimum of the objective function.

Factor 1 is more or less constant: If the function is
computationally expensive, it takes time to evaluate.
If it has to be called a lot of times, it will take a
lot of time to compute.

The second problem, the objective function, seems to be
the main source of your confucion. Optimization routines
compute what is known as 'objective functions', functions
that say something about how close the current best solution
is from the 'true' solution.

Most optimization routines are based on quadratic objective
functions,

x= -1:0.1:1;
y = x.^2;
plot(x,y)

In this case the true solution, x = 0, is easily find from
the grap, and something like a Newton iteration can find
the solution rather quickly, no matter where you start from.

But that was the ideal case.

You might have something like this:

x= -5:0.01:5;
z = abs(x/20)+0.1-0.1*cos(10*x);
plot(x,z)

The true solution is still at x = 0, but there is little chance
you will actually find it - you will have to start very close
to x = 0 to have any chance to find that solution.

There are all kinds of local minima all over the place, which
makes a mess. A first run would be likely to find some local
minimum that was not the global minimum. If so, the next run
might spend a lot of time, ending up in a different, adjacent
local minimum.

There is just now way you can tell what kind of minimum you
have found: The routine terminates in some *local* minimum,
but there might be other minima yet not found, that are better
solutions.

Rune

Rune Allnor <allnor@tele.ntnu.no> wrote in message <566c0cf6-4046-4872-90ed-c929a54a80df@z28g2000vbl.googlegroups.com>...

>
> There are all kinds of local minima all over the place, which
> makes a mess. A first run would be likely to find some local
> minimum that was not the global minimum. If so, the next run
> might spend a lot of time, ending up in a different, adjacent
> local minimum.
>

No, there is no way a descend method (as discussed here) behaves like that. It can rarely jump from one local minimum to another. When it does then it's not working properly.

The explanation is very simple, descend method usually stops based on *relative* gradient norm. The algorithm just tries to move the current point toward the minimum and stops when the gradient is smaller than a fraction of the gradient of the first guess. If the first guess is already "close", then the stopping criteria is more demanding, resulting a more or less constant time from run to run.

Bruno