Breaking the Curse of Dimensionality Using a Recursive Dynamic Programming Framework

Abstract

The resolution of optimal control problems (OCPs) in real-world applications is frequently beset by the curse of dimensionality and the inherent nonlinearity of system dynamics. This paper presents a literature framework that combines recursive relationship formulations with the principles of dynamic programming (DP) to address these challenges. The research stresses on a perspective that geared towards bridging the gap between the theoretical approach of DP and the numerical computation that demands practical applications. Dynamic programming is a method that finds solutions to larger sub-problems after the problem has been reduced to smaller ones. The main idea is to embed recursive relationships directly within the DP framework. The hypothesis is that for a significant class of OCPs, particularly those characterized by certain structural properties or separable cost functions, the optimal decision at a given state can be expressed recursively as a function of decisions made in states or stages. The Recursive Dynamic Programming (RDP), embeds a state-dependent recursive structure directly within the DP iteration, enabling a more efficient traversal of the state space and the generation of near-optimal control policies. We demonstrate the efficacy of this approach and its application to the resource-constrained problem. The approach follows derivation of an analytical and a semi-analytical recursive expression for major decision variables or for the gradient function value, which are then applied iteratively within the DP. The RDP framework is shown to significantly reduce computational overhead compared to classical DP while maintaining a high degree of solution accuracy, offering a pragmatic and scalable pathway for tackling complex OCPs prevalent in engineering and economic systems.