Primal-dual Interior-point Algorithm for Conic Optimization Based on Kernel Functions

Two important classes of polynomial-time interior-point method (IPMs) are small- and large-update methods, respectively. The theoretical complexity bound for large-update methods is a factor sqrtn worse than the bound for small-update methods, where n denotes the number of (linear) inequalities in the problem. In practice the situation is opposite: implemen- tations of largeupdate methods are much more efficient than those of small-update methods. This so-called irony of IPMs motivated the present work. Conic Optimization (CO) provides a new framework in the field of Optimization that includes linear optimization (LO), semidefinite optimization (SDO) and second-order cone optimization (SOCO) problems as special cases. This presentation focuses on the design of efficient primal-dual interior-point algorithm for special cases ( (LO) (SDO) and (SOCO) ) problems based on kernel functions. After briefly introducing the main concepts of this special conic optimization, the presentation turns to study the kernel function which covers a wide range of kernel functions, including the classical logarithmic barrier function, the prototype self-regular functions and also non self-regular functions. We generalize also the analysis for a class of linear complementarity problems. The iteration complexity obtained for SDO SOCO and Linear complementarity problems are the same as the best bound for primal-dual interior point methods in LO.