Linear programming with a feasible direction interior point technique for smooth optimization

Victorio Celis, Angélica Miluzca; Norman, José Herskovits

RAIRO. Operations Research, Tome 56 (2022) no. 5, pp. 3643-3658

We propose an adaptation of the Feasible Direction Interior Points Algorithm (FDIPA) of J. Herskovits, for solving large-scale linear programs. At each step, the solution of two linear systems with the same coefficient matrix is determined. This step involves a significant computational effort. Reducing the solution time of linear systems is, therefore, a way to improve the performance of the method. The linear systems to be solved are associated with definite positive symmetric matrices. Therefore, we use Split Preconditioned Conjugate Gradient (SPCG) method to solve them, together with an Incomplete Cholesky preconditioner using Matlab’s ICHOL function. We also propose to use the first iteration of the conjugate gradient, and to presolve before applying the algorithm, in order to reduce the computational cost. Following, we then provide mathematica proof that show that the iterations approach Karush–Kuhn–Tucker points of the problem under reasonable assumptions. Finally, numerical evidence show that the method not only works in theory but is also competitive with more advanced methods.

Classification : 90C05, 90C51, 90C06
Keywords: Interior point, feasible direction, linear programming

[1] G.B. Dantzig, Maximization of a Linear Function of Variables Subject to Linear Inequalities. New York (1951). | MR

[2] G. B. Dantzig, Linear Programming and Extensions. Princeton University (1963). | MR | Zbl

[3] J. V. Neumann, On a Maximization Problem. Manuscript. Institute for Advanced Studies, Princeton University, Princeton, NJ (1947).

[4] A. Hoffman, M. Mannos, D. Sokolowsky and N. Wiegmann, Computational experience in solving linear programs. J. Soc. Ind. Appl. Math. 1 (1953) 17–33. | MR | Zbl | DOI

[5] N. Karmarkar, A new polynomial-time algorithm for linear programming, in Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, ACM (1984) 302–311. | DOI

[6] I. Dikin, Iterative solution of problems of linear and quadratic programming. Soviet Mathematics Doklady. 8 (1967) 674–675. | MR | Zbl

[7] E. R. Barnes, A variation on Karmarkar’s algorithm for solving linear programming problems. Math. Program. 36 (1986) 174–182. | MR | Zbl | DOI

[8] T. Cavalier and A. Soyster, Some Computational Experience and a Modification of the Karmarkar Algorithm. Pennsylvania State Univ., College of Engineering, Department of Industrial and Management Systems Engineering (1985).

[9] C. C. Gonzaga, An algorithm for solving linear programming problems in $O\left(n^{3}L\right)$ operations, in Progress in Mathematical Programming, Springer (1989) 1–28. | MR | Zbl

[10] C. C. Gonzaga, Path-following methods for linear programming. SIAM Rev. 34 (1992) 167–224. | MR | Zbl | DOI

[11] Y. Ye, An $O\left(n^{3}L\right)$ potential reduction algorithm for linear programming. Math. Program. 50 (1991) 239–258. | MR | Zbl | DOI

[12] S. J. Wright, Primal-dual Interior-Point Methods. Vol. 54, SIAM (1997). | MR | Zbl | DOI

[13] J. V. Robert, Linear Programming: Foundations and Extensions. Kluwer Academic, Boston (2001). | Zbl

[14] J. Herskovits, Feasible direction interior-point technique for nonlinear optimization. J. Optim. Theory Appl. 99 (1998) 121–146. | MR | Zbl | DOI

[15] A. E. Gutierrez, S. R. Mazorche, J. Herskovits and G. Chapiro, An interior point algorithm for mixed complementarity nonlinear problems. J. Optim. Theory Appl. 175 (2017) 432–449. | MR | Zbl | DOI

[16] J. R. Roche, J. Herskovits, E. Bazán and A. Zúñiga, A feasible direction algorithm for general nonlinear semidefinite programming. Struct. Multidiscip. Optim. 55 (2017) 1261–1279. | MR | DOI

[17] M. Aroztegui, J. Herskovits, J. R. Roche and E. Bazán, A feasible direction interior point algorithm for nonlinear semidefinite programming. Struct. Multidiscip. Optim. 50 (2014) 1019–1035. | MR | DOI

[18] J. Herskovits, W. P. Freire, M. Tanaka Fo and A. Canelas, A feasible directions method for nonsmooth convex optimization. Struct. Multidiscip. Optim. 44 (2011) 363–377. | MR | Zbl | DOI

[19] J. Herskovits, A. Leontiev, G. Dias and G. Santos, Contact shape optimization: a bilevel programming approach. Struct. Multidiscip. Optim. 20 (2000) 214–221. | DOI

[20] R. H. Byrd, J. C. Gilbert and J. Nocedal, A trust region method based on interior point techniques for nonlinear programming. Math. Program. 89 (2000) 149–185. | MR | Zbl | DOI

[21] A. L. Tits, J. L. Zhou and A. Simple, Quadratically Convergent Interior Point Algorithm for Linear Programming and Convex Quadratic Programming. Springer US, Boston, MA (1994) 411–427. | MR | Zbl

[22] N. Ploskas and N. Samaras, Linear Programming using MATLAB®. Vol. 127, Springer (2017). | MR | Zbl | DOI

[23] Y. Saad, Iterative Methods for Sparse Linear Systems. Vol. 82, SIAM (2003). | MR | Zbl | DOI

[24] D. M. Gay, Electronic mail distribution of linear programming test problems. Mathematical Programming Society COAL Newsletter 13 (1985) 10–12.

[25] N. Maculan and M. H. C. Fampa, Otimização Linear. EdUnB, Braslia (2006).

[26] A. M. V. Celis, Algoritmo de ponto interior para programação linear baseado no fdipa. Master’s thesis, Universidade Federal do Rio de Janeiro (2018).

[27] N. Megiddo, Pathways to the optimal set in linear programming, in Progress in Mathematical Programming, Springer (1989) 131–158. | MR | Zbl | DOI

[28] M. Kojima, S. Mizuno and A. Yoshise, A Primal-Dual Interior-Point Method for Linear Programming, Progress in Mathematical Programming: Interior-point and Related Method, Edited by N. Megiddo, Springer Verlag, New York, New York (1989) 29–47. | MR | Zbl | DOI