Optimization Online


An Adaptive Self-Regular Proximity Based Large-Update IPM for LO

Maziar Salahi (msalahi***at***optlab.cas.mcmaster.ca)
Tama's Terlaky (terlaky***at***mcmaster.ca)

Abstract: Primal-Dual Interior-Point Methods (IPMs) have shown their power in solving large classes of optimization problems. However, there is still a gap between the practical behavior of these algorithms and their theoretical worst-case complexity results with respect to the update strategies of the duality gap parameter in the algorithm. The so-called small-update IPMs enjoy the best known theoretical worst-case iteration bound but their performance in computational practice is poor, while the so-called large-update IPMs have superior practical performance but with relatively weaker theoretical results. This gap was reduced by Peng, Roos, and Terlaky \cite{Pengbook} who introduced a new family of Self-Regular (SR) proximity functions based IPMs. In this paper, by restricting us to linear optimization, we propose an adaptive single step large-update IPM for a class of SR-proximities. At each step our algorithm chooses the target value adaptively and the update is a large update. The new algorithm does not do any inner iterations, unlike other large update methods. An $\O\br{qn^{\frac{q+1}{2q}}\log{\frac{n}{\e}}}$ worst-case iteration bound of the algorithm is established, where $q$ is the barrier degree of the SR-proximity. For a special choice of $q$ the best complexity for large-update IPMs is established.

Keywords: Linear Optimization, Primal-Dual Interior-Point Method, Self-Regular Proximity Function, Polynomial Complexity

Category 1: Linear, Cone and Semidefinite Programming

Citation: AdvOl-Report#2003/4(Advanced Optimization Lab, Department of Computing and Software McMaster University): Submitted to Math. Programming.

Download: [Postscript][PDF]

Entry Submitted: 11/28/2003
Entry Accepted: 11/28/2003
Entry Last Modified: 11/28/2003

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