On the B-differential of the componentwise minimum of two affine vector functions

  • This paper focuses on the description and computation of the B-differential of the componentwise minimum of two affine vector functions. This issue arises in the reformulation of the linear complementarity problem with the Min C-function. The question has many equivalent formulations and we identify some of them in linear algebra, convex analysis and discrete geometry. These formulations are used to state some properties of the B-differential, like its symmetry, condition for its complete- ness, its connectivity, bounds on its cardinality, etc. The set to specify has a finite number of elements, which may grow exponentially with the range space dimension of the functions, so that its description is most often algorithmic. We first present an incremental-recursive approach avoiding to solve any optimization subproblem, unlike several previous approaches. It is based on the notion of matroid circuit and the related introduced concept of stem vector. Next, we propose modifications, adapted to the problem at stake, of an algorithm introduced by Rada and ˇCerný (SIAM J Dis- cret Math 32(1):455-473, 2018, https://doi.org/10.1137/15M1027930) to determine the cells of an arrangement in the space of hyperplanes having a point in common. Measured in CPU time on the considered test-problems, the mean acceleration ratios of the proposed algorithms, with respect to the one of Rada and ˇCerný, are in the range 15..31, and this speed-up can exceed 100, depending on the problem, the approach and the chosen linear optimization and matroid solvers.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Jean-Pierre DussaultORCiD, Jean Charles GilbertORCiD, Baptiste Plaquevent-JourdainORCiD
DOI:https://doi.org/10.1007/s12532-024-00266-8
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2025
Volume:17
Issue:1
Page Number:52
First Page:1
Last Page:52
Mathematical Programming Computation :MPC 2025 - Issue 1
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.