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

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

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

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

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

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

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

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

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

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

[11]

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

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

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

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

[15]

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

[16]

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

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

[18]

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

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

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

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

[11]

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

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

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

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

[15]

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

[16]

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

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

[18]

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

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

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

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

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

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

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

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

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

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

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

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]

Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003
[2]

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

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 and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37
[4]

Yinghong Xu, Lipu Zhang, Jing Zhang. A full-modified-Newton step infeasible interior-point algorithm for linear optimization. Journal of Industrial and Management Optimization, 2016, 12 (1) : 103-116. doi: 10.3934/jimo.2016.12.103
[5]

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

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

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 and Continuous Dynamical Systems - S, 2020, 13 (3) : 561-574. doi: 10.3934/dcdss.2020031
[8]

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

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

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 and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101
[11]

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 and Management Optimization, 2022, 18 (4) : 2579-2598. doi: 10.3934/jimo.2021082
[12]

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

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 and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190
[14]

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

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

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

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

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

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

Guoyong Gu, Junfeng Yang. A unified and tight linear convergence analysis of the relaxed proximal point algorithm. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022107

 Impact Factor: 

Tools

Metrics

  • PDF downloads (642)
  • HTML views (674)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy