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

Maziar Salahi (msalahioptlab.cas.mcmaster.ca)
Tama's Terlaky (terlakymcmaster.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