Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T18:56:41.129Z Has data issue: false hasContentIssue false

An interior point method for linear programming based on a class of Kernel functions

Published online by Cambridge University Press:  17 April 2009

K. Amini
Affiliation:
Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran, e-mail: amini@mehr.sharif.edu, peyghami@mehr.sharif.edu
M. R. Peyghami
Affiliation:
Department of Mathematical Sciences, Sharif University of Technology, Tehran, Iran, e-mail: amini@mehr.sharif.edu, peyghami@mehr.sharif.edu
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Interior point methods are not only the most effective methods for solving optimisation problems in practice but they also have polynomial time complexity. However, there is still a gap between the practical behavior of the interior point method algorithms and their theoretical complexity results. In this paper, by focusing on linear programming problems, we introduce a new family of kernel functions that have some simple and easy to check properties. We present a simplified analysis to obtain the complexity of generic interior point methods based on the proximity functions induced by these kernel functions. Finally, we prove that this family of kernel functions leads to improved iteration bounds of the large-update interior point methods.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 2005