The Corvinus Centre for Operations Research (CCOR), the Corvinus Institute for Advanced Studies (CIAS), and the Institute of Operations and Decision Sciences invite you to the minicourse by Goran Lesaja (Corvinus University of Budapest)
Kernel-based Interior-Point Methods for Linear Complementarity Problems.
Venue: Corvinus University, Building C
Date:
February 25 (Tuesday) 9:50-11:20 (Room C554)
February 25 (Tuesday) 11:40-13:10 (Room C554)
February 27 (Thursday) 9:50-11:20 (Room C314)
Abstract
The class of Linear Complementarity Problems (LCPs) is an important class of problems closely related to many optimization problems. Thus, efficient algorithms for solving LCPs are of an interest for theoretical and practical purposes.
Interior-Point Methods (IPMs) have revolutionized the field of Optimization in the past several decades and have offered new, efficient methods to solve many important and difficult optimization problems, including LCPs.
The idea of using kernel functions in the design and analysis of the IPMs is quite powerful and rich. In kernel-based IPMs kernel function is used to determine search direction, proximity measure, step-size, and other important elements of the method, which are then used to prove the global convergence of the method and to calculate the iteration bounds of the method.
This approach was developed as an effort to improve the iteration bounds of long-step IPMs which in practice work much better than short-step IPMs but have worse theoretical iteration bounds. This phenomenon is known as “Irony of IPMs”, the term coined by J. Renegar.
In the first part of the Minicourse, we introduce different classes of LCPs and discuss generalization of classical IPM that leads to kernel-based IPMs. We define a wide class of kernel functions called Eligible Kernel Functions (EKFs) and provide the convergence and complexity analysis of IPMs based on the entire class of EKFs.
In the second part of the Minicourse, we consider a subclass of EKFs that we call Standard Kernel Functions (SKFs). The name comes from the fact that this subclass contains most of the EKFs which appear in the literature (with exception of EKFs with trigonometric barrier term). For this class we further develop complexity analysis of the related kernel-based IPMs for the entire class of SKFs and, in the process, develop the scheme that significantly simplifies the calculation of the iteration bounds. In all specific instances we matched the iteration bounds derived previously both for short- and long-step IPMs.
In the third part of the Minicourse, we consider different classes of kernel-functions and their connections to EKFs. We mention self-regular kernel function (SRKFs) and finite kernel functions (FKFs). We also introduce IPMs based on Algebraic Equivalent Transformation technique (AET), which was proposed by Darvay in 2005, and discuss the connection between AET functions and EKFs.
We conclude the Minicourse by discussing some open problems and directions for further research.