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
21 Downloads
Updated 23 May 2024

View License

# 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

Cite As

Jorge Paloschi (2024). hsolve - Homotopy solver for algebraic nonlinear equations (https://www.mathworks.com/matlabcentral/fileexchange/166286-hsolve-homotopy-solver-for-algebraic-nonlinear-equations), MATLAB Central File Exchange. Retrieved .

MATLAB Release Compatibility
Created with R2024a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Tags Add Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

DeployedToFileExchange/trunk/Code

DeployedToFileExchange/trunk/Code/common

DeployedToFileExchange/trunk/Code/homotopies

DeployedToFileExchange/trunk/Code/pathFollowing

DeployedToFileExchange/trunk/Test

DeployedToFileExchange/trunk/Test/Examples/AlgNonlinear

Version Published Release Notes
1.0.2

Added reference

1.0.1

Changed summary

1.0.0