Homotopy and Continuation Methods

A continuation method can be used to insure finding the solution when the problem is nonlinear and especially complicated. Suppose we wish to solve

h(x, a) = 0

and find x when 'a' is given, but the method we use is unsuccessful. If we can solve h(x,0) = 0, then we need a way to move from that solution to the one with the desired value of 'a'. Such a method is called continuation, and it is like a 'boot strap' process, in that each step we can make successfully, to reach the final goal, although we can't reach that goal in one step.

If the problem you are solving does not have any parameters, then we introduce them, and then call the method a homotopy method. Suppose we want to solve f(x) = 0, i.e. find the value of 'x' that makes f = 0, but we are unable to. We can, however, solve g(x) = 0 easily, where g(x) is some function, perhaps a simplification of f(x). Then we embed the two functions in a homotopy by taking

h(x,a) = a f(x) + (1 - a) g(x)

In this equation h can be a nxn matrix for problems involving n variables; then x is a vector of length n. We can solve h(x,a) = 0 for a=0; we then change 'a' gradually. Each time we solve to find the 'x' that makes h(x,a+a) = 0. We continue in this fashion until at a = 1, and we have solved h(x,1) = f(x) = 0. Since both methods use the same technique, the section is labeld homotopy and continuation methods.

Let us apply this method to the problem

which will be regarded as either a homotopy method or continuation method. Let us differentiate the equation with respect to 'a' along the homotopy path, that is the path where the equation is always satisfied. Using the properties of implicit functions, the derivative is

Let us also normalize the solution using the following equation.

First write Eq. (1) as

and then solve Eq. (3).

Then

but da/ds is unknown. Put this into Eq. (2) to get:

Sove this for da/ds (you will have to pick a sign for the solution). Once da/ds is known you can calculate the other derivatives.

The complete solution is

You can use an ODE integrator to step forward to a new value of {x_j}, a. Remember that to use an ODE integrator, you just need a function which takes a specified input and creates a specified output.

This method allows adjustable step sizes in s, since they are controlled by the ODE integrator.

But what happens if one can't solve Eq. (3) because the matrix is singular? A more general method follows. Expand the solution vector by taking

Then define the equations

Eq. (1) is now

and Eq. (2) is

Now select any variable

^{Solve Eq. (4) for y} _j.

Then solve the following equation for dX_k/ds.

Then

If Eq. (4) is singular, pick another value of k. Again, you can use an ODE integrator to step forward to a new value of {x_j}, a. Remember that to use an ODE integrator, you just need a function which takes a specified input and creates a specified output.

This method allows adjustable step sizes in s, since they are controlled by the ODE integrator. Naturally, one starts with a value of 'a' that allows solution at the first step.

It is shown elsewhere (link) that it is very cheap to solve for a new right-hand side, once a linear matrix problem is solved. For multiple equations, this step is almost free. Equation (3) then give us the derivative of the function x with respect to 'a'. When we know the solution x for some 'a', the guess of the solution for the next 'a' is taken as

Take Home Message: Continuation and homotopy can be used to solve sets of nonlinear equations when nothing else works, but it takes more effort.