Re: Opt TB - fminunc termination exitflag criteria

In article <ef28603.2@xxxxxxxxxxxxxxxx>, "group user" <usr_grp@xxxxxxxxx> wrote:

My guess is, the cost function is continuous but not differentiable
at a finite number of locations. it should have some noise in it
since i am doing a large number of numerical operations inside my
algorithm. (Plotting the cost function against the optimization
variable is a very time-consuming process and i have 8 dimensions to
plot against.)

The not differentiable part will definitely cause
problems with the gradient.

If you had a few less dimensions, I'd recommend
fminsearch instead as less of a problem.

I expect what is happening is the finite difference
approximation for the derivative is at one of these
derivative discontinuities.

Consider this scenario in only 2 variables: form an
objective function, z(x,y), composed of two planes
that intersect along a line.

z(x,y) = x + y/2 (if x>0)
-x + y/2 (if x<0)

If you wish, you can write it as

z(x,y) = abs(x) + y/2

The global minimizer? It occurs at (x,y) = (0,-inf).

A property of a line search is that the algorithm
directs its search along a straight line, minimizing
the objective along that line. Then it chooses a new
direction to search, based on the gradient and past
searches.

This means that the line search will tend to stop
exactly along the derivative break I've created in
my function. If it does, then the forward differenced
gradient will point the method in a direction that
causes the function to increase.

So once the method stops at such a discontinuity,
it will terminate at x = 0, but at an arbitrary
finite value of y. The exitflag will be -2.

In fact, this optimization should have diverged, in
which case I would want it to fail due to exceeding
its maximum number of iterations. But instead it will
return an exit flag of -2.


From your reply i think, i can ignore the exitflag. It looks like the
solution returned by fminunc is near or at a local minimum even when
exitflag == -2.

No. I'm not at all confident that this is correct,
given my example above.

The problem is that fminunc assumes a differentiable
objective function. There is no assurance it has
converged for this class of function.

Perhaps stochastic optimizer is best for this problem,
i.e., a genetic algorithm. Take a look at the GADS
toolbox. Also look at some of the particle swarm tools
on the file exchange, though I'd class them as still
in development.

HTH,
John D'Errico


--
The best material model of a cat is another, or preferably the same, cat.
A. Rosenblueth, Philosophy of Science, 1945

Those who can't laugh at themselves leave the job to others.
Anonymous
.

Relevant Pages

  • Re: Optimization using a *Bounded* Levenberg-Marquardt method
    ... The problem is that I don't understand how I must modify my algorithm to add ... penalty to the value you compute for the objective function. ... This should make the optimization algorithm avoid the ... triangle into the upper half plane, ...
    (sci.math.num-analysis)
  • Re: fminunc linesearch failure (error -2)
    ... that the line search module not find a so-called acceptable point. ... The line search module is a pretty complicated algorithm in itself ... value of the objective and the magnitude of the gradient at the final ... indicating that my objective function is ...
    (comp.soft-sys.matlab)
  • Re: Fmincon number of obj-function evaluations
    ... seemingly caused fmincon to still compute the gradient by finite ... explained in the optimization toolkit's handbook (in fact, ... even mentioned in the section about fmincon). ... associated with the objective function evaluation. ...
    (comp.soft-sys.matlab)
  • Re: Numerical Recipes (Fortran) Usenet ??
    ... algorithm, see if you can multiply all input cooefficients and values ... I've looked at different optimization libraries (netlib, Neumaier, ... Miller, Burkardt, and others) with no luck in identifying a Fortran ... outside the box as those values on the box boundaries. ...
    (comp.lang.fortran)
  • Re: Behaviour of FMINCON - question.
    ... The large-scale algorithm is a subspace trust region method and is ... Medium-Scale Optimization ... Use equality constraints and the medium-scale method instead. ...
    (comp.soft-sys.matlab)
Loading