A full-modified-Newton step infeasible interior-pointalgorithm for linear optimization

Yinghong Xu; Lipu Zhang; Jing Zhang

doi:10.3934/jimo.2016.12.103

Article Contents

2016, Volume 12, Issue 1: 103-116. Doi: 10.3934/jimo.2016.12.103

This issue Previous Article The optimal portfolios based on a modified safety-first rule with risk-free saving Next Article A compaction scheme and generator for distribution networks

A full-modified-Newton step infeasible interior-point algorithm for linear optimization

1.
Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, 310018
2.
Department of Mathematics, Zhejiang A&F University, Zhejiang, 311300

Received: August 2014

Revised: November 2014

Published: January 2016

Abstract / Introduction Related Papers Cited by

Abstract

Based on an equivalent reformulation of the central path, we obtain a modified-Newton step for linear optimization. Using this step, we propose an infeasible interior-point algorithm. The algorithm uses only one full-modified-Newton step search in each iteration. The complexity bound of the algorithm is the best known for infeasible interior-point algorithm.

Keywords:

Mathematics Subject Classification: Primary: 17C99, 90C25; Secondary: 90C51.

Citation:

Related Papers

Cited by

References

[1]	G. Gu, H. Mansouri, M. Zangiabadi, Y. Bai and C. Roos, Improved full-Newton step $\mathcal O(nL)$ infeasible interior-point method for linear optimization, Journal of Optimization Theory and Applications, 145 (2010), 271-288.doi: 10.1007/s10957-009-9634-0.
[2]	H. Mansouri and C. Roos, Simplified $\mathcal O(nL)$ infeasible interior-point algorithm for linear optimization using full-newton steps, Optimization Methods and Software, 22 (2007), 519-530.doi: 10.1080/10556780600816692.
[3]	H. Mansouri, M. Zangiabadi, Y. Bai and C. Roos, An infeasible interior-point algorithm with full-Newton step for linear optimization, 2008. Available from: http://www.optimization-online.org/DB-HTML/2008/07/2052.html.
[4]	C. Roos, A full-Newton step $\mathcal O(n)$ infeasible interior-point algorithm for linear optimization, SIAM Journal on Optimization, 16 (2006), 1110-1136.doi: 10.1137/050623917.
[5]	C. Roos, An improved and simplified full-newton step $\mathcal O(n)$ infeasible interior-point method for linear optimization, SIAM J. Optim., 25 (2015), 102-114, Available from: http://www.optimization-online.org/DB-HTML/2014/01/4205.html.doi: 10.1137/140975462.
[6]	C. Roos, T. Terlaky and J. P. Vial, Interior Point Methods for Linear Optimization, Revised edition, Springer, New York, 2006.
[7]	S. Wright, Primal-dual Interior-point Methods, SIAM, Philadelphia, 1997.doi: 10.1137/1.9781611971453.
[8]	L. Zhang and Y. Xu, A new infeasible interior-point algorithm with full step for linear optimization based on a simple function, International Journal of Computer Mathematics, 88 (2011), 3163-3185.doi: 10.1080/00207160.2011.597503.
[9]	L. Zhang and Y. Xu, A full-newton step interior-point algorithm based on modified newton direction, Operations Research Letters, 39 (2011), 318-322.doi: 10.1016/j.orl.2011.06.006.