Geodesic
New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization
Kybernetika, Tome 49 (2013) no. 6, pp. 883-896 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

A full Nesterov-Todd step infeasible interior-point algorithm is proposed for solving linear programming problems over symmetric cones by using the Euclidean Jordan algebra. Using a new approach, we also provide a search direction and show that the iteration bound coincides with the best known bound for infeasible interior-point methods.
A full Nesterov-Todd step infeasible interior-point algorithm is proposed for solving linear programming problems over symmetric cones by using the Euclidean Jordan algebra. Using a new approach, we also provide a search direction and show that the iteration bound coincides with the best known bound for infeasible interior-point methods.
Classification : 17C50, 90C25, 90C51
Keywords: interior-point methods; symmetric cone optimization; Euclidean Jordan algebra; polynomial complexity 
@article{KYB_2013_49_6_a3,
     author = {Kheirfam, Behrouz and Mahdavi-Amiri, Nezam},
     title = {New complexity analysis of a full {Nesterov-} {Todd} step infeasible interior-point algorithm for symmetric optimization},
     journal = {Kybernetika},
     pages = {883--896},
     year = {2013},
     volume = {49},
     number = {6},
     mrnumber = {3182646},
     zbl = {06285133},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a3/}
}
TY  - JOUR
AU  - Kheirfam, Behrouz
AU  - Mahdavi-Amiri, Nezam
TI  - New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization
JO  - Kybernetika
PY  - 2013
SP  - 883
EP  - 896
VL  - 49
IS  - 6
UR  - http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a3/
LA  - en
ID  - KYB_2013_49_6_a3
ER  - 
%0 Journal Article
%A Kheirfam, Behrouz
%A Mahdavi-Amiri, Nezam
%T New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization
%J Kybernetika
%D 2013
%P 883-896
%V 49
%N 6
%U http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a3/
%G en
%F KYB_2013_49_6_a3
Kheirfam, Behrouz; Mahdavi-Amiri, Nezam. New complexity analysis of a full Nesterov- Todd step infeasible interior-point algorithm for symmetric optimization. Kybernetika, Tome 49 (2013) no. 6, pp. 883-896. http://geodesic.mathdoc.fr/item/KYB_2013_49_6_a3/

[1] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York 1994. | MR | Zbl

[2] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86 (1997), 149-175. | DOI | MR | Zbl

[3] Faybusovich, L.: A Jordan-algebraic approach to potential-reduction algorithms. Math. Z. 239 (2002), 1, 117-129. | DOI | MR | Zbl

[4] Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. European J. Oper. Res. 214 (2011), 3, 473-484. | DOI | MR | Zbl

[5] Güler, O.: Barrier functions in interior-point methods. Math. Oper. Res. 21 (1996), 4, 860-885. | DOI | MR | Zbl

[6] Muramatsu, M.: On a commutative class of search directions for linear programming over symmetric cones. J. Optim. Theory Appl. 112 (2002), 3, 595-625. | DOI | MR | Zbl

[7] Nesterov, Y. E., Nemirovski, A.: Interior-point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia 1994. | MR

[8] Nesterov, Y. E., Todd, M. J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22 (1997), 1, 1-42. | DOI | MR | Zbl

[9] Rangarajan, B. K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16 (2006), 4, 1211-1229. | DOI | MR | Zbl

[10] Roos, C.: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136. | DOI | MR | Zbl

[11] Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization: An Interior-Point Approach. John Wiley and Sons, Chichester 1997, Second edition Springer 2006. | MR | Zbl

[12] Schmieta, S. H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96 (2003), 3, 409-438. | DOI | MR

[13] Sturm, J. F.: Similarity and other spectral relations for symmetric cones. Algebra Appl. 312 (2000), 1 - 3, 135-154. | DOI | MR | Zbl

[14] Vieira, M. V. C.: Jordan Algebraic Approach to Symmetric Optimization. Ph.D. Thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology 2007.