A Deterministic Dynamic Programming Approach for Optimization Problem with Quadratic Objective Function and Linear Constraints
This paper presents the novel deterministic dynamic programming approach for solving optimization problem with quadratic objective function with linear equality and inequality constraints. The proposed method employs backward recursion in which computations proceeds from last stage to first stage in a multi-stage decision problem. A generalized recursive equation which gives the exact solution of an optimization problem is derived in this paper. The method is purely analytical and avoids the usage of initial solution. The feasibility of the proposed method is demonstrated with a practical example. The numerical results show that the proposed method provides global optimum solution with negligible computation time.
[1] A. J. Wood and B. F. Wollenberg, Power generation, operation, and
control, John Wiley & Sons, 1996.
[2] O. Barrientos and R. Correa, “An algorithm for global minimization of
linearly constrained quadratic functions,” Journal of global optimization,
vol.16, pp. 77–93, 2000.
[3] R. E. Bellman, Dynamic programming, Princeton University Press,
1957.
[4] V. Marano, G. Rizzo, and F. A. Tiano, “Application of dynamic
programming to the optimal management of a hybrid power plant with
wind turbines, photovoltaic panels and compressed air energy storage,”
Applied Energy, vol. 97, pp. 849-859, 2012.
[5] I.R. Ilaboya, E. Atikpo, G. O. Ekoh, M. O. Ezugwu, and L. Umukoro,
“Application of dynamic programming to solving reservoir operational
problems,” Journal of applied technology in environmental sanitation,
vol.1, pp. 251-262, 2011.
[6] John. O. S. Kennedy, Dynamic programming applications to agriculture
and natural resources, Elsevier applied science publisher, 1986.
[7] J. E. Beasley and B. C. Cao, “A dynamic programming based algorithm
for the crew scheduling problem,” Computers & operation research,
vol.25, pp. 567-582, 1998.
[8] R. Balamurugan and S. Subramanian, “A simplified recursive approach
to combined economic emission dispatch,” Electric power components
and systems, vol. 36, pp. 17-27, 2008.
[9] S. Webster and M. Azizoglu, “Dynamic programming algorithms for
scheduling parallel machines with family setup times,” Computers &
operation research, vol. 28, pp. 127-137, 2001.
[10] H. A. Taha, Operation research – An introduction, Prentice- Hall India,
1997.
[11] E. Denardo, Dynamic Programming theory and applications, Prentice
Hall, 1982.
[12] D. Bertsekas, Dynamic programming: Deterministic and stochastic
models, Prentice Hall, 1987.
[13] L. Bayon, J. M. Grau, M. M. Ruiz, and P. M. Suarez, “The exact
solution of the environmental/Economic dispatch problem,” IEEE
transactions on power systems, vol. 27, pp. 723-731, 2012.
[14] D. P. Kothari and J. S. Dhillon, Power system optimization, Prentice
Hall India, 2004.
[1] A. J. Wood and B. F. Wollenberg, Power generation, operation, and
control, John Wiley & Sons, 1996.
[2] O. Barrientos and R. Correa, “An algorithm for global minimization of
linearly constrained quadratic functions,” Journal of global optimization,
vol.16, pp. 77–93, 2000.
[3] R. E. Bellman, Dynamic programming, Princeton University Press,
1957.
[4] V. Marano, G. Rizzo, and F. A. Tiano, “Application of dynamic
programming to the optimal management of a hybrid power plant with
wind turbines, photovoltaic panels and compressed air energy storage,”
Applied Energy, vol. 97, pp. 849-859, 2012.
[5] I.R. Ilaboya, E. Atikpo, G. O. Ekoh, M. O. Ezugwu, and L. Umukoro,
“Application of dynamic programming to solving reservoir operational
problems,” Journal of applied technology in environmental sanitation,
vol.1, pp. 251-262, 2011.
[6] John. O. S. Kennedy, Dynamic programming applications to agriculture
and natural resources, Elsevier applied science publisher, 1986.
[7] J. E. Beasley and B. C. Cao, “A dynamic programming based algorithm
for the crew scheduling problem,” Computers & operation research,
vol.25, pp. 567-582, 1998.
[8] R. Balamurugan and S. Subramanian, “A simplified recursive approach
to combined economic emission dispatch,” Electric power components
and systems, vol. 36, pp. 17-27, 2008.
[9] S. Webster and M. Azizoglu, “Dynamic programming algorithms for
scheduling parallel machines with family setup times,” Computers &
operation research, vol. 28, pp. 127-137, 2001.
[10] H. A. Taha, Operation research – An introduction, Prentice- Hall India,
1997.
[11] E. Denardo, Dynamic Programming theory and applications, Prentice
Hall, 1982.
[12] D. Bertsekas, Dynamic programming: Deterministic and stochastic
models, Prentice Hall, 1987.
[13] L. Bayon, J. M. Grau, M. M. Ruiz, and P. M. Suarez, “The exact
solution of the environmental/Economic dispatch problem,” IEEE
transactions on power systems, vol. 27, pp. 723-731, 2012.
[14] D. P. Kothari and J. S. Dhillon, Power system optimization, Prentice
Hall India, 2004.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:65440", author = "S. Kavitha and Nirmala P. Ratchagar", title = "A Deterministic Dynamic Programming Approach for Optimization Problem with Quadratic Objective Function and Linear Constraints", abstract = "This paper presents the novel deterministic dynamic programming approach for solving optimization problem with quadratic objective function with linear equality and inequality constraints. The proposed method employs backward recursion in which computations proceeds from last stage to first stage in a multi-stage decision problem. A generalized recursive equation which gives the exact solution of an optimization problem is derived in this paper. The method is purely analytical and avoids the usage of initial solution. The feasibility of the proposed method is demonstrated with a practical example. The numerical results show that the proposed method provides global optimum solution with negligible computation time.
", keywords = "Backward recursion, Dynamic programming, Multi-stage decision problem, Quadratic objective function.", volume = "7", number = "3", pages = "549-5", }
