MEGHÍVÓ

           Szeretettel meghívjuk Illés Tibor előadására

              az Optimalizálási Szeminárium keretében

            2018.11.22-én csütörtökön, 14:15-15:45 óráig

                 Helyszín: BME H épület 306 terem

Predictor-corrector interior-point algorithms for sufficient linear complementarity problems

Tibor Illés - Department of Differential Equations, Budapest University of Technology Budapest, Hungary

Abstract. The algebraic equivalent transformation (AET) of the system which defines the central path has been introduced by Darvay (2003) for linear programming problem resulting new search directions for interior point algorithms (IPA). Generalization of AET for some types of IPAs for sufficient linear complementarity problems (SU-LCP) can cause difficulties, especially for predictor-corrector (PC) ones. After overcoming these difficulties, we introduce new PC-IPAs for SU-LCPs. Moreover, we present a unified discussion of the effect of different AETs on proposing and analysing new IPAs for SU-LCPs.

These new PC IPAs from complexity analysis point of view possess similar properties like IPAs with the best know complexity, namely have polynomial iteration complexity in κ, the dimension n and the bit length L of the problem.

There are several known results (Fukuda and Terlaky, 1992; Hertog et al. 1993; Valiaho, 1996; Fukuda et al. 1998; P. Tseng 2000; de Klerk and Eisenberg-Nagy 2011) that discuss properties of the sufficient matrices and explain why it is difficult to generate, recognize (decide) and use these matrices. Furthermore, some algorithms (Csizmadia and Illés, 2006; Illés et al. 2000, 2007, 2009, 2010; Csizmadia et al. 2013, etc.) have been developed that do not need apriori information about the matrix properties. These algorithms could be applied either to solve the LCPs or its dual efficiently or give a polynomial size certificate that the matrix is not sufficient.

Recently, Illés and Morapitiye (2018) have introduced, some new ways of generating sufficient matrices making possible, for the first time, to test the computational performance of IPAs on sufficient LCPs, with positive κ parameter. Our, new PC IPAs have been tested on a well-known, triangular, P-matrix designed by Zs. Csizmadia (2011) with κ that is at least exponentially large in the dimension n of the problem. Computational performance of a variant of our, new PC IPA has not been affected by this fact, namely the number of iterations for this particular algorithm is not exponential in the dimension n.  Unfortunately, two other variants of the new PC IPAs do show exponential iteration performance.