  


An Adaptive SelfRegular Proximity Based LargeUpdate IPM for LO
Maziar Salahi (msalahioptlab.cas.mcmaster.ca) Abstract: PrimalDual InteriorPoint 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 worstcase complexity results with respect to the update strategies of the duality gap parameter in the algorithm. The socalled smallupdate IPMs enjoy the best known theoretical worstcase iteration bound but their performance in computational practice is poor, while the socalled largeupdate 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 SelfRegular (SR) proximity functions based IPMs. In this paper, by restricting us to linear optimization, we propose an adaptive single step largeupdate IPM for a class of SRproximities. 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}}}$ worstcase iteration bound of the algorithm is established, where $q$ is the barrier degree of the SRproximity. For a special choice of $q$ the best complexity for largeupdate IPMs is established. Keywords: Linear Optimization, PrimalDual InteriorPoint Method, SelfRegular Proximity Function, Polynomial Complexity Category 1: Linear, Cone and Semidefinite Programming Citation: AdvOlReport#2003/4(Advanced Optimization Lab, Department of Computing and Software McMaster University): Submitted to Math. Programming. Download: [Postscript][PDF] Entry Submitted: 11/28/2003 Modify/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  