Optimization Online


A Dynamic Large-Update Primal-Dual Interior-Point Method for Linear Optimization

Jiming Peng (pengj***at***mcmaster.ca)
Tamas Terlaky (terlaky***at***mcmaster.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/2001
Entry Accepted: 12/11/2001
Entry Last Modified: 12/10/2001

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society