HNM4LCP Matlab function
HNM4LCP is a Matlab function that computes the solution of a linear complementarity problem using the hybrid
Newton-min algorithm.
Description of the function
HNM4LCP solves a linear complementarity problem, which consists in finding a vector $x\in\mathbb{R}^n$ with nonnegative components
such that the vector $Mx+q$ (the square matrix $M\in\mathbb{R}^{n× n}$ and the vector $q\in\mathbb{R}^n$ are given) is also
nonnegative and perpendicular to $x$ ($x^\mathsf{T}(Mx+q)=0$). This is denoted compactly by
$0 \leq x \perp (Mx+q) \geq 0.$
This type of problem appears
-
in the optimality conditions of a quadratic optimization problem,
-
in nonsmooth mechanics (in robotics in particular),
-
to express dissolution-precipitation phenomena in chemistry, in multiphase flows, in meteorology, etc.
The followed solution approach consists in reformulating the problem in the form of the equivalent nonsmooth equation $H(x) =
0$, where $H$ is the minimum C-function, defined at $x\in\mathbb{R}^n$ by
$H(x) := \min(x,Mx+q)$
and to apply the hybrid Newton-min algorithm to the system $H(x) = 0$. This algorithm is a kind of semismooth Newton
algorithm (the used Jacobian belongs to the product B-differential of $H$, not necessarily to its B-differential, which
may be difficult to compute) that is modified to ensure global convergence (this requires to compute a point in a convex
polyhedron at some iterations, rarely actually).
Authors
Jean-Pierre Dussault
Département d'Informatique, Faculté des Sciences, Université de Sherbrooke, Québec, Canada
Jean-Pierre.Dussault@Usherbrooke.ca
ORCID 0000-0001-7253-7462
Jean Charles Gilbert
INRIA (centre de recherche Inria de Paris, équipe-projet Serena), 48 rue Barrault, CS 61534, 75647 PARIS Cedex, France
Département de Mathématiques, Faculté des Sciences, Université de Sherbrooke, Québec, Canada
Jean-Charles.Gilbert@inria.fr
ORCID 0000-0002-0375-4663
Documentation
Associated publications
HNM4LCP is introduced, described, analyzed (for nonlinear complementarity problems) and numerically assessed (for
linear complementarity problems) in the following paper:
Here are other personal contributions on the minimum C-function and the Newton-min algorithm:
-
Nonconvergence of the plain Newton-min algorithm for linear
complementarity problems with a P-matrix, by Ibtihel Ben Gharbia and Jean Charles Gilbert, Mathematical
Programming, 134 (2012) 349-364 [doi].
-
An algorithmic characterization of P-matricity, by Ibtihel
Ben Gharbia and Jean Charles Gilbert, SIAM Journal on Matrix Analysis and Applications, 34:3 (2013) 904-916 [doi].
-
An algorithmic characterization of P-matricity II: adjustments,
refinements, and validation, by Ibtihel Ben Gharbia and Jean Charles Gilbert, SIAM Journal on Matrix Analysis and
Applications, 40:2 (2019) 800-813 [doi].
-
A lower bound on the iterative complexity of the Harker and
Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem, by Jean-Pierre
Dussault, Mathieu Frappier and Jean Charles Gilbert, EURO Journal on Computational Optimization, 7:4 (2019) 59-380 [doi].
-
Exact computation of an error bound for the balanced linear
complementarity problem with unique solution, by Jean-Pierre Dussault and Jean Charles Gilbert, Mathematical
Programming 199:1-2 (2023) 1221-1238 [doi].
-
On the B-differential of the componentwise minimum of two affine
vector functions, by Jean-Pierre Dussault, Jean Charles Gilbert and Baptiste Plaquevent-Jourdain, Mathematical
Programming Computation (2024) (to appear) [doi].
Version
Version 1.0 (November 2024).
License
QPL 1.0.
Upload
Download
The code Hnm4lcp can be downloaded here (15 Mb).