- A Dynamic Large-Update Primal-Dual Interior-Point Method for Linear Optimization Jiming Peng (pengjmcmaster.ca) Tamas Terlaky (terlakymcmaster.ca) Abstract: 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. Keywords: Linear Optimization, Primal-Dual Interior-Point Method, Proximity Function, Polynomial Complexity, Self-Regular Function. Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Linear, Cone and Semidefinite Programming Citation: AdvOl-Report No. 2001/7, Department of Computing and Softwatre, McMaster University, Hamilton, ON, Canada Download: [Postscript][PDF]Entry Submitted: 12/10/2001Entry Accepted: 12/11/2001Entry Last Modified: 12/10/2001Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.