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]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[2]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399

[4]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008

[5]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[6]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933

[7]

Demetres D. Kouvatsos, Jumma S. Alanazi, Kevin Smith. A unified ME algorithm for arbitrary open QNMs with mixed blocking mechanisms. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 781-816. doi: 10.3934/naco.2011.1.781

[8]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023

[9]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

[10]

Wen-Bin Yang, Yan-Ling Li, Jianhua Wu, Hai-Xia Li. Dynamics of a food chain model with ratio-dependent and modified Leslie-Gower functional responses. Discrete & Continuous Dynamical Systems - B, 2015, 20 (7) : 2269-2290. doi: 10.3934/dcdsb.2015.20.2269

[11]

Hyeong-Ohk Bae, Hyoungsuk So, Yeonghun Youn. Interior regularity to the steady incompressible shear thinning fluids with non-Standard growth. Networks & Heterogeneous Media, 2018, 13 (3) : 479-491. doi: 10.3934/nhm.2018021

[12]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437

[13]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311

[14]

Martial Agueh, Reinhard Illner, Ashlin Richardson. Analysis and simulations of a refined flocking and swarming model of Cucker-Smale type. Kinetic & Related Models, 2011, 4 (1) : 1-16. doi: 10.3934/krm.2011.4.1

[15]

Rui Hu, Yuan Yuan. Stability, bifurcation analysis in a neural network model with delay and diffusion. Conference Publications, 2009, 2009 (Special) : 367-376. doi: 10.3934/proc.2009.2009.367

[16]

Seung-Yeal Ha, Shi Jin. Local sensitivity analysis for the Cucker-Smale model with random inputs. Kinetic & Related Models, 2018, 11 (4) : 859-889. doi: 10.3934/krm.2018034

[17]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119

[18]

W. Cary Huffman. On the theory of $\mathbb{F}_q$-linear $\mathbb{F}_{q^t}$-codes. Advances in Mathematics of Communications, 2013, 7 (3) : 349-378. doi: 10.3934/amc.2013.7.349

[19]

Carlos Fresneda-Portillo, Sergey E. Mikhailov. Analysis of Boundary-Domain Integral Equations to the mixed BVP for a compressible stokes system with variable viscosity. Communications on Pure & Applied Analysis, 2019, 18 (6) : 3059-3088. doi: 10.3934/cpaa.2019137

[20]

Misha Bialy, Andrey E. Mironov. Rich quasi-linear system for integrable geodesic flows on 2-torus. Discrete & Continuous Dynamical Systems - A, 2011, 29 (1) : 81-90. doi: 10.3934/dcds.2011.29.81

2019 Impact Factor: 1.366

Metrics

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

Other articles
by authors

[Back to Top]