Dynamic large-update primal–dual interior-point method for linear optimization

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 have superior practical performance but with relatively weaker theoretical results. In this article, by restricting us to linear optimization (LO), we first exploit some interesting properties of a self-regular proximity function, proposed recently by the authors of this work and Roos, and use it to define a neighborhood of the central path. These simple but interesting properties of the proximitiy 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 design a specific self-regularity based IPM. Among others, we show 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 new self-regular IPMs. A dynamic large-update IPM in large neighborhood is proposed. Different from traditional large-update IPMs, the new dynamic IPM always takes large-updates and does not utilize any inner iteration to get centered. An O(n^2/3loge(n/ϵ)) worst-case iteration bound of the algorithm is established.