Dynamic Programming Approach to Time-Staged Convex Programs

摘要

This paper describes a dynamic programming-like technique for solving large scale (or at least moderately large scale) convex programs which have a time-staged (i.e., ''staircase'') structure. At the heart of the technique is a method for avoiding ''the curse of dimensionality'' which normally prevents the application of dynamic programming to problems whose time stages contain more than just a small number of variables. Three algorithms are developed: a ''backward'' algorithm, a ''forward'' algorithm, and a ''time-symmetric'' algorithm. The ''backward'' algorithm most closely resembles standard dynamic programming since ''pricing'' information propagates from the future back to the past. A strong connection is shown between these D.P.-like techniques and the ''nested decomposition'' algorithms of Manne and Ho, and Abrahamson and Wittrock, particularly the latter. These nested decomposition algorithms are used to solve ''staircase linear programs'' - a special case of the problem considered in this paper. (ERA citation 10:025079)