Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a new type of kernel functions

Abstract

Kernel functions are essential for designing and analyzing interior-point methods (IPMs). They are used to determine search directions and reduce the computational complexity of the interior point method. Currently, IPM based on kernel functions is one of the most effective methods for solving LO [1,20], second-order cone optimization (SOCO) [2], and symmetric optimization (SO) and is a very active research area in mathematicalprogramming. This paper presents a large-update primal-dual IPM for SDO based on a new bi-parameterized hyperbolic kernel function. Then we proved that the proposed large-update IPM has the same complexity bound as the best-known IPMs for solving these problems. Taking advantage of the favorable characteristics of the kernel function, we can deduce that the iteration bound for the large update method is $\mathcal{O}\left( \sqrt{n}\log n\log\dfrac{n}{\varepsilon }\right) $ when a takes a special value utilizing the favorable properties of the kernel function. These theoretical results play an essential role in the design and analysis of IPMs for CQSCO [7] and the Cartesian$\ P_{\ast }\left( \kappa \right) $-SCLCP [8]. The proximity function has never been used. In order to validate the efficacy of our algorithm and verify the effectiveness of our algorithm, examples aregiven to illustrate the applicability of our main results, and we compare our numerical results with some alternatives presented in the literature.