Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function

doi:10.1016/j.amc.2005.09.079

Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function

2006-05-01

3

PRE

AI

DOI：10.1016/j.amc.2005.09.079

Original

Original request for help

Save

Abstract

En 中文

Interior point methods have shown their powers in solving linear optimization problems and large classes of other optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst case complexity. The so-called large update interior point methods perform in practice much better than the small update methods which have the best known theoretical complexity. Recently, this gap has been reduced by Peng, Roos and Terlaky by introducing new self regular kernel functions. In this paper, by focusing on linear optimization problem and motivated by the self regular family of kernel functions, we impose some mild condition on the kernel functions and we give a new class of kernel functions. We also give a simple complexity analysis for large-update interior point methods based on the kernel functions in this new class. Finally, we apply our analysis to two family of kernel functions in our new class. We also explore the complexity of the algorithm and we show that the so far worst case O(root n log n log n/is an element of) iteration bound can be achieved in special case. (c) 2005 Elsevier Inc. All rights reserved.

Keywords:

linear optimization

primal-dual interior point method

kernel function

proximity function

large update method

polynomial complexity

Complexity analysis of interior-point methods for linear optimization based on some conditions on kernel function

Abstract

Journal

Organization