Complexity analysis of primal-dual interior-point methods for linear optimization based on a new parametric kernel function with a trigonometric barrier term (Q1724788)

Summary: We introduce a new parametric kernel function, which is a combination of the classic kernel function and a trigonometric barrier term, and present various properties of this new kernel function. A class of large- and small-update primal-dual interior-point methods for linear optimization based on this parametric kernel function is proposed. By utilizing the feature of the parametric kernel function, we derive the iteration bounds for large-update methods, \(O(n^{2 / 3} \log(n / \varepsilon))\), and small-update methods, \(O(\sqrt{n} \log(n / \varepsilon))\). These results match the currently best known iteration bounds for large- and small-update methods based on the trigonometric kernel functions.