J.Ch. Gilbert

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:

Polyhedral Newton-min algorithms for complementarity problems, by Jean-Pierre Dussault, Mathieu Frappier and Jean Charles Gilbert, Mathematical Programming (in revision).

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, developed with the Matlab version '9.11.0.1837725 (R2021b) Update 2').

License

QPL 1.0.

Download

hnm4lcp-public-2024-11-24.zip (15 Mb).