AM  Vol.3 No.9 , September 2012
A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function
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.

Cite this paper
S. Bouali and S. Kabbaj, "A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function," Applied Mathematics, Vol. 3 No. 9, 2012, pp. 1014-1022. doi: 10.4236/am.2012.39150.
References
[1]   E. de Klerk, “Aspects of Semidefinite Programming,” Kluwer Academic Publishers, Dordrecht, 2002.

[2]   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

[3]   H. Wolkowicz R. Saigal and L. Vandenberghe, “Handbook of Semidefinite Programming: Theory, Algorithms and Applications,” Kluwer, Norwell, 1999.

[4]   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

[5]   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.

[6]   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

[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

[8]   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

[9]   J. Peng, C. Roos and T. Terlaky, “Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms,” Princeton University Press, Princeton, 2002.

[10]   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

[11]   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

[12]   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.

 
 
Top