Abstract
It is known that predictor-corrector methods in a large neighborhood of the central path are among the most efficient interior-point methods (IPMs) for linear optimization (LO) problems. The best iteration bound based on the classical logarithmic barrier function is O(nlog (n/∊)). In this paper, we propose a family of self-regular proximity-based predictor-corrector (SRPC) IPMs for LO in a large neighborhood of the central path. In the predictor step, we use either an affine scaling or a self-regular direction; in the corrector step, we use always a self-regular direction. Our new algorithms use a special proximity function with different search directions and thus allows us to improve the so far best theoretical iteration complexity for a family of SRPC IPMs. An O \((\sqrt{n}{\exp} ((1 - q + {\log} n)/2) {\log} n {\log} (n/\epsilon))\) worst-case iteration bound with quadratic convergence is established, where q is the barrier degree of the SR proximity function.
Similar content being viewed by others
References
KARMARKAR, N.K., A New Polynomial-Time Algorithm for Linear Programming, Combinatorica, Vol. 4, pp. 373–395, 1984.
ROOS, C., TERLAKY, T., and VIAL, J.P., Theory and Algorithms for Linear Optimization: An Interior-Point Approach, John Wiley and Sons, Chichester, UK, 1997.
WRIGHT, S.J., Primal-Dual Interior-Point Methods, SIAM, Philadelphia, Pennsylvania, 1997.
MIZUNO, S., TODD, M.J., and YE, Y., On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming, Mathematics of Operations Research, Vol. 18, pp. 964–981, 1993.
JI, J., POTRA, F.A., and HUANG, S., A Predictor-Corrector Method for Linear Complementarity Problems with Polynomial Complexity and Superlinear Convergence, Journal of Optimization Theory and Applications, Vol. 84, pp. 187–199, 1995.
YE, Y., and ANSTREICHER, K.M., On Quadratic and O(\(\sqrt{n}\) L) Convergence of a Predictor-Corrector Algorithm for LCP, Mathematical Programming, Vol. 62, pp. 537–551, 1993.
ANSTREICHER, K.M., and BOSCH, R.A., A New Infinity-Norm Path-Following Algorithm for Linear Programming, SIAM Journal on Optimization, Vol. 5, pp. 236–246, 1995.
GONZAGA, C.C., Complexity of Predictor-Corrector Algorithms for LCP Based on a Large Neighborhood of the Central Path, SIAM Journal on Optimization, Vol. 10, pp. 183–194, 1999.
POTRA, F.A., A Superlinearly Convergent Predictor-Corrector Method for Degenerate LCP in a Wide Neighborhood of the Central Path, Mathematical Programming, Vol. 100, pp. 317–337, 2004.
POTRA, F.A., and LIU, X. Predictor-Corrector Methods for Sufficient Linear Complementarity Problems in a Wide Neighborhood of the Central Path, Optimization Methods and Software, Vol. 20, pp. 145–168, 2005.
HUNG, P., and YE, Y., An Asymptotically O(\(\sqrt{n}\) L)-Iteration Path-Following Linear Programming Algorithm That Uses Long Steps, SIAM Journal on Optimization, Vol. 6, pp. 570–586, 1996.
MEHROTRA, S., On the Implementation of a (Primal-Dual) Interior-Point Method, SIAM Journal on Optimization, Vol. 2, pp. 575–601, 1992.
PENG, J., ROOS, C., and TERLAKY, T., Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Methods, Princeton University Press, Princeton, New Jeresy, 2002.
SALAHI, M., and TERLAKY, T., An Adaptive Self-Regular Proximity-Based Large-Update Interior-Point Method for Linear Optimization, Optimization Methods and Software, Vol. 20, pp. 169–185, 2005.
PENG, J., TERLAKY, T., and ZHAO, Y.B., A Predictor-Corrector Algorithm for Linear Optimization Based on a Specific Self-Regular Proximity Function, SIAM Journal on Optimization, Vol. 15, pp. 1105–1127, 2005.
MEGIDDO, N., Pathways to the Optimal Set in Linear Programming, Progress in Mathematical Programming: Interior Point and Related Methods, Edited by N. Megiddo, Springer Verlag, New York, NY, pp. 131–158, 1989.
SONNEVEND, G., An Analytic Center for Polyhedrons and New Classes of Global Algorithms for Linear (Smooth, Convex) Programming, System Modeling and Optimization: Proceedings of the 12th IFIP Conference, Edited by A. Prékopa, J. Szelezsán, and B. Strazicky, Budapest, Hungary, pp. 866–876, 1985.
SALAHI, M., and TERLAKY, T., Adaptive Large-Neighborhood Self-Regular Predictor-Corrector Interior - Point Methods for Linear Optimization, OptimizationMethods and Software, Vol. 20(1), pp. 168–195, 2005.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by F.A. Potra
This researchwas supported by aMITACS project, an NSERC discovery grant, and the CRC program. The first, author thanks the Iranian Ministry of Science, Research, and Technology for supporting his research. The authors are grateful to F.A. Potra for constructive comments on an earlier draft of this paper. Finally, we are grateful to the referees for the valuable comments.
Rights and permissions
About this article
Cite this article
Salahi, M., Terlaky, T. Adaptive Large-Neighborhood Self-Regular Predictor-Corrector Interior-Point Methods for Linear Optimization. J Optim Theory Appl 132, 143–160 (2007). https://doi.org/10.1007/s10957-006-9095-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-006-9095-7