0
$\begingroup$

Are there any optimization algorithms aimed at finding a coinciding root and a (local) minimum of a multi-variable function f. Say it is known analytically that these should coincide for the function.


I am interested in any such algorithm but more specifically for the case where f is continuous, at least twice differentiable and very expensive to compute (so internal costs for the algorithm can be neglected, only function calls matter). What would you use if the gradient could be computed for free? What if the Hessian can also be computed for free? What if the root and the minimum only coincide approximately, i.e. the minimum $f(x_c)\in $ $[-\epsilon,\epsilon]$ for some small epsilon.

$\endgroup$
8
  • $\begingroup$ What is the advantage of it being a root of the function? If it coincides with a local minimum it means that a perturbation would lead to infinite crosses with zero or non in the vicinity. Why not using an optimization algorithm? $\endgroup$ – nicoguaro Apr 15 at 17:08
  • $\begingroup$ @nico, There is a clear advantage in knowing you are searching for a root as well. Say you would like to use gradient descent. Normally you don't know what step length to take. Now at least some idea of the appropriate step length comes from solving for the root. Similarly for something using a quadratic model you can solve for both the minimum and the root (if you have a full Hessian this would be overconstrained but if you use some kind of BFGS updating where the Hessian is not fully determined the extra equations can help). $\endgroup$ – Kvothe Apr 15 at 17:19
  • $\begingroup$ Of course we can trivially rephrase this question as searching for a minimum if the value at the minimum is already known. Perhaps that will make things more clear and ring some bells for some people instead. $\endgroup$ – Kvothe Apr 15 at 17:21
  • $\begingroup$ You could do something like a line search for the step size. $\endgroup$ – nicoguaro Apr 15 at 20:36
  • 2
    $\begingroup$ This can be formulated as a standard constrained optimization problem in which $f(x_c) = 0$ or $f(x_c) \in [-\epsilon,\epsilon]$ is included in the constraints. Whether incorporation of such constraint makes it easier or harder to solve is another matter. Presuming $f$ is nonlinear, the added constraint(s) will be non-convex. $\endgroup$ – Mark L. Stone Apr 18 at 20:43

Your Answer

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

Browse other questions tagged or ask your own question.