hsolve - Homotopy solver for algebraic nonlinear equations

This solver is a complement to fsolve, the MATLAB solver. It solves a problem within given bounds for the variables and is more robust

# hsolve - A homotopy based solver

% Copyright 2024 The MathWorks, Inc.

This is an implementation of a solver for algebraic nonlinear equations

following a homotopy approach. In a few words, the idea of a homotopy

solver is that instead of solving the original problem:

f(x) = 0, f:Rn --> Rn

it solves

h(x,t)=0, h:RnxR --> Rn,

where h(x,0) has a known solution and h(x,1)=0 <==> f(x)=0.

The idea is then start with t=0 and hopefully follow the path h(x,t) until t=1.

This code does not intent to replace the built in solver in MATLAB for this

purpose, fsolve, but rather complement it when it fails to solve a problem.

Therefore, the first action of the code is to attempt solving f(x)=0 using

fsolve, and only resort to the homotopy code if it fails.

One important aspect of the code is that it will respect bounds, i.e.,

the solution to f(x)=0 will be searched in the region defined by lb<=x<=ub,

where lb and ub are respectively lower and upper bounds vectors compatible

with x.

Respecting bounds is a very important feature, especially in Engineering

problems, where physical bounds cannot be violated.

## Usage

Let's assume you want to solve a system of 2 equations with 2 variables.

Create an m file in MATLAB (say prob.m) by copying the following lines:

% Script starts here

options.Display = 'none';

x0 = [-0.1,0.1]; lb = [-0.5,-1]; ub = [2,1];

[xsol,fval,exitFlag,path] = hsolve(@fun , @funDeriv, x0, lb, ub, options);

% Display results

fprintf('hsolve returned exitFlag=%d solution=[%g %g] function norm=%g\n', ...

exitFlag,xsol(1),xsol(2),norm(fval))

% Function to be solved

function y = fun(x)

y(1,1) = x(1)^2 + x(2)^2 - 1;

y(2,1) = x(1)^3 - x(1) - x(2);

end

function yp = funDeriv(x)

yp(1,1) = 2 * x(1); yp(1,2) = 2 * x(2); yp(2,1)= 3 * x(1)^2-1; yp(2,2) = -1;

end

% Script end here

The parameters to be passed to hsolve are:

- A handle to the function to be solved

- A handle to calculate the Jacobian of the previous function, if known,

otherwise it could be empty and will be calculated automatically.

- A starting point from where to initiate the solving process. Must be

within the provided bound

- A vector of lower bounds

- A vector of upper bounds

- A structure containing the solver options (type "help hsolve" for info)

Assuming you named the created file above prob.m, type prob in the MATLAB

command line to run the script. The code will first try to solve the problem

with fsolve, which fails because of the bounds, then will apply the homotopy

approach obtaining the solution within the bounds, which is displayed in the

command line as:

>> prob

hsolve returned exitFlag=1 solution=[1 -1.49554e-21] function norm=1.49554e-21

>>

## Testing

We have used a set of 48 problems taken from the literature for testing.

Comparing the robustness of hsolve against other solvers produced the

following results:

fsolve fmincon hsolve py.root

______ _______ ______ _______

Success 41 31 48 23

Success %: 85.4 64.6 100.0 47.9

The solver fsolve is the well known built in solver in MATLAB, fmincon is

an optimizer which is used as minimizing the norm of f(x) instead of f(x)=0,

and py.root is the well known solver for algebraic equations in Python.

As can be seen from this limited results, hsolve does a good job for this

set of examples.

We have performed another experiment, by generating at random a number of

initial points within the bounds for the sample problems. We have observed

that hsolve consistently solves 92% of the problems, followed by fsolve at

80% and fmincon at 64%. Code is provided to reproduce these experiments.

References:

J.R.Paloschi - Bounded homotopies to solve systems of algebraic nonlinear equations

Computers & Chemical Engineering - Vol 9 - Issue 12 - 1995 - pp1243-1254

https://www.sciencedirect.com/science/article/abs/pii/0098135494001227

## License

See the license.txt file provided