Interior Points Algorithms in Data Envelopment Analysis (Case Study: An Iranian Bank)
Keywords:
Interior points algorithms, Data envelopment analysis, Efficiency, Linear programmingAbstract
In this paper, interior point methods are discussed and analyzed. First, general aspects of Data Envelopment Analysis (DEA) are expressed, then the concept of efficiency, CCR and BCC, BCC-CCR, CCR-BCC models, and the reference sets in DEA models and super-efficiency in ranking are presented. Ellipsoid methods that theoretically prove that linear programming problems are efficiently solvable are also used. The result is significant since when a problem is solvable, practical and efficient algorithms can be developed. The ellipsoid method is not a practical algorithm for solving linear programming problems. Finally, a new category of algorithms, known as the interior point optimization method, is introduced, both valuable and efficient. The other advantage of the process above is that the complexity of the interior point algorithm is in polynomial order. In contrast, the simplex algorithm uses exponential order in the worst cases. This is a good reason to indicate the priority of the interior point optimization algorithm compared with the simplex algorithm. Therefore, this point justifies using the interior point methods in DEA.
References
Charnes, A., Cooper, W. W., & Rhodes, E. (1978). Measuring the efficiency of decision making units. European journal of operational research, 2(6), 429–444. https://doi.org/10.1016/0377-2217(78)90138-8
Banker, R. D., Charnes, A., & Cooper, W. W. (1984). Some models for estimating technical and scale inefficiencies in data envelopment analysis. Management science, 30(9), 1031-1142. https://doi.org/10.1287/mnsc.30.9.1078
Cooper, W. W., Seiford, L. M., Tone, K. (2007). Data envelopment analysis: A comprehensive text with models, applications, references and DEA-solver software (Vol. 2). Springer. https://doi.org/10.1007/b109347
Bertsimas, D., & Tsitsiklis, J. N. (1997). Introduction to linear optimization (Vol. 6). Athena Scientific Belmont, MA. https://B2n.ir/tb1508
Cooper, A. C. W. W., & Charnes, W. (1962). Programming with linear fractional functionals. Naval research logistics quarterly, 9(3), 181–186. https://doi.org/10.1002/nav.3800090303
Alizadeh, F. (1995). Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM journal on optimization, 5(1), 13–51. https://doi.org/10.1137/0805002
Alizadeh, F., Haeberly, J. P. A., & Overton, M. L. (1998). Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results. SIAM journal on optimization, 8(3), 746–768. https://doi.org/10.1137/S1052623496304700
Karmarkar, N. (1984). A new polynomial-time algorithm for linear programming. Proceedings of the Sixteenth annual acm symposium on theory of computing (pp. 302–311). Association for Computing Machinery. https://doi.org/10.1145/800057.808695
Borgwardt, K. H. (2012). The simplex method: A probabilistic analysis (Vol. 1). Springer Science & Business Media. https://doi.org/10.1007/978-3-642-61578-8
Fiacco, A. V, & McCormick, G. P. (1964). Computational algorithm for the sequential unconstrained minimization technique for nonlinear programming. Management science, 10(4), 601–617. https://doi.org/10.1287/mnsc.10.4.601
Andersen, E. D., & Andersen, K. D. (1995). Presolving in linear programming. Mathematical programming, 71, 221–245. https://doi.org/10.1007/BF01586000
Andersen, K. D. (1996). A modified Schur-complement method for handling dense columns in interior-point methods for linear programming. ACM transactions on mathematical software (TOMS), 22(3), 348–356. https://doi.org/10.1145/232826.232937
Kojima, M., Shindoh, S., & Hara, S. (1997). Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM journal on optimization, 7(1), 86–125. https://doi.org/10.1137/S1052623494269035
Jansen, B., Roos, C., & Terlaky, T. (1996). A polynomial primal-dual Dikin-type algorithm for linear programming. Mathematics of operations research, 21(2), 341–353. https://doi.org/10.1287/moor.21.2.341
Chvatal, V. (1983). Linear programming.” W. H. Freeman and Company, New York. https://B2n.ir/pb2293
Freund, R. M. (1991). Polynomial-time algorithms for linear programming based only on primal scaling and projected gradients of a potential function. Mathematical programming, 51(1), 203–222. https://doi.org/10.1007/BF01586933
Freund, R. W., & Jarre, F. (1997). A QMR-based interior-point algorithm for solving linear programs. Mathematical programming, 76, 183–210. https://doi.org/10.1007/BF02614383
Gonzaga, C. C. (1990). Polynomial affine algorithms for linear programming. Mathematical programming, 49, 7–21. https://doi.org/10.1007/BF01588776
Ahuja, R. K., Magnanti, T. L., Orlin, J. B. (1993). Network flows: Theory, algorithms, and applications (Vol. 1). Prentice Hall Englewood Cliffs, NJ. https://B2n.ir/jg9167
Adler, I., & Monteiro, R. D. C. (1991). Limiting behavior of the affine scaling continuous trajectories for linear programming problems. Mathematical programming, 50, 29–51. https://doi.org/10.1007/BF01594923
Jarre, F., & Saunders, M. A. (1995). A practical interior-point method for convex programming. SIAM journal on optimization, 5(1), 149–171. https://doi.org/10.1137/0805008
Karmarkar, N. K., Lagarias, J. C., Slutsman, L., & Wang, P. (1989). Power series variants of Karmarkar-type algorithms. AT & T technical journal, 68(3), 20–36. https://doi.org/10.1002/j.1538-7305.1989.tb00316.x
Fourer, R., & Mehrotra, S. (1993). Solving symmetric indefinite systems in an interior-point method for linear programming. Mathematical programming, 62(1), 15–39. https://doi.org/10.1007/BF01585158
Kojima, M., Mizuno, S., & Yoshise, A. (1989). A primal-dual interior point algorithm for linear programming. Springer. https://doi.org/10.1007/BF01582151
Den Hertog, D. (2012). Interior point approach to linear, quadratic and convex programming: Algorithms and complexity (Vol. 277). Springer Science & Business Media. https://doi.org/10.1007/978-94-011-1134-8
Metrics
