On sufficient properties of sufficient matrices

Janez Povh (Avtor), Janez Žerovnik (Avtor)

Povzetek

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.

Ključne besede

linearna komplementarnost;zadostne matrike;linearno programiranje;linear complementarity problem;sufficient matrix;linear programming;

Podatki

Jezik:	Angleški jezik
Leto izida:	2021
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UL FS - Fakulteta za strojništvo
UDK:	512.643:519.852
COBISS:	64416003
ISSN:	1613-9178
Št. ogledov:	150
Št. prenosov:	60
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarne ključne besede:	linearna komplementarnost;zadostne matrike;linearno programiranje;
Vrsta dela (COBISS):	Članek v reviji
Konec prepovedi (OpenAIRE):	2022-05-07
Strani:	str. 809-822
Zvezek:	ǂVol. ǂ29
Čas izdaje:	2021
DOI:	10.1007/s10100-021-00747-4
ID:	14306008