- 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/2003Entry Accepted: 11/28/2003Entry Last Modified: 11/28/2003Modify/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.