A Deterministic Dynamic Programming Approach for Optimization Problem with Quadratic Objective Function and Linear Constraints

Authors: S. Kavitha, Nirmala P. Ratchagar

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.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088438

References:

[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.