-
Previous Article
A new reprojection of the conjugate directions
- NACO Home
- This Issue
-
Next Article
Second order modified objective function method for twice differentiable vector optimization problems over cone constraints
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 [
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. |
[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. 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. |
[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] |
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 |
[2] |
Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020 doi: 10.3934/jdg.2021001 |
[3] |
Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020162 |
[4] |
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 |
[5] |
Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013 |
[6] |
Vivina Barutello, Gian Marco Canneori, Susanna Terracini. Minimal collision arcs asymptotic to central configurations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 61-86. doi: 10.3934/dcds.2020218 |
[7] |
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 |
[8] |
Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018 |
[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] |
Ugo Bessi. Another point of view on Kusuoka's measure. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020404 |
[11] |
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 |
[12] |
Bing Sun, Liangyun Chen, Yan Cao. On the universal $ \alpha $-central extensions of the semi-direct product of Hom-preLie algebras. Electronic Research Archive, , () : -. doi: 10.3934/era.2021004 |
[13] |
Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020 doi: 10.3934/naco.2020054 |
[14] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
[15] |
Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021012 |
[16] |
Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136 |
[17] |
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 |
[18] |
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 |
[19] |
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 |
[20] |
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 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]