ISF and BDIFFMIN Matlab functions
BDIFFMIN is a Matlab function that computes the B-differential of the componentwise minimum of two affine vector functions. To
achieve this task, BDIFFMIN uses the Matlab function ISF, which determines the chambers of an arrangement of hyperplanes having
a point in common.
(Download on Software Heritage)
Description of the functions
The B-diffrential computed by BDIFFMIN (for B-DIFFerential of the MINimum function) is a concept of derivative for a
nonsmooth function. The function considered by BDIFFMIN is the componentwise minimum of two affine vector functions
$x\in\mathbb{R}^n \mapsto \min (Ax+a,Bx+b)\in\mathbb{R}^m$,
where $A$ and $B$ are $m\times n$ real matrices, while $a$ and $b$ are real vectors of size $m$. In this
case, the B-differential is a finite (between 1 and $2^m$ elements) collection of Jacobians (i.e., $m\times n$ matrices). The
computing time is polynomial per computed Jacobian.
To realize this task, BDIFFMIN calls the Matlab function ISF (for Incremental Sign Feasibility), which has been
designed to determine the chambers of an arrangement of hyperplanes having a point in common. The sign vectors
computed by ISF can be used to solve a number of other enumeration problems such as
-
determining the signed feasibility of strict inequality systems,
-
listing the orthants encountered by the null space of a matrix,
-
itemizing the pointed cones generated by a set of vectors and their inverses,
-
giving the bipartitions of a finite set of points that can be separated by an affine hyperplane and many others.
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), 2 rue Simone Iff, CS 42112, 75589 Paris Cedex 12, 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
Baptiste Plaquevent-Jourdain
Département de Mathématiques, Faculté des Sciences, Université de Sherbrooke, Québec, Canada
INRIA (centre de recherche Inria de Paris), 2 rue Simone Iff, CS 42112, 75589 Paris Cedex 12, France
Baptiste.Plaquevent-Jourdain@USherbrooke.ca
baptiste.plaquevent-jourdain@inria.fr
Documentation
ISF and BDIFFMIN - Matlab functions for the hyperplane
arrangement and the computation of the B-differential of the componentwise minimum of two affine vector functions, by J.-P.
Dussault, J.Ch. Gilbert and B. Plaqevent-Jourdain.
Associated publication
You are invited to read and cite the following paper:
On the B-differential of the componentwise
minimum of two affine vector functions, by J.-P. Dussault, J.Ch. Gilbert and B. Plaqevent-Jourdain, submitted to
Mathematical Programming Computation.
Version
Version 1.0 (01-05-2023).
License
Both functions are distributed under the QPL license.
Upload
The code has been uploaded on Software Heritage on 11-06-2023, via HAL.
The code has been mentioned on Matlab Central File Exchange on 15-06-2023.
Download on Software Heritage
isf-bdiffmin_1.0