×

Predictor-corrector primal-dual interior point method for solving economic dispatch problems: a postoptimization analysis. (English) Zbl 1264.90177

Summary: We propose a predictor-corrector primal-dual interior point method which introduces line search procedures (IPLS) in both the predictor and corrector steps. The Fibonacci search technique is used in the predictor step, while an Armijo line search is used in the corrector step. The method is developed for application to the economic dispatch (ED) problem studied in the field of power systems analysis. The theory of the method is examined for quadratic programming problems and involves the analysis of iterative schemes, computational implementation, and issues concerning the adaptation of the proposed algorithm to solve ED problems. Numerical results are presented, which demonstrate improvements and the efficiency of the IPLS method when compared to several other methods described in the literature. Finally, postoptimization analyses are performed for the solution of ED problems.

MSC:

90C51 Interior-point methods
90C90 Applications of mathematical programming
90B30 Production models
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] N. Karmarkar, “A new polynomial-time algorithm for linear programming,” Combinatorica, vol. 4, no. 4, pp. 373-395, 1984. · Zbl 0557.90065 · doi:10.1007/BF02579150
[2] I. I. Dikin, “Iterative solution of problems of linear and quadratic programming,” Doklady Akademii Nauk SSSR, vol. 174, pp. 747-748, 1967 (Russian). · Zbl 0189.19504
[3] E. R. Barnes, “A variation on Karmarkar’s algorithm for solving linear programming problems,” Mathematical Programming, vol. 36, no. 2, pp. 174-182, 1986. · Zbl 0626.90052 · doi:10.1007/BF02592024
[4] R. J. Vanderbei, M. S. Meketon, and B. A. Freedman, “A modification of Karmarkar’s linear programming algorithm,” Algorithmica, vol. 1, no. 4, pp. 395-407, 1986. · Zbl 0626.90056 · doi:10.1007/BF01840454
[5] I. Adler, M. G. C. Resende, G. Veiga, and N. Karmarkar, “An implementation of Karmarkar’s algorithm for linear programming,” Mathematical Programming, vol. 44, no. 1-3, pp. 297-335, 1989. · Zbl 0682.90061 · doi:10.1007/BF01587095
[6] A. R. Balbo, M. A. S. Souza, and E. C. Baptista, “Métodos primal-dual de pontos interiores aplicados à resolu de problemas de despacho econômico: sobre a influência da solu inicial,” in Proceedings of the Simpósio Brasileiro de Pesquisa Operacional, João Pessoa-Pb. Anais do XL SBPO (XL SBPO ’08), pp. 2074-2085, ILTC, Rio de Janeiro, RJ, Brazil, 2008.
[7] N. Megiddo and M. Shub, “Boundary behavior of interior point algorithms in linear programming,” Mathematics of Operations Research, vol. 14, no. 1, pp. 97-146, 1989. · Zbl 0675.90050 · doi:10.1287/moor.14.1.97
[8] A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley & Sons, New York, NY, USA, 1968. · Zbl 0713.90043
[9] A. V. Fiacco and G. P. McCormick, Nonlinear Programming, vol. 4 of Classics in Applied Mathematics, SIAM, Philadelphia, Pa, USA, 2nd edition, 1990. · Zbl 0713.90043
[10] K. R. Frisch, The Logarithmic Potential Method of Convex Programming, University Institute of Economics, Oslo, Norway, 1955.
[11] P. E. Gill, W. Murray, M. A. Saunders, J. A. Tomlin, and M. H. Wright, “On projected Newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method,” Mathematical Programming, vol. 36, no. 2, pp. 183-209, 1986. · Zbl 0624.90062 · doi:10.1007/BF02592025
[12] Y. Ye, “An O(n3L) potential reduction algorithm for linear programming,” in Contemporary Mathematics, vol. 114, pp. 91-107, American Mathematical Society, Providence, RI, USA, 1990. · Zbl 0725.90063 · doi:10.1090/conm/114/1097867
[13] J. Renegar, “A polynomial-time algorithm, based on Newton’s method, for linear programming,” Mathematical Programming, vol. 40, no. 1, pp. 59-93, 1988. · Zbl 0654.90050 · doi:10.1007/BF01580724
[14] P. M. Vaidya, “An algorithm for linear programming which requires O(((m+n)n2+(m+n)1.5n)L) arithmetic operations,” Mathematical Programming, vol. 47, no. 2, pp. 175-201, 1990. · Zbl 0708.90047 · doi:10.1007/BF01580859
[15] N. Megiddo, “On the complexity of linear programming,” in Advances in Economic Theory, T. Bewley, Ed., pp. 225-268, Cambridge University Press, Cambridge, UK, 1989. · Zbl 0735.90044
[16] C. C. Gonzaga, “An algorithm for solving linear programming problems in O(n3L) operations,” in Progress in Mathematical Programming: Interior-Point and Related Methods, N. Megiddo, Ed., pp. 1-28, Springer, New York, NY, USA, 1989. · Zbl 0691.90053
[17] C. C. Gonzaga, “Polynomial affine algorithms for linear programming,” Mathematical Programming, vol. 49, no. 1, pp. 7-21, 1990. · Zbl 0777.90027 · doi:10.1007/BF01588776
[18] R. D. C. Monteiro and I. Adler, “Interior path following primal-dual algorithms. I. Linear programming,” Mathematical Programming, vol. 44, no. 1, pp. 27-41, 1989. · Zbl 0676.90038 · doi:10.1007/BF01587075
[19] R. D. C. Monteiro, I. Adler, and M. G. C. Resende, “A polynomial-time primal-dual affine scaling algorithm for linear and convex quadratic programming and its power series extension,” Mathematics of Operations Research, vol. 15, no. 2, pp. 191-214, 1990. · Zbl 0714.90060 · doi:10.1287/moor.15.2.191
[20] M. Kojima, S. Mizuno, and A. Yoshise, “A primal-dual interior point algorithm for linear programming,” in Progress in mathematical programming: Interior-Point and Related Methods, N. Megiddo, Ed., pp. 29-47, Springer, New York, NY, USA, 1989. · Zbl 0708.90049
[21] S. Mehrotra and J. Sun, “An algorithm for convex quadratic programming that requires O(n3.5L) arithmetic operations,” Mathematics of Operations Research, vol. 15, no. 2, pp. 342-363, 1990. · Zbl 0714.90075 · doi:10.1287/moor.15.2.342
[22] I. J. Lustig, R. E. Marsten, and D. F. Shanno, “On implementing Mehrotra’s predictor-corrector interior-point method for linear programming,” SIAM Journal on Optimization, vol. 2, no. 3, pp. 435-449, 1992. · Zbl 0771.90066 · doi:10.1137/0802022
[23] Y. C. Wu, A. S. Debs, and R. E. Marsten, “Direct nonlinear predictor-corrector primal-dual interior point algorithm for optimal power flows,” IEEE Transactions on Power Systems, vol. 9, no. 2, pp. 876-883, 1994. · doi:10.1109/59.317660
[24] S. C. Fang and S. Puthenpura, Linear Optimization and Extensions: Theory and Algorithms, Prentice-Hall, Englewood Cliffs, NJ, USA, 1993. · Zbl 0799.90080
[25] J. O. Kim, D. J. Shin, J. N. Park, and C. Singh, “Atavistic genetic algorithm for economic dispatch with valve point effect,” Electric Power Systems Research, vol. 62, no. 3, pp. 201-207, 2002. · doi:10.1016/S0378-7796(02)00036-6
[26] N. M. Rodrigues, Um algoritmo cultural para problemas de despacho de energia elétrica, Disserta de Mestrado, Universidade Estadual de Maringá, 2007.
[27] M. M. A. Samed, Um algoritmo genético Hibrido co-evolutivo para resolver problemas de despacho, Tese de Doutorado, UEM, Departamento de Engenharia Química, 2004.
[28] H. H. Happ, “Optimal power dispatch-a comprehensive survey,” IEEE Transactions on Power Apparatus and Systems, vol. 96, no. 3, pp. 841-854, 1977.
[29] M. J. C. Steinberg and T. H. Smith, Economic Loading of Power Plants and Electric Systems, MacGraw-Hill, 1943.
[30] A. R. L. Oliveira, S. Soares, and L. Nepomuceno, “Optimal active power dispatch combining network flow and interior point approaches,” IEEE Transactions on Power Systems, vol. 18, no. 4, pp. 1235-1240, 2003. · doi:10.1109/TPWRS.2003.814851
[31] M. S. Bazaraa, H. D. Sherali, and C. M. Shetty, Non Linear Programming-Theory and Algorithm, John Wiley & Sons, New York, NY, USA, 2nd edition, 1993. · Zbl 0774.90075
[32] S. J. Wright, Primal-Dual Interior-Point Methods, SIAM, Philadelphia, Pa, USA, 1997. · Zbl 0863.65031
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.