A New Predictor-corrector Infeasible Interior-point Algorithm for Linear Optimization in a Wide Neighborhood

• Autorzy: Kheirfam Behrouz

Identyfikatory

DOI

10.3233/FI-2020-1983

• Języki publikacji: EN

Abstrakty

EN

In this paper, we propose a Mizuno-Todd-Ye type predictor-corrector infeasible interior-point method for linear optimization based on a wide neighborhood of the central path. According to Ai-Zhang’s original idea, we use two directions of distinct and orthogonal corresponding to the negative and positive parts of the right side vector of the centering equation of the central path. In the predictor stage, the step size along the corresponded infeasible directions to the negative part is chosen. In the corrector stage by modifying the positive directions system a full-Newton step is removed. We show that, in addition to the predictor step, our method reduces the duality gap in the corrector step and this can be a prominent feature of our method. We prove that the iteration complexity of the new algorithm is 𝒪 (n log ɛ ⁻¹ ), which coincides with the best known complexity result for infeasible interior-point methods, where ɛ > 0 is the required precision. Due to the positive direction new system, we improve the theoretical complexity bound for this kind of infeasible interior-point method [1] by a factor of √n . Numerical results are also provided to demonstrate the performance of the proposed algorithm.

Słowa kluczowe

EN

predictor-corrector methods; interior-point method; wide neighborhood; polynomial complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 177, nr 2
• Strony: 141--156
• Opis fizyczny: Bibliogr. 39 poz., tab.

Twórcy

autor

Kheirfam Behrouz

• Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I.R. Iran

Bibliografia

