Counterexample to a Conjecture on an Infeasible Interior-Point Method

In [SIAM J. Optim., 16 (2006), pp. 1110–1136], Roos proved that the devised full-step infeasible algorithm has $O(n)$ worst-case iteration complexity. This complexity bound depends linearly on a parameter $\bar{\kappa}(\zeta)$, which is proved to be less than $\sqrt{2n}$. Based on extensive computational evidence (hundreds of thousands of...

Improved Full-Newton Step O(nL) Infeasible Interior-Point Method for Linear Optimization

We present several improvements of the full-Newton step infeasible interior-point method for linear optimization introduced by Roos (SIAM J. Optim. 16(4):1110–1136, 2006). Each main step of the method consists of a feasibility step and several centering steps. We use a more natural feasibility step, which targets the ?+-center of the next pair...

Full-step interior-point methods for symmetric optimization

In [SIAM J. Optim., 16(4):1110--1136 (electronic), 2006] Roos proposed a full-Newton step Infeasible Interior-Point Method (IIPM) for Linear Optimization (LO). It is a primal-dual homotopy method; it differs from the classical IIPMs in that it uses only full steps. This means that no line searches are needed. In this thesis, we first present an...