zbMATH — the first resource for mathematics

Infeasible interior-point methods for linear optimization based on large neighborhood. (English) Zbl 1346.90567
Summary: In this paper, we design a class of infeasible interior-point methods for linear optimization based on large neighborhood. The algorithm is inspired by a full-Newton step infeasible algorithm with a linear convergence rate in problem dimension that was recently proposed by the second author. Unfortunately, despite its good numerical behavior, the theoretical convergence rate of our algorithm is worse up to square root of problem dimension.

90C05 Linear programming
90C51 Interior-point methods
Full Text: DOI
[1] Megiddo, N. (ed.): Pathways to the optimal set in linear programming. In: Progress in Mathematical Programming (Pacific Grove, CA, 1987), pp. 131-158. Springer, New York (1989) · Zbl 1131.90029
[2] Anstreicher, KM, A combined phase I-phase II projective algorithm for linear programming, Math. Progr., 43, 209-223, (1989) · Zbl 0662.90048
[3] Mizuno, S, Polynomiality of infeasible-interior-point algorithms for linear programming, Math. Progr., 67, 109-119, (1994) · Zbl 0828.90086
[4] Roos, C, A full-Newton step \(O(n)\) infeasible interior-point algorithm for linear optimization, SIAM J. Optim., 16, 1110-1136, (2006) · Zbl 1131.90029
[5] Bai, Y; Ghami, M; Roos, C, A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization, SIAM J. Optim., 15, 101-128, (2004) · Zbl 1077.90038
[6] Peng, J., Roos, C., Terlaky, T.: Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2002) · Zbl 1136.90045
[7] Salahi, M; Peyghami, MR; Terlaky, T, New complexity analysis of IIPMs for linear optimization based on a specific self-regular function, Eur. J. Oper. Res., 186, 466-485, (2008) · Zbl 1175.90291
[8] Potra, FA; Stoer, J, On a class of superlinearly convergent polynomial-time interior-point methods for sufficient LCP, SIAM J. Optim., 20, 1333-1363, (2009) · Zbl 1213.90245
[9] Roos, C., Terlaky, T., Vial, J.-Ph.: Interior-Point Methods for Linear Optimization. Springer, New York (2006). In: Second edition of Theory and Algorithms for Linear Optimization [Wiley, Chichester, 1997] · Zbl 0954.65041
[10] El Ghami, M.: New Primal-Dual Interior-Point Methods Based on Kernel Functions. Ph.D. thesis, Delft University of Technology, The Netherlands (2005)
[11] Peng, J; Roos, C; Terlaky, T, A new and efficient large-update interior-point method for linear optimization, Vychisl. Tekhnol., 6, 61-80, (2001) · Zbl 0987.90089
[12] Potra, FA, A superlinearly convergent predictor-corrector method for degenerate LCP in a wide neighborhood of the central path with \(O(\sqrt{n}L)\)-iteration complexity, Math. Progr., 100, 317-337, (2004) · Zbl 1116.90101
[13] Ye, Y.: Interior Point Algorithms. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1997)
[14] Asadi, A; Gu, G; Roos, C, Convergence of the homotopy path for a full-Newton step infeasible interior-point method, Oper. Res. Lett., 38, 147-151, (2010) · Zbl 1185.90206
[15] Gu, G; Mansouri, H; Zangiabadi, M; Bai, Y; Roos, C, Improved full-Newton step \(O(n)\) infeasible interior-point method for linear optimization, J. Optim. Theory Appl., 145, 271-288, (2010) · Zbl 1205.90194
[16] Zhang, Y, Solving large-scale linear programs by interior-point methods under the MATLAB environment, Optim. Methods Softw., 10, 1-31, (1998) · Zbl 0916.90208
[17] Lustig, I; Marsten, RE; Shanno, DF, On implementing mehrotra’s predictor-corrector interior-point method for linear programming, SIAM J. Optim., 2, 435-449, (1992) · Zbl 0771.90066
[18] Mehrotra, S, On the implementation of a primal-dual interior-point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[19] Lustig, I.: Feasibility issues in a primal-dual interior-point method for linear programming. Math. Progr. 49(2, (Ser. A)):145-162 (1990/91) · Zbl 0828.90086
[20] Vanderbei, RJ, LOQO: an interior-point code for quadratic programming, Optim. Methods Softw., 11/12, 451-484, (1999) · Zbl 0973.90518
[21] Andersen, E.D., Andersen, K. D.: The Mosek interior-point optimizer for linear programming: an implementation of the homogeneous algorithm. In: Frenk, H., Roos, K., Terlaky, T., Zhang, S. (eds.) High Performance Optimization, vol. 33 of Appl. Optim. pp. 197-232. Kluwer Academy Publication, Dordrecht (2000) · Zbl 1028.90022
[22] Czyzyk, J; Mehrotra, S; Wagner, M; Wright, S, Pcx: an interior-point code for linear programming, Optim. Methods Softw., 11/12, 397-430, (1999) · Zbl 0970.90118
[23] Mansouri, H; Roos, C, A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization, Numer. Algorithms, 52, 225-255, (2009) · Zbl 1180.65079
[24] Gu, G; Zangiabadi, M; Roos, C, Full Nesterov-Todd step infeasible interior-point method for symmetric optimization, Eur. J. Oper. Res., 3, 473-484, (2011) · Zbl 1245.90144
[25] Mansouri, H; Zangiabadi, M; Pirhaji, M, A full-Newton step \(O(n)\) infeasible-interior-point algorithm for linear complementarity problems, Nonlinear Anal. Real World Appl., 12, 545-561, (2011) · Zbl 1229.90236
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.