Share This Article:

A New Full-NT-Step Infeasible Interior-Point Algorithm for SDP Based on a Specific Kernel Function

Abstract Full-Text HTML XML Download Download as PDF (Size:168KB) PP. 1014-1022
DOI: 10.4236/am.2012.39150    4,204 Downloads   6,249 Views  

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.

Conflicts of Interest

The authors declare no conflicts of interest.

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.

  
comments powered by Disqus

Copyright © 2019 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.