An Arc-search Interior Point Method in the N - ∞ Neighborhood for Symmetric Optimization

• Autorzy: Kheirfam B.

Identyfikatory

DOI

10.3233/FI-2016-1385

• Języki publikacji: EN

Abstrakty

EN

In this paper, we propose an arc-search infeasible interior point algorithm for symmetric optimization using the negative infinity neighborhood of the central path. The algorithm searches the optimizers along the ellipses that approximate the entire central path. The convergence of the algorithm is shown for the set of commutative scaling class, which includes some of the most interesting choice of scalings such as xs; sx and the Nesterov-Todd scalings.

Słowa kluczowe

EN

symmetric optimization; arc-search directions; infeasible-interior-point method; negative infinity neighborhood; polynomial complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 146, nr 3
• Strony: 255--269
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Kheirfam B.

• Department of Applied 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-393. doi:10.1007/BF02579150.
• [2] Faybusovich L. Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 1997; 86: 149-175. doi:10.1016/S0377-0427(97)00153-2.
• [3] Schmieta SH, Alizadeh F. Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. 2003; 96(3): 409-438. doi:10.1007/s10107-003-0380-z.
• [4] Rangarajan, B.K. Polynomial convergence of infeasible interior-point methods over symmetric cones. SIAM J. Optim. 2006; 16(4): 1211-1229. doi:10.1137/040606557.
• [5] Nesterov Y. Long-step strategies in interior-point primal-dual methods. Math. Program. 1996; 76: 47-94.
• [6] Hung P, Ye Y. An aymptotical O(√nL)-iteration path-following linear programming algorithm that use wide neighborhood. SIAM J. Optim. 1996; 6: 570-586. doi:10.1137/S1052623494266869.
• [7] Jansen B, Roos C, Terlaky T, Ye Y. Improved complexity using higher-order corrections for primal-dual Dikin affine scaling. Math. Program. 1996; 76: 117-130. doi:10.1007/BF02614380.
• [8] Yang Y. A polynomial arc-search interior-point algorithm for linear programming. J. Optim. Theory Appl. 2013; 158 (3): 859-873. doi:10.1007/s10957-013-0281-0.
• [9] Zhang J, Zhang K. Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming. Math. Meth. Oper. Res. 2011; 73: 75-90. doi:10.1007/s00186-010-0334-1.
• [10] Ai W, Zhang S. An O(√nL) iteration primal-dual path-following method, based on wide neighborhoods and large updates, for monotone LCP. SAIM J. Optim. 2005; 16(2): 400-417. doi:10.1137/040604492.
• [11] Liu H, Yang X, Liu C. A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. J. Optim. Theory Appl. 2013; 158 (3): 796-815. doi:10.1007/s10957-013-0303-y.
• [12] Yang X, Zhang Y, Liu H. A wide neighborhood infeasible-interior-point method with arc-search for linear programming. J. Appl. Math. Comput. 2015; doi 10.1007/s12190-015-0900-z
• [13] Faraut J, Korányi A. Analysis on Symmetric Cones. Oxford University Press, New York, USA (1994). ISBN:0198534779, 9780198534778.