A primal-dual interior-point algorithm based on a new kernel function

Authors

  • Gyeong-Mi Cho
  • Y. Y. Cho
  • Y. H. Lee

DOI:

https://doi.org/10.21914/anziamj.v51i0.1724

Keywords:

primal-dual interior-point method, kernel function, complexity, polynomial algorithm, linear optimization problem

Abstract

We propose a new primal-dual interior-point algorithm based on a new kernel function for linear optimization problems. New search directions and proximity functions are proposed based on the kernel function. We show that the new algorithm has $\mathcal{O}(\sqrt{n}\log n\log(n/\epsilon))$ and $\mathcal{O}(\sqrt{n}\log(n/\epsilon))$ iteration bounds for large-update and small-update methods, respectively, which are currently the best known bounds for such methods. doi:10.1017/S1446181110000908

Published

2011-05-03

Issue

Section

Articles for Printed Issues