Homotopy Method

Let the nonlinear equation to be solved be $\boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0}$. The Homotopy method introduces an auxiliary equation $\boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{0}$ with a trivial solution and a continuous parameter $\lambda \in [0, 1]$ to construct the following Homotopy Map:

The set of zeros of this $H(\boldsymbol{x}, \lambda)$ forms a "solution curve" connecting the known solution at $\lambda=0$ to the desired solution at $\lambda=1$. Depending on the choice of the auxiliary equation $\boldsymbol{g}(\boldsymbol{x})$, methods are classified as follows:

① Fixed-Point Homotopy

The most standard form where $\boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{x} - \boldsymbol{x}_0$. It has a unique solution $\boldsymbol{x} = \boldsymbol{x}_0$ at $\lambda=0$, from which the search begins.

\[ H(\boldsymbol{x}, \lambda) = (1 - \lambda)(\boldsymbol{x} - \boldsymbol{x}_0) + \lambda \boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0} \]

② Newton Homotopy

A form where $\boldsymbol{g}(\boldsymbol{x}) = \boldsymbol{f}(\boldsymbol{x}) - \boldsymbol{f}(\boldsymbol{x}_0)$. This corresponds to giving an offset that forces the residual at the initial value $\boldsymbol{x}_0$ to zero, and then gradually removing it.

\[ H(\boldsymbol{x}, \lambda) = \boldsymbol{f}(\boldsymbol{x}) - (1 - \lambda)\boldsymbol{f}(\boldsymbol{x}_0) = \boldsymbol{0} \]

③ Odd Homotopy

A form using the odd function part of $\boldsymbol{f}(\boldsymbol{x})$ for $\boldsymbol{g}(\boldsymbol{x})$. It excels in proofs of solution existence and topological stability when searching for multiple solutions.

\[ H(\boldsymbol{x}, \lambda) = \lambda \boldsymbol{f}(\boldsymbol{x}) + (1 - \lambda) \frac{\boldsymbol{f}(\boldsymbol{x}) - \boldsymbol{f}(-\boldsymbol{x})}{2} = \boldsymbol{0} \]

When tracking the solution curve $H(\boldsymbol{x}, \lambda) = \boldsymbol{0}$, treating $\lambda$ as a simple incremental parameter causes the Jacobian matrix to become singular at "turning points," breaking the computation. To avoid this, the Arc-length Continuation method is used, where the path length (arc length) $s$ of the solution curve is treated as the independent variable.

① Construction of Augmented Equations

Let the variable vector be $\boldsymbol{y} = [\boldsymbol{x}^T, \lambda]^T$, and solve the $n+1$ dimensional augmented equation. Letting the tangent vector with respect to arc length $s$ be $\dot{\boldsymbol{y}} = [d\boldsymbol{x}/ds, d\lambda/ds]^T$, the following constraint holds:

② Predictor-Corrector Cycle

• Predictor: Calculate the tangent vector at the current step from $\boldsymbol{J}_H \dot{\boldsymbol{y}} = \boldsymbol{0}$. Obtain $\boldsymbol{y}_{pred} = \boldsymbol{y}_k + \Delta s \cdot \dot{\boldsymbol{y}}_k$ using Euler's method or similar.
• Corrector: Pull the predicted point back to the solution curve using Newton's method on the hyperplane orthogonal to the tangent vector. The Augmented Jacobian Matrix of order $n+1$, which includes the tangent condition, remains non-singular even at turning points, guaranteeing stable convergence.

Consider the following nonlinear system finding the intersection of a "circle" and a "line." With Newton's method, convergence becomes unstable if the initial value is outside the circle, but the Homotopy method reliably leads to the solution.

Step 1: Constructing the Homotopy
Select an initial value $\boldsymbol{x}_0 = [0, 2]^T$ (outside the circle) and apply Fixed-Point Homotopy.

\[ H(\boldsymbol{x}, \lambda) = (1-\lambda) \begin{bmatrix} x_1 - 0 \\ x_2 - 2 \end{bmatrix} + \lambda \begin{bmatrix} x_1^2 + x_2^2 - 1 \\ x_1 - x_2 \end{bmatrix} = \boldsymbol{0} \]

Step 2: Behavior of the Solution Curve
When $\lambda=0$, the solution is trivially $(0, 2)$. As the arc length $s$ progresses, the solution approaches the boundary of the circle as $\lambda$ increases. The intermediate Jacobian $\partial H / \partial \boldsymbol{x}$ becomes:

\[ \boldsymbol{J} = (1-\lambda) \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} + \lambda \begin{bmatrix} 2x_1 & 2x_2 \\ 1 & -1 \end{bmatrix} \]

Step 3: Convergence
Finally, when $\lambda=1$ is reached, the equation perfectly matches $\boldsymbol{f}(\boldsymbol{x}) = \boldsymbol{0}$, yielding the solution $\boldsymbol{x} = [1/\sqrt{2}, 1/\sqrt{2}]^T$. Strongly nonlinear regions where Newton's method would "jump" are avoided by accurately tracing the curve using the arc-length method.

The most important aspect of implementing the Homotopy method is "Adaptive Step Control" when path tracking fails. By monitoring the curvature $d^2\boldsymbol{y}/ds^2$, minimizing $\Delta s$ at steep changes and increasing it at flat regions balances computation time and robustness.