Article ID: | iaor20033307 |
Country: | United Kingdom |
Volume: | 17 |
Issue: | 6 |
Start Page Number: | 985 |
End Page Number: | 1008 |
Publication Date: | Dec 2002 |
Journal: | Optimization Methods & Software |
Authors: | Roos Cornelis, Bai Y.Q., Ghami M. El |
Keywords: | interior point methods |
In this article we present a generic primal–dual interior-point algorithm for linear optimization in which the search direction depends on a univariate kernel function which is also used as proximity measure in the analysis of the algorithm. We present some powerful tools for the analysis of the algorithm under the assumption that the kernel function satisfies three easy to check and mild conditions (i.e., exponential convexity, superconvexity and monotonicity of the second derivative). The approach is demonstrated by introducing a new kernel function and showing that the corresponding large-update algorithm improves the iteration complexity with a factor n1/4 when compared with the classical method, which is based on the use of the logarithmic barrier function.