Homotopy and Continuation Methods
Algorithms that use trust-region and line-search strategies require the
condition
to hold for each iteration. Consequently, they can become trapped in a region in which
the function 
has a local minimizer 
for which 
, and they can therefore fail to
converge to a solution 
of the original nonlinear system
.
To be more certain of convergence to from arbitrary starting points,
we need to turn to a more complex class of algorithms known as homotopy, or continuation
methods. These methods are usually slower than line-search and trust-region methods, but
they are useful on difficult problems for which a good starting point is hard to find.
Continuation methods define an easy problem for which we know the
solution, and a path between this easy problem and the hard problem that we actually wish
to solve. The solution to the easy problem is gradually transformed to the solution of the
hard problem by tracing this path. The path may be defined by introducing an additional
scalar parameter 
into the problem and defining a function
where 
is a given point in 
. The problem
is then solved for values of between 
and 
. When 
, the solution to (1.6) is clearly
. When 
, we have that
,
and so the solution of (1.6) coincides with the solution of the original
problem .
There may be other ways of defining the path that are more closely tied to the
underlying problem.
The path that takes 
from 
to 
may have turning points at which switches from
increasing to decreasing and vice versa, so it may not be possible to move from to by gradually
increasing
from to . The algorithms
in CONTIN (formerly known as
PITCON) and HOMPACK use
the more robust approach of expressing both 
and in terms of a third parameter, 
, which
represents arc length along the solution path. One of the methods implemented in HOMPACK traces the path by
differentiating 
with respect to to obtain the ordinary differential equation
Sophisticated solvers may then be applied to this problem with initial condition
and side condition
.
Another method, implemented in both HOMPACK and CONTIN , obtains a new iterate 
from the
current iterate 
by solving an augmented system of the form
The additional (linear) equation is usually chosen so that 
is one of the unit vectors in 
, and 
is a target
value for one of the components of 
whose value has been fixed by a
predictor step.
HOMPACK includes additional
features such as sparse linear algebra software for large-scale systems and algorithms for
finding the solution of systems of polynomial equations. In addition to simple systems of
nonlinear equations, CONTIN can
solve parametrized systems, in which is an intrinsic parameter rather
than an artificial parameter as in the discussion above. The code allows features of the
solution path such as bifurcation points and turning points to be calculated accurately.
Up To:
Systems of Nonlinear Equations .
[ OTC Home Page | NEOS Guide | NEOS
Server | Optimization Tree ]
Updated 28 March 1996