A Full-Newton Step Interior-point Method Based on a Class of Specific Algebra Transformation

• Autorzy: Kheirfam B. , Nasrollahi A.

Identyfikatory

DOI

10.3233/FI-2018-1747

• Języki publikacji: EN

Abstrakty

EN

We present a primal-dual path-following interior-point method for linear optimization that is based on the integer powers of the square root function. Our derived search directions is a generalization of the standard directions and the search directions given by Darvay. The proposed algorithm uses only full steps and hence no need to perform line search. We first prove that the iterates lie in the quadratic convergence neighborhood of the proximity measure and then derive the iteration-complexity bound for the algorithm.

Słowa kluczowe

EN

feasible interior-point method; full-Newton step; linear optimization; polynomial complexity; small-update methods

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2018
• Tom: Vol. 163, nr 4
• Strony: 325--337
• Opis fizyczny: Bibliogr. 33 poz.

Twórcy

autor

Kheirfam B.

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

autor

Nasrollahi A.

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

Bibliografia

• [1] Achache M. A new primal-dual path-following method for convex quadratic programming, Computational and Applied Mathematics, 2006;25(1):97-110. URL http://dx.doi.org/10.1590/S0101-82052006000100005.
• [2] Ai W, Zhang S. An O(pnL) 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.
• [3] Darvay Z. New interior point algorithm in linear programming, Advanced Modeling and Optimization, 2003;5(1):51-92.
• [4] Darvay Z, Papp IM, Takács P-R. Complexity analysis of a full-Newton step interior-point method for linear optimization, Periodica Mathematica Hungarica, 2016;73(1):27-42. doi:10.1007/s10998-016-0119-2.
• [5] Karmarkar N. A new polynomial-time algorithm for linear programming, Combinatorica,1984;4(4):373-395. doi:10.1007/BF02579150.
• [6] Kheirfam B. An interior-point method for Cartesian P⸼(k)-linear complementarity problem over symmetric cones, ORiON, 2014;30(1):41-58.
• [7] Kheirfam B. A predictor-corrector interior-point algorithm for P⸼(k)-horizontal linear complementarity problem, Numerical Algorithms, 2014;66(2):349-361. doi:10.1007/s11075-013-9738-3.
• [8] Kheirfam B. A corrector-predictor path-following method for convex quadratic symmetric cone optimization, Journal of Optimization Theory and Applications, 2015;164(1):246-260. doi:10.1007/s10957-014-0554-2.
• [9] 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-2017-1511.
• [10] Kheirfam B. A corrector-predictor path-following method for second-order cone optimization, International Journal of Computer Mathematics, 2016;93(12). doi:10.1080/00207160.2015.1085028.
• [11] Kheirfam B. A full step infeasible interior-point method for Cartesian P⸼(k)-SCLCP, Optimization Letters, 2016;10(3):591-603. doi:10.1007/s11590-015-0884-5.
• [12] Kheirfam B. An improved full-Newton step O(n) infeasible interior-point method for horizontal linear complementarity problem, Numerical Algorithms, 2016;71(3):491-503. doi:10.1007/s11075-015-0005-7.
• [13] 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.
• [14] 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.
• [15] 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.
• [16] 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.
• [17] Kheirfam B, Mahdavi-Amiri N. A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem, Optimization Letters, 2014;8(3):1017-1029. doi:10.1007/s11590-013-0618-5.
• [18] Kheirfam B, Mohamadi-Sangachin M. A wide neighborhood second-order predictor-corrector interiorpoint algorithm for semidefinite optimization with modified corrector directions, Fundamenta Informaticae, 2017;153(4):327-346. doi:10.3233/FI-2017-1543.
• [19] de Klerk E. Aspects of Semidefinite Programming: Interior Point Algorithms and Selected Applications, Springer, 2002, ISBN 978-0-306-47819-2. doi:10.1007/b105286.
• [20] Kojima M, Mizuno S, Yoshise A. A primal-dual interior-point algorithm for linear programming. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior Point and Related Methods, Springer, New York, NY, 1989, ISBN 978-1-4613-9619-2. doi:10.1007/978-1-4613-9617-8_8.
• [21] Megiddo N. Pathways to the optimal set in linear programming. In: Megiddo, N. (ed.) Progress in Mathematical Programming: Interior Point and Related Methods, Springer, New York, NY, 1989, ISBN 978-1-4613-9619-2. doi:10.1007/978-1-4613-9617-8_8.
• [22] Renegar J. A polynomial-time algorithm, based on Newton’s method, for linear programming, Mathematical Programming, 1998;40(1-3):59-93. doi:10.1007/BF01580724.
• [23] Roos C. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM Journal on Optimization, 2006;16(4):1110-1136. doi:10.1137/050623917.
• [24] 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:10.1137/140975462.
• [25] Roos C, Terlaky T, Vial J-P. Interior Point Methods for Linear Optimization, Springer, US, 2005, ISBN 978-0-387-26379-3, 2nd Edition. doi:10.1007/b100325.
• [26] Sonnevend G. An ”analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: Prkopa A., Szelezsan J., Strazicky B. (eds) System Modelling and Optimization. Lecture Notes in Control and Information Sciences, Springer, Berlin, Heidelberg, 1986, ISBN 978-3-540-16854-6. doi:10.1007/BFb0043914.
• [27] Wang G. A new polynomial interior-point algorithm for the monotone linear complementarity problem over symmetric cones with full NT-steps, Asia-Pacific Journal of Operational Research, 2012;29(2):1250015. doi:10.1142/S0217595912500157.
• [28] Wang G, Bai Y. A new primal-dual path-following interior-point algorithm for semidefinite optimization, Journal of Mathematical Analysis and Applications, 2009;353(1):339-349. doi:10.1016/j.jmaa.2008.12.016.
• [29] 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.
• [30] 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, 2012;154(3):966-985. doi:10.1007/s10957-012-0013-x.
• [31] Wang G, Kong L, Tao J, Lesaja G. Improved complexity analysis of full Nesterov-Todd step feasible interior-point method for symmetric optimization, Journal of Optimization Theory and Applications, 2015;166(2):588-604. doi:10.1007/s10957-014-0696-2.
• [32] Wang G, Yu C, Teo K. A full-Newton step feasible interior-point algorithm for P⸼(k)-linear complementarity problem, Journal of Global Optimization, 2014;59(1):81-99. doi:10.1007/s10898-013-0090-x.
• [33] Wright SJ. Primal-Dual Interior-Point Methods, SIAM, Philadelphia, USA, 1997, ISBN 978-0-89871-382-4. doi:10.1137/1.9781611971453.