COMPLEXITY ANALYSIS OF INTERIOR-POINT METHODS FOR LINEAR OPTIMIZATION BASED ON A NEW KERNEL FUNCTION WITH A TRIGONOMETRIC BARRIER TERM
SAMIR BOUALI *
Department of Mathematics and Informatics, University Ibn Tofail, Faculty of Sciences, B.P. 133 Kenitra 14000, Morocco.
*Author to whom correspondence should be addressed.
Abstract
In this paper, we present a new barrier function for primal-dual interior-point methods in linear optimization. This kernel function has a trigonometric barrier term. It is proved that the algorithm based on this new kernel function has O (n34log nϵ) iteration complexity for a large-update methods, for a small-update the algorithm has O(√n log nϵ), which coincide with the best known iteration bound for linear optimization.
Keywords: Linear optimization, primal-dual interior-point method, kernel function, polynomial complexity