Research ArticleOpen AccessGoogle Scholar indexed
A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function
Department of Mathematics and Informatics, Faculty of Sciences, University Ibn Tofail, Kenitra, Morocco
Department of Mathematics and Informatics, Faculty of Sciences, University Ibn Tofail, Kenitra, Morocco
- 1 Department of Mathematics and Informatics, Faculty of Sciences, University Ibn Tofail, Kenitra, Morocco
- 2 Department of Mathematics and Informatics, Faculty of Sciences, University Ibn Tofail, Kenitra, Morocco
Applied Mathematics·Volume 03 (2012)·Pages 1014–1022·Published 27 September 2012·DOI10.4236/am.2012.39150
Copy link · social · email
Abstract
In this paper, we propose a new infeasible interior-point algorithm with full NesterovTodd (NT) steps for semidefinite programming (SDP). The main iteration consists of a feasibility step and several centrality steps. We used a specific kernel function to induce the feasibility step. The analysis is more simplified. The iteration bound coincides with the currently best known bound for infeasible interior-point methods.
KeywordsSemidefinite ProgrammingFull Nesterov-Todd StepsInfeasible Interior-Point MethodsPolynomial ComplexityKernel Functions
- E. de Klerk, “Aspects of Semidefinite Programming,” Kluwer Academic Publishers, Dordrecht, 2002.
- C. Roos, “A Full-Newton Step O(n) Infeasible InteriorPoint Algorithm for Linear Optimization,” SIAM Journal on Optimization, Vol. 16, No. 4, 2006, pp. 1110-1136. doi:10.1137/050623917
- H. Wolkowicz R. Saigal and L. Vandenberghe, “Handbook of Semidefinite Programming: Theory, Algorithms and Applications,” Kluwer, Norwell, 1999.
- Y. Q. Bai M. El Ghami and C. Roos, “A Comparative Study of Kernel Functions for Primaldual Interior-Point Algorithms in Linear Optimization,” SIAM Journal on Optimization, Vol. 15, No. 1, 2004, pp. 101-128. doi:10.1137/S1052623403423114
- J. Peng C. Roos and T. Terlaky, “Self-Regular Functions and New Search Directions for Linear and Semidefinite Optimization,” Mathematical Programming, Vol. 93, No. 1, 2002, pp. 129-171.
- H. Mansouri and C. Roos, “A New Full-Newton Step O(nL) Infeasible Interior-Point Algorithm for Semidefinite Optimization,” Numerical Algorithms, Vol. 52, No. 2, 2009, pp. 225-255. doi:10.1007/s11075-009-9270-7
- W. Sun and Z. Liu, “A Full-NT-Step Infeasible InteriorPoint Algorithm for sdp Based on Kernel Functions,” Applied Mathematics and Computation, Vol. 217, No. 10, 2011, pp. 4990-4999. doi:10.1016/j.amc.2010.11.049
- G. Gu, H. Mansouri, M. Zangiabadi, Y. Q. Bai and C. Roos, “Improved Full-Newton Step O(nL) Infeasible Interior-Point Method for Linear Optimization,” Journal of Optimization Theory and Applications, Vol. 145, No. 2, 2010, pp. 271-288. doi:10.1007/s10957-009-9634-0
- J. Peng, C. Roos and T. Terlaky, “Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms,” Princeton University Press, Princeton, 2002.
- W. Sun, Z. Liu and F. Tian, “A Full-Newtonstep Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function,” Applied Mathematics and Optimization, Vol. 60, No. 2, 2009, pp. 237-251. doi:10.1007/s00245-009-9069-x
- H. Mansouri and C. Roos, “Simplified O(nL) Infeasible Interior-Point Algorithm for Linear Optimization Using Full-Newton Steps,” Optimization Methods and Software, Vol. 22, No. 3, 2007, pp. 519-530. doi:10.1080/10556780600816692
- C. Roos, T. Terlaky and J.-Ph. Vial, “Interior Point Methods for Linear Optimization,” 2nd Edition, Theory and Algorithms for Linear Optimization, Wiley, Chichester, 1997.