×

zbMATH — the first resource for mathematics

New complexity analysis of a full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization. (English) Zbl 1320.90105
Summary: 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.

MSC:
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: Link
References:
[1] Faraut, J., Korányi, A.: Analysis on Symmetric Cones. Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York 1994. · Zbl 0841.43002
[2] Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86 (1997), 149-175. · Zbl 0889.65066
[3] Faybusovich, L.: A Jordan-algebraic approach to potential-reduction algorithms. Math. Z. 239 (2002), 1, 117-129. · Zbl 0996.65065
[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. · Zbl 1245.90144
[5] Güler, O.: Barrier functions in interior-point methods. Math. Oper. Res. 21 (1996), 4, 860-885. · Zbl 0867.90090
[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. · Zbl 0994.90095
[7] Nesterov, Y. E., Nemirovski, A.: Interior-point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia 1994. · Zbl 0824.90112
[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. · Zbl 0871.90064
[9] Rangarajan, B. K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16 (2006), 4, 1211-1229. · Zbl 1131.90043
[10] Roos, C.: A full-Newton step \(O(n)\) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136. · Zbl 1131.90029
[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. · Zbl 0954.65041
[12] Schmieta, S. H., Alizadeh, F.: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96 (2003), 3, 409-438. · Zbl 1023.90083
[13] Sturm, J. F.: Similarity and other spectral relations for symmetric cones. Algebra Appl. 312 (2000), 1 - 3, 135-154. · Zbl 0973.90093
[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.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.