A new wide neighborhood primal-dual second-order corrector algorithm for linear optimization
Tóm tắt
We propose a new large-step primal-dual second-order corrector interior-point method for linear optimization. At each iteration, our method uses the new wide neighborhood introduced by Darvay and Takács (Cent Eur J Oper Res 26(3):551–563, 2018.
https://doi.org/10.1007/s10100-018-0524-0
). In this paper we would like to improve the directions proposed by Darvay and Takács by adding a second-order corrector direction. The corrector step is multiplied by the square of the step length in the expression of the new iterate. To our best knowledge, this is the first primal-dual second-order corrector interior-point algorithm based on Darvay–Takács’s new wide neighborhood, which has the same complexity as the best short-step algorithms for linear optimization. Finally, numerical experiments show that the proposed algorithm is efficient and reliable.
Tài liệu tham khảo
Ai, W., Zhang, S.: An \(O(\sqrt{n}L)\) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SIAM J. Optim. 16(2), 400–417 (2005)
Darvay, Zs: New interior point algorithms in linear programming. Adv. Model. Optim. 5(1), 51–92 (2003)
Darvay, Zs, Takács, P.R.: Large-step interior-point algorithm for linear optimization based on a new wide neighborhood. Cent. Eur. J. Oper. Res. 26(3), 551–563 (2018). https://doi.org/10.1007/s10100-018-0524-0
De Klerk, E.: Aspects of Semidefinite Programming. Applied Optimization, vol. 65. Kluwer Academic, Dordrecht (2002)
Feng, Z.: A new \(\cal{O}(\sqrt{n}L)\) iteration large-update primal-dual interior-point method for second-order cone programming. Numer. Funct. Anal. Optim. 33(4), 397–414 (2012)
Gay, D.: Electronic mail distribution of linear programming test problems. COAL Newslett. 13, 10–12 (1985)
Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 375–395 (1984)
Kheirfam, B.: A predictor–corrector infeasible-interior-point algorithm for semidefinite optimization in a wide neighborhood. Fundam. Inform. 152(1), 33–50 (2017)
Kheirfam, B., Chitsaz, M.: Corrector–predictor arc-search interior-point algorithm for \(P_*(\kappa )\)-LCP acting in a wide neighborhood of the central path. Iran. J. Oper. Res. 6(2), 1–18 (2015)
Kheirfam, B., Chitsaz, M.: A new second-order corrector interior-point algorithm for \(P_*(\kappa )\)-LCP. Filomat 31(20), 6379–6391 (2017)
Kheirfam, B., Mohamadi-Sangachin, M.: A wide neighborhood second-order predictor–corrector interior-point algorithm for semidefinite optimization with modified corrector directions. Fundam. Inform. 153(4), 327–346 (2017)
Kojima, M., Megiddo, N., Noma, T., Yoshise, A.: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Lecture Notes in Computer Science, vol. 538. Springer, Berlin (1991)
Li, Y., Terlaky, T.: A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with \(O\left(\sqrt{n}\log \left(\frac{{\rm Tr}(X^0S^0)}{\epsilon }\right)\right)\) iteration complexity. SIAM J. Optim. 8, 2853–2875 (2010)
Liu, C., Liu, H.W., Cong, W.: An \(O(\sqrt{n}L)\) iteration primal-dual second-order corrector algorithm for linear programming. Optim. Lett. 5, 729–743 (2011)
Liu, C., Liu, H.: A new second-order corrector interior-point algorithm for semidefinite programming. Math. Methods Oper. Res. 75, 165–183 (2012)
Nesterov, Y.E., Nemirovskii, A.S.: Interior Point Polynomial Methods in Convex Programming: Theory and Algorithms. SIAM Studies in Applied Mathematics, vol. 13. SIAM Publications, Philadelphia (1994)
Peng, J., Roos, C., Terlaky, T.: Self-regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton (2002)
Potra, F.A.: Interior point methods for sufficient horizontal LCP in a wide neighborhood of the central path with best known iteration complexity. SIAM J. Optim. 24(1), 1–28 (2014)
Potra, F.A.: A superlinearly convergent predictor–corrector method for degenerate LCP in a wide neighborhood of the central path with \(\cal{O}(\sqrt{n}L)\)-iteration complexity. Math. Program. 100, 317–337 (2004)
Roos, C., Terlaky, T., Vial, J-Ph: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, Chichester (1997)
Sonnevend, Gy.: An ”analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: Prékopa, A., Szelezsán, J., Strazicky, B. (eds.), System Modelling and Optimization: Proceedings of the 12th IFIP-Conference held in Budapest, Hungary, September 1985. Lecture Notes in Control and Information Sciences, vol. 84, pp. 866-876. Springer, Berlin (1986)
Terlaky, T.: An easy way to teach interior-point methods. Eur. J. Oper. Res. 130(1), 1–19 (2001)
Wolkowicz, H., Saigal, R., Vandenberghe, L.: Handbook of Semidefinite Programming, Theory, Algorithm, and Applications. Kluwer Academic Publishers, Dordrecht (2000)
Wright, S.J.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997)
Ye, Y.: Interior Point Algorithms, Theory and Analysis. Wiley, Chichester (1997)
Ye, Y., Todd, M., Mizuno, S.: An \(O(\sqrt{n}L)\)-iteration homogeneous and self-dual linear programming algorithm. Math. Oper. Res. 19, 53–67 (1994)