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

Soodabeh Asadi; Hossein Mansouri

doi:10.3934/naco.2019011

Article Contents

2019, Volume 9, Issue 2: 147-156. Doi: 10.3934/naco.2019011

This issue Previous Article Second order modified objective function method for twice differentiable vector optimization problems over cone constraints Next Article A new reprojection of the conjugate directions

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
^* Corresponding author

Received: February 2017

Revised: August 2018

Published: January 2019

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: 90C05, 90C51.

Citation:

Full Text(HTML)

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

Related Papers

Cited by

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.