Re: Optimization using a *Bounded* Levenberg-Marquardt method

Simone wrote:

Hello, I'm trying use the LM method to minimize a function over a bounded
domain. I've looked around and I found some paper regarding the argument. I
have understood the mechanism behind the unbounded LM and I succesfully
wrote a program that works.
The problem is that I don't understand how I must modify my algorithm to add
the fact that I want to optimize over a BOUNDED domain... I mean, from what
I read, I guess I can't simply resize the step lenght if it would bring me
off the domain?
I read about projecting the step vector over my domain... But what if my
domain isn't a vectorial space? I mean, if we work on R^2 and my domain is:
D={(x,y)|x>0,y>0,x+y<1}
I can't project a vector over it..

I hope that my question is understandable and excuse me for my english.

Thanks.

Simone




Here are a couple of quick and dirty tricks that
sometimes work. If they do, you can use your
program written for unbounded optimization and use
it to solve a problem with constraints.

1. When evaluating the objective function, check to
see if you are inside the domain or not. If not, add a
penalty to the value you compute for the objective function.
This should make the optimization algorithm avoid the
out of bounds area, since it is trying to minimize the
objective function, and the function increases every time
the algorithm steps out of bounds.

This might require some tinkering -- how much of a
penalty to add, whether the penalty should be a step
function or proportional to the distance from the boundary,
etc.

2. Sometimes one can map a finite domain into an infinite
domain, and then use an algorithm for unconstrained
optimization.

A good example is when x and y must be greater than zero.
If you choose new variables x' = log(x) and y'=log(y), then
x' and y' can vary over the entire R^2 plane and the
corresponding x and y are guaranteed to be positive.

In your case, the x+y<1 constraint makes the situation
a bit more complex. You might be able to use a
Schwartz-Christoffel transformation to map your
triangle into the upper half plane, and from there map
into the entire plane.

I admit I don't quite understand what you mean by "projecting
a step vector." You might be talking about the same sort of thing.

Like I say, these are quick and dirty tricks. Both require
that you make changes only to the function you are optimizing --
you don't have to tinker with the optimization program at all.
I'm sure there are algorithms for constrained optimization,
and I'm sure that there are more elegant solutions to your
problem, but these tricks sometimes work and they don't
take much effort to try.

Olin Perry Norton

.

Relevant Pages

  • Re: Opt TB - fminunc termination exitflag criteria
    ... (Plotting the cost function against the optimization ... problems with the gradient. ... objective function, z, composed of two planes ... A property of a line search is that the algorithm ...
    (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)
  • 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, ... The Fortran bobyqa optimization algorithm is a derivative-free ... outside the box as those values on the box boundaries. ...
    (comp.lang.fortran)
  • 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)