Advanced Search
Article Contents
Article Contents

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

  • * Corresponding author

    * Corresponding author
Abstract Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by
  • 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].

    Mathematics Subject Classification: 90C05, 90C51.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 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
     | Show Table
    DownLoad: CSV
  • [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. AsadiH. MansouriG. 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. AsadiH. 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. CzyzykS. MehrtotraM. 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. JiF. 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. KojimaN. 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. MizunoM. 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. SalahiJ. 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.
  • 加载中



Article Metrics

HTML views(993) PDF downloads(698) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint