Table 1.
The number of iterations
-
Previous Article
Second order modified objective function method for twice differentiable vector optimization problems over cone constraints
- NACO Home
- This Issue
-
Next Article
A new reprojection of the conjugate directions
June
2019, 9(2): 147-156.
doi: 10.3934/naco.2019011
A Mehrotra type predictor-corrector interior-point algorithm for linear programming
Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran |
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 [
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. |
| [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. |
| Problem | Alg 1 (It.) | Alg 1 ( |
Alg 2 (It.) | Alg 2 ( |
||
| 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 |
| Problem | Alg 1 (It.) | Alg 1 ( |
Alg 2 (It.) | Alg 2 ( |
||
| 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, 2018, 13 (5) : 1-18. 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] |
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 |
| [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 & Continuous Dynamical Systems - S, 2018, 0 (0) : 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 & 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 & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891 |
| [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] |
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 |
| [12] |
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 |
| [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 & Management Optimization, 2017, 13 (5) : 1-27. doi: 10.3934/jimo.2018190 |
| [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] |
Rich Stankewitz, Hiroki Sumi. Random backward iteration algorithm for Julia sets of rational semigroups. Discrete & Continuous Dynamical Systems - A, 2015, 35 (5) : 2165-2175. doi: 10.3934/dcds.2015.35.2165 |
| [20] |
Scott Crass. New light on solving the sextic by iteration: An algorithm using reliable dynamics. Journal of Modern Dynamics, 2011, 5 (2) : 397-408. doi: 10.3934/jmd.2011.5.397 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]