3. Introduction to Dynamic Programming
Society for Industrial and Applied Mathematics eBooks · 2005
3.1 Introduction The goal of functional optimization problems is to find the function of time that minimizes the scalar cost functional. Most direct methods of optimization, such as recursive quadratic programming (RQP), transform the calculus of variations problem into a suboptimal parameter optimization problem. These direct method algorithms are of the order N3 or N2 in the optimization parameters (i.e., parameterized functions of time with interpolation or series approximations) and n in the state variables. The indirect methods of optimization attempt to solve the “true” optimization problem by solving the two-point boundary value problem (TPBVP). The problem with indirect methods is that they are extremely sensitive to the initial guess of the initial conditions of the costate equations. As a result, direct methods are often used to initialize indirect methods when solving functional optimization problems. Dynamic programming (DP) is the best of both worlds. It solves the direct problem, which is less sensitive to the initial guess, and provides a discrete-time approximation to the optimal function of time since the DP algorithms are of order N in the optimization parameters. However, the cost of this linear behavior in N is an order n2 or n3 in the state variables. This chapter describes the basics of discrete dynamic programming (DDP) and demonstrates the ability of DDP to find smooth input shaping profiles and optimal trajectories from zero initial guesses. 3.2 Discrete Dynamic Programming The details of a DDP algorithm for input shaping and trajectory optimization are presented in this section for linear problems. Constraints are dealt with approximately by using a simple penalty approach. DDP algorithms for unconstrained nonlinear problems [28], nonlinear problems with equality constraints [29], and problems with a combination of equality and inequality constraints [31] will be discussed in detail in Chapter 4, as well as being introduced to the reader by the last example in this chapter. The principle of optimality [32, 33, 34] is the basis of DP.