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.  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.  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.  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.  doi: 10.1137/140975462.  Google Scholar

[6]

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

[7]

S. Wright, Primal-dual Interior-point Methods,, SIAM, (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.  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.  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.  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.  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.  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.  doi: 10.1137/140975462.  Google Scholar

[6]

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

[7]

S. Wright, Primal-dual Interior-point Methods,, SIAM, (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.  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.  doi: 10.1016/j.orl.2011.06.006.  Google Scholar

[1]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[2]

Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007
[3]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[4]

C. J. Price. A modified Nelder-Mead barrier method for constrained optimization. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020058
[5]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[6]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122
[7]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167
[8]

Fioralba Cakoni, Pu-Zhao Kow, Jenn-Nan Wang. The interior transmission eigenvalue problem for elastic waves in media with obstacles. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020075
[9]

Xiaofeng Ren, David Shoup. The impact of the domain boundary on an inhibitory system: Interior discs and boundary half discs. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3957-3979. doi: 10.3934/dcds.2020048
[10]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[11]

Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347
[12]

Guido Cavallaro, Roberto Garra, Carlo Marchioro. Long time localization of modified surface quasi-geostrophic equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020336
[13]

Rong Chen, Shihang Pan, Baoshuai Zhang. Global conservative solutions for a modified periodic coupled Camassa-Holm system. Electronic Research Archive, 2021, 29 (1) : 1691-1708. doi: 10.3934/era.2020087
[14]

Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020404
[15]

Hai-Yang Jin, Zhi-An Wang. Global stabilization of the full attraction-repulsion Keller-Segel system. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3509-3527. doi: 10.3934/dcds.2020027
[16]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320
[17]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115
[18]

Sabira El Khalfaoui, Gábor P. Nagy. On the dimension of the subfield subcodes of 1-point Hermitian codes. Advances in Mathematics of Communications, 2021, 15 (2) : 219-226. doi: 10.3934/amc.2020054
[19]

Balázs Kósa, Karol Mikula, Markjoe Olunna Uba, Antonia Weberling, Neophytos Christodoulou, Magdalena Zernicka-Goetz. 3D image segmentation supported by a point cloud. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 971-985. doi: 10.3934/dcdss.2020351
[20]

Claudio Arancibia-Ibarra, José Flores, Michael Bode, Graeme Pettet, Peter van Heijster. A modified May–Holling–Tanner predator-prey model with multiple Allee effects on the prey and an alternative food source for the predator. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 943-962. doi: 10.3934/dcdsb.2020148

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences