  


A Dynamic LargeUpdate PrimalDual InteriorPoint Method for Linear Optimization
Jiming Peng (pengjmcmaster.ca) Abstract: Primaldual interiorpoint 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 worstcase complexity results, with respect to the strategies of updating the duality gap parameter in the algorithm. The socalled smallupdate IPMs enjoy the best known theoretical worstcase iteration bound but work very poorly in practice, while the socalled largeupdate 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 largeupdate IPM emerges to be the only natural choice. Then, we apply these results to a specific selfregularity based IPM proposed recently by the authors of this work and C. Roos. Among others, we show that this selfregularity 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 selfdual homogeneous model for LO. This provides a remedy for an implementation issue of the proposed IPMs. A dynamic largeupdate IPM in large neighborhood is proposed. Different from the usual large update IPMs, the new dynamic IPM always takes largeupdate 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, PrimalDual InteriorPoint Method, Proximity Function, Polynomial Complexity, SelfRegular Function. Category 1: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 2: Linear, Cone and Semidefinite Programming Citation: AdvOlReport No. 2001/7, Department of Computing and Softwatre, McMaster University, Hamilton, ON, Canada Download: [Postscript][PDF] Entry Submitted: 12/10/2001 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  