20.500.12556/RUL-165205 Sufficient matrices properties, generating and testing This paper investigates various aspects of sufficient matrices, one of the most relevant matrix classes introduced in connection with linear complementarity problems. We summarize the most important theoretical results and properties related to sufficient matrices. Based on these, we propose different construction rules that can be used to generate new matrices that belong to this class. A nonnegative number can be assigned to each sufficient matrix, which is called its handicap and works as a measure of sufficiency. The handicap plays a crucial role in proving convergence and complexity results for interior point algorithms for linear complementarity problems. For a particular sufficient matrix, called Csizmadia’s matrix, we give the exact value of the handicap, which is exponential in the size of the matrix. Another important topic that we address is deciding whether a matrix is sufficient. Tseng proved in 2000 that this decision problem is co-NP hard. We investigate three different algorithms for determining the sufficiency of a given matrix: Väliaho’s algorithm, a linear programming-based algorithm, and an algorithm that facilitates nonlinear programming reformulations of the definition of sufficiency. We tested the efficiency of these methods on our recently launched benchmark data set that consists of four different sets of matrices. In this paper, we give the description and most important properties of the benchmark set, which can be used in the future to compare the performance of different interior point algorithms for linear complementarity problems. linear algebra optimization theory sufficient matrices P∗(κ)-matrices linear complementarity problem linearna algebra teorija optimizacije zadostne matrike P∗(κ)-matrike problem linearne komplementarnosti true false true Angleški jezik Slovenski jezik Članek v reviji 2024-11-27 07:31:11 2024-11-27 07:31:13 2024-11-28 04:02:40 0000-00-00 00:00:00 2024 0 0 Str. 204-236 Vol. 202 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 512.643 0022-3239 10.1007/s10957-023-02280-7 183125251 E-Nagy_..._Sufficient_Matrices_-_Properties,_Generating_and_Testing.pdf E-Nagy_..._Sufficient_Matrices_-_Properties,_Generating_and_Testing.pdf 1 0F136E28054DC73DE32C92D0BA14E5C9 5e15815e456a3bcba7c9b4daa6a792fdc02d1874f70d9442b1727ed187044575 7825fbe4-ac89-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=196236 https://link.springer.com/article/10.1007/s10957-023-02280-7 1 ca8c73f5-ac88-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=196235 Fakulteta za strojništvo 0 0 0