• [1] Liu C, Shang Y, Han P. A new infeasible-interior-point algorithm for linear programming over symmetric cones. Acta Mathematicae Applicatae Sinica, English Series, 2017. 33(3):771-788. doi:10.1007/s10255-017-0697-7.
• [2] Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984. 4(4):373-395. doi:10.1007/BF02579150.
• [3] Megiddo N. Pathways to the optimal set in linear programming, In N. Megiddo, editor, Progress in Mathematical Programming, Interior-Point and Related Methods. Springer-Verlag New Yor, 1989. ISBN 978-1-4613-9619-2.
• [4] Sonnevend G. An “Analytic Center” for Polyhedrons and New Classes of Global Algorithms for Linear (Smooth, Convex) Programming, In A. Prékopa and J. Szelezsán and B. Strazicky editor, System Modelling and Optimization: Proceedings of the 12th IFIP-Conference held in Budapest, Hungary, September 1985, Lecture Notes in Control and Information Sciences, 84. Springer, Berlin, Heidelberg, 1986. ISBN 978-3-540-16854-6. doi:org/10.1007/BFb0043914.
• [5] Kojima M, Mizuno S, Yoshise A. A Primal-Dual Interior Point Algorithm for Linear Programming. In: Megiddo N. (eds) Progress in Mathematical Programming. Springer, New York, NY., 1989. ISBN 978-1-4613-9619-2. doi:org/10.1007/978-1-4613-9617-8_2.
• [6] McShane K, Monma C, Shanno D. An implementation of a primal-dual interior point method for linear programming. ORSA Journal on Computing, 1989. 1(2):70-83. doi:org/10.1287/ijoc.1.2.70.
• [7] Lustig I, Marsten R, Shanno D. Computational experience with a primal-dual interior point method for linear programming. Linear Algebra and its Applications, 1991. 152:191-222. doi:10.1016/0024-3795(91)90275-2.
• [8] Kojima M, Mizuno S, Yoshise A. A polynomial-time algorithm for a class of linear complementarity problems. Mathematical Programming, 1989. 44(1-3):1-26. doi:10.1007/BF01587074.
• [9] Monteiro RDC, Adler I. Interior path-following primal-dual algorithms. Part I: Linear programming. Mathematical Programming, 1989. 44:27-41. doi:org/10.1007/BF01587075.
• [10] Monteiro RDC, Adler I. Interior path-following primal-dual algorithms. Part II: Convex quadratic programming. Mathematical Programming, 1989. 44:43-66. doi:org/10.1007/BF01587076.
• [11] Wright SJ. Primal-Dual Interior-Point Methods. SIAM, Philadelphia, USA, 1997. ISBN 1611971454, 9781611971453.
• [12] Mizuno S, Todd MJ, Ye Y. On adaptive step primalual interior-point algorithms for linear programming. Mathematics of Operations Research, 1993. 18(4):964-981. doi:10.1287/moor.18.4.964.
• [13] Mehrotra S. On the implementation of a primal-dual interior point method. SIAM Journal on Optimization, 1992. 2(4):575-601. doi:10.1137/0802028.
• [14] Ai W, Zhang S. An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM Journal on Optimization, 2005. 16(2):400-417. doi:10.1137/040604492.
• [15] Potra FA. Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM Journal on Optimization, 2014. 24(1):1-28. doi:10.1137/120884341.
• [16] Li Y, Terlaky T. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with O(√n log tr(X0S0)ε ) iteration complexity. SIAM Journal on Optimization, 2010. 20(6):2853-2875. doi:10.1137/080729311.
• [17] Feng Z, Fang L. A new O(√nL)-iteration predictor-corrector algorithm with wide neighborhood for semidefinite programming. Journal of Computational and Applied Mathematics, 2014. 256:65-76. doi:10.1016/j.cam.2013.07.011.
• [18] Feng Z. A new O(√nL) iteration large update primal-dual interior-point method for second-order cone programming. Numerical Functional Analysis and Optimization, 2012. 33(4):397-414. doi:10.1080/01630563.2011.652269.
• [19] Kheirfam B, Chitsaz M. Polynomial convergence of two higher order interior-point methods for P*(k)-LCP in a wide neighborhood of the central path. Periodica Mathematica Hungarica, 2018. 76(2):243-264. doi:10.1007/s10998-017-0231-y.
• [20] Kheirfam B, Haghighi M. A full-Newton step infeasible interior-point method for linear optimization based on a trigonometric kernel function. Optimization, 2016. 65(4):841-857. doi:10.1080/02331934.2015.1080255.
• [21] Ma X, Liu H, Zhou C. A predictor-corrector algorithm for monotone linear complementarity problems in a wide neighborhood. International Journal of Bifurcation and Chaos, 2015. 25(14):1540035. doi: 10.1142/S0218127415400350.
• [22] Kojim M, Megiddo N, Mizuno S. A primal-dual infeasible-interior-point algorithm for linear programming. Mathematical Programming, 1993. 61(1-3):263-280. doi:10.1007/BF01582151.
• [23] Potra FA. On a predictor-corrector method for solving linear programming from infeasible starting points. Reprots on computational mathematics 34, Department of Mathematics. The University of Iowa City, IA 52242, USA, 1992.
• [24] Zhang Y. On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem. SIAM Journal on Optimization, 1994. 4(1):208-227. doi:org/10.1137/0804012.
• [25] Roos C. An improved and simplified full-Newton step O(n) infeasible interior-point method for linear optimization. SIAM Journal on Optimization, 2015. 25(1):102-114. doi:org/10.1137/140975462.
• [26] Kheirfam B. An infeasible full-NT step interior point algorithm for CQSCO. Numerical Algorithms, 2017. 74(1):93-109. doi:10.1007/s11075-016-0140-9.
• [27] Kheirfam B, Mahdavi-Amiri N. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem. Bulletin of the Iranian Mathematical Society, 2014. 40(3):541-564.
• [28] Kheirfam B. A predictor-corrector infeasible-interior-point algorithm for semidefinite optimization in a wide neighborhood. Fundamenta Informaticae, 2017. 152(1):33-50. doi:10.3233/FI-2017-1511.
• [29] Liu H, Yang X, Liu C. A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. Journal of Optimization Theory and Applications, 2013. 158(3):796-815. doi:10.1007/s10957-013-0303-y.
• [30] Yang X, Liu H, Liu C. A Mehrotra-type predictor-corrector infeasible-interior-point method with a new one-norm neighborhood for symmetric optimization. Journal of Computational and Applied Mathematics, 2015. 283:106-121. doi:10.1016/j.cam.2015.01.027.
• [31] Yang X, Zhang Y, Liu H, Pei Y. A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones. Numerical Algorithms, 2016. 72(4):915-936. doi:org/10.1007/s11075-015-0074-7.
• [32]Yang X, Zhang Y, Liu H, Pei Y. A Mizuno-Todd-Ye predictor-corrector infeasible-interior-point method for linear programming over symmetric cones. Numerical Algorithms, 2016. 72(4):915–936. doi:org/10. 1007/s11075-015-0074-7.
• [33] Kheirfam B. An arc-search interior point method in the N¯∞ neighborhood for symmetric optimization. Fundamenta Informaticae, 2016. 146(3):255-269. doi:10.3233/FI-2016-1385.
• [34] Kheirfam B. A second-order corrector infeasible interior-point method with one-norm wide neighborhood for symmetric optimization. Fundamenta Informaticae, 2020. 172(4):343-359. doi:10.3233/FI-2020-1908.
• [35] Ye Y, Todd MJ, Mizuno S. An O(√nL)-iteration homogeneous and self-dual linear programming algorithm. Mathematics of Operations Research, 1994. 19(1):53-67. doi:org/10.1287/moor.19.1.53.
• [36] Roos C, Terlaky T, Vial JP. Interior Point Methods for Linear Optimization. Springer Science, Heidelberg/Boston, 2006.
• [37] Zhang Y, Zhang D. On polynomiality of the Mehrotra-type predictor-corrector interior-point algorithms. Mathematical Programming, 1995. 68:303-318. doi:org/10.1007/BF01585769.
• [38] Yang X, Zhang Y, Liu H. A wide neighborhood infeasible-interior-point method with arc-search for linear programming. Journal of Applied Mathematics and Computing, 2016. 51(1-2):209-225. doi:org/10.1007/s12190-015-0900-z.
• [39] Browne S, Dongarra J, Grosse E, Rowan T. The netlib mathematical software repository. Corporation for National Research Initiatives, 1995.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).