homotopy continuation
/ ho-MOT-uh-pee /
Newton's method is fast but local — it only works if you already start close to a root. What do you do for a hard problem where you have NO good initial guess? Homotopy continuation is a strategy borrowed from a mountaineer's trick: do not jump straight to the hard summit; start from an easy nearby peak you can already reach, then walk along a connecting ridge, step by step, until you arrive. You deform an easy problem you can solve into the hard one you want, tracking the solution as it moves.
Set it up with a parameter t running from 0 to 1. Build a family of problems H(x, t) = 0 (a homotopy) such that at t = 0 it is an EASY problem with a known solution, and at t = 1 it is your TARGET problem F(x) = 0. A common choice is the convex homotopy H(x, t) = (1 - t) * G(x) + t * F(x), where G is easy (its root you already know) and F is your goal. Now increase t in small steps from 0 to 1; at each new t, use the solution from the previous t as the starting guess for Newton's method, which converges quickly because you only moved a little. The solution traces a continuous PATH through (x, t)-space from the easy root to the hard one — hence 'path following'.
Continuation turns a globally hard root-finding problem into a sequence of locally easy ones, and it is the method of choice when good initial guesses are scarce: nonlinear circuit and structural analysis, power-flow equations, and especially finding ALL solutions of polynomial systems (polynomial homotopy continuation can locate every isolated complex root). The honest difficulties are real: the path can fold back (turning points where it momentarily reverses in t), branch, or pass near singularities where the Jacobian goes bad — robust implementations use arc-length parametrization to step ALONG the path rather than in t, plus adaptive step control, predictor-corrector steps, and care near bifurcations.
To solve a hard F(x) = 0 with no good guess, pick an easy G(x) = x - x_0 whose root x_0 you choose freely. Form H(x, t) = (1 - t)(x - x_0) + t F(x). At t = 0 the root is x_0; nudge t to 0.1, run Newton from x_0, get the new root; nudge to 0.2, and so on. By t = 1 you have walked the solution all the way to a root of F, no lucky initial guess required.
Deform an easy problem into the hard one, tracking the root along the path.
Path following is not automatic: the solution path can turn, branch, or skirt singularities where the Jacobian fails, and naive stepping in t then breaks. Serious codes step along arc length with adaptive control — and even so, a poorly chosen homotopy may miss roots.