Primal-dual interior-point methods (IPMs) have shown their power in solving large classes of optimization problems. However, at present there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results, with respect to the strategies of updating the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy the best known theoretical worst-case iteration bound but work very poorly in practice, while the so-called large-update IPMs perform much better in practice but with relatively weaker theoretical results. In this paper, by restricting us to linear optimization (LO), we first exploit some interesting properties of a proximity measure function that has a key role in defining the neighborhood of the central path. These simple but important features of the proximity measure function indicate that, when the current iterate is in a large neighborhood of the central path, then the large-update IPM emerges to be the only natural choice. Then, we apply these results to a specific self-regularity based IPM proposed recently by the authors of this work and C. Roos. Among others, we show that this self-regularity based IPM can also predict precisely the change of the duality gap as the standard IPM does. Therefore, we can directly apply the modified IPM to the simplified self-dual homogeneous model for LO. This provides a remedy for an implementation issue of the proposed IPMs. A dynamic large-update IPM in large neighborhood is proposed. Different from the usual large update IPMs, the new dynamic IPM always takes large-update and does not utilize any inner iteration to get centered. An $\O\br{n^{\frac23}\log{\frac{n}{\e}}}$ iteration bound of the algorithm is established.
Citation
AdvOl-Report No. 2001/7, Department of Computing and Softwatre, McMaster University, Hamilton, ON, Canada
Article
View A Dynamic Large-Update Primal-Dual Interior-Point Method for Linear Optimization