Codes

ISF (MATLAB) #

ISF and BDIFFMIN are available at Software Heritage and its functioning described in this pdf. See also the associate article PDF. Work done with Jean Charles Gilbert and Jean-Pierre Dussault.

ISF - BDIFFMIN is a MATLAB set of functions that computes the Bouligand differential of the minimum of two affine functions. This computation arose from the use of the (componentwise) minimum on a Linear Complementarity Problem:

\[x \in \mathbb{R}^n \mapsto F(x) := \min(Ax+a, Bx+b) \in \mathbb{R}^m.\quad (\mathrm{LCP})\]

Let \(\mathcal{E} := \{i \in [1:m] : (Ax+a)_i = (Bx+b)_i\}\), \(p := |\mathcal{E}|\) and let

\(V = (B_{\mathcal{E},:} - A_{\mathcal{E},:})^{\mathsf{T}}\), one has \(\partial_B F(x) \Longleftrightarrow \mathcal{S}(V)\)

where \(\mathcal{S}(V) := \{s \in \{\pm 1\}^p : \exists\ d \in \mathbb{R}^n, s \cdot V^{\mathsf{T}} d > 0 \} \)

The name ISF, for Incremental Sign Feasibility, is a description of the algorithm employed, initially designed by Rada and Černý in this article (available preprint).

This computation is done by determining the chambers of the related central hyperplane arrangement. Other equivalent problems can also be dealt with by ISF, such as

• enumerating the orthants encountered by the null space of a matrix,
• knowing the pointed cones generated by a set of vectors (and their opposites),
• finding the possible partitions in two subsets by a hyperplane of a set of points,
• determining the (sign combinations of the) vertices of a zonotope.

ISF (Julia) #

This software is a direct ‘descendant’ of the MATLAB version and aims at dealing with arbitrary arrangements. A first version, developped in Julia, is mostly finished and possesses additional features such as computations in rational number and more algorithmical variants. See here for a documentation. Work done with Jean Charles Gilbert and Jean-Pierre Dussault.