Kybernetika 49 no. 6, 883-896, 2013

New complexity analysis of a full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization

Behrouz Kheirfam and Nezam Mahdavi-Amiri

Abstract:

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.

Keywords:

interior-point methods, polynomial complexity, Euclidean Jordan algebra, symmetric cone optimization

Classification:

90C51

paper.pdf

References:

  1. J. Faraut and A. Korányi: Analysis on Symmetric Cones. Oxford Mathematical Monographs, The Clarendon Press Oxford University Press, New York 1994.   CrossRef
  2. L. Faybusovich: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86 (1997), 149-175.   CrossRef
  3. L. Faybusovich: A Jordan-algebraic approach to potential-reduction algorithms. Math. Z. 239 (2002), 1, 117-129.   CrossRef
  4. G. Gu, M. Zangiabadi and C. Roos: Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. European J. Oper. Res. 214 (2011), 3, 473-484.   CrossRef
  5. O. G${\rm \ddot{u}}$ler: Barrier functions in interior-point methods. Math. Oper. Res. 21 (1996), 4, 860-885.   CrossRef
  6. M. Muramatsu: On a commutative class of search directions for linear programming over symmetric cones. J. Optim. Theory Appl. 112 (2002), 3, 595-625.   CrossRef
  7. Y. E. Nesterov and A. Nemirovski: Interior-point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia 1994.   CrossRef
  8. Y. E. Nesterov and M. J. Todd: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22 (1997), 1, 1-42.   CrossRef
  9. B. K. Rangarajan: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16 (2006), 4, 1211-1229.   CrossRef
  10. C. Roos: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136.   CrossRef
  11. C. Roos, T. Terlaky and J.-Ph. Vial: Theory and Algorithms for Linear Optimization: An Interior-Point Approach. John Wiley and Sons, Chichester 1997, Second edition Springer 2006.   CrossRef
  12. S. H. Schmieta and F. Alizadeh: Extension of primal-dual interior-point algorithm to symmetric cones. Math. Program. 96 (2003), 3, 409-438.   CrossRef
  13. J. F. Sturm: Similarity and other spectral relations for symmetric cones. Algebra Appl. 312 (2000), 1 - 3, 135-154.   CrossRef
  14. M. V. C. Vieira: Jordan Algebraic Approach to Symmetric Optimization. Ph.D. Thesis, Electrical Engineering, Mathematics and Computer Science, Delft University of Technology 2007.   CrossRef