Professor Goran Lesaja (Georgia Southern University) is a guest of the Corvinus Center for Operation Research (CCOR) this semester. As part of his visit, he will present a minicourse titled Kernel-based Interior-point Methods for Linear Complementarity Problems and Generalizations.
Venue: Corvinus University, Building C
November 27. (Monday) 9:50-11:20 (Room C208)
November 27. (Monday) 13:40-15:10 (Room CVII)
November 28. (Tuesday) 9:50-11:20 (Room C108)
We would like to inform you that the lectures will be broadcast online. Please be aware that this broadcast will not utilize professional-grade equipment, and we appreciate your understanding that we cannot ensure the broadcast’s quality.
If you would like to join online, please send an e-mail to anita dot varga at uni-corvinus dot hu by November 27, 8:00.
The class of Linear Complementarity Problems (LCPs) is an important class of problems closely related to many optimization problems. The KKT optimality conditions of important optimization problems such as Linear and Quadratic Optimization problems can be formulated as LCPs. Furthermore, a number of problems in engineering and other areas of science and technology can be directly formulated as LCPs. Thus, efficient algorithms for solving LCP are of the interest for theoretical and practical purposes.
At the beginning of the mini-course, the idea of the feasible Interior-Point Methods (IPM) for LCPs based on the kernel functions will be introduced and the properties of kernel functions will be discussed. Next, the class of eligible kernel functions will be presented and its connection to the class of self-regular kernel functions and the class of algebraic equivalent transformation will be briefly discussed.
In the sequel, the IPMs based on the entire class of eligible kernel functions will be analyzed and it will be shown that this class of methods globally converges and iteration bounds to obtain epsilon-approximate solution match best known iteration bounds for these types of methods. In particular, one of the main achievements of the kernel-based IPMs is the improved complexity of long-step methods.
In the last part of the mini-course, generalizations of these methods to LCPs over symmetric cones will be considered. Recently, a surprising connection has been shown: The algebraic structure of Euclidean Jordan Algebras (EJAs) and associated symmetric cones are connected to important optimization problems and can serve as a unifying frame to analyze IPMs for semi definite optimization problems, second order cone optimization problems, and classical optimization problems over nonnegative orthant. Using tools of EJA and symmetric cones it is shown that generalizations of the kernel based IPMs for LCP over symmetric cones still possess the best known complexity achieved for the LCPs over nonnegative orthant.