A Second-order Corrector Infeasible Interior-point Method with One-norm wide Neighborhood for Symmetric Optimization

• Autorzy: Kheirfam Behrouz

Identyfikatory

DOI

10.3233/FI-2020-1908

• Języki publikacji: EN

Abstrakty

EN

In this article, we present a second-order corrector infeasible interior-point method based on one-norm large neighborhood for symmetric optimization. We consider the classical Newton direction as the sum of two other directions associated with the negative and positive parts of the right-hand side of the centrality equation. In addition to equipping them with different step lengths, we add a corrector step that is multiplied by the square of the step length in the expression of the new iterate. The convergence analysis of the algorithm is discussed and it is proved that the new algorithm has the same complexity as small neighborhood infeasible interior-point algorithms for the Nesterov-Todd (NT) direction, and the xs and sx directions.

Słowa kluczowe

EN

Euclidean Jordan algebra; infeasible interior-point methods; polynomial complexity; symmetric optimization

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 172, nr 4
• Strony: 343--359
• Opis fizyczny: Bibliogr. 25 poz., tab.

Twórcy

autor

Kheirfam Behrouz

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

Bibliografia

• [1] Karmarkar N. A new polynomial-time algorithm for linear programming. Combinatorica, 1984. 4(4):373-395. doi:10.1007/BF02579150.
• [2] Nesterov Y, Todd M. Self-scaled barriers and interior-point methods for convex programming. Mathematics of Operations Research, 1997. 22(1):1-42.
• [3] Faybusovich L. Linear systems in Jordan algebras and primal-dual interior-point algorithms. Journal of Computational and Applied Mathematics, 1997. 86(1):149-175. doi:10.1016/S0377-0427(97)00153-2.
• [4] Güler O. Barrier functions in interior-point methods. Mathematics of Operations Research, 1996. 21(4):860-885. doi:10.1287/moor.21.4.860.
• [5] Schmieta SH, Alizadeh F. Extension of primal-dual interior-point algorithms to symmetric cones. Mathematical Programming, 2003. 96(3):409-438. doi:10.1007/s10107-003-0380-z.
• [6] Darvay Z. New interior point algorithms in linear programming. Advanced Modeling and Optimization, 51-92. 5(1):2003.
• [7] Wang G, Bai Y. A new primal-dual path-following interior-point algorithm for semidefinite optimization. Journal of Mathematical Analysis and Applications, 339-349. 353(1):2009. doi:10.1016/j.jmaa.2008.12.016.
• [8] Wang G, Bai Y. A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov-Todd step. Applied Mathematics and Computation, 2009. 215(3):1047-1061. doi:10.1016/j.amc.2009.06.034.
• [9] Wang G, Bai Y. A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. Journal of Optimization Theory and Applications, 966-985. 154(3):2012. doi:10.1007/s10957-012-0013-x.
• [10] Kheirfam B. A new infeasible interior-point method based on Darvay’s technique for symmetric optimization. Annals of Operations Research, 2013. 211(1):209-224. doi:10.1007/s10479-013-1474-5.
• [11] Rangarajan BK. Polynomial convergence of infeasible interior-point methods over symmetric cones. SIAM Journal on Optimization, 2006. 16(4):1211-1229. doi:10.1137/040606557.
• [12] 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.
• [13] 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.
• [14] 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.
• [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] 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.
• [17] Kheirfam B, Mohamadi-Sangachin M. A wide neighborhood second-order predictor-corrector interior-point algorithm for semidefinite optimization with modified corrector directions. Fundamenta Informaticae, 2017. 153(4):327-346. doi:10.3233/FI-2017-1543.
• [18] 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.
• [19] 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.
• [20] 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.
• [21] Liu C, Wu D, Shang Y. A new infeasible-interior-point algorithm based on wide neighborhoods for symmetric cone programming. Journal of the Operations Research Society of China, 2016. 4(2):147-165. doi:10.1007/s40305-016-0118-2.
• [22] Yang X, Zhang Y, Liu H, Shen P. A new second-order infeasible primal-dual path-following algorithm for symmetric optimization. Numerical Functional Analysis and Optimization, 2016. 37(4):499-519. doi:10.1080/01630563.2016.1138127.
• [23] Faraut J, Kornyi A. Analysis on symmetric cones. Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York, Oxford Science Publications. ISBN 0198534779, 9780198534778.
• [24] Wang G, Tao J, Kong L. A note on an inequality involving Jordan product in Euclidean Jordan algebras. Optimization Letters, 2016. 10(4):731-736. doi:10.1007/s11590-015-0926-z.
• [25] Liu C, Liu H, Shang Y. Neighborhood-following algorithms for symmetric cone programming (in Chinese). Sci. Sin. Math., 2013. 43:691-702.

Uwagi

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