American Institute of Mathematical Sciences

Advanced
January  2016, 12(1): 103-116. doi: 10.3934/jimo.2016.12.103

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

Yinghong Xu 1, , Lipu Zhang 2, and  Jing Zhang 2,

1. 

Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou, 310018
2. 

Department of Mathematics, Zhejiang A&F University, Zhejiang, 311300, China, China

Received  August 2014 Revised  November 2014 Published  April 2015

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: modified-Newton-direction, linear optimization, complexity analysis., Infeasible interior-point algorithm, full-Newton step.
Mathematics Subject Classification: Primary: 17C99, 90C25; Secondary: 90C5.
Citation: Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial & Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
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.  Google Scholar

[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.  Google Scholar

[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: , ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

C. Roos, T. Terlaky and J. P. Vial, Interior Point Methods for Linear Optimization, Revised edition, Springer, New York, 2006.  Google Scholar

[7]

S. Wright, Primal-dual Interior-point Methods, SIAM, Philadelphia, 1997. doi: 10.1137/1.9781611971453.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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: , ().   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[6]

C. Roos, T. Terlaky and J. P. Vial, Interior Point Methods for Linear Optimization, Revised edition, Springer, New York, 2006.  Google Scholar

[7]

S. Wright, Primal-dual Interior-point Methods, SIAM, Philadelphia, 1997. doi: 10.1137/1.9781611971453.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[1]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[2]

Xiaoni Chi, Zhongping Wan, Zijun Hao. A full-modified-Newton step $ O(n) $ infeasible interior-point method for the special weighted linear complementarity problem. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021082
[3]

Behrouz Kheirfam. A full Nesterov-Todd step infeasible interior-point algorithm for symmetric optimization based on a specific kernel function. Numerical Algebra, Control & Optimization, 2013, 3 (4) : 601-614. doi: 10.3934/naco.2013.3.601
[4]

Behrouz Kheirfam, Guoqiang Wang. An infeasible full NT-step interior point method for circular optimization. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 171-184. doi: 10.3934/naco.2017011
[5]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[6]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[7]

Behrouz Kheirfam, Morteza Moslemi. On the extension of an arc-search interior-point algorithm for semidefinite optimization. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 261-275. doi: 10.3934/naco.2018015
[8]

Soodabeh Asadi, Hossein Mansouri. A Mehrotra type predictor-corrector interior-point algorithm for linear programming. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 147-156. doi: 10.3934/naco.2019011
[9]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211
[10]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949
[11]

Zheng-Hai Huang, Jie Sun. A smoothing Newton algorithm for mathematical programs with complementarity constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 153-170. doi: 10.3934/jimo.2005.1.153
[12]

Enrique Fernández-Cara, Arnaud Münch. Numerical null controllability of semi-linear 1-D heat equations: Fixed point, least squares and Newton methods. Mathematical Control & Related Fields, 2012, 2 (3) : 217-246. doi: 10.3934/mcrf.2012.2.217
[13]

Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008
[14]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial & Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[15]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739
[16]

Andy M. Yip, Wei Zhu. A fast modified Newton's method for curvature based denoising of 1D signals. Inverse Problems & Imaging, 2013, 7 (3) : 1075-1097. doi: 10.3934/ipi.2013.7.1075
[17]

Lianshuan Shi, Enmin Feng, Huanchun Sun, Zhaosheng Feng. A two-step algorithm for layout optimization of structures with discrete variables. Journal of Industrial & Management Optimization, 2007, 3 (3) : 543-552. doi: 10.3934/jimo.2007.3.543
[18]

Zheng-Hai Huang, Shang-Wen Xu. Convergence properties of a non-interior-point smoothing algorithm for the P*NCP. Journal of Industrial & Management Optimization, 2007, 3 (3) : 569-584. doi: 10.3934/jimo.2007.3.569
[19]

Liping Zhang, Soon-Yi Wu, Shu-Cherng Fang. Convergence and error bound of a D-gap function based Newton-type algorithm for equilibrium problems. Journal of Industrial & Management Optimization, 2010, 6 (2) : 333-346. doi: 10.3934/jimo.2010.6.333
[20]

Zhi Guo Feng, Kok Lay Teo, Volker Rehbock. A smoothing approach for semi-infinite programming with projected Newton-type algorithm. Journal of Industrial & Management Optimization, 2009, 5 (1) : 141-151. doi: 10.3934/jimo.2009.5.141

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (103)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences