An Improved and Simplified Full-Newton Step O(n) Infeasible Interior-Point Method for Linear Optimization

Journal article (2015)

Authors

Department
Software Computer Technology (EEMCS) (TU Delft)
Copyright: © 2015 Society for Industrial and Applied Mathematics
More Info
expand_more

Published Date

08-01-2015

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

SIAM Journal on Optimization, 25 (1), 2015

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Computer Technology

Abstract

We present an improved version of an infeasible interior-point method for linear optimization published in 2006. In the earlier version each iteration consisted of one so-called feasibility step and a few---at most three---centering steps. In this paper each iteration consists of only a feasibility step, whereas the iteration bound improves the earlier bound by a factor $2\sqrt{2}$. The improvements are due to a new lemma that gives a much tighter upper bound for the proximity after the feasibility step.

Files

Roos_2015.pdf
(pdf | 0.181 Mb)