2
$\begingroup$

I have a somewhat large (20+ dimensional) root finding problem that I'm solving with Levenberg-Marquardt. One of the functions has box constraints on [0, 2]. When it is against those bounds it will not be able to find a zero of the function. Leaving that in the solution and letting the optimizer try to find a minimum does not find a good solution for the rest of the problem.

I've tried a few different techniques to insert zeros into that function, the most naive being:

if ( y0[m] <= 0 || y0[m] >= 2 )
  z[n] = 0
else
  z[n] = H0tf
end

(where y0[m] is the independent variable that is bounded, z[n] is the zero function being produce, and H0tf is a somewhat complicated function).

I've also tried less naive ways of introducing those zeros, with various potentials introduced near 0 and 2 so that the function becomes smooth and not discontinuous.

The overall difficulty of all of those approaches is that now in the non-bounded case the optimizer needs to solve a global optimization problem where there may be a zero at 0 and 2 and also the correct 0 in H0tf somewhere in the [0, 2] range, which gets very 'hacky' trying to solve that with a local optimizer.

Is there a better way to handle somehow deleting this function from consideration of the optimizer when it is at its bounds? And what do you call such a technique?

$\endgroup$
1
$\begingroup$

Did you try adding penalty regularisation scheme to your least-squares objective function?

The Levenburg-Marquardt algorithm with attempt to minimise the residual, $r(x_i)$ where $x_i$ is your parameter vector. You could try adding a penalty term which penalizes the solver for suggesting to place the troublesome parameter near to a boundary.

$r^\prime(x_i) = r(x_i) + p(x_i)$

Here $p(x_i)$ is the penalty term, which will be non-zero when one of your parameters gets stuck or approaches the boundary. Obviously, you should only accept solutions where $p(x_i)=0$.

As an aside, have you tried Trust Region Reflection algorithm. These things can be problem specific, but I have been very impressed with how efficient and robust this can be. It is the default option in scipy.

$\endgroup$
  • $\begingroup$ I'm using the L-M algorithm in alglib.net which already handles the box constraints fine. The problem is that at the constraints the problem it solves is wrong (it can't find the root because the constrained function does not have a zero). By deleting the function (and fixing the variable at the correct bound) I can get the solution. I don't have TRR in C# so I'd need to write my own from scratch, which is rather a lot just to solve this problem. $\endgroup$ – lamont Oct 22 '18 at 3:21
  • $\begingroup$ OK. I understand a little better. When the problem occurs can you stop the solver, start a new solver from the same point but with the troublesome parameter removed? $\endgroup$ – boyfarrell Oct 22 '18 at 10:58
  • $\begingroup$ The difficulty is that once the problem is solved I need to iterate on the solution with slightly changed initial conditions. At some point it can actually flip so that there would now be a valid zero in the function. Reconverging from zero is very expensive while the iterations are always close and fairly cheap -- but trying both setups every iteration will be expensive for the second setup that fails. $\endgroup$ – lamont Oct 23 '18 at 19:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.