Extending and Simplifying Existing Piecewise-Linear Homotopy Methods for Solving Nonlinear Systems of Equation

This dissertation research extends and simplfiies existing piecewise-linear homotopy (PL) methods to solve G(x) = 0, with G : Rn → Rm. Existing PL methods are designed to solve F(x) = 0, with F : Rn → Rn and some related point-to-set mappings. PL methods are a component of what is also known as numerical continuation methods, and they are known for being globally convergent methods. First, we present a new PL method for computing zeros of functions of the form f : R n → R by mimicking classical PL methods for computing zeros of functions of the form f : R → R. Our PL method avoids traversing subdivisions of R n x [0, 1] and instead uses an object that we refer to as triangulation-graph, which is essentially a triangulation of R x [0, 1] with hypercubes of Rn as its vertices. The hypercubes are generated randomly, and a sojourn time of an associated discrete-time Markov chain is used to show that not too many cubes are generated. Thereafter, our PL method is applied to solving G(x) = 0 for G : Rn → Rm under inequality constraints. The resultant method for solving G(x) = 0 translates into a new type of iterative method for solving systems of linear equations. Some computational illustrations are reported. A possible application to optimization problems is also indicated as a direction for further work.