×

zbMATH — the first resource for mathematics

CurveLP-A MATLAB implementation of an infeasible interior-point algorithm for linear programming. (English) Zbl 1378.65127
The author develops a competitive arc-feasible infeasible interior-point algorithm. He shows that based on the results on Netlib problems, the comparison of Mehrotra’s algorithm and the arc-feasible infeasible interior-point algorithm yields that the proposed arc-feasible infeasible interior-point algorithm is a more reliable and efficient algorithm than Mehrotra’s algorithm.
This article is well written, structured and explained, it contains six sections: Section 1 on Introduction, Section 2 on Problem descriptions, Section 3 on Arc-search algorithm for linear programming, Section 4 on Implementation details, Section 5 on Numerical tests, and, Section 6 on Conclusions.

MSC:
65K05 Numerical mathematical programming methods
90C05 Linear programming
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Wright, S.: Primal-Dual Interior-Point Methods. SIAM, Philadelphia (1997) · Zbl 0863.65031
[2] Megiddo, N; Megiddo, N (ed.), Pathway to the optimal set in linear propramming, 131-158, (1989), New York
[3] Kojima, M; Mizuno, S; Yoshise, A, A polynomial-time algorithm for a class of linear complementarity problem, Math. Program., 44, 1-26, (1989) · Zbl 0676.90087
[4] Kojima, M; Mizuno, S; Yoshise, A; Megiddo, N (ed.), A primal-dual interior point algorithm for linear programming, (1989), New York · Zbl 0708.90049
[5] Mehrotra, S, On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 575-601, (1992) · Zbl 0773.90047
[6] Lustig, I; Marsten, R; Shannon, D, Computational experience with a primal-dual interior-point method for linear programming, Linear Algebra Appl., 152, 191-222, (1991) · Zbl 0731.65049
[7] Lustig, I; Marsten, R; Shannon, D, On implementing mehrotra’s predictor-corrector interior-point method for linear programming, SIAM J. Optim., 2, 432-449, (1992) · Zbl 0771.90066
[8] Mizuno, S, Polynomiality of the kojima-megiddo-mizuno infeasible interior point algorithm for linear programming, Math. Program., 67, 109-119, (1994) · Zbl 0828.90086
[9] Zhang, Y, On the convergence of a class of infeasible-interior-point methods for the horizontal linear complementarity problem, SIAM J. Optim., 4, 208-227, (1994) · Zbl 0803.90092
[10] Mizuno, S; Todd, M; Ye, Y, On adaptive step primal-dual interior-point algorithms for linear programming, Math. Oper. Res., 18, 964-981, (1993) · Zbl 0810.90091
[11] Miao, J, Two infeasible interior-point predictor-corrector algorithms for linear programming, SIAM J. Optim., 6, 587-599, (1996) · Zbl 0856.90075
[12] Roos, C, A full-Newton step O(n) infeasible interior-point algorithm for linear optimization, SIAM J. Optim., 16, 1110-1136, (2006) · Zbl 1131.90029
[13] Salahi, M; Peng, J; Terlaky, T, On mehrotra-type predictor-corrector algorithms, SIAM J. Optim., 18, 1377-1397, (2007) · Zbl 1165.90569
[14] Kheirfam, B; Ahmadi, K; Hasani, F, A modified full-Newton step infeasible interior-point algoirhm for linear optimization, Asia-Pacific J. Operational Research, 30, 11-23, (2013) · Zbl 1401.90267
[15] Yang, Y., Yamashita, M. An \(\mathcal{O},(nL))\) Infeasible-Interior-Point Algorithm for Linear Programming (2015). arXiv:1506.06365 · Zbl 1165.90569
[16] Winternitz, LB; Tits, AL; Absil, P-A, Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization, J Optim Theory Appl, 160, 127-157, (2014) · Zbl 1311.90180
[17] Vanderbei, RJ, LOQO: an interior point code for quadratic programming, Optim. Methods Soft., 12, 451-484, (1999) · Zbl 0973.90518
[18] Czyzyk, J., Mehrotra, S., Wagner, M., Wright, S.J.: PCX User Guide (version 1.1), Technical Report OTC 96/01 Optimization Technology Center (1997) · Zbl 0973.90518
[19] Zhang, Y.: Solving large-scale linear programs by interior-point methods under the matlab environment, Technical Report TR96-01, Department of Mathematics and Statistics University of Maryland (1996)
[20] Monteiro, R; Adler, I; Resende, M, A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension, Math. Oper. Res., 15, 191-214, (1990) · Zbl 0714.90060
[21] Cartis, C, Some disadvantages of a mehrotra-type primal-dual corrector interior point algorithm for linear programming, Appl. Numer. Math., 59, 1110-1119, (2009) · Zbl 1163.90042
[22] Yang, Y, A polynomial arc-search interior-point algorithm for linear programming, J. Optim. Theory Appl., 158, 859-873, (2013) · Zbl 1274.90494
[23] Yang, Y, A polynomial arc-search interior-point algorithm for convex quadratic programming, Eur. J. Oper. Res., 215, 25-38, (2011) · Zbl 1252.90059
[24] Cartis, C., Gould, N.I.M.: Finding a point in the relative interior of a polyhedron, Technical Report NA-07/01, Computing Laboratory Oxford University (2007)
[25] Do Carmo, M.P.: Differential Geometry of Curves and Surfaces. Prentice-Hall, New Jersey (1976) · Zbl 0326.53001
[26] Brearley, AL; Mitra, G; Williams, HP, Analysis of methematical programming problems prior to applying the simplex algorithm, Math. Program., 8, 54-83, (1975) · Zbl 0317.90037
[27] Andersen, ED; Andersen, KD, Presolving in linear programming, Math. Program., 71, 221-245, (1993) · Zbl 0846.90068
[28] Mahajan, A.: Presolving mixed-integer linear programs, Preprint ANL/MCS-p1752-0510 argonne national laboratory (2010)
[29] Ghidini, CTLS; Oliveira, ARL; Silvab, J; Velazco, MI, Combining a hybrid preconditioner and a optimal adjustment algorithm to accelerate the convergence of interior point methods, Linear Algebra Appl., 436, 1267-1284, (2012) · Zbl 1236.65065
[30] Tits, AL; Yang, Y, Globally convergent algorithms for robust pole assignment by state feedback, IEEE Trans. Autom. Control, 41, 1432-1452, (1996) · Zbl 0884.93030
[31] Dolan, ED; More, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[32] Curtis, AR; Reid, JK, On the automatic scaling of matrices for Gaussian elimination, J. Inst. Maths Applics, 10, 118-124, (1972) · Zbl 0249.65026
[33] Andersen, ED, Finding all linearly dependent rows in large-scale linear programming, Optim. Methods Soft., 6, 219-227, (1995)
[34] Duff, J.F., Erisman, A.M., Reid, J.K.: Direct method for sparse matrices. Oxford University Press, New York (1989) · Zbl 0666.65024
[35] Dobes, J.: A modified Markowitz criterion for the fast modes of the LU factorization. In: Proceedings of 48th Midwest Symposium on Circuits and Systems, (2005), pp. 955-959 · Zbl 1049.90004
[36] Ng, E; Peyton, BW, Block sparse Cholesky algorithm on advanced uniprocessor computers, SIAM J. Sci. Comput., 14, 1034-1056, (1993) · Zbl 0785.65015
[37] Liu, JW, Modification of the minimum degree algorithm by multiple elimination, ACM Trans. Math. Softw., 11, 141-153, (1985) · Zbl 0568.65015
[38] Goldman, A.J., Tucker, A.W.: Theory of Linear Programming. In: Kuhn, H.W., Tucker (eds.) Linear Equalities and Related Systems, pp. 53-97. Princeton University Press, Princeton, N.J (1956) · Zbl 0072.37601
[39] Guler, O., den Hertog, D., Roos, C., Terlaky, T., Tsuchiya T.: Degeneracy in interior-point methods for linear programming: a survey. Ann. Oper. Res. 46, 107-138 (1993) · Zbl 0785.90067
[40] Gill, PE; Murray, W; Saunders, MA; Tomlin, JA; Wright, MH, On projected Newton barrier methods for linear programming and an equivalence of karmarkar’s projective method, Math. Program., 36, 183-209, (1986) · Zbl 0624.90062
[41] Vavasis, SA; Ye, Y, A primal dual interior-point method whose running time depends on the constraint matrix, Math. Program. A, 74, 79-120, (1996) · Zbl 0868.90081
[42] Yang, Y.: Arc-Search Infeasible Interior-Point Algorithm for Linear Programming. arXiv:1406.4539 (2014) · Zbl 1252.90059
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.