4Homotopy and continuation methods

The material of this Chapter is from Kincaid & Cheney, 2002.

4.1Main idea¶

Let $f : X \to Y$ and consider the problem: find $x \in X$ such that $f(x) = 0$. This problem may be difficult to solve; for Newton method, we need a good initial guess, which we may not know.

Suppose we can easily solve the problem: find $x \in X$ such that $g(x) = 0$. Define

Note that

Partition the interval $[0,1]$ into

We can easily solve the problem $h(t_0,x) = g(x) = 0$, let $x_0$ be the solution. Now to solve the problem $h(t_1,x)=0$, say using Newton method, we can use $x_0$ as the initial guess. Since the two problems are close, $x_0$ can be expected to be a good initial guess for the next problem. This process can be continued until we solve the problem $h(t_m,x) = f(x) = 0$ using the initial guess $x_{m-1}$.

The simplest example is the linear interpolation between the two problems, which we discussed above.

4.2An ODE¶

Instead of solving the sequence of problems, we will convert it into an ODE problem. The solution of $h(t,x)=0$ depends on the parameter $t$, so $x(t)$ satisfies

Differentiate wrt $t$

so that

For this ODE to be valid, we need $h$ to be differentiable wrt $t$ and $x$ and $h_x$ must be non-singular. Suppose we know that $x_0$ solves $h(0,x)=0$. We solve the ODE approximately upto $t=1$ with initial condition $x(0) = x_0$.

4.3Relation to Newton method¶

Choose an $x_0$ and consider the homotopy

so that

The curve $x(t)$ such that

satisfies the ODE

so that

Applying forward Euler scheme with $\Delta t = 1$ we get

we get the Newton-Raphson method.

4.4Linear programming¶

Let $c,x \in \re^n$, $A \in \re^{m \times n}$, $m < n$ and consider the constrained optimization problem

Choose a starting point $x^0$ which satisfies the constraints, i.e.

Our goal is to find $x^1$ such that $c^\top x^1 > c^\top x^0$ and $x^1 \in \mathcal{F}$. Equivalently, find a curve $x(t)$ such that

1. $x(0) = x^0$

2. $x(t) \ge 0$ $\forall t \ge 0$

3. $A x(t) = b$

4. $c^\top x(t)$ is increasing function of $t$, $t \ge 0$

Let us try to find an equation satisfied by such a curve $x(t)$

To satisfy (2), choose $f$ such that $f_i(x) \to 0$ as $x_i \to 0$. One such choice is

To satisfy (3) we must have $A x'(t) = 0$ or $A D(x) G(x) = 0$. Choose

where $P : \re^n \to$ null space of $AD(x)$. So we can take

The null space of $AD(x)$ is a subspace of $\re^n$. By Projection Theorem in Hilbert spaces, we have

In particular

Such a $P$ is given by

The existence of $P$ requires that $(AD)(AD)^\top = (m\times n)(n\times m) = (m \times m)$ is invertible, and hence rank $AD = m$. This is true if each $x_i > 0$ and rank $A=m$.

Now (4) will be satisfied by the solution of the ODE if

Let us choose $H(x) = D(x) c$, then

We have constructed an ODE model whose solution has all the required properties. How do we compute $Pv$ ? Using the definition of $P$ requires computing an inverse matrix which can be expensive if the sizes involved are large. Instead, define $B=AD$ and given $v \in \re^n$, compute $Pv$ by the following steps.

1. Solve for $z$

   $$B B^\top z = Bv$$

   (38)

2. $Pv = v - B^\top z$

Now we are in a position to solve the ODE

The simplest approach is the Euler method which finds $x^{k+1} \approx x(t_k+\Delta t_k)$ from

It is easy to verify that $Ax^{k+1}=b$ since $Af(x^k) = 0$. It remains to ensure that $x^{k+1} > 0$ which may not be automatically satisfied by the Euler method. We can satisfy this condition by choosing $\Delta t_k$ small enough,

e.g.,

The factor $9/10$ ensures the strict inequality $x^{k+1} > 0$.