Report
On the B-differential of the componentwise minimum of two affine vector functions - The full report ; Sur le B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles - Le rapport complet
| العنوان: | On the B-differential of the componentwise minimum of two affine vector functions - The full report ; Sur le B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles - Le rapport complet |
|---|---|
| المؤلفون: | Dussault, Jean-Pierre, Gilbert, Jean Charles, Plaquevent-Jourdain, Baptiste |
| المساهمون: | Université de Sherbrooke, Département d'Informatique, Inria de Paris, Institut National de Recherche en Informatique et en Automatique (Inria), Université de Sherbrooke, Département de Mathématiques, Inria de Paris, France & Université de Sherbrooke, Canada |
| المصدر: | https://hal.science/hal-03872711 ; Inria de Paris, France & Université de Sherbrooke, Canada. 2023. |
| بيانات النشر: | HAL CCSD |
| سنة النشر: | 2023 |
| المجموعة: | Archive ouverte HAL (Hyper Article en Ligne, CCSD - Centre pour la Communication Scientifique Directe) |
| مصطلحات موضوعية: | B-differential, Bipartition of a finite set, C-differential, Complementarity problem, Complexity, Componentwise minimum of functions, Connectivity, Hyperplane arrangement, Pointed cone, Strict linear inequalities, Symmetry, Winder's formula, Dual approach, Gordan's alternative, Matroid circuit, Stem vector, B-différentiel, Bipartition d'un ensemble fini, C-différentiel, Complexité, Cône pointu, Connexité, Formule de Winder, Inégalités linéaires strictes, Minimum par composante de fonctions, Problème de complémentarité, Symétrie, Alternative de Gordan, Approche duale, Arrangement d'hyperplans |
| الوصف: | 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 completeness, its connectivity, bounds on its cardinal, 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 present first an incremental-recursive approach avoiding to solve any optimization subproblem, which 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 Černý in 2018 for determining 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 Černý, are in the range 7.15, and this speed-up can exceed 30, depending on the problem and the approach. ; Cet article se concentre sur la description et le calcul du B-différentiel du minimum par composante de deux fonctions affines à valeurs vectorielles. Ce problème se pose dans la reformulation du problème de complémentarité linéaire avec la C-fonction Min. Cette question a de nombreuses formulations équivalentes et nous en citons quelques-unes en algèbre linéaire, en analyse convexe et en géométrie discrète. Ces formulations sont utilisées pour établir certaines propriétés du B-différentiel, comme sa symétrie, une condition assurant sa complétude, sa connectivité, des bornes sur son cardinal, etc. L'ensemble à décrire comporte un nombre fini ... |
| نوع الوثيقة: | report |
| اللغة: | English |
| Relation: | hal-03872711; https://hal.science/hal-03872711; https://hal.science/hal-03872711v2/document; https://hal.science/hal-03872711v2/file/dussault-gilbert-plaqueventjourdain-2023-03-27.pdf |
| الاتاحة: | https://hal.science/hal-03872711 https://hal.science/hal-03872711v2/document https://hal.science/hal-03872711v2/file/dussault-gilbert-plaqueventjourdain-2023-03-27.pdf |
| Rights: | http://creativecommons.org/licenses/by-nd/ ; info:eu-repo/semantics/OpenAccess |
| رقم الانضمام: | edsbas.DD7C3BDC |
| قاعدة البيانات: | BASE |
| الوصف غير متاح. |