MATLAB Central Newsreader - Line search failing?

Line search failing?

David Doria — Thu, 14 Aug 2008 21:33:02 -0400

I am using fminunc to try to find the minimum of a function.
I plotted the function (it is only 2d) and it seems
extremely well behaved - visually it there is without a
doubt a single local min if you start any where near the min
value (the value is at (20, 0) and there looks to be about a
5 unit radius of convergence).

However, when I run fminunc, I get:

Line search cannot find an acceptable point along the
current search direction.

The only thing I could think to check is if the gradient was
somehow 0-ish even though it didn't look like it in the
plot, but when I output the gradient at the iteration it
gives the error it is

Gradient is:

ans =

-1.2747
0.4237

Does anyone know what else to check to see why line search
can't find a good point?

Thanks,

Dave

Re: Line search failing?

Matt — Thu, 14 Aug 2008 22:04:01 -0400

> Does anyone know what else to check to see why line search
> can't find a good point?
>
> Thanks,
>
> Dave

Singularity of the Hessian possibly. If the method the
routine is using is Newton-like, it may be trying to
compute the Hessian, or some approximation to it, and to
invert it.

If the Hessian at the point is nearly singular, it will
have problems, I'd imagine.

Re: Line search failing?

Matt — Thu, 14 Aug 2008 22:12:02 -0400

"Matt " <mjacobson.removethis@xorantech.com> wrote in
message <g82a4h$hj9$1@fred.mathworks.com>...
>
> > Does anyone know what else to check to see why line
search
> > can't find a good point?
> >
> > Thanks,
> >
> > Dave
>
> Singularity of the Hessian possibly. If the method the
> routine is using is Newton-like, it may be trying to
> compute the Hessian, or some approximation to it, and to
> invert it.
>
> If the Hessian at the point is nearly singular, it will
> have problems, I'd imagine.
>

Just to elaborate a bit, if the Hessian (or its
approximation) is not positive definite, the routine may
have computed a search direction which is not a descent
direction. In this case, the line search may easily not
find a point of descent.

Do you have anyway of extracting the search direction
vector? I'm afraid I'm not that familiar with fminunc, but
if you can extract it, you can take its inner product with
the (-gradient) to see if the directional derivative along
the search direction is negative (as you would like it to
be).

Re: Line search failing?

Marcelo Marazzi — Fri, 15 Aug 2008 20:31:49 -0400

Dave,

Possible reasons are that the line search algorithm failed
because the objective function is not differentiable. Or
because roundoff errors are stalling convergence of the line
search algorithm.

Is it possible to post the objective? If it's not, you
may want to send the data needed to reproduce the problem to
tech support http://www.mathworks.com/support/

-Marcelo

David Doria wrote:
> I am using fminunc to try to find the minimum of a function.
> I plotted the function (it is only 2d) and it seems
> extremely well behaved - visually it there is without a
> doubt a single local min if you start any where near the min
> value (the value is at (20, 0) and there looks to be about a
> 5 unit radius of convergence).
>
> However, when I run fminunc, I get:
>
> Line search cannot find an acceptable point along the
> current search direction.
>
> The only thing I could think to check is if the gradient was
> somehow 0-ish even though it didn't look like it in the
> plot, but when I output the gradient at the iteration it
> gives the error it is
>
> Gradient is:
>
> ans =
>
> -1.2747
> 0.4237
>
> Does anyone know what else to check to see why line search
> can't find a good point?
>
> Thanks,
>
> Dave