Journal of Software, Vol 6, No 10 (2011), 2029-2035, Oct 2011
doi:10.4304/jsw.6.10.2029-2035

A full-Newton step interior-point algorithm based on modified-Newton direction

Lipu Zhang, Yinghong Xu

Abstract


By a modification of the classic-Newton direction in scaled version for linear optimization, we give a new interior-point algorithm based on a very simple function. The algorithm uses full modified-Newton step, thus no need to perform line search. In the processing of the algorithm, the simple function is used to control the searching direction and measure the proximity of iterates to the central path. Moreover, the modified-Newton step used in the algorithm has local quadratic convergence property according to the proximity function. The iteration complexity is derived, and which is the best-known.


Keywords


complexity analysis;linear optimization;interior-point algorithm;modified-Newton direction.

References


[1] N. Karmarkar, “A new polynomial-time algorithm for linear programming,” in Proceedings of the sixteenth annual ACM symposium on Theory of computing. ACM, 1984, pp. 302–311.

[2] C. Roos, T. Terlaky, and J. Vial, Theory and algorithms for linear optimization: an interior point approach. John Wiley & Son Ltd, 1997.

[3] S. Wright, Primal-dual interior-point methods. Society for Industrial Mathematics, 1997.
http://dx.doi.org/10.1137/1.9781611971453

[4] Y. Bai, M. El Ghami, and C. Roos, “A new efficient large-update primal-dual interior-point method based on a finite barrier,” SIAM Journal on Optimization, vol. 13, pp. 766–782, 2002.
http://dx.doi.org/10.1137/S1052623401398132

[5] ——, “A comparative study of kernel functions for primal-dual interior-point algorithms in linear optimization,” SIAM Journal on Optimization, vol. 15, pp. 101–128, 2004.
http://dx.doi.org/10.1137/S1052623403423114

[6] J. Peng, C. Roos, and T. Terlaky, “New Complexity Analysis of the Primal-Dual Newton Method for Linear Optimization,” Annals of Operations Research, vol. 99, no. 1, pp. 23–39, 2000.
http://dx.doi.org/10.1023/A:1019280614748

[7] ——, “Self-regular functions and new search directions for linear and semidefinite optimization,” Mathematical Programming, vol. 93, no. 1, pp. 129–171, 2002.
http://dx.doi.org/10.1007/s101070200296

[8] ——, “A new and efficient large-update interior-point method for linear optimization,” Vychisl. Tekhnol., vol. 6, no. 4, pp. 61–80, 2001.

[9] ——, Self-Regularity: A new paradigm for Primal-Dual interior-point algorithms. Princeton Univ Pr, 2002.

[10] Y. Bai, C. Roos, and M. Ghami, “A primal-dual interior-point method for linear optimization based on a new proximity function,” Optimization Methods and Software, vol. 17, no. 6, pp. 985–1008, 2002.
http://dx.doi.org/10.1080/1055678021000090024

[11] M. El Ghami, “New primal-dual interior-point methods based on kernel functions,” Ph.D Thesis, Delft University of Technology, 2005.

[12] M. Kojima, N. Megiddo, and S. Mizuno, “A primal-dual infeasible-interior-point algorithm for linear programming,” Mathematical Programming, vol. 61, no. 1, pp. 263–280, 1993.
http://dx.doi.org/10.1007/BF01582151

[13] N. Megiddo, “Pathways to the optimal set in linear programming,” Progress in Mathematical Programming: Interior Point and Related Methods, pp. 131–158, 1989.

[14] Z. Darvay, “A weighted-path-following method for linear optimization,” Studia Universitatis Babes-Bolyai, Series Informatica, vol. 47, no. 1, pp. 3–12, 2002.


Full Text: PDF


Journal of Software (JSW, ISSN 1796-217X)

Copyright @ 2006-2013 by ACADEMY PUBLISHER – All rights reserved.