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

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

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

Keywords


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



DOI: http://dx.doi.org/10.21914/anziamj.v51i0.1724



Remember, for most actions you have to record/upload into this online system
and then inform the editor/author via clicking on an email icon or Completion button.
ANZIAM Journal, ISSN 1446-8735, copyright Australian Mathematical Society.