-
Feasible corrector-predictor interior-point algorithm for P* (k)-linear complementarity problems based on a new search directionDarvay, Zsolt ...We introduce a new feasible corrector-predictor (CP) interior-point algorithm (IPA), which is suitable for solving linear complementarity problem (LCP) with P*(k)-matrices. We use the method of ... algebraically equivalent transformation (AET) of the nonlinear equation of the system which defines the central path. The AET is based on the function [varphi](t) = t - [sqrt]t and plays a crucial role in the calculation of the new search direction. We prove that the algorithm has O((1 + 2k) [sqrt]n log 9n[micro]0/8[epsilon]) iteration complexity, where k is an upper bound of the handicap of the input matrix. To the best of our knowledge, this is the first CP IPA for P*(k)-LCPs which is based on this search direction. We implement the proposed CP IPA in the C++ programming language with specific parameters and demonstrate its performance on three families of LCPs. The first family consists of LCPs with P*(k)-matrices. The second family of LCPs has the P-matrix defined by Csizmadia. Eisenberg-Nagy and de Klerk [Math. Program., 129 (2011), pp. 383-402] showed that the handicap of this matrix should be at least 2[sup]2n-8 - 1/4 . Namely, from the known complexity results for P*(k)-LCPs it might follow that the computational performance of IPAs on LCPs with the matrix defined by Csizmadia could be very poor. Our preliminary computational study shows that an implemented variant of the theoretical version of the CP IPA (Algorithm 4.1) presented in this paper, finds a [epsilon]-approximate solution for LCPs with the Csizmadia matrix in a very small number of iterations. The third family of problems consists of the LCPs related to the copositivity test of 88 matrices from [C. Brás, G. Eichfelder, and J. Júdice, Comput. Optim. Appl., 63 (2016), pp. 461-493]. For each of these matrices we create a special LCP and try to solve it using our IPA. If the LCP does not have a solution, then the related matrix is strictly copositive, otherwise it is on the boundary or outside the copositive cone. For these LCPs we do not know whether the underlying matrix is P*(k) or not, but we could reveal the real copositivity status of the input matrices in 83 out of 88 cases (accuracy _> 94%). The numerical test shows that our CP IPA performs well on the sets of test problems used in the paper.Source: SIAM journal on optimization. - ISSN 1052-6234 (Vol. 30, iss. 3, 2020, str. 2628-2658)Type of material - article, component partPublish date - 2020Language - englishCOBISS.SI-ID - 31245059
Author
Darvay, Zsolt |
Illés, Tibor |
Povh, Janez, 1973- |
Rigó, Petra Renáta
Topics
corrector-predictor interior-point algorithm |
P*(k)-linear complementarity problem |
new search direction |
polynomial iteration complexity |
copositivity test |
korekcijsko napovedovalne metode notranjih točk |
P*(k)-problem linearne komplementarnosti |
nova iskalna smer |
polinomska časovna zahtevnost |
test kopozitivnosti
Shelf entry
Permalink
- URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year | Impact factor | Edition | Category | Classification | ||||
---|---|---|---|---|---|---|---|---|
JCR | SNIP | JCR | SNIP | JCR | SNIP | JCR | SNIP |
Select the library membership card:
DRS, in which the journal is indexed
Database name | Field | Year |
---|
Links to authors' personal bibliographies | Links to information on researchers in the SICRIS system |
---|---|
Darvay, Zsolt | |
Illés, Tibor | |
Povh, Janez, 1973- | 22649 |
Rigó, Petra Renáta |
Select pickup location:
Material pickup by post
Notification
Subject headings in COBISS General List of Subject Headings
Select pickup location
Pickup location | Material status | Reservation |
---|
Please wait a moment.