# American Institute of Mathematical Sciences

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

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