3
$\begingroup$

I have a system of nonlinear equations of which I know it has a single root I am interested in, and has a continuum of roots I am not interested in. I am currently using Newton with line-searching in an attempt to find that single root, but the algorithm will obviously always converge to one of the roots from the continuum, as there are infinity of them.

How should I go about excluding such roots from my system of equations?

My first idea was to add sharp Gaussian functions to my system of equations that are non-zero at those roots, and almost zero everywhere else. I am currently implementing this, but it already seems like convergence is now very slow and inconsistent.

Would I be better off rewriting my problem as an optimization problem? I would have to find a global minimum of a constrained function.

|cite|improve this question
$\endgroup$
  • $\begingroup$ It seems that you know where the continuum of roots is located. How much do you know about them? Also, what is the broader context in which this problem arises? $\endgroup$ – Victor Liu Oct 31 '13 at 9:17
  • $\begingroup$ I previously asked a question about the same problem: scicomp.stackexchange.com/questions/8772/… Where I explained the origin of the problem. The continuum of roots I am referring to occurs when for instance $\sum_{i=1}^{m} C_{i} = 0$ and for every $j$, $x_{ij}$ is the same for all $i$. $\endgroup$ – RobVerheyen Oct 31 '13 at 9:39
  • 2
    $\begingroup$ I think this question does a better job of explaining the broader context: scicomp.stackexchange.com/questions/8676/… $\endgroup$ – Geoff Oxberry Oct 31 '13 at 20:47
3
$\begingroup$

You could try using an optimization formulation to exclude undesirable roots via constraints. However, global optimization is a notoriously difficult problem and solving such a problem deterministically could be challenging. If you can exclude all suboptimal local minima in some way, that would make it easier. For deterministic approaches, you're essentially limited to calling BARON from GAMS (unless you want to write your own branch-and-bound framework with convex and concave relaxations implemented using interval arithmetic and automatic differentiation). Nondeterministic approaches will converge with probability one; you could try using such an approach, and if the solution it returns is not a root, use that solution as an initial guess for a Newton-like method. I doubt this approach will work especially well; to work, the guess for your Newton method would have to be within the basin of convergence of the root you want, and it can't preferentially converge to other roots. I think you're better off exploiting the structure Nico discussed in his answer to your other question; if you can express the desired root as a simpler closed-form expression without an infinity of roots (for instance, without all of the $C_i$), you'll have a more tractable problem.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Thank you for this answer. I don't think I understand what you mean with expressing the root as a closed-form expression. Could you elaborate? $\endgroup$ – RobVerheyen Oct 31 '13 at 21:07
  • $\begingroup$ And perhaps if you don't mind: What do you think of the idea of adding sharp Gaussian functions to my system of equations? $\endgroup$ – RobVerheyen Oct 31 '13 at 21:10
  • $\begingroup$ What I mean is, you know the form of all of the roots: they're some product of orthonormal vectors. If you know you want a root with a given $\mathbf{C}$ or $\mathbf{d}$, using the notation in scicomp.stackexchange.com/questions/8676/…, you should use that information first. If you perturb your system of equations, you need to make sure that the resulting equation does not have roots you don't want, and does have roots you do want. Slow convergence could mean your perturbed system has no roots. $\endgroup$ – Geoff Oxberry Oct 31 '13 at 22:29
  • $\begingroup$ In general, I shouldn't be able to find a root at all if I choose either $C$ or $d$ myself. I have a small test problem of which I know there exists only a single root, and it is at a single specific value for both $C$ and $x$. I know exactly what the roots that I want to exclude look like: they are the trivial ones. Any other root is one I'd like to find. $\endgroup$ – RobVerheyen Oct 31 '13 at 23:00
  • $\begingroup$ Will Newton run into trouble if my system of equations has no actual roots, but the value of all functions at those roots much closer to 0 than the precision of my machine would be able to see? $\endgroup$ – RobVerheyen Oct 31 '13 at 23:02

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.