American Institute of Mathematical Sciences

Advanced
June  2019, 9(2): 147-156. doi: 10.3934/naco.2019011

A Mehrotra type predictor-corrector interior-point algorithm for linear programming

Soodabeh Asadi and  Hossein Mansouri ,

Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran

* Corresponding author

Received  February 2017 Revised  August 2018 Published  January 2019

In this paper, we analyze a feasible predictor-corrector linear programming variant of Mehrotra's algorithm. The analysis is done in the negative infinity neighborhood of the central path. We demonstrate the theoretical efficiency of this algorithm by showing its polynomial complexity. The complexity result establishes an improvement of factor $ n^3 $ in the theoretical complexity of an earlier presented variant in [2], which is a huge improvement. We examine the performance of our algorithm by comparing its implementation results to solve some NETLIB problems with the algorithm presented in [2].

Keywords: Interior-point algorithm, linear programming, central path, predictor-corrector, iteration complexity.
Mathematics Subject Classification: 90C05, 90C51.
Citation: 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
References:
[1]

R. Almeida, F. Bastos and A. Teixeira, On polynomiality of a predictor-corrector variant algorithm, in International conference on numerical analysis and applied mathematica, Springer-Verlag, New York, (2010), 959–963. Google Scholar

[2]

R. Almeida and A. Teixeira, On the convergence of a predictor-corrector variant algorithm, TOP, 23 (2015), 401-418.  doi: 10.1007/s11750-014-0346-8.  Google Scholar

[3]

E. D. Andersen and K. D. Andersen, The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm, in High Performance Optimization (eds. H. Frenk, K. Roos, T. Terlaky and S. Zhang), Kluwer Academic Publishers, (2000), 197–232. doi: 10.1007/978-1-4757-3216-0_8.  Google Scholar

[4]

S. Asadi, H. Mansouri, Zs. Darvay and M. Zangiabadi, On the $P_*(\kappa)$ horizontal linear complementarity problems over Cartesian product of symmetric cones, Optim. Methods Softw., 31 (2016), 233-257. doi: 10.1080/10556788.2015.1058795.  Google Scholar

[5]

S. Asadi, H. Mansouri, Zs. Darvay, G. Lesaja and M. Zangiabadi, A long-step feasible predictor-corrector interior-point algorithm for symmetric cone optimization, Optim. Methods Softw., 67 (2018), 2031–2060 doi: 10.1080/10556788.2018.1528248.  Google Scholar

[6]

S. Asadi, H. Mansouri, G. Lesaja and M. Zangiabadi, A long-step interior-point algorithm for symmetric cone Cartesian $P_*(\kappa)$ -HLCP, Optimization, 67 (2018), 2031-2060.  doi: 10.1080/02331934.2018.1512604.  Google Scholar

[7]

S. Asadi, H. Mansouri, Zs. Darvay, M. Zangiabadi and N Mahdavi-Amiri, Large-neighborhood infeasible predictor-corrector algorithm for horizontal linear complementarity problems over cartesian product of symmetric cones, J. Optim. Theory Appl., q doi: 10.1007/s10957-018-1402-6.  Google Scholar

[8]

S. Asadi, H. Mansouri and and Zs. Darvay, An infeasible full-NT step IPM for $P_*(\kappa)$ horizontal linear complementarity problem over Cartesian product of symmetric cones, Optimization, 66 (2017), 225-250.  doi: 10.1080/02331934.2016.1267732.  Google Scholar

[9]

J. Czyzyk, S. Mehrtotra, M. Wagner and S. J. Wright, PCx: an interior-point code for linear programming, Optim. Methods Softw., 11/12 (1999), 397-430.  doi: 10.1080/10556789908805757.  Google Scholar

[10]

J. Ji, F. Potra and R. Sheng, On a local convergence of a predictor-corrector method for semidefinite programming, SIAM J. Optim., 10 (1999), 195-210.  doi: 10.1137/S1052623497316828.  Google Scholar

[11]

N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.  doi: 10.1007/BF02579150.  Google Scholar

[12]

M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Springer, Berlin, 1991. doi: 10.1007/3-540-54509-3.  Google Scholar

[13]

M. Kojima, N. Megiddo and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Math. Program., 61 (1993), 263-280.  doi: 10.1007/BF01582151.  Google Scholar

