The art and theory of dynamic programming, Volume 130 (Mathematics in Science and Engineering)
Stuart E. Dreyfus, Averill M. Law
Language: English
Pages: 284
ISBN: 0122218604
Format: PDF / Kindle (mobi) / ePub
Cyber Warfare: Techniques, Tactics and Tools for Security Practitioners (2nd Edition)
Classic Operating Systems: From Batch Processing to Distributed Systems
Introduction to the Theory of Computation (3rd Edition)
Introduction to Artificial Intelligence (Undergraduate Topics in Computer Science)
Data Structures and Algorithm Analysis in C++ (4th Edition)
Mathematically as subject to c c Y, N x, = X , r=l N I= I = (3.10) Y? ..,X y I = O , 1, . . . , Y x I = O , 1,. ..,N), 1,2, . . . , N ) . ( i = 1,2,. (i= Let us call this problem P . In order to solve this problem by the Lagrange multiplier procedure, the following four steps are employed: 6. LAGRANGE MULTIPLIERS 41 1. Guess a A 2 0. 2. Use dynamic programming to solve the following one-dimensiona1 problem: N 2 xi= subject to X, i= I x,=O, 1, . . . , X ( i = 1 , 2, . . .
Dynamic-programming formulation is as follows: recurrence relation: Ll(j7 k) 1 ( i = I , 2, . . . , N ) , (4.22) fi-l(j, i ) +J,-l(i, k ) boundary conditions: fo(j,k) = (4.23) answers: fN(j,k ) f o r j = 1, 2, . . . , N and k = 1, 2, . . . , N . (4.24) Notice that we have allowed the possibility of j = k on the r.h.s. of (4.22). This allows us to detect negative cycles. If f . ( j , j ) < 0 foI. some node, j , then a negative cycle exists. Let us show that J.(j, k), as defined by (4.21), is.
Comparisons (N - 2) necessary to compute the answer; however, these are negligible. Consider a 20-city traveling-salesman problem. For this problem a total of approximately 85 million operations are required. Actually, the practical limit on the size of the problem that can be solved by the above procedure is probably due to storage space rather than the amount of computation. At stage i, ( N - 1)(Nf2)storage locations are required to store fi. For N even, the number of storage locations required.
Equations of the form xj(i + 1) = xj(i) +J,;(x1(i), . . . , x n ( i ) , y l ( i ) , . . . , y m ( i ) ) ( j = I , . . . , n; i = O , . . . , N - 1). (7.15) If we attempt to modify derivation 1 we discover that we want to vary one component of x(i), say xk(i), while we keep fixed all other components of x at stage i as well as all components of x at all other stages. When performing this variation in xk(i), all components of y ( i - 1) and y(i) are allowed to vary dependently. Then (7.6).
Such as developed in this section and second-order, Newton-Raphson procedures such as given in Problem 6.6 is beyond the scope of this text. Briefly, a gradient procedure requires much less computation per iteration and will converge for initial guesses further from optimal than second-order a + a +a. a 7. DISCRETE-TIME OPTIMAL-CONTROL PROBLEMS 106 procedures. Second-order procedures converge rapidly once close to the solution while gradient procedures encounter difficulties (both the.