On sufficient properties of sufficient matrices

Povh, Janez (avtor), Žerovnik, Janez (avtor)

In this paper we study sufficient matrices, which play an important role in theoretical analysis of interior-point methods for linear complementarity problems. We present new characterisations of these matrices which imply new necessary and sufficient conditions for sufficiency. We use these results to develop an algorithm with exponential iteration complexity which in each iteration solves a simple instance of linear programming problem and is capable to reveal whether given symmetric matrix is sufficient or not. This algorithm demonstrates 100 % accuracy on all tested instances of matrices.

• Jezik: Angleški jezik
• Ključne besede: linear complementarity problem, sufficient matrix, linear programming
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FS - Fakulteta za strojništvo
• Status publikacije: Objavljeno
• Različica publikacije: Recenzirani rokopis
• Leto izida: 2021
• Št. strani: Str. 809-822
• Številčenje: Vol. 29
• PID: 20.500.12556/RUL-134491
• UDK: 512.643:519.852
• ISSN pri članku: 1613-9178
• DOI: 10.1007/s10100-021-00747-4
• COBISS.SI-ID: 64416003
• Datum objave v RUL: 18.01.2022

Gradivo je del revije

• Naslov: Central European journal of operations research
• Skrajšan naslov: Cent. Eur. j. oper. res.
• Založnik: Springer Nature, Österreichische Gesellschaft für Operations Research, Croatian Operational Research Society, Czech Society for Operations Research, Hungarian Operations Research Society, Slovak Society for Operations Research, Slovenian Association Informatika, Section for Operational Research
• ISSN: 1613-9178
• COBISS.SI-ID: 513642521

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: linearna komplementarnost, zadostne matrike, linearno programiranje