Sufficient matrices : properties, generating and testing

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

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.

• Language: English
• Keywords: linear algebra, optimization theory, sufficient matrices, P∗(κ)-matrices, linear complementarity problem
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering
• Publication status: Published
• Publication version: Version of Record
• Year: 2024
• Number of pages: Str. 204-236
• Numbering: Vol. 202
• PID: 20.500.12556/RUL-165205
• UDC: 512.643
• ISSN on article: 0022-3239
• DOI: 10.1007/s10957-023-02280-7
• COBISS.SI-ID: 183125251
• Publication date in RUL: 27.11.2024

Record is a part of a journal

• Title: Journal of optimization theory and applications
• Shortened title: J. optim. theory appl.
• Publisher: Plenum Pub. Corp.
• ISSN: 0022-3239
• COBISS.SI-ID: 25773824

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: linearna algebra, teorija optimizacije, zadostne matrike, P∗(κ)-matrike, problem linearne komplementarnosti

Projects

• Funder: Other - Other funder or multiple funders
• Funding programme: Corvinus University of Budapest