[14]

S. Mehrotra, On finding a vertex solution using interior-point methods, Linear Algebra Appl., 152 (1991), 233-253.  doi: 10.1016/0024-3795(91)90277-4.  Google Scholar

[15]

S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2 (1992), 575-601.  doi: 10.1137/0802028.  Google Scholar

[16]

N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming, (1989), 135–158.  Google Scholar

[17]

S. Mizuno, M. J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18 (1993), 964-981.  doi: 10.1287/moor.18.4.964.  Google Scholar

[18]

R. D. C. Monteiro, Primal-dual path-following algorithm for semidefinite programming, SIAM J. Optim., 7 (1997), 663-678.  doi: 10.1137/S1052623495293056.  Google Scholar

[19]

J. Peng, C. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton, New Jersey, 2002.  Google Scholar

[20]

M. Salahi, J. Peng and T. Terlaky, On mehrotra-type predictor-corrector algorithms, SIAM J. Optim., 18 (2007), 1377-1397.  doi: 10.1137/050628787.  Google Scholar

[21]

M. Salahi, A finite termination mehrotra type predictor-corrector algorithm, Appl. Math. Comput., 190 (2007), 1740-1746.  doi: 10.1016/j.amc.2007.02.061.  Google Scholar

[22]

Gy. Sonnevend, An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in Lecture Notes in Control and Information Sciences, Springer, Berlin, (1985), 866–876. doi: 10.1007/BFb0043914.  Google Scholar

[23]

J. Stoer and M. Wechs, Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity, Math. Program. Ser. A., 83 (1998), 407-423.  doi: 10.1016/S0025-5610(98)00011-2.  Google Scholar

[24]

G. Q. Wang and Y. Q. Bai, Polynomial interior-point algorithms for $P_*(\kappa)$ horizontal linear complementarity problem, J. Comput. Appl. Math., 233 (2009), 248-263.  doi: 10.1016/j.cam.2009.07.014.  Google Scholar

[25]

G. Q. Wang and G. Lesaja, Full Nesterov-Todd step feasible interior-point method for the Cartesian $P_*(\kappa)$-SCLCP, Optim. Methods Softw., 28 (2013), 600-618.  doi: 10.1080/10556788.2013.781600.  Google Scholar

[26]

Y. Zhang and D. Zhang, Superlinear convergence of infeasible-interior-point methods for linear programming, Math. Program., 66 (1994), 361-377.  doi: 10.1007/BF01581155.  Google Scholar

[27]

Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim., 4 (1994), 208-227.  doi: 10.1137/0804012.  Google Scholar

[28]

Y. Zhang, Solving large scale linear programmes by interior point methods under the Matlab environment, Optim. Methods Softw., 10 (1999), 1-31.  doi: 10.1080/10556789808805699.  Google Scholar

show all references

References:
[1]

R. Almeida, F. Bastos and A. Teixeira, On polynomiality of a predictor-corrector variant algorithm, in International conference on numerical analysis and applied mathematica, Springer-Verlag, New York, (2010), 959–963. Google Scholar

[2]

R. Almeida and A. Teixeira, On the convergence of a predictor-corrector variant algorithm, TOP, 23 (2015), 401-418.  doi: 10.1007/s11750-014-0346-8.  Google Scholar

[3]

E. D. Andersen and K. D. Andersen, The MOSEK interior point optimizer for linear programming: an implementation of the homogeneous algorithm, in High Performance Optimization (eds. H. Frenk, K. Roos, T. Terlaky and S. Zhang), Kluwer Academic Publishers, (2000), 197–232. doi: 10.1007/978-1-4757-3216-0_8.  Google Scholar

[4]

S. Asadi, H. Mansouri, Zs. Darvay and M. Zangiabadi, On the $P_*(\kappa)$ horizontal linear complementarity problems over Cartesian product of symmetric cones, Optim. Methods Softw., 31 (2016), 233-257. doi: 10.1080/10556788.2015.1058795.  Google Scholar

[5]

S. Asadi, H. Mansouri, Zs. Darvay, G. Lesaja and M. Zangiabadi, A long-step feasible predictor-corrector interior-point algorithm for symmetric cone optimization, Optim. Methods Softw., 67 (2018), 2031–2060 doi: 10.1080/10556788.2018.1528248.  Google Scholar

