Kybernetika 48 no. 5, 907-923, 2012

Full-Newton step infeasible interior-point algorithm for SDO problems

Hossein Mansouri

Abstract:

In this paper we propose a primal-dual path-following interior-point algorithm for semidefinite optimization. The algorithm constructs strictly feasible iterates for a sequence of perturbations of the given problem and its dual problem. Each main step of the algorithm consists of a feasibility step and several centering steps. At each iteration, we use only full-Newton step. Moreover, we use a more natural feasibility step, which targets at the $\mu^+$-center. The iteration bound of the algorithm coincides with the currently best iteration bound for semidefinite optimization problems.

Keywords:

polynomial complexity, semidefinite optimization, infeasible interior-point method, primal-dual method, Newton-step, optimal solutions

Classification:

90C05, 90C51

paper.pdf

References:

  1. F. Alizadeh: Interior-point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5 (2006), 13-51.   CrossRef
  2. C. Helmberg: Semidefinite Programming for Combinatorial Optimization. Technical Report 00-34, Konrad-Zuse-Zentrum f{ü}r Informationstechink Berlin 2000.   CrossRef
  3. R. A. Horn and C. R. Johnson: Topics in Matrix Analysis. Cambridge University Press, Cambridge 1991.   CrossRef
  4. E. de Klerk: Aspects of Semidefinite Programming. Kluwer Academic Publishers, Dordrecht 2002.   CrossRef
  5. M. Kojima, M. Shida and S. Shindoh: Local convergence of predictor-corrector infeasible interior-point algorithm for SDPs and SDLCPs. Math. Program. 80 (1998), 129-160.   CrossRef
  6. M. Kojima, N. Megiddo, T. Noma and A. Yoshise: A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems. Lecture Notes in Comput. Sci. 538, Springer, Berlin 1991.   CrossRef
  7. Z. Q. Luo, J. Sturm and S. Z. Zhang: Superlinear convergence of a symmetric primal-dual path following algorithm for semidefinite programming. SIAM J. Optim. 8 (1998), 59-81.   CrossRef
  8. I. J. Lustig: Feasible issues in a primal-dual interior point method for linear programming. Math. Program. 49 (1990/1991), 145-162.   CrossRef
  9. H. L{ü}tkepohl: Handbook of Matrices. John Wiley \& Sons, Chichester 1996.   CrossRef
  10. H. Mansouri: Full-Newton Step Interior-Point Methods for Conic Optimization. Ph.D. Thesis, Faculty of Mathematics and Computer Science, TU Delft, 2008.   CrossRef
  11. H. Mansouri and C. Roos: A new full-Newton step $o(n)$ infeasible interior-point algorithm for semidefinite optimization. J. Numer. Algorithms 52 (2009), 2, 225-255.   CrossRef
  12. H. Mansouri and M. Zangiabadi: New complexity analysis of full Nesterov-Todd steps for semidefinite optimization. Bull. Iranian Math. Soc. 1 (2011), 269-286.   CrossRef
  13. H. Mansouri, T. Siyavash and M. Zangiabadi: A path-following infeasible interior-point algorithm for semidefinite programming. Iranian J. Oper. Res. 3 (2012), 1, 11-30.   CrossRef
  14. 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
  15. Y. E. Nesterov and M. J. Todd: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8 (1998), 2, 324-364.   CrossRef
  16. J. Peng, C. Roos and T. Terlaky: Self-regular functions and new search directions for linear and semidefinite optimization. Math. Program. 93 (2002), 129-171.   CrossRef
  17. F. A. Potra and R. Sheng: A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Optim. 8 (1998), 1007-1028.   CrossRef
  18. C. Roos: A full-Newton step $O(n)$ infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16 (2006), 4, 1110-1136.   CrossRef
  19. 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 2005.)   CrossRef
  20. H. Wolkowicz, R. Saigal and L. Vandenberghe: Handbook of Semidefinite Programming, Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht 2000.   CrossRef
  21. Y. Zhang: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8 (1998), 365-386.   CrossRef