Sufficient matrices : properties, generating and testing

Nagy, Marianna E.- (avtor), Illés, Tibor (avtor), Povh, Janez (avtor), Varga, Anita (avtor), Žerovnik, Janez (avtor)

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.

• Jezik: Angleški jezik
• Ključne besede: linear algebra, optimization theory, sufficient matrices, P∗(κ)-matrices, linear complementarity problem
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FS - Fakulteta za strojništvo
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2024
• Št. strani: Str. 204-236
• Številčenje: Vol. 202
• PID: 20.500.12556/RUL-165205
• UDK: 512.643
• ISSN pri članku: 0022-3239
• DOI: 10.1007/s10957-023-02280-7
• COBISS.SI-ID: 183125251
• Datum objave v RUL: 27.11.2024

Gradivo je del revije

• Naslov: Journal of optimization theory and applications
• Skrajšan naslov: J. optim. theory appl.
• Založnik: Plenum Pub. Corp.
• ISSN: 0022-3239
• COBISS.SI-ID: 25773824

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: linearna algebra, teorija optimizacije, zadostne matrike, P∗(κ)-matrike, problem linearne komplementarnosti

Projekti

• Financer: Drugi - Drug financer ali več financerjev
• Program financ.: Corvinus University of Budapest