[6]

S. Asadi, H. Mansouri, G. Lesaja and M. Zangiabadi, A long-step interior-point algorithm for symmetric cone Cartesian $P_*(\kappa)$ -HLCP, Optimization, 67 (2018), 2031-2060.  doi: 10.1080/02331934.2018.1512604.  Google Scholar

[7]

S. Asadi, H. Mansouri, Zs. Darvay, M. Zangiabadi and N Mahdavi-Amiri, Large-neighborhood infeasible predictor-corrector algorithm for horizontal linear complementarity problems over cartesian product of symmetric cones, J. Optim. Theory Appl., q doi: 10.1007/s10957-018-1402-6.  Google Scholar

[8]

S. Asadi, H. Mansouri and and Zs. Darvay, An infeasible full-NT step IPM for $P_*(\kappa)$ horizontal linear complementarity problem over Cartesian product of symmetric cones, Optimization, 66 (2017), 225-250.  doi: 10.1080/02331934.2016.1267732.  Google Scholar

[9]

J. Czyzyk, S. Mehrtotra, M. Wagner and S. J. Wright, PCx: an interior-point code for linear programming, Optim. Methods Softw., 11/12 (1999), 397-430.  doi: 10.1080/10556789908805757.  Google Scholar

[10]

J. Ji, F. Potra and R. Sheng, On a local convergence of a predictor-corrector method for semidefinite programming, SIAM J. Optim., 10 (1999), 195-210.  doi: 10.1137/S1052623497316828.  Google Scholar

[11]

N. K. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, 4 (1984), 373-395.  doi: 10.1007/BF02579150.  Google Scholar

[12]

M. Kojima, N. Megiddo, T. Noma and A. Yoshise, A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Springer, Berlin, 1991. doi: 10.1007/3-540-54509-3.  Google Scholar

[13]

M. Kojima, N. Megiddo and S. Mizuno, A primal-dual infeasible-interior-point algorithm for linear programming, Math. Program., 61 (1993), 263-280.  doi: 10.1007/BF01582151.  Google Scholar

[14]

S. Mehrotra, On finding a vertex solution using interior-point methods, Linear Algebra Appl., 152 (1991), 233-253.  doi: 10.1016/0024-3795(91)90277-4.  Google Scholar

[15]

S. Mehrotra, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2 (1992), 575-601.  doi: 10.1137/0802028.  Google Scholar

[16]

N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming, (1989), 135–158.  Google Scholar

[17]

S. Mizuno, M. J. Todd and Y. Ye, On adaptive-step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18 (1993), 964-981.  doi: 10.1287/moor.18.4.964.  Google Scholar

[18]

R. D. C. Monteiro, Primal-dual path-following algorithm for semidefinite programming, SIAM J. Optim., 7 (1997), 663-678.  doi: 10.1137/S1052623495293056.  Google Scholar

[19]

J. Peng, C. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton, New Jersey, 2002.  Google Scholar

[20]

M. Salahi, J. Peng and T. Terlaky, On mehrotra-type predictor-corrector algorithms, SIAM J. Optim., 18 (2007), 1377-1397.  doi: 10.1137/050628787.  Google Scholar

[21]

M. Salahi, A finite termination mehrotra type predictor-corrector algorithm, Appl. Math. Comput., 190 (2007), 1740-1746.  doi: 10.1016/j.amc.2007.02.061.  Google Scholar

[22]

Gy. Sonnevend, An analytic center for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, in Lecture Notes in Control and Information Sciences, Springer, Berlin, (1985), 866–876. doi: 10.1007/BFb0043914.  Google Scholar

[23]

J. Stoer and M. Wechs, Infeasible-interior-point paths for sufficient linear complementarity problems and their analyticity, Math. Program. Ser. A., 83 (1998), 407-423.  doi: 10.1016/S0025-5610(98)00011-2.  Google Scholar

[24]

G. Q. Wang and Y. Q. Bai, Polynomial interior-point algorithms for $P_*(\kappa)$ horizontal linear complementarity problem, J. Comput. Appl. Math., 233 (2009), 248-263.  doi: 10.1016/j.cam.2009.07.014.  Google Scholar

