On Implementing Self-Regular Proximity Based Feasible IPMs

Xiaohang Zhu (zhux2mcmaster.ca)
Jiming Peng (pengjcas.mcmaster.ca)
Tamás Terlaky (terlakymcmaster.ca)
Guoqing Zhang (gzhanguwindsor.ca)

Abstract: Self-regular based interior point methods present a unified novel approach for solving linear optimization and conic optimization problems. So far it was not known if the new Self-Regular IPMs can lead to similar advances in computational practice as shown in the theoretical analysis. In this paper, we present our experiences in developing the software package McIPM that uses the dynamic version of SR IPMs based on the homogeneous self-dual embedding model. After a brief review of the underlying algorithm, various issues with respect to implementation are addressed. Numerical stability and sparsity of the normal equation system are explored as well. Extensive testing shows that the McIPM package is competitive with other leading academic packages and that the Self-Regular proximity based approach allows to improve the performance of interior point method software when solving difficult linear optimization problems, and offers avenues for further improvements.

Keywords: Linear optimization, interior point methods, self-regular

Category 1: Linear, Cone and Semidefinite Programming (Linear Programming )

Category 2: Optimization Software and Modeling Systems (Optimization Software Benchmark )

Citation: AdvOl-Report#2004/3, McMaster University, Advanced Optimization Laboratory, 1280 Main St. W., ITB, Hamilton, ON L8S 4L7 April, 2004

Download: [Postscript][PDF]

Entry Submitted: 04/07/2004
Entry Accepted: 04/07/2004
Entry Last Modified: 04/08/2004

Modify/Update this entry