A new parallel algorithm for optimal-control problems of interconnected systems

Parallel algorithms play a crucial role in utilizing parallel computers to overcome the difficulties of computation intensive problems. This paper presents a new parallel algorithm for solving optimal control of discrete-time interconnected systems. The idea is to use Lagrange multipliers to relax the coupling among subsystems. The decomposed subproblems are solved in parallel by using the differential dynamic programming (DDP) method. The Lagrange multipliers are selected as coordinating variables and updated at the high level of ensure global optimality. A method for estimating the computational complexity of the decomposition/coordination approach is presented, and the relationship between speed-up and major system parameters is established. It is shown that significant speed-ups are difficult to achieve by using conventional optimization techniques at high level. A large number of high level iterations may offset the reduction in computation for dealing with smaller decomposed subproblems in parallel. The parallel variable metric (PVM) method is found to be a promising high level algorithm for loosely coupled systems. Numerical results show that comparing with one level DDP, the PVM/DDP algorithm obtains significant speed-ups under a simulated parallel processing environment. Moreover global variational feedback controls which are invaluable for on-line control systems are obtained.