Dynamic programming, reduction of dimensionality and matrix eigenvalue computations

This paper is a continuation of earlier papers by Ng & Sancho for solving certain dynamic programming problems. An iterative algorithm, based on a priori deduction from Bellman’s principle of optimality, is developed. The technique is applied to evaluate the smallest eigenvalue of positive definite symmetric matrices. It is shown to use only minimal storage requirements as compared to the traditional dynamic programming approach. Solutions on test matrices compare favorably in accuracy and convergence speed with other numerical solutions. The significance of the method is that it provides a means of reducing Bellman’s ‘curse of dimensionality’ and broadens the scope of problems that can effectively be solved with the dynamic programming approach.