[25]

G. Q. Wang and G. Lesaja, Full Nesterov-Todd step feasible interior-point method for the Cartesian $P_*(\kappa)$-SCLCP, Optim. Methods Softw., 28 (2013), 600-618.  doi: 10.1080/10556788.2013.781600.  Google Scholar

[26]

Y. Zhang and D. Zhang, Superlinear convergence of infeasible-interior-point methods for linear programming, Math. Program., 66 (1994), 361-377.  doi: 10.1007/BF01581155.  Google Scholar

[27]

Y. Zhang, On the convergence of a class of infeasible interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim., 4 (1994), 208-227.  doi: 10.1137/0804012.  Google Scholar

[28]

Y. Zhang, Solving large scale linear programmes by interior point methods under the Matlab environment, Optim. Methods Softw., 10 (1999), 1-31.  doi: 10.1080/10556789808805699.  Google Scholar

Table 1.  The number of iterations
Problem $ m $ $ n $ Alg 1 (It.) Alg 1 ($ x^Tv $) Alg 2 (It.) Alg 2 ($ x^Tv $)
blend 74 114 242 8.3720e-4 280 8.4720e-4
adlittle 56 138 61 3.8658e-4 376 3.7909e-4
scagr7 129 185 308 4.2065e-4 217 7.5233e-4
share1b 117 253 51 1.3551e-4 344 1.0125e-4
share2b 96 162 191 3.8527e-4 296 3.9533e-4
scsd1 77 760 75 1.1725e-4 112 1.0346e-4
sc105 105 163 238 5.0063e-4 266 1.6058e-4
agg 488 615 31 1.0920e-4 199 1.0088e-4
Table Options

Download as excel

Problem $ m $ $ n $ Alg 1 (It.) Alg 1 ($ x^Tv $) Alg 2 (It.) Alg 2 ($ x^Tv $)
blend 74 114 242 8.3720e-4 280 8.4720e-4
adlittle 56 138 61 3.8658e-4 376 3.7909e-4
scagr7 129 185 308 4.2065e-4 217 7.5233e-4
share1b 117 253 51 1.3551e-4 344 1.0125e-4
share2b 96 162 191 3.8527e-4 296 3.9533e-4
scsd1 77 760 75 1.1725e-4 112 1.0346e-4
sc105 105 163 238 5.0063e-4 266 1.6058e-4
agg 488 615 31 1.0920e-4 199 1.0088e-4
[1]

Liming Sun, Li-Zhi Liao. An interior point continuous path-following trajectory for linear programming. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1517-1534. doi: 10.3934/jimo.2018107
[2]

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
[3]

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
[4]

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
[5]

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
[6]

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
[7]

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
[8]

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
[9]

Antonio Coronel-Escamilla, José Francisco Gómez-Aguilar. A novel predictor-corrector scheme for solving variable-order fractional delay differential equations involving operators with Mittag-Leffler kernel. Discrete & Continuous Dynamical Systems - S, 2020, 13 (3) : 561-574. doi: 10.3934/dcdss.2020031
[10]

Andrew E.B. Lim, John B. Moore. A path following algorithm for infinite quadratic programming on a Hilbert space. Discrete & Continuous Dynamical Systems - A, 1998, 4 (4) : 653-670. doi: 10.3934/dcds.1998.4.653
[11]

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
[12]

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
[13]

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
[14]

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
[15]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[16]

Rong Hu, Ya-Ping Fang. A parametric simplex algorithm for biobjective piecewise linear programming problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 573-586. doi: 10.3934/jimo.2016032
[17]

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
[18]

Jianqin Zhou, Wanquan Liu, Xifeng Wang. Complete characterization of the first descent point distribution for the k-error linear complexity of 2n-periodic binary sequences. Advances in Mathematics of Communications, 2017, 11 (3) : 429-444. doi: 10.3934/amc.2017036
[19]

Yibing Lv, Tiesong Hu, Jianlin Jiang. Penalty method-based equilibrium point approach for solving the linear bilevel multiobjective programming problem. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1743-1755. doi: 10.3934/dcdss.2020102
[20]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477

 Impact Factor: 

Tools

Metrics

  • PDF downloads (128)
  • HTML views (502)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences