An interior-point algorithm for linear optimization based on a new barrier function

作者：Cho Gyeong Mi^*

来源：Applied Mathematics and Computation, 2011, 218(2): 386-395.

DOI：10.1016/j.amc.2011.05.075

• Primal-dual interior point method
• Kernel function
• Complexity
• Polynomial algorithm
• Linear optimization

Primal-dual interior-point methods (IPMs) are the most efficient methods for a computational point of view. At present the theoretical iteration bound for small-update IPMs is better than the one for large-update IPMs. However, in practice, large-update IPMs are much more efficient than small-update IPMs. Peng et al. [14,15] proposed new variants of IPMs based on self-regular barrier functions and proved so far the best known complexity, e. g. O(root n log n log n/epsilon), for large-update IPMs with some specific self-regular barrier functions. Recently, Roos et al. [2-9] proposed new primal-dual IPMs based on various barrier functions to improve the iteration bound for large-update methods from O(n log n/epsilon) to O(root n log n log n/epsilon). Motivated by their works we define a new barrier function and propose a new primal-dual interior point algorithm based on this function for linear optimization (LO) problems. We show that the new algorithm has O(root n log n log n/epsilon) iteration bound for large-update and O(root n log n/epsilon) for small-update methods which are currently the best known bounds, respectively.

• 出版日期2011-9-15