OPTIMAL CONTROL COMPUTATIONS FOR LINEAR SAMPLED-DATA SYSTEMS Thesis for the Degree of Ph. D. MICHIGAN STATE UNIVERSiTY JENG NAN UN 1968 In? l' H hblb LIBRARY Michigan State University. This is to certify that the thesis entitled OPTIMAL CONTROL COMPUTATIONS FOR LINEAR SAMPLED-DATA SYSTEMS presented by Jeng Nan Lin has been accepted towards fulfillment of the requirements for Ph. D. EE degree in flex/2145' 0 ($4 2/ Mi W Major professor Date November 20, 1968 0-169 IINSING 3‘! tons a sour - 909K 31qu In“; I only Inn-n1- "‘ “3V ABSTRACT OPTIMAL CONTROL COMPUTATIONS FOR LINEAR SAMPLED-DATA SYSTEMS BY Jeng Nan Lin This thesis presents a new algorithm for computing optimal controls for linear sampled-data systems in which easily-imple— mented matrix calculations are performed at each step. A com- prehensive analysis is given for several classes of optimiza— tion problems and numerical data are presented for six example problems. The thesis considers an ntn order, time-invariant, scalar-control, linear discrete system.ci: which is governed by the following difference equation: x((i+l)T) : éx(iT) + bu(iT), (l) where 9 is an (nicn) constant transition matrix, b is an (nicl) non-zero vector, u(t) is constant in the interval 1T 5 t < (i+l)T and |u(iT)| s 1 for all i. Iteration on (1) starting with i = O and x(0) = 0 yields @N'lbu(0)+QN-2bu(T)+°°-+ébu((N-2)T)+bu((N-1)T)o (2) Let x = X(NT), 21 = el'lb, i:=l,2,...,N, and uj = u((N-j)T), x(NT) = J = 1:2,--.,N. Then (2) becomes X : z uN + ZN-luN-l + °'°" + Z2112 + zlul. (3) Jeng Nan Lin The reachable set from the origin at time N, RN 9 N {XN 6 En : XN = Z Ziui’ luil S l, l S i S N} can be described i=1 as a system of linear inequalities: |cj x| s l, where C3 is a computable (D)(l) vector, 3 = l,2,...,K, and K s (nyl)' The properties of this set are fundamental in the computing algor- ithms in this thesis. Two broad classes of problems are considered: 1. Time-optimal control problem - Given the linear system if, starting from x(0) = O, and given a desired terminal target point d, find the smallest integer number N such that d = xN Z = Elziui. (i) When the optimal time is N S n, the solution to the l time-optimal control problem always exists and is shown to be unique. (ii) When the optimal time is N > n, the solution to the time—optimal control problem is, in general, not unique. In this case, in addition to seeking a time-optimal control sequence, a choice is made to also minimize the absolute value of uN. An algorithm for implementing the optimal control sequence is presented, which avoids the corresponding tedious quadratic and linear programming problems. The solution exhibits the special features that x1 is in R1 when u(N-l) is applied at the first stage, x2 is on the boundary of R2 when u(N-2) is applied at the second stage, ..., etc., and finally xN is on Jeng Nan Lin the boundary of 'E , a set closely related to B when u(O) N) . . th is applied at the N stage. 2. Terminal-error regulator problem - Given.J€/with x(0) = O, the terminal time N, and a desired terminal state d at time N; find a point x E R such that Hd-xH2 is minimum, and the N corresponding optimal control sequence, where on denotes the Euclidean norm. (i) In the case where N < n, it is shown that the con- trol sequence always exists and is unique. (ii) Consider the case where N 2 n. If d 6 6R the N3 control sequence is unique; if d 6 RN but d K BRN, the optimal control sequence is not unique. This then leads to the time-optimal problem, and the minimum of Iu can be required to make the time- NI optimal control sequence unique. If d K RN’ then Hd-xH2 > O and the corresponding optimal control sequence is unique. A control algorithm which terminates in a finite number of steps and guaran- tees the exact solution except for round-off errors is demonstrated. This algorithm does not require solving the corresponding quadratic programming problem. These new methods include matrix calculations which are easily programmed. The above results for the time-optimal and terminal-error regulator problems can easily be extended to apply to: (i) (ii) (iii) (iV) (V) (vi) Jeng Nan Lin Control constraints given in the form of lui|:§ni, n >0, i=1,2,ooo,No 1 Target sets given in the form of ,JL: x'Sx 2 p, where S is an (nicn) symmetric, positive definite matrix and b > 0. Target sets which are time-varying, i.e., X : j,(i). Time-varying linear discrete systems. Systems with variable sampling instants. Linear discrete systems with the initial state X(O) % 0. (vii) Multi-input control systems. A brief survey of these extensions is presented. OPTIMAL CONTROL COMPUTATIONS FOR LINEAR SAMPLED-DATA SYSTMES BY Jeng Nan Lin A THESIS Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Electrical Engineering 1968 ACKNOWLEDGEMENTS The author wishes to express his heartfelt appreciation to Dr. R. O. Barr for his interest and valuable comments concerning this thesis. Dr. Barr's critical review of the manuscript, which resulted in a number of improvements, is gratefully acknowledged. He also wishes to extend his sincere appreciation to Dr. G. L. Park for his continued guidance and inspiration in the preparation of this work. Dr. Park's generous and kind help with the example problems and computer programming is especially extoled. The author is indebted to Dr. H..E. Koenig who contri- buted in many ways to the author's graduate study, to Dr. J. S. Frame who carefully proofread the thesis and provided many fruitful comments regarding this thesis, and to Dr. R. D. Dubes who graciously served as guidance committee member. Finally to his wife, Tzu Hsia, the author is whole- heartedly grateful for her constant encouragement during this study. ii CHAPTER 1 CHAPTER 2 2.1 2.2 2.3 2.4 2.5 CHAPTER 3 3.1 3.2 CHAPTER R 1+.l A.2 H.3 TABLE OF CONTENTS LIST OF TABLES. . . . . . . . . . . . LIST OF FIGURES . . . . . . . . . . LIST OF SYMBOLS . INTRODUCTION . . . . . PRELIMINARY ANALYSIS AND THEORETICAL DEVELOPMENT . . . . . . . . . . . . . Vector Spaces, Linear Transformations, Elementary Matrices, and Solution Proper- ties Of AX: y 0 O 0 O I O O O 0 O 0 O 0 Description of the System . . . . . . . . Assumption of Complete Controllability. . Convex Sets, Polyhedra, and Properties of the Reachable Set . . . . . . . . . . . Computation of the Optimal Control ufi . TIME-OPTIMAL CONTROL PROBLEM. . . . . . . Statement of Time-Optimal Control Problem Solution PrOperties and Computing Algori- thm for Time—Optimal Control Problem . . TERMINAL-ERROR REGULATOR PROBLEM. . . Statement of Terminal-Error Regulator PrOblem O O O O O O O O O O O O I O O O 0 Solution Properties and Computing Algori— thm for Terminal-Error Regulator Problem; n > N o o o o o o o o o O o o o o o e o 0 Solution Properties and Computing Algori- thm for Terminal-Error Regulator Problem; n s N . . . . . . . . . . . . . . . . . iii Page v vi viii 10 ll 12 32 38 38 39 #6 H6 47 51 Page CHAPTER 5 SUMMARY AND EXTENSIONS. . . . . . . . . . . 59 5.1 Summary . . . . . . . . . . . . . . . . . . 59 5.2 Extensions. . . . . . . . . . . . . . . . . 63 CHAPTER 6 NUMERICAL EXAMPLES AND CONCLUSIONS. . . . . 70 REFERENCES. . . . . . . . . . . . . . . . . 86 iv Table 6.1 6.3 LIST OF TABLES Boundary Hyperplane Coefficients of R3 for Example 6.1. . . . . . . . . . . . . Boundary Hyperplane Coefficients of R40 for Example 6.1 . . . . . . . 1 Some |cid| for @14 of Example 6.2 . . Page 72 73 74 Figure la lb 10 LIST OF FIGURES Intersection of RN with hyperplane a'x = B, where a'xN < SVXN 6 RN Intersection of Rn with hyperplane a'x = B, I where a xN S S V’xN 6 RN . . . . . . . . . . Closed half—spaces for Example 2.#.l . |u vs. u with luNl s l . . . . . . . . . N| N ufi is the minimum of lu such that N| r=r +ugzN (with r EBR3,N=L+). . O 0 x2 6 5R2 with x1 Z 5R1 . Computer flow diagram for time-optimal control prOblem O O O O O O O I O O O I O O O O I Minimum squared length of Fd can be improved by finding an appropriate Ek for which Computer flow diagram for terminal—error regu- lator problem . . . . . . . . . . . Intersection of Rh and the target set ii: x'Sx 2 R . . . . . . . . . . . . . Time-varying targets: intersection of yX(1+)and EL.- 0 o o o o o o o o o o o o o o o o o o o 0 vi Page 92 92 92 93 93 95 94 95 96 97 97 Figure 11 12 Page Translation of coordinates when XO # 0 resulting in a new equivalent problem with x0 = O . . . . . . . . . . . . . . . . . . . 98 Some relations between RN and MK: x'Sx s 5 (when x0 # o). . . . . . . . . . . . . . . . 99 vii :3 t“ W quid: CI: rd 0 31> in L1. LIST OF SYMBOLS linear transformation reduced echelon matrix Euclidean n-space hyperplane in En support hyperplane to RN set of integers total number of boundary hyperplanes of R N elementary matrix L1 = -- product of elementary matrices L 2 optimal time for time-optimal control problem; also terminal time for terminal-error regulator problem performance index for terminal-error regulator problem reachable set of (3:, at time N from the origin sampling period in seconds identity matrix (of dimension (nicn)) (zl,zz,...,zN), a matrix of dimension (nicN) (nail) driving non-zero vector for single-input system (nicl) driving non-zero vector for multi-input system viii h(Y) r(A) extreme point of RN the convex hull of the set of points Y in En dimension of the state space x the rank of linear transformation A time scalar control for single—input system scalar control for multi-input system control sequence of length N, [ul,u2,...,uN] for . . 2 l Single-input system and [ui,ul,...,uT, u2,..., u§,..., .13“ optimal control .., u?] for multi—input system vertex of RN (HDCI) vector defined by 21 = i‘ l o 0‘ (nicl) vector defined by 2% - completement of the set A the intersection of two closed half-spaces Pi and ri closed half-space on En linear system to be controlled target set reachable subset for multi-input system subspace spanned by 21,22,...,zk set of integers fundamental matrix (nicn) real transition matrix ix NI BX XCY my (1) (2) edge the line segment between x and y integer, its value is either +1 or —1 for all x set difference operation set of points of closure of X boundary of X (prime) transpose of a matrix or a vector X is a subset of Y intersection of X and Y I1 w, x, y, z are vectors in E a, b, v, n, A, p, v.5 , p are scalar constants CHAPTER 1 INTRODUCTION During the last two decades, discrete optimal control problems have been investigated by many workers. One of the basic problems in the theory of optimal control is the time— optimal control problem. In general terms, the problem is the determination of system inputs which will take the system from a certain initial state to a prescribed terminal state in the shortest possible time, subject to various constraints. Numerous techniques for obtaining solutions to the time- optimal control problems have been proposed by many investi- gators [D2, D3, Du, El, G1, H6, K6, N1, N4, T1, T2, T3, TH, W1, Z1]*. Other related problems such as minimum norm prob- lems [C1, C2, R1], minimum energy problems [CH, R1], mini- mum effort problems [C3], terminal state problems [B2, N2, N3, P2], minimum time-fuel problems [T1, 21], minimum time- energy problems [C5, H6] and problems of minimum quadratic functionals of states and/or controls [C6, C7, C8, C9, D1, G1, H4, H7, K2, Pl] have also been considered. Linear programming [Fl, H1, T1, 21], non-linear programming [05, H6, N2, N3, P1, R2], dynamic programming [B1, D1, T5], Pontryagin‘s maximum * The alphanumeric numbers refer to the references at end of this dissertation. 2 principle [B3, c7, c8, c9, H2, H3, H7, H8, H9. R3, RA, R5] and variational methods [Jl, K3, K4] are among the various techniques which have been used extensively. One main subject of this dissertation is the discrete time-optimal control problem: determining an input signal which steers a linear discrete time-invariant ntn order system from the origin to a desired terminal state d in mini- mum time (the minimum number of sampling periods, N) sub- ject to amplitude constraints on the input signal. When n 2 N, a method is proposed for finding the unique optimal solution. When n < N, the optimal solution is, in general, non- unique [H6], and various procedures have been suggested for finding that time-optimal control which, among all time- optimal controls, also minimizes the energy supplied to the system [C5, H6] or which also minimizes the fuel consumption [T1, 21]. A new algorithm is presented to find the minimum time N such that d is in R the reachable set from the N’ origin at time N. Then, a new method is proposed for find— ing the unique time-optimal control sequence whose first mem- ber is minimum in absolute value. Another main subject is the terminal-error regulator problem: determining a control sequence such that the quan- tity “d - x is minimum, where N is the given terminal Nu 3 time. Based on the fact that the control input is constrained in magnitude, the reachable set can be described by the inter- section of 2(ngl) closed half-spaces, and the boundary of the reachable set RN is formed by subsets of hyperplanes. A new algorithm for solving the terminal-error regulator prob- lem is developed. In contrast to a previously suggested method [N2, N3], this algorithm does not involve solving a quadratic programming problem. The outline of the thesis is as follows. In Chapter 2 some elementary results on linear algebra, fundamental pro- perties of the reachable set, and the computing algorithm for the optimal control ufi are presented. Chapter 3 con- tains the precise statement of the time-optimal control prob- lem and algorithms for implementing the optimal control sequence. Chapter A involves the exact statement of the terminal-error regulator problem and algorithms for calcula- ting the corresponding optimal control sequence. In Chapter 5 a brief summary of new results, and some possible exten- sions of these results are carefully stated. Finally, in Chapter 6 examples of time-optimal control problems and terminal-error regulator problems are given; certain perti- nent conclusions are drawn by comparison with other existing techniques in the literature. CHAPTER 2 PRELIMINARY ANALYSIS AND THEORETICAL DEVELOPMENT In Section 2.1 some fundamental definitions and well- established theorems from vector spaces and matrix algebra needed in the sequel are presented. A description of the system to be studied is stated in Section 2.2 and the assump- tion of complete controllability is stated in Section 2.3. Section 2.4 contains the main body of the theory as well as properties of convex sets, polyhedra, and the reachable set. Section 2.5 involves the computation of the optimal control ufi. 2.1 Vector Spaces, Linear Transformations, Elementary Matrices, and Solution Properties of A}{= y. A brief description of some standard definitions and well-known theorems from finite—dimensional vector spaces and linear algebra [F2, F3, HlO] is given for the contin- uity of presentation in the sequel. Also the solution pro- perties of the equation AJCZ y, where A is (nicm), are discussed. Definition If a Euclidean vector space has dimension n, then it is denoted by En. In En the scalar_product is t, introduced by the formula: (x,y) = xlyl + ny2 + ...,. + xnyn, where xi and yi are the ith components of x and y respectively. The length of a vector~ x 6 En is defined as ”X“ = (XI + X2 + ..... + Xfi)l/2- Definition Two vectors x, y 6 En are said to be orthogonal if their scalar product is equal to zero. Definition The identity matrix of order n, written U or U is a square matrix having ones along the main diagonal n) and zeros elsewhere. “1000] O l O ~-- 0 001 .., O LOOOH-l Definition Let A be an (nicn) matrix. If there exists an (nicn) matrix B which satisfies the relation AB = BA = Un’ then B is called the inverse of A. Definition The rank of an (micn) matrix A, written r(A), is the maximum number of linearly independent columns in A. Theorem 2.1.1 If a square matrix A has an inverse, then so does A' and (A')-1 = (A-l)', where A' denotes the transpose of A. Theorem 2.1.2 For any matrix A, r(A), the rank of A is equal to r(A'). Theorem 2.1.3 For two conformable matrices A and B, r(AB) 3 min {r(A),r(B)}- Theorem 2.1.4 If A is (nick), and A has rank k, then r(A'A) = r(A). Theorem 2.1.5 Let G = A(A'A)—lA', where A is (nick), k < n and A has rank k. Then the image Gx under G of each vector x 6 En (also in En) lies in the subspace Ak of En spanned by the column vectors of A. 2322; By Theorem 2.1.4, the rank of A'A is k. Since the matrix A'A is (kick), it has an inverse. Thus G is well- defined. For any vector x 6 En, Gx = A(A'A)-lA'x. Let A = (21,22,..::zk) and X1 -1 _ _" ... '- (A'A) A'x — . Then Gx — Xlzl + x222 + + szk’ Thus Gx 6 Ak' Theorem 2.1.6 Let G = A(A'A)-lA'. Then G2 = G = G', and Gx is orthogonal to x-Gx. Proof Since G = A(A'A)-1A' = G', G2 = GG = [A(A'A)-1A'] 7 [A(A'A)-1A'] = A(A'A)-1A' = e. G'(U-G) (Gx, x-Gx) = (Gx,(U-G)x) = (x,G'(U-G)x) G-G2:Oo (x,0) = 0. Hence CI is orthogonal to x - Gx. Definition The distinguished columns of A are the 14, non- zero columns of A, no one of which is a linear ccmbination of its predecessors. . Dginition An (nxk) matrix of rank /L is a row echelon matrix if its last (nnflJ rows are zero, its distinguished columns are the first IL» columns of the identity matrix Un in order, and the 1's in these columns are the first nonzero mtries of their respective rows. If /L = n, there are no rows of 0's and the (nick) matrix is a reduced row echelon matrix. The transpose of a row echelon matrix is a column echelon matrix. Example 2.1.1 The following matrices are row echelon matri- ces. The fourth one is a reduced row echelon matrix. 12.303 ”0120] Piool 12010 0 o o 1 l o o o i o l o o o i 2 o o o o o o ; o o o o 3 o o l ; o o o o 1 LP 0 o 0_ Lo 0 o_ Definition A null matrix of dimension (nick) is one with every entry 0. ‘ Definition Let Eij denote the (nick) matrix obtained from the (nick) null matrix by replacing just one entry, the ij entry, by 1. Now some solution properties of the equation Ax = y are presented. Let the equation Ax = y be given, where A is (nick) known matrix of rank n.and y is a known vector. ' When solving this equation for x, the following operations will simplify a set of n linear equations without changing the solution set (if any solutions exist): El. Add v times equation j to a lower equation 1 (where j‘< 1). E2. Add v times equation 'j to an upper equation 1 (where j > 1). E3. Multiply equation 1 by a scalar v # 0. E4. Interchange equations i and j. Given the equation Ax = y, it can be written as follows: x (AtY) = O. (1) In actual computations, however, it is much simpler to work with the coefficient matrix (A,y) in (1) when y is a known constant vector. (Thus the matrix (A,y) is transformed to a row echelon matrix by successive elementary operations on rows. These transformations have the same effect on the rows as the operations just described do on the equations. Each operation is effected by a left-sided multiplication by a corresponding elementary matrix, of one of the following types: 9 El. Lower elementary: Add v times row j to lower row 1 Matrix Lij(v) = U + v eij j < 1. E2. Upper elementary: Add v times row j to upper row i Matrix Lij(v) = U - v Eij j > i. E3. Elementary diagonal: Multiply row i by v # 0 Matrix Li(v) = U + (v-—l) 611' E4. Transposition: Interchange rows i and j Matrix Lij = U - Eli - Ejj + E + e Suppose the equation Ax = y is given. Let L denote ij 31° the product of elementary matrices that reduce A to an echelon matrix LA, i.e., l I LlA : Lly C I Lly I LILY]: ———|——" = —-I—-_ , (2) ' l [L2A l L2y _ L0 | L2y-_ where L2A in (2) is the (n-Jlick) null matrix, and LlA = C is a. (ngk) reduced echelon matrix. The following theorem is useful. Theorem 2.1.7 If A is an (nick) matrix of rank IL, and y is (nicl) constant vector, the equation Ax = y has a solution for x if L2y = O in (2). 2399: Since the product of elementary matrices is non- singular, the equation Ax = y has the same solution set as the equation L(Ax-y) = O. Equivalent to the equation lO Ax = y are the two equations: L1(Ax-y) = Cx-—Lly = O and L2(Ax-y) = - L2y = O (see equation (2) L Thus the necessary condition for a solution is L2y = O. Sufficient conditions are L2y = O and Cx = Lly. This completes the proof. Remark: Consider a special case of Theorem 2.1.7 where A is an (n xk) matrix with k s n and IL.= k. In this case C is a reduced echelon matrix of dimension (k){k) and thus C = Uk' It is clear that if L2y = O, then the solution for x is given by x = Lly = (A‘A)-1A'y. 2.2 Description of the System Let an nth order, time-invariant, scalar-control, linear discrete system $6; be governed by the following difference equation: x((i-+1)T) = Qx(iT) + bu(iT), (3) where i = integers O,l,2,....., T = sampling period in seconds, x(iT) = (nicl) state vector at time iT, Q = (nicn) transition matrix, b = (nicl) non-zero vector. The scalar control has the following pre-determined proper- ties: u(t) = constant iT s t < (i-+1)T (4) Iu(iT)| s l for all i. (5) In the subsequent development, the case where x(O) = O is 11 considered for notational simplicity. The more general case when x(O) # O requires only slight modifications. Since the system cf: is time—invariant, no loss of gen- erality will occur if the system is started at i = O of (3). By iteration on (3), x(NT) is given by N-l N-2 x(NT) = i bu(O) + Q bu(T) + °°°°° + A bu((N-2)T) + bu((N-1)T). (6) By defining xN = x(NT), 2i 2 Ql-l b for i = l,2,...,N and u3 = u((N-j)T) for j = l,2,...,N, (6) becomes + x uN-lzN-l + --~-- + ulzl. (7) N : uNZN Definition A control sequence uN = [ul,u2,...,uN] of length N is called admissible if each ui, i = l,2,...,N satisfies (4) and (5). 2.3 Assumption of Complete Controllability It is assumed that the system c1: is completely con- trollable in the sense of Kalman [K2]. This assumption is satisfied if and only if for any integer k > O, the n vectors Zk’zk+l"°°’zk+n—l are linearly independent, where 21 = sl’l b, i = k,k+1,...,k+n-l [B2,K2]. Often a stronger condition than complete controllability is required; thus the following definition is useful. Definition The system ‘1:, is normal in the discrete sense if every set of n vectors z. ,21 ,...,zi with 1l 2 n i 5 il < i2 < -°° < in is linearly independent. 12 2.4 Convex sets, Polyhedra, and Properties of the Reachable Set Some standard definitions and properties concerning con— vex sets, polyhedra, and the reachable set which are needed in the subsequent presentation are given in this section. Definition The set of points Xfic Er1 is said to be convex if whenever two points xl,x2 belong to X, all the points of the form x1X1 T *2X2’ where xl,x2 2 O and Al + x2 = 1, also belong to X. Definition The line segment £(x,y) between x and y is the set of all points of the form ax + By, where a 2 o, p 2 O, and a + B : 1. Definition The convex hull h(Y) of any arbitrary set of points Y in En is the set of points which is the inter- section of all the convex sets that contain Y. Definition A set X in En is said to be 223g in En if for each point x in X, there is a positive number s such that every point y in En satisfying HX-YH < 6 also belongs to the set X. Definition A point x in En is called a point of closure of a set X in En if x 6 X or if for every 6 > 0 there is a point y, y # x and y e X such that Hx-YH < 6. Notation The set of points of the closure of X is denoted 13 by 'X. ‘ Definition A set D in En is closed if D =‘B. ‘Definition If x is in En, then any set which contains an open set containing x is called a neighborhood of x in En. Definition A point x is said to be an interior point of a set X if X is‘a neighborhood of the point x. Definition The difference X‘~ Y is the set of elements in X _which are not in Y. Thus X‘~ Y = {x : x E X and x K Y}. Dgfinition A point x is said to be a boundarygpoint of a subset X of En if every neighborhood of x contains a point of X and a point of C(X) = En ~ X. ' ‘Definition The boundary of a subset X of En, denoted by ex, is the set of all boundary points of X. Definition Let R be the set of states of i; which can N be reached at time N, starting from x0 = O, with an admiss- ible control sequence 'Rh, i.e., d n _ N . -> _ admissible],RN is called the reachable set at time N. It follows that R has the following properties: N .Eroperty 1: RN is convex. £222; Suppose x1 6 RN, x2 6 RN, i.e., N Z i lziui with luil s 1 and X1: 14 X 2 i z 1 Y IIMZ i i with [vi] s 1, Then for O S X S 1, N N Ax + (l-X)x = X 2 z.u. + (l—x) 2 z.y. l 2 i=1 i i 121 i i N - E zihui + <1-x>Y11. By the triangle inequality, |xui + (l-i)Yi| s liuil + [(l-X)Yi| Kluii + (l-X)‘Yi| S X + (l-X) = 1. Hence for O S X s l, Xxl + (l-X) x2 6 RN if xl,x2 6 RN, which implies that RN is convex. Property 2: RN is closed and bounded, i.e., RN is compact. 3329; By the definition of RN, if xN 6 RN, then N xN = iElziui "ull u2 [zl,z2,.....,zn] F211 Zi2 Z1N u1 ui Z21 Z22 °'° Z2N u2 u2 = ‘ ° ‘ = Z ' . (IO) _Zn1 Zn2 ZnN_ _uN] __uNJ Since zi = (211,221,...,zni), i 2 l,2,...,N are given bounded constant vectors, the linear transformation Z is continuous. And since |ui| s 1, i = l,2,...,N, therefore the linear transformation Z in (10) maps the closed unit cube in the control signal space onto a closed subset RN,C En. Since |ui| s 1, i = l,2,...,N, is bounded, it is clear that RN is bounded for N finite. Property_3: R is symmetrical with respect to the origin, N and hence O is an interior point of Ri’ i 2 n. N Proof If x 6 RN, then x : iElziui with |ui| s l for N i = l,2,...,N. Clearly -x = 2 z. (-u.) e R , because 1:1 1 i N |-ui| : |ui| s 1. Since RN is symmetrical with respect to the origin, O is an interior point of RN. Property 4: RN Q'RN-l g'RN_2 ; °°°°' Q'Rl Q'RO, RO is a set containing one single element O, the origin. 16 k —\ n Proof Rk = {x e E : x = E z u., uk = [ul,u2,...,uk] i1il admissible]. n k+l u; Rk+l = {x 6 E : x = iElziui, uk+l = [ul,u2,...,uk+l] k admissible}. Suppose x 6 Rk’ then x = Z ziui with izl |ui| S l for i = l,2,...,k. Take uk+l = O, then k x : iElziui + Zk+luk+1’ which implies that x 6 Rk+1' Thus Rk+l D Rk' By finite induction on k, it follows that RN 3 RN-l N-2 3 °-°-- 3 R1 3 R0. By the assumption that the system J8, is completely con- 3 R trollable, 21 % O Vii. Since zk+l % O, Rk+l # Rk’ for k = O,1,..., therefore RN irRN-l QVRN-212 ----‘:¥ R12? R0. Also since the system 5:. is started from the origin, hence at time O, R0 = 0. Definition A hyperplane in ED is the set H of all points x 6 En such that a'x = B, where a is an (nitl) non-zero constant vector called the normal to H, and B is a scalar. Definition A support hyperplane HS to RN is a hyper- plane such that R lies entirely to one side of Hs and N intersects R in at least one point, i.e., either N a'x S B or a'x 2 B. 17 Theorem 2.4.1 Let a‘x = B be a support hyperplane to RN, N 2 n. Then B > 0 if and only if \/ xN 6 RN, a'xN s B, and s< o if and only if V xN 6 RN, a'xN 2 s. Proof Only the case where B > O is considered; the proof for B < O is similar. 9:;:) Assume B > O. In view of Property 4 of R O E R N’ N' Suppose a'xN > B \/ xN 6 RN. Then a‘O = O > B, a contra- diction. Hence a'xN s B \/ xN 6 RN. (23>) Assume a'xN s B \7/ xN 6 RN. Since 0 6 RN, hence O S B. By Property 4 of RN, 0 is an interior point of RN, hence B S O; for otherwise a'x = O cannot be a support hyperplane to RN. Definition Let a'x = B be a support hyperplane HS to R Then a is called the outward normal to H5 if B > O; N. a is called the inward normal to H5 if B < O. Theorem 2.4.2 Let a'x = B be a support hyperplane to RN. Then la'le S [B] VXN 6 RN. Proof Case 1. B > O. By Theorem 2.4.1, a'xN S B V/xN 6 RN. By the symmetry property of R -x 6 RN, hence N’ N ~a'xN S BVxN 6 RN. It is clear that Ia'le s BVxN 6 RN, if 15> o. (11) Case 2. B < O. Similarly, it can be obtained that Ia'le S—BVXN 6 RN, if B < O. A (12) 18 Combining (11) and (12), it is clear that Ia‘xNI S lB|\/J%JEI1 Definition A point v in R N. is called a vertex if (1) N N v = Z z.u., where lu.| : l, i = l,2,...,N and (2) there i=1 i i i exists at least one support hyperplane to RN with v as the only intersection point. Examples show that points N v = Z z.u., hi.|==].\/i. may be interior points of R ; 1:1 1 i i N hence property (2) is essential. Theorem 2.4.3 Consider the reachable set from the origin at time N, RN, and a vertex v of RN. If a support hyper— plane to RN at v is described by a'x = B with B > O, N v = iEllzlui and [uil = l for i = l,2,...,N, then ui satisfies uia'zi 2 C)N/:i. For B l c1\/in < O, uia'z. s Proof Consider the case B > O. By Theorem 2.4.1, 15 . ax BVXERN (13) Suppose for some k, uka'zk < O. Then a'v - 2uka'zk = a'(v-—2ukzk) = B-2uka'zk. (14) But v1 = v--2ukzk of (14) is in RN, because N N v1 = v-—2ukzk = g ziui - ukzk — .g ziui + zk(-uk), i—l i—l ifik ifik where hxi|==l.N/id This implies a‘vl:> B, a contradiction. 19 Since u a'z < O for no k, therefore u.a‘z. 2 OVi. k k i 1 Consider B < O. By Theorem 2.4.1, if a'x = B < 0, then a'x 2 Bv x E R or equivalently, a‘x S -B Vx 6 RN. If for N) some k, uka'zk > O, then _1 I : _' I _ a v + 2uka zk B + 2uka zk > B. Because v2 = -v + 2ukzk is in RN, hence a contradiction. Therefore if B < O, then uia'zi S O N’i. This completes the proof. Definition A point e in the closed convex reachable set R is an extreme point if there are no two points w, and N y of RN such that e = Xw + (l-X)y, O S X S l (W'% e, y fi-e)- Lemma 2.4.4 Vertices of R are extreme points of RN and N vice versa. £22.91: This part is to prove that vertices of RN are its extreme points. Let v be a vertex of RN and let a'x = B describe a support hyperplane to RN at v. Without loss of generality it can be assumed that B > O. Two cases are considered. Case 1. a'x < B V x 6 RN (see Figure la). Suppose v is not an extreme point of RN. Then there exist two points w and y 6 RN, w # v, y # v such that v = Aw + (l-X)y with O S X S 1. Hence 20 a'v = Xa'w + (1-X)a'y, s i max{a'w,a'y} + (l-x) max{a'W:a'Y}: max{a'w,a'y}: pk a'zk that p k 1 1 1 I l # ukl, and nk2fi uk2. Hence ukla zk I and uk a 2k > n a'z 2 k k for a'zk % O and a'zk # O. 2 2 2 l 2 Thus it is clear from (16) that a'v < B, contrary to (15). Therefore v must be an extreme point. If a'z = a'z = O, the proof given above is not kl k2 valid. However, recall that one of the necessary conditions 21 N for v = 2 u z to be a vertex is Iu. : l, i = l,2,...,N. l i 1 1| Clearly, if there is at least one i such that luil % 1, then v is not a vertex. This argument can be used in the following proof. Again suppose v is not an extreme.point, then there exist two points w and y in RN, w # v, y S v such that v = Aw + (1-X)y with O < A < 1, (17) where w and y are as given above. From (17), v can be written explicitly as N N A Z pizi + (1-X) Z nizi i=1 i=1 <: H N 2 [ Xpi + (l-X) ni] zi. (18) i=1 Since w # y, therefore there exists at least one k3 such that p 2 n . Thus lip + (l-x)n l S Alp | + (l-x)|n l < l, and clearly v is not a vertex. We now prove that the extreme points of R are its N N vertices. Let v = Z Ziui be a vertex with luil = l V’i. i=1 N It is clear that v1 = Z Ziui + kak is not a vertex if i=1 ifik ka| # 1. Then -1 < pk < 1. Therefore there exist two 22 scalars g1 and g2, with 51 < pk < g2 such that vl = Xw + (l-X)y where w : iElziui + glzk and isz N Y = Z Ziui + §2zk. Clearly w # Vl’ y # v1 and i=1 w,y 6 RN. Hence V1 is not an extreme point. Thus the proof is completed. This theorem is valid for any linear systems. The following theorem from Eggleston [E2] is presented here without proof: Theorem 2.4.5 (1) A support hyperplane to the closed, bounded, convex set RN contains at least one extreme point of R . N (2) The closed, bounded, convex set R N is the closure of the convex hull of its extreme points. Definition Let X be any convex, closed and bounded set in En, n 2 2. An egg§_.e_ is a line segment between two vertices vl, v2 of X such that there exists a support hyperplane HS of X satisfying: (1) HS 3.2, (2) HS contains no vertices except v1 and v2. Note: 2,: X. Definition A gage is the intersection of a support hyperplane to RN with RN. Clearly, a vertex is a point and hence a zero-dimensional face, an edge is a one-dimensional face. The largest dimen- sion for a face in En is (n-l). An (n-l)-dimensiona1 23 face in En is a hyperplane which can be described as H = [x 6 En a'x = B}, where a is an (n){l) constant non- zero vector and B a constant. If the hyperplane passes through the origin then B = 0. Only (n-l) independent vectors are required to determine the components of a. Assume N > n. It follows from the assumption of complete controllability that any n consecutive vectors from {zl,z2,...,zN} form a linearly independent set, thus Zl’z2""’Zn-l determine a hyperplane in En. Let ai = [all’al2"'°’aln] and zi = [le’z21""’znl]’ Z2 = [212’222"°"Zn2]"'°’Zh-1 z [Zl,n-l’z2,n-l"'°’Zn,n-l]° If a'x = 0 passes through Zl’z2’°°"Zn-l’ then ( Z11811 + Z21812 + """ T analn : O Z12311 + Z22812 + """ + Zn2aln : 0 ° (19) K Zl,n-—1all + Z2,n-lal2 + °°°°° + Zn,n-laln — 0’ Since Zl’z2""’Zn-l are linearly independent, (19) can be solved for, say, a12,al3,...,aln in terms of all’ i.e., ai = [p11,pl2,...,pln] all’ where pll = 1. It can further be required that this hyperplane aix = 0 pass through a point wl yet to be determined. That is, Pl : [pll’pl2""’p1n]x : [P119912,°°-9Pln]wl- (20) _ 24 'Let n = {l,2,...,N}, Al_= {l,2,...,n-1} and (:(l\ ) = {n,n+1,...,N} = n ~' A . Define w = 2 n z , l 1 l RGCKAl) 1k k where Inlkl = l and nlk[pll’pl2""’pln]zk > O for all k 6 (:(.Al). If there is some j such that [p11,p12,..., j is contained in the hyperplane [p11,912,...,pln]x = 0. Therefore zj can be neglected in pln]zJ = 0, then z. determining wl. Consequently from zl,22,...,zn_l an (n-l)-dimensional face can be constructed which passes through wl and has the following form: [1: Pi2)--°:Pln]x : 51° (20') Division of both sides of (20') by Bl yields 1. 11. £21. _ I [51, 5i’ 51].: - l. (21) For brevity (21) is written as cix = l, (22) 1 p12 pin where C' = _ —'-' ... _ .1 [P1, 51’ ’ Bl ] From (22), two closed half-spaces can be constructed as: P [x 6 En : cix 2 -l} and (23) r emu FHA [x 6 En : cix s 1}. In a similar manner, from zl,zz,...,zn_2,zn,1\2 = {l,2,...,n-2,n},C(/\ ) = {n-l,n+1,...,N}, w = 2 ’0 z 2 2 kEC(1\2) 2k k 25 with |n2k| =1 and n2k[l,p22,...,p2n]zk>0 for k€C(l\2), the hyperplane can be constructed as [1’922’°'°’P2n]x = P2’ where B2 = [1,p22,...,p2n]w2. P P Finally let Cé = [BTU 752—2" 0-0: T522] 9 2 2 2 c'2x= 1. (21+) From (24), two closed half-spaces can be constructed as: F [x 6 En : c'i(2 -1] and 2 NM l\)l—‘ {x E En : c' 23(3 1}. This procedure can be carried out consecutively up to the final step at which I‘; and 1‘2 are constructed from _ N ZN-n+2’ZN-n+3’°'"ZN-l’ZN’ where p — (n-l) , the total number of ways of choosing (n-l) vectors from N vectors. It can be observed that there may exist some (n-l) vectors from {21,22,...,zN} which are linearly dependent. In this case, these (n-l) vectors do not uniquely determine a hyper- plane in En, and they are contained in some hyperplanes which pass through these (n-l) linearly dependent vectors. Definition All the hyperplanes c.x = l and cix = -l, or i in short form |ci3<| = l, i = l,2,...,K, K S , are called boundary hyperplanes of RN. For notational simpli- city, let the total number of the boundary hyperplanes of 26 RN be denoted by K. Thus, given 21's, it is possible to compute boundary hyperplanes of R and hence f E‘s. N, . _ 2 _ O . _ l . Example 2.4.1 Given 2l '[1]’ 22 — [é], Z3 — {—1] s in a - _ - _ N _ 3 _ Figure 2, then N - 3, n — 2, and hence p — n-l — 1 _ . l 2 l 2 l 2 Find I‘l, I‘l, I‘2, I‘2, 1‘3, f‘3. Solution: Let ai = [all,a12], Z1 2 [i] . Then from (19) it follows that 2all + a12 = O i.e., a12 = -2all. Hence ai : [l,-2]all. Now Tr = {1,2,3}, A1 = [l], C(Al) = {2,3}. Define wl = n12z2 + ”1323’ with [n12] = |nl3| = 1. Since n12[1,-2] [g] -4an > 0, hence n12 = -1- Since nl3[1,-2] [_11] Therefore W1 2 -22 + 23 = {2] + £11] = [E3] . 151 = [1.-2][_l3] = 7. 3913 > O, hence n13 : l. 1 -2 1 _ 2 [1 -2] '- — — _ C — — - Let cl -[7, 7] . ThenI‘l {x6 E . 7, ,7 X2 1} and I‘i = {x E E2 : [%3 TE] x s l}. _ _ O . Let aé — [a21,a22], z2 — [2] . Then from (19) it follows that Oa21 + 2a22 = O i.e., a22 = O, and a21 any number. [l’OJa21. 2 O i: :> I\) II {2}, and CL(1\2) : {1,3}. Define w2 = “2121 + n23z3, with [n21| = [n23] = 1. . 2 - Since n21[l,O] [I] = 21121 > O, . . n21 : 1. Since n23[l,O] [EJ = n23 > O, .'. n23 : 1. Therefore w2 2 z1 + 23 = [i] + [:1] z [a] II M >< m E2 : [%,o]x 2 -1} and F [x E E2 : [%,O]x s l}. . , _ _ 1 Finally let a3 — [331’8321’ and 23 — [-l] . Then from (19), it follows that a31 - a32 = O i.e., a32 2 a31. a3 — [1,l]a3l. Now /\3 = {3}. and (:(/\3) = {1,2}. Define w3 = ”3121 + n32z2, with |n3l| = |n32l = 1. Since n3l[l,l][i] = 3n3l > O, ... n31 = 1. Since n32[1,1] [g] = 2n32 > O, ... n32 = 1. _ _ 2 O _ 2 Therefore w - Z1 + 22 — [1:l+ [2] _ [3] . 3 53 = [1 l] [3] Z 5 Let c3 = [%'-%] . Then F % = {x E E2 : [% -%] x 2 -l} and F 3 = {x E E2 : [% '%] x s 1}. It is shown now that the reachable set R is directly 2 ' I related to the sets F g s. 28 . . . _ l 2 _ 1 2 _ Definition Let 01 — I31 0 1‘1, 02 — [‘2 0 1‘2, ..., OK — l 2 I‘K n I‘K. Theorem 2.4.6 For the reachable set at time N, RN, RN : 01 n 02 n ... n Q where Oi, i = l,2,...,K are defined K! above. Proof First prove RN c 01. Any point xN E R can be written as xN : .E Ziui’ |ui| S l, i = l,2,...,N. Hence N 1—1 1 2 ci xN = iElciziui. Since 01 = {‘1 n [‘1’ ci 2i 2 O for i = l,2,...,n-l and 2 n c' z = l where In I = 1 kECAAl) 1k 1 k lk for k €(:(A.l) {n,n+l,...,N}, hence z.u.| S E lu.||c' z I S [c' z I. KECKAl) i l k The last inequality of (25) follows because of Iuil S l, i = l,2,...,N. But where lnlk‘ = l for k E(3(A l). 1 p12 pin Then 2 Ic' z | = 2 n e—u ———3 ..., ———] z k€C(/\l) l k keg/xi) lkl:ijl L51 81 k l l :-—- 2 [1, ’00., ]Z :- 21 (27) [31 keCMl) p12 pln 1‘ I51 51 29 From (25), (26) and (27), it follows that o ' S |cl le l. (28) .. _1 2 .. From (28), it follows that xN E 01 - I‘l n I‘l. By Similar arguments it can be shown that xN E 02,...,OK. Hence XN 6 01 0 02 0 "° 0 UK. Next it remains to be shown that 01 n 02 fl ... 0 OK c RN. N This is equivalent to show that x = Z z.u. { R implies N i=1 i i N that xN E 01 n “2 n ... n 0K. By definition of a vertex v, there exists at least one support hyperplane a'x = B to RN with v as an intersection point, and v satisfies N v = E z.u. with [uil = 1, i = l,2,...,N. Since R is . i 1 i=1 N closed, convex, and symmetrical with respect to the origin, therefore C1 is an outward normal to R and perpendicular N to the hyperplane ci x = 1. By definition, Qi is construc- N ted from Ci x = l, with x = kElzkuk, |uk| = l Vk E C(A i)' For those j 6 Ai’ ci 23 = 0, hence uj can be taken as either 1 or —1. Since there are (n-l) elements in A'i’ 1 hence c! x = 1 actually passes through 2n- vertices. l n-l All of these 2 v's satisfy Ci v = 1, while Ci xN s l V’xN 6 RN. The corresponding symmetrical hyper- . . = _ . 2 _ plane 18 defined by ci v 1, while oi xN lN/XN 6 RN. 30 By Theorem 2.4.5, the reachable set RN is the convex hull of its vertices, thus if xN é RN, then Ick xN| > 1 for at least one k. This implies that if xN S RN, then xN K 0k fl...O D for at least one k. Consequently xN i 01 n 02 K' This establishes the proof. By Theorem 2.4.6, the reachable set from the origin at time N, RN , is described as 01 O 02 fl...n OK, where M O. Then define B1 = [p11,p12,...,pln]wl and p p p ~ Ci = [7%l, —lg, ..., 7&2] . Now for RN+1’ wl = )nlkz k 1 1 1 kechl) T n1.N+1ZN+1 : w1 T T‘1.N+1ZN+1’ Where ln1,N+1| : l and nl,N+l[pll’p12’°..’pln] ZN+]_ > 0' Define Bl : [9119912’°°°: ~ 1 p11 p12 pln] N W Wthh IS the same as — _ — —— _._.. pln] l, p [ B1: 1, 3 R1 1 Pi 11 p12 p1n Clearly -—-= l + | , ———3 , ——— z I — 1 + |§|9 1 [ R1 1 1 ] NTl ~ p11 p12 : l : where 5 cl zN+l Therefore c' [P PlTl+l§17T PlriTTST)’ pln ] T c'. This completes the proof. Pl(lTl§l) 1+|§I 1 Thus in constructing the boundary hyperplanes Icg it is only required to solve (;§2> l x| = l of R N+l’ additional systems of (n-l) linear equations in (n-l) 32 unknowns. All the others are constructed from those |ci XI = 1 of RN by merely a simple translation with an adjustment factor of |§| = |ci ZN+1|° Considerable time is reduced in using this property to construct the boundary hyperplanes |3i x| : l of RN+1 from those |ci x| = l of RN. 2.5 Computation of the Optimal Control ufi The method for constructing R was presented in N Section 2.4, for given zi‘s. For a certain point f 6 En, if f E R and f S R then the optimal control u* can N N-l’ N be found. Theorem 2.5.1 establishes the optimal condition that ufi satisfies. An algorithm for finding the ufi is proposed. Theorem 2L5.1 Given N > n, Zl’z2"'°’ZN and f 6 RN- N-l' * ' - If uN is the value uN such that f uNzN E RN-l and : C . O : - * . |uN| minimum, define fO f uNzN E RN-l' Then f0 15 unique and lies on the boundary of RN-l' Proof (1) Because |uN| > O for uN S O and O for uN = O, its minimum is unique and at uN = 0 if no restric- tion is imposed on uN (see Figure 3). But since it is re- quired that f 2 f0 + uNzN, where f E RN—RN-l and f0 6 RN-l’ therefore uN cannot be zero. It is shown in Figure 4 that ufi is the minimum of |uN| such that f = f + u z . It is clear that if u* is the minimum then O N N N H1 it 1 .T llll. . 33 _ * . . . = * uN cannot be the minimum. For if f fO + uN 2N and : _ * f fO uN 2 Therefore u then f = f which is a contradiction. 0, fi is unique, and hence fO is unique. (2) By the result of (l),|ufi| is the minimum dis- N, tance from f to f - u z (in the direction of z N N N)’ where f - uNzN E RN-l' Since RN—l is a closed convex subset of En and f S RN-l’ hence f0 = f - ufi ZN is on the boundary of RN-l' Let f : fO + UNZN’ where ufi is as defined in u* Theorem 2.5.1. Also let 2% = ufizN, then f 2 f0 + TfigfiN : f0 + YN EN. Define Rfi.= {xN 6 En : xN = :§:Ziui +'ENuN, |ui| s i = l,2,...,N], then f is on the boundary of TRN. Let the boundary hyperplanes of RN be specified by [Ci x| = l and those of RN by ICi x| = 1. Theorem 2.5.2 Let ufi satisfy Theorem 2.5.1, i.e., * ' - uN is the value uN such that f uNzN E RN-l and z . . . . : _ * . |uN| minimum, and f0 13 defined as fO f uN zN UN * : : * ' Also let YN TfifiT’ ZN uN ZN. and let f satisfy 'Cif = 6, where 6 is either 1 or -1. Then Cg f > O if and only if 'Ci fO > O; and similarly 'Ci f < O if and only if Ci fO < O. Proof Consider 6 = 1. Then 'Ci f = l and [Bi is the outward normal to 'RN. Clearly Ci is perpendicular to 34 the hyperplane 'C! x = 1. Since RN22 RN—l and RN contains 1 the origin, hence Ci f > Ci f0. (i) Suppose ci fO > 0. It is obvious that Ci f > Ci fO > O. (ii) Assume Ci f = 1. Since f 2 f0 + YN ZN, thus Ci (f0 + YA ZN = 1- (29) Because TEN 6 RN, thus CE Efi.< 1. From (29), it follows that Ci f0 = 1 - Yfi Ci zN > O. (30) The last inequality of (30) follows because |yfi| = l. The case 6 = -1 can be proved similarly by remembering E: f < C; fO < O. Thus the proof is completed. Remark For a special case of the theorem when f E BRN, then |ufil 2 l and this theorem states: Ci f > O if and only if Ci fO > O; and similarly Ci f < O if and only if Ci fO < O. Corollary 2.5.3 Let the boundary hyperplanes of RN be specified by lCi x] = l, i : l,2,...,K, where K s (PRlY . , . If f 6 RN, f e RN-l’ and f0 6 aRN-l’ then ci f > O if and only if Ci fO > O; and similarly Ci f < O if and only if Ci fO < O. Proof The necessary part is obvious, since f0 6 RN-l % RN, and f 6 RN. Now suppose that ci f > O, then Ci f = C'i(fO + uNzN) > O. (31) But C1 is found such that 35 I uNCiZN 2 O. (32) Equality of (32) holds if CiZN = O. Thus it is Clear from (32) that Ci fO > O. An alternative proof is easily seen by applying Theorems 2.4.7 and 2.5.2. The proof that Ci f < O if and only if Ci fO < O can be carried out similarly. Corollary 2L§.H Let the boundary hyperplanes of RN-l be specified by |gi X| = l, i = l,2,...,K', where N- K‘ s<§_£) . If f 6 RN, f K RN-l’ and f0 6 aRN-l’ then gi f > O if and only if gi fO > O; similarly gi f < 0 if and only if gi fO < O. Proof Only the first half and the sufficient part is proved. Suppose gi f > 1 > O, then there exists a corresponding boundary hyperplane Ci x l of R such that Ci f > O, N g1 . 1+ . , where Ci — W by Theorem 2. .7. Since Ci f > 0, it is Clear that Ci fO > O by Corollary 2.5.3. Consequently gi fO > O. By applying Theorem 2.5.2 and Corollaries 2.5.3 and 2.5.h, the unique ufi satisfying Theorem 2.5.1 can be found by the following Algorithm for Computing ufi Let f 6 RN but f K RN-l’ Assume that the boundary hyperplanes of RN—l are specified by |gi XI = l, i = l,2,...,K', where K' S 1 for at 36 least one i. It is desired to find that gi for which gi(f—-uNzN) = 6 2‘: 1 and further (f-uNzN) E BRN_1, or equivalently g1 f = 5 + (giZNWN- (33) From (33), uN is given as g!f - b H UN 2 W . (3 ) . . . . . * If this uN satisfies (f— uN ZN) e 6RN_ 1’ then it is uN. Proof of the Algorithm Since f 2 f0 + uNZN’ thus gi f = gi(fO + uNzN) = gi fO + u W(g lZN). (35) If gi f > 1 > O, then gi fO > O by Corollary 2.5.#. Take gifo = 1. Since fO is required to be on the boundary hyperplane gi x = l of RN-l’ thus _ _ I 8i f-l+uN(gizN) —1+ 0. (35) From (359, it yields 0 u =——- (36) N (gizN) Similarly, if gi f < -1 < O, then gi fO < 0. Thus Si f = '1 + uN(giZN) ‘ -l + 0‘ (37) From (37) then oI uN :(giz ——)_N (38) After having found uN by either (36) or (38), it can be Checked whether (f—-uNzN) E aRN_l. If indeed (f- uN ZN) E BRN- 1’ then this uN is ufi, the optimal 37 solution. On the other hand, if (f-—uNzN) ( aRN_l, then other gi‘s have to be considered for which Igi f| > 1, until this unique ufi is found such that (f-u§zN) 6 6R Theorem 2.5.5 If ufi 1 xi = kEluKzK e 5R1, i = 2,3,...,N-1, With x1 6 R1 and BB N-l' satisfies Theorem 2.5.1, then XN E N. Proof By Theorem 2.5.1, f0 6 6RN_1. Clearly f0 = X Suppose for some 1 £ 1 suCh that Xi l 6R1. N-l e aRN_l. Then either Xi E R1 or Xi is an interior point of Ri' Xi é Ri is not possible. If Xi is an interior point of R. then x. . is an interior point of Ri+ j = l,2,..., 1’ 1+3 j’ N-i-l. In particular, XN_l is an interior point of This is a contradiction to X R N-l 6 BRN_1. Therefore N-l' for i Z 2,3,...,N-l, X- l 6 8R1, and XN 6 BEN. For all i Z 2,3,...,N—l, X- l E 6R1, it is not required that x1 6 6R1. Actually, 5R1 is Simply the set {21, —zl}. As Figure 5 shows, x2 6 6R2 without x1 being on the boundary of R1. CHAPTER 3 TIME-OPTIMAL CONTROL PROBLEM 3.1 Statement of Time-Optimal Control Problem Given the linear system. 5f; as described in Section 2.2, and a desired target point d 6 En, d' = (dl,d2,..., dn), find the smallest integer N and an admissible control sequence 'fiN = [ul,u2,...,uN] such that d 6 RN, i.e., - ulzil + u2212 + ~-- + uNziN 2 di’ i = l,2,...,n (1) |uj| s l, j = l,2,...,N (2) where di is the ith element of d, and zij is the ith element of 2. J. Observe that equation (1) can be rewritten in several equivalent forms: zlul + 22u2 + ----- + zNuN = d, (3) — .1 — ‘T r- - Zii Zi2 °°° ZiN ui d1 Z21 Z22 Z2N u2 d2 . Z . 9 (1+) _an Zn2 "° ZnN‘ LPN_ _dn‘ 39 Zuzd: (5) where Z = (21’22"'°’ZN) is an (nicN) constant matrix. It can be shown [D4, H6, Kl] that for unstable systems, a solution exists for (1) and (2) while for stable systems, a solution exists for very limited cases. .;Consider the last n columns of the matrix Z. Then it can be asserted that : l. The last n columns of Z are linearly independent, and thus form a basis for the n- dimensional state space. 2. The matrix @N becomes un- bounded when N ~ a for an unstable system. From the preceding two statements, it is a simple matter to conclude that an unstable system witnarbitrary constraints can always be steered to any desired terminal state d, “<1“ < O, by choosing as control policy zero controls for the first N-n members and some appropriate control signals for the last n members for N sufficiently large. On the other hand, only a sufficiently small region around the origin can be reached by a stable system starting from the origin. 3.2 Solution Properties and Computing Algorithm for Time- .Optimal Control Problem Because a direct method to find the minimum control time required is not available, a systematic iterative process is employed. smallest integer 1. The computer problem proceeds Phase 1. For N u? Let N = 1, If the answer is the answer is in repeated. N s n. If N = Phase 3 is initiated. has to be found for which (5) is satisfied. there is a solution for Let convert Z n and d ( RN, HO To ensure that the N found is the such that d 6 R N is set initially to N) algorithm for the time-optimal control in four phases as is illustrated by Figure 6. s n, does Zu = d for some (N}(l) vector does Zu = d for some (NJ(l) vector u? in the affirmative, Phase 2 is started. If the negative, set N = 2 and Phase 1 is This process is carried out iteratively for then set N = n + 1, and In Phase 1, the minimal integer N To see whether Zu = d, Theorem 2.1.7 can be employed. L denote the product of the elementary matrices that to an echelon matrix (6) If L2d # O, then there is no solution for ui, i = 1,2,..., N such that increased by 1 repeatedly. If set equal to (5) n + l is satisfied. In this case, N is and Phase 1 computations are carried out is L2d # O for N = l,2,...,n, then N and the calculations are done in #1 Phase 3. If for some N s n, L d = O, then Phase 2 calcula- 2 tions are performed to find the unique ui's for which (4) is satisfied. Phase 2. Compute u = le, is u admissible? If the control sequence u = le found is admissible, then the time-optimal control problem is solved and the unique optimal control is fifi = u. However, if u is not admissible, then Phase 3 is started. Following the assumption that the system :13, is completely controllable, the N vectors 2i 2 Qi-lb, i = 1, 2,...,N s n are linearly independent. Therefore it is obvious that the control sequence is unique and is given by C-lle = le, where the ith component of le corresponds to ui. Now it is clear whether this control sequence is admissible. Suppose the control sequence is not admissible, then the desired state d cannot be reached in less than or equal to n sampling periods, as the following Lemma 3.2.1 shows. Thus Phase 3 has to be considered. Lemma 3.2.1 Let d 6 En, and ul"zl + u2"22 + ~-- + uk"zkm= d with k s n. Then there exist no ui's satisfying ulzl + u2z2 + + ukzk + uk+lzk+l + --- + unzn = d, where ui" # ui for i = l,2,...,k. Proof Assume the converse is true. Then 3' ' o o o : u"zl + u222 + + u"zk d (7) M2 and ulzl + u222 + ~-- + ukzk + uk+lzk+l + ... + unzn = d. (8) Subtract (7) from (8), then (ul-u£)zl + ... + (uk-ug) + uk+lzk+1 + ... + unzn : 0' Since Zl’ZZ""’Zn are linearly independent, hence ul 2 uf, u2 2 ug, ..., uk = ufl, and uk+l = O, ..., un = O. This completes the proof. Remark: For N = n, Z has an inverse. Thus u = Z.1 d can be obtained directly and Checked whether it is admissible. It has been established in either Phase 1 or Phase 2 that N s n is not the minimal time. The calculations to find the minimal time N and the corresponding optimal control for N > n are considered in Phases 3 and H. For the case when N > n, it has been shown [H6] that there exists either a unique or an infinity of control sequences to the time-optimal control problem. The calculations in Phase 3 will indicate whether the control sequence is unique or not. Phase 3. For N > n, is d 6 RN? By Theorem 2.4.6, RN 2 01 2 n K' d K RN if and only if d K Oi, for at least one i, where n O . n 0 Thus 1 s i s K. Since 0i = {x 6 En : lei x| s 1}, to find whether d K Oi, or equivalently d K RN, it is only k3 . necessary to check whether lei d| > 1 for some i. If d‘K RN, then N is increased by l, and check whether d 6 RN, etc. The procedure can be continued up to a certain H, such that d e R If. d 6 RN, this algorithm will indi-' N. cate whether the control sequence is unique. As is shown in Theorem 3.2.2, any point d e aRN with N > n corresponds to a unique optimal control sequence. Thus if d é RN, and if |c3d| = l for at least one 3, then d 6 BR and the N) optimal control sequence is unique. If d 6 RN, and the solution for control is not unique, then Phase M has to be started. .a Ehase H. Find uN for which |u = minimum, and the NI algorithm.terminates. when an infinity of control sequences exists, it is desirable to choose, among those which satisfy the minimum- time, a unique control sequence which also minimizes luNl, where uN = u(O) is the first member of the control sequence. In a more compact form the problem can be 'stated as : to find min [luN|}, ' (lo) luulsl where d =dO + uNzN, d0 6 RN-l Minimization of (10) can be obtained by directly applying Theorem 2.5.1; the solution is unique as is shown in 44 , Theorem 3.2.4. Let f = d, and f0 = do, then f0 6 BR As proved below in Theorem 3.2.2, f0 6 aRN_l control sequence, and thus the time-optimal control problem N-l' has a unique is completely solved. Theorem 3.2.2 'For a linear normal system a point r E §RN corresponds to a unique control sequence A uN a [ul,u2,...,uN].. Proof Suppose f is on the hyperplane Ci x = 1, i.e., ci’f = 1. From the way C1 is constructed, there are n-l vectors 23’ j e C(Ai), such that ciz3 = O; and there - ' are N n vectors zm, m 6 Ai, such that cizm K'O. For those 2m with cizIn # O, the corresponding control is suCh that luml = l and umcizm > 0. Therefore these N-h controls with magnitude unity are determined and unique. oh the other hand, when Cizj = 0, j e C(Ai), these controls uj are not specified. However, any set of n vectors from {21,22,...,zN} forms a linearly independent set in En. In particular, 23, j 6 (:(Ai), is a linearly independent set. Since + 2 z u = d, thus 2 2.11 J€C(Ai) J 3 meAi “1 m :d- 2211. (ll) 2 z.u. JGCMi) J J men1 m m Solution of (11), i.e., determination of uj, j E (3(Ai) is guaranteed by the linear independence of 23, j e C(Ai), 45 and the solution is unique. Therefore it is concluded that corresponding to a point on the boundary of R the control N’ sequence is unique and has at most (n-l) members with magnitude less than unity. Corollary 3.2.3 A point f e aRk, k = N-l, N-2, ..., n+1, corresponds to a unique control seuqence 3k 2 [ul,u2,...,uk]. Theorem 3.2.4 The solution to (10) is unique. Ergo; Two different situations will be considered. (1) When d = f 6 BEN. This is proved in Theorem 3.2.2. (ii) when d = r K aRN, but d = r e R and d = r K R N N-l' Minimization of (IO) is obtained by applying Theorem 2.5.1. Since the minimal uN, ufi is unique for (10), then * = * 2 O + uN ZN (:10 + uN ZN, where (:10 f0 6 aRN_l. By Corollary 3.2.3, the optimal control sequence is unique. d = f = f This completes the proof. CHAPTER 4 TERMINAL-ERROR REGULATOR PROBLEM 4.1 Statement of Terminal-Error Regulator Problem The system considered is the one described in Sec- tion 2.2. It is desired to determine a control sequence Rh = [ul,u2,...,uN], |uil 3,1, l s i s N, such that the scalar quantity P = (d-XN)'Q (d-XN) (l) is minimum, where d is the desired terminal state of the system, Q is an (nicn) positive definite metrix, and the terminal time N is given in advance. It is well known [01] that any positive definite matrix can be decom- posed into the product of the transpose of some (nicn) matrix w and itself, i.e., Q = w'w. By a change of variable, w = wx, P becomes P (wd-WN)'(wd-WN), (2) where wd = Wd and wN = WX from (2) that no loss of generality will occur if the N' Consequently, it is Clear original matrix Q in (1) is assumed to be the identity matrix Un' Since the reachable set RN is compact, it is Clear that there exists a unique point x such that N (l) is minimum. However, there may be several control 46 L+7 N' The solution properties and A computing algorithms for generating xN and some uN are considered separately depending upon whether n > N or sequences which generate x n s N. 4.2 Solution Properties and Computing Algorithm for the Terminal-Error Regulator Problem; n > N It is shown that the terminal-error regulator optimal control sequence must exist and is unique. Moreover, the procedures for finding the optimal control sequence are described thoroughly. Given the terminal time N, let Z be defined as Z = (z ,22,...,zN), an (nicN) matrix whose columns con- 1 sist of 21,22,...,zN. By the controllability assumption of the system 36, , the vectors 21,22,...,ZN with N s n are linearly independent, and therefore r(Z) = N. From Theorem 2.1.4, Z'Z is non-singular and its inverse exists. Let G = Z(Z'Z)-lZ'. For any vector d 6 En, the vector Gd is a projection of d on A which is the N, subspace spanned by 21,22,...,zN. These results follow. from Theorem 2.15 and Theorem 2.1.6. Cases Gd 6 RN and Gd K RN are considered separately. Case 1. If Gd 6 R then the optimal control N! sequence is unique. This is a consequence of the remark following Theorem 2.1.7. 48 Case 2. If Gd K RN, the optimal control sequence is also unique, and a point x E R can be found such that N N Hd-xNH is minimum. Since Hd—XNH2 = Hd-GdH2 + HGd-xNHZ, where Hd-Gdll2 is a fixed number for given G and d, thus HGd-xNH2 is minimum implies that Hd-xNH2 is minimum. The problem then becomes finding a point xN 6 RN such that HGd-xNH2 is minimum. As has been described, for both cases Gd E RN and Gd K RN the optimal control sequence is unique. The procedures for finding the optimal control sequence are presented now. Given the terminal time N s n, and the desired terminal state d, then Z = (21,22,...,ZN) and G = Z(Z'Z)—lZ' are well-defined. To check whether Gd 6 R or not, Theorem 2.1.7 is employed. Apply elemen- N tary transformations to convert (Z,Gd) to an echelon matrix, then I I LlZ | LlGd C ' LlGd L(Z,Gd) = ““7"" = —-.--— . <3) L2Z | L2Gd O l L2Gd If L2Gd = O in (3), then Gd 6 RN. Also C = LlZ = U. The unique optimal control sequence is given by (LlZ)-1L1Gd = C-lLlGd = LlGd, where the ith component of LlGd is ui, i = l,2,...,N. On the other hand, if 49 L Gd K O, then Gd K RN. In this case, a different approach 2 is taken to implement the optimal control sequence by using Gram-Schmidt orthogonalization process. As a consequence, the problem becomes an equivalent one where the dimension n is reduced to N. Since 21,22,...,ZN are linearly independent, they can be converted into an orthogonal set in En as is illustrated in the following: [’21 ~ E1 2 21 2 ~ 3 - + a 2 82222 lel 2 = a z + a E + a E (4) 3 33 3 32 2 31 l k_zN e ZN : aN,NZN + aN,N-lZN-l + --- + aN,222 + aN,lzl’ where 31’32’°"’EN are mutually orthogonal. Clearly, other orthogonal sets are also available but will not affect later computations. From (4) it follows directly that So a2l~ 1 ~ 2 : ~——— 2 + ——— z _ im~ i32~ _1_~ Z __ Z — Z + Z (5) 3 833 1 833 2 833 3 a a — N’l ~ _N.z_‘_2.~ N:N-1 ~ 1 ~ Z —- Z - Z - coo - ——— Z + Z 0 Observe that 31,32,...,EN is a basis for the subspace spanned by 21,22,...,zN. If 21,22,...,ZN are expressed as linear combinations of Ei,§2,...,E as in (5), then the N coefficient matrix is [yl,y2,...,yN]', where {Yi : (1,020-010) a _ 21 l Yé — (- a22, 822’ O, coo, 0) ( ° (6) y. : (- aN 1’ - aN 2 o o o "' aN,N-l l )0 K N a a ’ ’ a ’ a N,N N,N N,N N,N Using the correspondence between 21 and yi, i : l,2,...,N, then the reachable set at time N from the origin, namely, nfvnz _ n . _ RN — {XN 6 E . x — N z.ui, |ui| s l, i==l,2,...,NJ, l i l (7) 51 can be converted to yiui, luil s l, i:=l,2,...,N}. (8) Now a similar expression can be found for Gd. Applying trj N2 ll IIMZ i 1 Theorem 2.1.5, Gd = 2(2'2)‘lz'd = (21,22....,ZN)(Z'Z)’lz'd = dlzl + d222 + --- + szN, (9) where Hi 2 the ith component of (Z'Z)-lZ'd. After some simple algebraic manipulations, Gd can be shown to corres- pond to yd = dfyl + d”y2 + °°° + dfiyN- (10) Note that the dimension of yi's in (6) is N. Then the problem becomes: given yl,y2,...,yN, and the terminal 6 R state yd, find a point E and the corresponding N N control sequence such that Hyd - xNHZ = minimum. This equivalent problem has n = N and thus can be solved by the procedure of the next section. 4.3 Solution Properties and Computing Algorithm for the Terminal-Error Regulator Problem; n 5 N Now the case when n s N is considered. In the case where the desired terminal state d lies outside the reachable set RN at time N, then the optimal control sequence is unique and P > O. When the desired terminal state d is an element of R it is Clear that x = d, N’ N 52 P = O, and the optimal control sequence is, in general, not unique. Case 1. P = O. The determination of the smallest m such that d E Rm and d E R is the time-optimal control problem which can m-l be solved by the algorithm in Section 3.2. Therefore an effective procedure for the terminal-error regulator problem with n s N can begin by using the algorithm of Section 3.2 subject to m s N. If d K RN, then P > O and Case 2 is used. If d e R then P = O and the time-optimal solu- N9 tion m satisfies m s N. If m = N, then the time-optimal A A control sequence um equals uN, the terminal-error regula- A tor optimal control sequence. If m < N, then uN : [ul,u2,...,um,O,O,...,O], i.e., the last (N-m) members of .5 UN are zero. Case 2. P > 0. Clearly P > 0 if and only if d K RN. Since d K RN, 2 N e aRN has to be found such that Hd-xNH is minimum. From Theorem 2.H.6, RN = 01 2 n is contained in the hyper- a unique point x n 0 °°° fl 0 K, and thus the boundary of RN plane specified by ci x = 6, i = l,2,...,K where 6 = :_l and K s (n§1)' Obviously, x is an extreme point (i.e., N vertex) of R or is contained in the intersection of at N most (n—l) hyperplanes: ci x = 6. The problem of finding 53 such that Hd-x is minimum can be solved in three 2 XN 6 RN NH parts. 1. Verification of vertex of RN Recall that v is a vertex of RN if i) v = a- z. 111’ IIMZ i = l, i = l,2,...,N and ii) there exists at least one support hyperplane to RN with v as an intersection point. By Theorem 2.H.6 \/ x 6 RN it is true that |ci x| s l, i = l,2,...,K, where K ‘ (nN l) and ci x = 5 are the boundary hyperplanes as defined previously in N Section 2.H. It is obvious that if v = 2 aizi satisfies i=1 i) and |cj v| = l for some 3, then v is a vertex of RN. 2. Determination of a closest vertex of RN to d The procedure described below permits finding one of the closest vertices of R to d. It can be observed that N there may be several different vertices of RN with the N smallest equal distance to d. Let v(l) 2 ai(l)zi be i=l By changing signs of some of the con- ~ N~ V(l) : 2 a (1)2. . l 1 1:1 any vertex of R N. (l) trols ai , a new vertex can be found. Compute Ild-V(l)|12 and lid-(l)||2 Ir \ld-v(l)||2 Hd-v(l)H2, then set v(2) = v(l); if Hd- v(l)n2 > Ha -(1)H2, V(2) ~<1>° then set : v Thus it is clear that Hd-v(l)||2 2 Hd-v(2)||2 . In a similar manner 51+ ..., etc. can be found and they satisfy ';(2);v(3);;(3),v(4), Hd-v(2)u2 2 Hd-v(3)u2 2 Hd-v(h)u2 2 ..., etc. Since vertices of RN are finite in number, it is evident that the process will terminate in a finite number of steps and determine one of the closest vertices of R to d. N 3.. Determination of the optimal ui's satisfying |ui| s 1 Observe that the point x 6 RN satisfying “d-XNHZ = N minimum is contained in a zero-dimensional face (i.e., vertex), one-dimensional face (i.e., edge), two-dimensional face, ..., or (n-l)-dimensional face of R Consider N. Fd = d-v, where v is determined in part 2). Let J = {J 3 (Fd’ajzj) < O} z {j :(anjzj) > (d,ajzj)}. The following theorem is useful in identifying which members of the control sequence obtained in part 2) can be modified to yield smaller length of d-x for some x 6 RN. Theorem H.3.l Let v = 2 “121’ [ail = 1 be a vertex of i 1 RN which is one of the closest to d. Let d be the desired terminal target point and d é RN. If there is a k such that (d-v,akzk) < 0, then there exists a point x 6 RN such that Hd-xH < Hd-VH- N Eroof Let x = 2 i=1 L£k squared lengths of d-v and d-x can be computed: 012. l + akzk, where ak fi'ak. Then the 55 2 N 2 N Hd-vH : HdH2 + H iZlaiziH - 2(d,akzk) - 2(d, wild Zi) i£k ifk 2 N + HQKZKH + 2(asz’ 'Elaizi) (11) i- iz—[k 2 N N Hd-XH = udn2 + n 21a fin - 2 ifik ifik ~ 2 ~ N + Hakzkn + 2(akzk! .Zlaizi) ° (12) 1: 1%}: To compare Hd-vH2 and Hd-xH2, their difference is taken: nakzkn2 - HEHZKHZ N + 2(aka " akzk’ izlaizi - d) (13) Mi nd-vn2 - nd-xn2 nakzkn2 - HEKZKHZ + 2(akzk - Ekzk’ v-d - akzk)' (14) Equation (14) can be examined more closely by assigning either (1k = +1 or “R = —l. Consider GK = +1. It is clear that x 6 RN if ER is substituted for 3k in (1%), then ua-vn2 - Hd-XH2 = 2O by hypothesis, there always exists an 56 2 2 ~ 6 such that Hd-xH < Hd-vH . Clearly ak e [-l,l). For “k = -l, it is also true that there exists at least one 3k E (-l,l] such that Hd-xH2 < Hd-VH2. This completes the proof. As demonstrated in Figure 7, 3k can be taken to be xak, O < x < l, to improve the minimum squared length of Fd' It follows from the previous theorem that if J is empty, then the v found in part 1) is xN, which is the intersection of some n boundary hyperplanes c! x = 6 of 1 RN, and clearly the optimal control sequence is given by [al,a2,...,aN]. If J has one element, then xN is the intersection of some (n-l) boundary hyperplanes of RN. In general, if J has k elements, then XN is the intersection of (n-k) boundary hyperplanes of RN. Now it is shown that J can have at most (n-l) elements. Obviously the closest vertex v to d is contained in some (n-l)-dimensional support hyperplane, say, oi x = 5. Since 03 x = 6 is a support hyperplane, then from Theorem 2.h.3 uJ satisfies ujcizJ 2 O for 6 l and ch'izJ s O for 6 = -l, J = l,2,...,N. But cizj = O for exactly (n-l) 23's (see Section 2.h) and cizJ # O for (N-n+l) zj's. Thus those controls uJ corresponding to ujcizJ # O are fixed at 1,1 and the (n-l) controls uJ corresponding to cizJ = O are not specified. If there are more than 57 n elements in J then this implies that the v found in part 1) is not on the hyperplane ci x = 6. This is a con- tradiction. Hence it can be concluded that J has at most (n-l) elements. Let jl,j2,...,jk,k S n-l, denote the elements of J. Then the original problem becomes determination of u.j ,uj , l 2 N ...,u. such that Hd - 2 aizi - 23 u. 2. H2 = minimum, 3x i=1 jieJ 31 31 15.1.1 subject to the admissibility conditions on u. , i.e., i |uj \ s l for all ji' This problem can be solved by using i the algorithm in Section h.2, with the new desired terminal N state replaced by d - iElaizi. iiJ To summarize, the following is sketched: Given the terminal time N, with N 2 n, and the desired terminal state d, if d 6 RN, then the control is, in general, not unique. In order to have a unique optimal control sequence, an additional requirement that uN be minimum in absolute value is associated with the control sequence, as has been solved in Section 3.2. If d f RN, then the scalar quantity P = (d-xN)'(d-xN) > O and the optimal control sequence is unique. In this case 58 xN is on the boundary of RN. It has been shown that xN may be on one of the boundary hyperplanes or at the inter- section of more than one boundary hyperplanes of R A N. method is presented to find the unique point x E R N N and the corresponding optimal control, which avoids solving the quadratic programming problem. The computer algorithm for the terminal-error regulator problem is illustrated in Figure 8. CHAPTER 5 SUMMARY AND EXTENSIONS Some important features of the computing procedures described in Chapters 2, 3, and 4 are summarized in Section 5.1. In Section 5.2 certain possible extensions of these results are depicted. 5.1 Summary This section contains brief summaries of the computing procedures developed in Chapters 2, 3, and H and some of the more prominent properties of the algorithms. In adiition, a refinement which is useful for calculating the vectors is c. which describe the boundary hyperplanes of R 1’ N’ included in part (iv). This often saves computational time for both the time-optimal and terminal-error regulator problems. (1) Determining whether d e R or d 1 RN. N In this dissertation a simple algorithm is proposed for determining whether a given point d 6 En is in RN. Depending upon whether n 2 N or n < N, two different algorithms are considered. Case 1. n 2 N. Let Z = (21,22,...,zN) be an (nicN) matrix. By performing row operations (see Section 3.2, Phases 1 and 2), 59 6O (Z,d) is transformed to an echelon matrix: L12 : le c { le L(z.d) - -—-1--- = ——:—-- , L22 | L2d O l de . I'1 where L = -- is the product of elementary matrices. If L2 de.= O, and furthermore u = Ll d 6 RN' If L2d f'O or if L2d = O and u = le is not d is admissible, then admissible, then d Z RN’ When de = O and u = le is not admissible, it is also true that d f Rh' gase 2. n < N. From.Theorem 2.h.6, the boundary of R consists of N subsets of 2K1 hyperplanes Of the form oi x = 6, 6 = :_l. The (nxl) vector c1 can be determined by solving K s (nEl) systems of (n-l) simultaneous equations in (n-l) unknowns (see Section 2.h). Then d 6 R if and N only if Ici d] i 1, i = l,2,...,K. (ii) Properties of the Algorithm for Time-Optimal Control Problem . 1 The calculations in (i) can be performed sequentially for N = l,2,..., etc. to determine the smallest integer N such that d 6 RN. This N is the optimal time. If n 2 N; the time-optimal control sequence exists and is unique. 61 th Moreover, it is given by le, where the i component of le is ui, i = l,2,...,N. If n < N, the time—optimal control sequence either is unique or has an infinite number of solutions. If the control sequence is unique, then there are at most (n-l) controls with magnitude less than unity. If the control sequence is not unique, an additional re- quirement that uN be minimum in absolute value is imposed. In this case, the resulting optimal control sequence is unique and has at most n components with magnitude less than unity. (iii) Properties of the Algorithm for Terminal-Error Regulator Control Problem In the terminal-error regulator problem the terminal time N and the desired terminal state d are given. The Optimal control sequence is the one which minimizes the 6 R scalar quantity: P = Hd-xNH2, where x Two cases N N' are considered for n > N and n s N. Case 1. n > N. If n > N, the optimal control sequence for the terminal- error regulator problem is shown to be unique. Furthermore, 1 it is given by LlGd if Gd 6 R where G = Z(Z'Z)- Z', N, and z = (21,22,...,zN). If Gd z RN, then the optimal control sequence can be found by employing the Gram-Schmidt orthogonalization process to reduce the problem to an 62 equivalent one with lower dimension. Then the method of Case 2 is used. Case 2. n s N. For n s N, if d e 6R then the optimal control N sequence is unique. If d 6 RN but d ¢ BRN, then P = O and the problem becomes the time—optimal control problem considered in Section 3.2, Phase 3 and Phase k. If d K RN, then P > O and the optimal control sequence is unique. The algorithm which is proposed requires computa- tion of the C1 which describe the boundary hyperplanes of R but avoids solving the corresponding quadratic N) programming problem. (iv) Construction of Boundary Hyperplanes for R from N+l Those of RN In part (i) case 2 and part (iii) case 2 it is re- quired to calculate the ci which describe the boundary hyperplanes of R The boundary hyperplanes of RN+l are N' also needed frequently and computational time can be saved by computing them indirectly from those of R It may be N. recalled that the direct computation required solving (Eti) systems of (n-l) simultaneous equations in (n-l) unknowns. All the subsets of the hyperplanes which constitute the boundary of R will be subsets of the boundary hyperplanes N of R by a simple translation: N+l 63 If subset of |ci xl = l is one of the subsets of the boundary hyperplanes of RN, then l?! XI = I l xl = l 1 l+|§l is the corresponding subset of the boundary hyperplanes of R z N+l’ where g : Ci N+1° The new subsets of the boundary hyperplanes of RN+l’ i.e., those which cannot be obtained by a translation from subsets of the boundary hyperplanes of RN, can be calculated by (n-l) vectors, which consist of z and (n-2) vectors N+l from {zl,zz,...,zN}. Thus the total number of subsets of the boundary hyperplanes of R N+l). N+l is 2[1 - 2( It is clear that at each step from R to R N N+l’ subsets of the boundary hyperplanes of RN+1 can be obtained by solving only (ng2) systems of (n-l) simultaneous equa- tions in (n-l) unknowns and (HH 1) simple translations. 5.2 Extensions In chapters 2, 3, and 4 two basic control problems are examined. There are a number of extensions which can be con- sidered. The extension to a higher-dimensional control signal is of primary importance. Other various extensions are briefly investigated. (i) Alternate Control Constraints Given by |u.| 5 mi 1 The actual constraints on the control signal, luil S l, 6% i = l,2,...,N, have been fully utilized to construct the boundary of R When the constraints are given in the form, N' lui‘ 5 hi, i = l,2,...,N, the construction of the boundary of R presents no difficulty at all. In fact, if 21 is re- N placed by nizi for all i, then the method presented applies without any modifications. (ii) Target Sets Given in the Form of x'Sx 2 B Let the target set x'Sx 2 b be given, where S is an (n)(n) symmetric positive definite matrix and p > O. By the well-known result of matrix theory [01], S can be written as S = w'w. By a change of variable, w = WX, the form of the target set can be rewritten as: w'w = HwH 2 B. Hence without loss of generality S can be assumed to be an identity matrix. If x(O) = x = O, the time-optimal control 0 problem is to find a point xN 6 RN and to find the corresponding control sequence. Because of such that HxNH2 2 p the symmetry of R and the convexity of the set x'Sx S b, N it is clear that when N is the minimum time the sets RN and x'SX 2 B will intersect at a finite number of vertices or at an infinite number of points (see Figure 9). In any Case controllability implies that there exist N and a vertex v 6 RN such that v and -v are solutions. Thus to get a solution, the vertices of R can be computed N using part 1) of Section h.3 for each choice of N = l,2,..., 65 etc. The control sequence is easily implemented (see Theorem 3.2.2). (iii) Target Sets Which Are Time-Varying Consider target sets xg,(i) : x'S(i)x 2 hi, i = l, 2,..., etc. In this case the analysis in part (ii) is modified to consider for each N the set (£(N), etc. Figure 10 illustrates an example where the optimal time N is #. (iv) Time-Varying Linear Discrete Systems It is assumed that the system to be considered satisfies the following difference equation: x(i + 1) = ©(i)x(i) + b(i)u(i). Note that x(i) can be written as x(i) = w<1>x + tuilxu(j-1>, J: where Y(i) is an (nicn) matrix with Y(i+1) : ¢(i)Y(i), Y(O) = U. Also note that Y(i) : @(i-l)-®(i-2)°°°°¢(O) and l . (J) ww' ¢-¢--°¢<0)-¢‘1 3. By defining 2i 2 Y(N)Y-l(i)b(i-l), i = l,2,...,N, u1 = u(i-l), i = l,2,...,N, xi = x(i), i : O,1,...,N, then xN = Y(N)xO + Zlul + z2u2 + ~---- + The time-optimal zNuN. control problem is to find a point x 6 R and a correspon- N N ding control sequence such that XN = d, the desired terminal 66 state. This problem is essentially the same as the one consid- ered except now zi's, i = l,2,...,N are time-varying and for eacn N, zi's have to be recalculated. The same results apply to this time—varying system. (v) Systems with Variable Sampling Instants Consider the linear system governed by the differential equation: x(t) : Qx(t) + bu(t). The solution is given by t x(t Y(tN) [x(O) + g NY(—s)bu(s)ds] N) N-l t. Y(tN) [x(O) + 2 I 1+1Y(—s)dsbu(i)] , ° 0 t. 1 l: @tN where Y(tN) = e , u(t) = u(i), ti S t < ti+l° ti Let zi : Y(tN) f Y(—s)dsb and ui : u(i-l), i = l,2,...,N. ti-l Then N x(tN) = Y(tN)x(O) + .2 Ziui' (1) 1—1 Thus (1) is the same equation as (11) of Section 2.2 with @N replaced by Y(tN). It is clear that the algorithms can be applied to systems with variable sampling instants. All the 2i and Y(tN) have to be recalculated for each N. (vi) Linear Discrete Systems with the Initial State xO % O If xO fi O and d is given, translation of coordinates Such that xO becomes the new origin yields the formulation 67 of Chapter 2, and all the algorithms apply (see Figure 11). (vii) Multi-Input Control Systems For multi-input control system, the construction of RN presents no real difficulty, although it is more complicated than in the single-input system. However, further constraints are necessary to insure that the control sequence is unique. The following considerations are important. Let the multi-input control system be governed by the following difference equation: X((i+l)T) = @X(iT) + BU(iT), (2) where B = (n)(m) constant control matrix with columns bl’b""°’ bm’ where m S n, u(iT) = (micl) control vector with components ul(iT),u2(iT),...,um(iT), and i, T, 2, x(iT) are the same as previously defined. The control has the following pre-determined properties: uj(t) = constant for j = l,2,...,m iT S t < (i+l)T (3) Iuj(iT)| s 1 for all i and for j = l,2,...,m. (R) It is assumed that the system is completely controllable [K2]. The system is completely controllable if and only if r[§n_lB,¢n-2B,...,®B,B] = n [B2]. By iteration on (1), x(NT) is given by 68 x(NT) = QN_lBu(O) + §N_2Bu(T) + --~ + éBu((N-2)T) + Bu((N-1)T) (5) or in matrix form _u(O) x(NT) = [éN'lB,¢N‘ZB,...,¢B,B] u(T) <6) u((N-2)T) Lu((N-1)T)_ . By letting xN : x(NT), 2% : @l-lbj, for i = l,2,...,N, j = l,2,...,m and ui = uJ((N—i)T) for i = l,2,...,N, J = l,2,...,m, (H) becomes _ l l 2 2 ... m m m m l l ... m m uNzN + + uNzN. (7) Definition The reachable subset from the origin at time N is defined as . . k R @Y = {x 6 En x = Z 2 ugzq + 2 u z , N 121 3:1 1 l kzl N N lui| S l \/ i and J}, _ m where l s y s m and N 2 1. Clearly RN — ®N-1 . It is clear from the above definition that given N and Y y, 1 S y S m, the construction of ON does not present any difficulty. In the time-optimal control problem, for any desired 69 terminal state d with HdH < m, there exist Y and N such that d E OE and d.e @fifl, where 2 S y S m. If Y = m, and d E BOH then the time-optimal control sequence is m N control is, in general, not unique. In this case, the time- unique. If y < m, or y = m but d K BO then the optimal optimal control sequence is defined as the one with |u§| = minimum and ug = O, 3 = y + l, y + 2, ..., m. All the above extensions require only slight modifications of the algorithms in Chapters 2, 3, and H. For non—symmetrical constraints on the control or target sets which are non- symmetrical considerable modifications are required and they are not treated here. Another problem in which it is difficult to extend the algorithms is: initial state xO # O, target set kfi : x'Sx S B. Several configurations which may arise in this problem are illustrated in Figure 12. 'CHAPTER 6 NUMERICAL EXAMPLES AND CONCLUSIONS The study of control of a system with a discrete model is of value in its own right because of the close relation of such models with various physical, biological, and socio-economic processes [K5]. In some cases, a physical system is modeled by an ordinary differential equation whose solution is assumed to approximate the actual evolution of the system. .In general, the continuous system with differential equation model is solved on a digital computer, which is in fact a process of discrete approximation to the continuous problem. In the following examples, the first two are given as discrete models and the remaining four as continuous models. The continuous ones are approximated by a corresponding discrete version for computational purposes. Consider the system governed by the vector differential equation: x(t) = A x(t) + D u(t), (1) where A is an (nacn) constant transition matrix and D is an (nxm) control matrix. The solution to the vector differential equation (1) is x(t) = wt) [x(O) + ISM-OD um d'r] , <2) 70 71 where ¢(t) = eAt is the fundamental matrix, and satisfies 5(t) = AN(t), and N(O) = U, the identity matrix. If the control signal satisfies u(t) = u(i) = conStant iT S t < (i+l)T (3) and" k is a positive integer, then X((k+l)T) = ¢«x+1)r)[x(o) + f‘k+1)T}(-T)Du(w)aw] k+1 = V((k+l)T)[x(o) + 121 IT (-T)D dTu(i-l)] . (i- 1)T (h) Let k- — k- 1. Then from (h) x(kT)= v(kr)[x(6) + 12 ff ¢(-¢)D d7u(i—l)] . (5) (i- 1)T It is clear that (5) can be solved for x(O). Thus -1 ‘ k iT . x(O) = w (kT)[x(kT) - 2 f ¢(-T)D dTu(1-l)] . (6) 1: 1 (i-1)T - Substitute (6) into (R), then w((k+1)T)[v1(kT)x 1, 73 hence d K R3. Let N : H. The coefficients of the boundary hyperplanes of R4 are calculated and listed in Table 6.2. Table 6.2 Boundary Hyperplane Coefficients of R4 Subscripts of z's N“ maxim.“ Ci 1 1, 2 0.60067, -0.33333, 0.0 2 1, 3 0.28571, -0.14286, -0.28571 3 l, h 1.0 , -0.5 , -0.16667 A 2, 3 0.25 , -0.25 , 0.25 5 2, h 0.71u29, -0.28751, -0.1h286 6 3, H 1.0 , -0.72727, -0.09091 lei dl, i = l,2,...,6, can be calculated: [oi d| 0.86667, lcé d| = 0.97143, |cé to; dl = 0.5, Icé 0| = 0.82571, lcé dl = 0.9u546. d| : 0051667: Since [oi d| < l for i = l,2,...,6, thus it is clear that d E R4. The corresponding control is found to be [-1,0, -O.5833, -0.9107, 0.8333], where IO.8333| is a minimum. Example 6.2 1 O 3 Let the difference equation [K5] x(i+1) = 1 2-4. x(i) + O 1 H l Ofl ”1(i) 1 2 O 2 2 be given, with lu (i){ S 1 and [u (i)| S 1 u (i) 2 1g for all i, and the initial state be 0, the terminal state be find the sequence Solution d' = (2682.7, 15H.l, 6020.2). minimal integer N 74 d e 0Y such that N-l’ Y It is clear that z}, 2%, zé, Zg, : l or 2, and |u§_l| The problem is to and the corresponding control = minimum. can be calculated fairly easily by recursion relations (see part (vii) of Section 5.2). The computer output shows that d K Rj’ 1 s j s 1%. Some Table 6.3, where of the numbers Ici dl are shown in ci's correspond to the boundary hyperplane . . . 1 coeif1c1ents of 014. lC'i dl Table 6.3 Some [oi d| for ®1h 1 101 d‘ i 1 0.000000706 2 0.000000330 3 0.000000800 H 0.0000011u6 5 0.0000017h2 401 6 0.000003187 h02 7 0.017966655 #03 Mon #05 M06 000000 .55360002 .32617638 .77601H98 .55480775 .1283u193 .7918106h From Table 6.3, |ci dl s 1 for all i. optimal control sequence is found to be [u%, u 1 Thus d E ®1H’ The Hui] : [1.0, -l°O, 100’ -100, -100) -100, -100, -100, 100, -100, 1.0, -100, 1.0, -1.0, 1.0, 1.0, 1.0, 1.0, 1.0, .100, 1.0, 75 -1.0, 1.0, -1.0, 1.0, 0.037, 0.848, -0.2088, 0.0]. Example 6.3 _ _ 0 1 0 0 . 0 0 0 2w Given (1) The system equation [H11] x(t) = 0 0 0 :1 x(t) 19 -2w 3w2 0 '0 d ‘ 1 0 ul(t) rad + , where w = 0.00111 ( /sec)° 0 0 u2(t) L0 l- (2) Constant sampling periods of 10 seconds. (3) The control constraints are |u1(t)| S 1 and |u2(t)| s l. (h) The initial state x6 : (0 0 0 0). (5) Desired terminal state d' = (1402.5, HH.5, 1%9.8, -8.8). Find the smallest integer N and the corresponding optimal control sequence satisfying d E ®N—1’ Y = 1 or 2, and |u§_l| = minimum. Solution The continuous system equation is approximated by equation (10). Furthermore, the fundamental matrix W(T) = eAT is evaluated by an approximation: eAT = M Ai Ti 3 U + Z 17 In this example and Example 6.6 M is taken i=1 ° to be 10. Thus a discrete model as described in Section 2.2 is realized after these approximations, and hence the techniques developed in Chapters 3 and N are applicable. 76 The smallest integer N is found to be 6 and y to be 1, i.e., d E 0%. The corresponding optimal control sequence is 1 2 2 _ M [111, ul, ..., us] _ [0.09173, -0.022 0, 1.0, -1.0, 1.0, -1.0, 1.0, 001+5176, 1.0, 100) 0032827) O-O]' Example 6.# Let the same system equation of Example 6.3 be given and let y = 2, N = 5, d' = (1H02.5, #5.2, 139.5, -10.8). Y N-l ding control sequence such that Hd-xH2 is minimum. Solution The point x is one of the vertices of @E and The problem is to find a point x e 0 and the correspon- the corresponding optimal control sequence is [1.0, -1.0, 1.0, -1.0, 1.0, 1.0, 1.0, -1.0, 1.0, 1.0]. Example 6.5 Given (1) the system equation [P2] — l —— -— 0 0 o 0 -1 T1 TL 7% 0 0 0 0 3 3 . K T+T x(t) = 0 T—2 -—TLi—f—5 --T—l—T— o x(t) + 0 u(t), 1, 4 5 1+5 0 n l 0 o 0 1 D 0 0 0 — -— 0 L. M 1L _ A 77 (T +T )K where n : TlT_ - “225 2, Tl : 94.25, T3 = 3.8, 4 5 Tums TL+ = 113.1, 15 = 4524, K = 0.324, M = 18221.6, and D = 5.94. 2 (2) Constant sampling periods of 5 seconds. (3) The control constraint is lu(t)| S l. (4) The initial state x6 = (0 0 0 0). (5) The terminal state d' = (-43.88, -41.77, -3.09, -63.7, 0.052). Find the smallest integer N and the corresponding optimal control sequence satisfying d 6 RN and lu I = minimum. NI Solution The method used to approximate the continuous equation is the same as Example 6.4, and hence it is not repeated. The smallest integer is 12, and the optimal control sequence is uN = [ul,u2,...,u12] = [1.0, 1.0, 1.0, 1.0,1.0,1.0,1.0,1J0,(L985,0.85,1.0,1J0]. Example 6.6 Let the same system equation of Example 6.5 be given and let y : 2, N = 6, d' = (-43.88, 21-77, -3-O9, 26.70, -2.05). The problem is to find a point x 6 ®N-l and the corresponding control sequence such that Hd-xll2 is minimum. Solution The point x is one of the vertices of 0% and the corresponding optimal control sequence is [1.0, 1.0, 100’ 100, 1.0, -100, '100, 100, 1.0, -190, -100, '100]. 78 The computations for these examples were performed using the CDC 3600 computer at Michigan State University Computer Laboratory. The acutal running time for each of the six example problems were: 0.15, 11.458, 2.143, 5.936, 6.918, 29.013 seconds respectively. The examples are intended to illustrate the application of the theory developed in Chapter 2 and the algorithms in Chapters 3, and 4 to time-optimal control problems and terminal-error regulator problems. Some general results and particular comments on the algorithms will be discussed in the following: (1) The speed of the algorithm for checking d 6 R is depen- N dent considerably upon the nature of a given specific problem. For instance, in the third-order system of Example 6.1, the subsets of hyperplanes which constitute the boundary of R4 are Ici x] : 1, i = l,2,...,6, as listed is Table 6.2. The computer program is written to cheek whether lei d| > 1 or lci d|5;1 for i = l,2,...,6, in order. If for certain desired terminal state d, Icid] > 1, then it is clear that d z Ru. 0n the other hand, if \ci d] s 1 for i = 1, 2,...,5, but |cé d] > 1, then it is obvious that five more calculations are needed before the conclusion that d K R4 can be made than it would in the former case. For systems of various orders and different N's, similar considerations 79 hold. The time-optimal algorithm compares favorably with other methods for finding the smallest N such that d 6 RN, i.e., Z11 z12 Z1N u1 'ul‘ Z21 Z22 Z2N u2 u2 d = Z u 2 . . . : [Zl’z2’°°"ZN] . (11) LGl Zn2 ... ZnN_ [?N_ LuN and |ui| S l, i : l,2,...,N (12) Assume N 2 n. From (11), u .., and un_1 can be 1,112, ° solved 1n terms of un’un+l"' N' N an (N-n)-f1at in E . 0n the other hand, (12) defines a hypercube M around the origin in EN. It is clear that .,u Geometrically this defines d E R if and only if the intersection of M and this N (N-n)-f1at is not empty [H6]. But no further implementation of this method was suggested in [H6]. Koepcke [K8] solved the problem by storing all the boundary hyperplanes of RN, cix = ni. In this dissertation only ci of |ci x] = 1 are stored, hence no additional storage is required for storing ni's. Koepcke did not treat the most general problems in that 01's are constructed from the linearly independent columns of Z. A simple example can confirm this claim. For example, let 80 1 0 1 Z : [21,22,23] : l 2 3 0 2 2 Hence Z3 : Z1 + 22, but {21,22}, {zl,z3}, and {22,23} determine six subsets of the boundary hyperplanes of R 3, which is indeed correct. Neustadt's method [N4] consists of . . N m . finding 2 2 |(CK’Z1)‘ * izlgizl u(N) = min _ k [(Ck’d)] If u(N) S 1, then N is the minimum time. It is clear that for some N, to check whether log d] = |(ck,d)| S 1 is easier and faster than to find u(N) and check whether u(N) s 1. In order to use the linear programming technique [T1, 21], some transformations must be made to (11) and (12). Let uim = ui + 1, i = l,2,...,N. Then (11)and (12) become N _ €11 Zlulm + 22u2m + --- + ZNuN. = d - 12121 = d = .2 (13) Ian. and 0 s u. s 2, j = l,2,...,N (14) respectively. Depending upon whether ‘31 is positive or negative, either xi or - Xi is added to the left * This applies also when the input signal to the system is scalar, i.e., m = 1. 81 side'of (13). Then (13) becomes zilulm + zi2u2m + °-- + ziNuNm-i xi 2 di’ 1 = l,2,...,n. (15) Add qj z 0 to the left side of (14), then qu + qj = 2, j = l,2,...,N. A [(16) To find whether d e R by linear programming technique, N 211 has to be minimized. It can be shown that if any feasible solution exists to Equations (11) and (12), then a basic feasible solution also exists. Therefore, unless there is no solution to the original constraints, the optimal solution to this auxiliary linear programming problem will be 211 = 0. Since the 11's were required to be non-negative, their sum can be zero only when each variable is itself zero. In general, the total number of multiplications and divisions required by a linear programming technique is N 2.{21+(i+n)+21(i+n)}21 = (6N + 8n + 24)( i=n N+l 3 (N31) + (6-14n)(“§1). (17) while that by using the method presented in this dissertation )+(6n+lo). is n-l _ i 2 [ + ] 1.21%511] . gn§l>=22- 1, there is flexibility in using either 1 + C or 1 - 6 instead of 1, where e is a small number. (4) When some (n—l) vectors from {21,22,...,ZN} are nearly linearly dependent, the method of finding the 83 coefficients of the boundary hyperplanes of R which, in N! essence, is finding solutions to systems of simultaneous linear equations, may suffer difficulties. (5) In the multi-input system, any (n-l) vectors from {zi,z§,...,zT,z:,...,z§,...,z§,z§,...,z§} may not be linearly independent. Since the algorithm in- cludes all the possibilities of taking (n-l) vectors from the Nm vectors, it is clear that if any (n-l) vectors are linearly dependent, then they are contained in some hyper- plane determined by other (n-l) vectors from the Nm vectors. Hence the construction of RN or 0%. does not exhibit any problem. As was pointed out by Hankley and Tou [H5], Desoer and Wing's method [D2, D3, D4, Wl] in constructing the critical surfaces is not, in general, valid. (6) The computer storage and time requirements depend mainly on the terminal time N and the order of the system n. But, in general, as described in (l), the algorithm for finding the smallest N such that d E R requires less N computer storage and computer time. (7) In the terminal-error regulator problem the terminal time N and the desired target point d are given in advance. It is required to find a point xN 6 RN and the corresponding control sequence such that lld-lel2 is minimum. If N < n and Gd 6 RN, then LlGd is the 84 unique optimal control sequence (see equation (3)). If N 2 n or if N < n and Gd K RN, then xN is either a vertex (then the problem is completely solved) or the problem is reduced to an equivalent one with lower dimen- sion. In the first case where N 2 n, the problem is re- duced to k-dimensional one (k S n-l, see pp.57). In the second case when N < n, and Gd K RN, then Gram-Schmidt orthogonalization process (see part (ii) of Section 4.2) is used to reduce the problem to N-dimensional one, where N = n. The procedure then repeats for N ‘ n. This method, as contrast to the quadratic programming technique suggested by Nahi and Wheeler [N2, N3], mainly involves matrix calcu- lations and is easily programmed on a computer. (8) For N < n, the computational aspects of both time- optimal and terminal-error regulator problems have never been before considered in the literature. In this disser- tation, all possible relationships between n and N are considered. In the time-optimal control problem, if the minimum time is N 2 n and d 6 6R then optimal control N, sequence has at most (n-l) members with magnitude different from unity. If the minimum time N 2 n and d K 6R then N! the optimal control sequence has at most n members with magnitude different from unity. In the terminal-error regu- lator problem, if the given time N 2 n and d K RN, then 85 the optimal control sequence has at most (n-l) members with magnitude different from unity. 0n the other hand, if N 2 n and d 6 R and d K RN-l’ then the optimal control sequence N) has at most n members with magnitude different from unity. [Bl] [B2] [B3] [Cl] [CZ] [031 [C4] [051 [06] [C7] REFERENCES R. Bellman, Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1957. J.E. Bertram, P.E. SaraChik, "0n Optimal Computer Control," Pro. First Int'l Congress of Automatic Control, Butterworth, pp. 419-422, 1960. A.G. Butkovskii, ”The Necessary and Sufficient Condi- tions for Optimality of Discrete Control Systems," Automation and Remote Control, Vol. 24, No. 8, pp. 963- 970, January, 1963. J.A. Cadzow, ”A Study of Minimum Norm Control for Sampled-Data Systems," Pro. JACC, pp. 545-550, 1965. J.A. Cadzow, "An Extension of the Minimum Controller for Discrete Systems," IEEE Trans. Auto. Control, Vol. AC-l2, No.2, pp. 202-203, April, 1967. J.A. Cadzow, "Minimum-Effort Control for Discrete Systems,” IEEE Trans. Auto. Control, Vol. AC-11, NOoZ, Pp. 309-310, April, 1966. J.A. Cadzow, "Minimum Energy Regulator for a Linear Discrete System," IEEE Trans. Auto. Control, Vol. AC- 12, NO. 2) ppo 183-185, 1967. M.D. Canon, J.H. Eaton, "A New Algorithm for a Class of Quadratic Programming Problems with Application to Cogtrol," J. SIAM Control, Vol. 4, No.1, pp. 34-45, 19 6. D.H. Chyung, "Discrete Linear Optimal Control Systems with Essentially Quadratic Cost Functionals," IEEE Trans. Auto. Control, Vol. AC-11, No. 3, pp. 404- 413, July, 1966. D.H. Chyung, "Discrete Linear Systethith Convex Cost Functional," Presented at the 4 Allerton Conf., Univ. of Illinois, Urbana, 111., October, 1966. 86 [08] [c9] [D1] [D2] [D3] [D4] [El] [E2] [F1] [F2] [F3] [G1] 87 D.H. Chyung, "Linear Discrete Optimal Systems with Side Constraints," Department of Electrical Engineering, University of South Carolina, Columbia, S.C., 1966. D.H. Chyung, "An Approximation to Bounded Phase Coordi- nate Control Problem for Linear Discrete Systems," IEEE Trans. Auto. Control, Vol. AC-l2, No. 1, pp. 37- 42, February, 1967. G.W. Deley, G.F. Franklin, "Optimal Bounded Control of Linear Sampled-Data Systems with Quadratic Loss," Trans. ASME, Vol. 87, No. 1, pp. 135-141, March, 1965. C.A. Desoer, J. Wing, "An Optimal Strategy for a Satura- ting Sampled—Data System," IRE Trans. Auto. Control, Vol. AC-6, pp. 5-15, February, 1961. C.A. Desoer, J. Wing, "A Minimum Time Discrete Systems," IRg Trans. Auto. Control, Vol. AC-6, pp. 111-125, May, 19 l. C.A. Desoer, J. Wing, "The Minimum Time Regulator Problem for Linear Sampled-Data Systems: General Theory," J. Franklin Inst., Vol. 272, No. 9, pp. 208-228, Septem- ber, 1961. J.H. Eaton, "An On Line Solution to Sampled-Data Time Optimal Control," J. Electronics and Control, Vol. 15, pp. 333-341, 1963- H.G. Eggleston, "Convexity," Cambridge Tracts in Math andBMath. Physics No. 47, Cambridge University Press, 195 . K.A. Fegley, M.I. Hsu, "Optimal Discrete Control by Linear Programming," IEEE Trans. Auto. Control, Vol. AC-10, No. 1, pp. 114-115, Jan. 1965. J.S. Frame, "Matrix Theory and Linear Algebra with Applications," (Class Notes) Department of Mathematics, Michigan State University. J.S. Frame, H.E. Koenig, "Matrix Functions and Applica- tions," IEEE Spectrum, March-July, 1964. pp. 208-220, 102-108, 100-109, 123-131. T.L. Gunkel, G.F. Franklin, "A General SolUtion for Linear Sampled—Data Control,” Trans. ASME, Vol. 85, No. 2, pp. 197-203, June, 1963. [H1] [H2] [H3] [H4] [H5] [H6] [H7] [H5] [H91 [H10] [H11] [J1] 88 G. Hadley, Linear Programming, Addison-Wesley Pub. Co., Reading, Mass., 1962. H. Halkin, ”Optimal Control for Systems Described by Difference Equations," in Advances in Control Systems: Theory and Applications, C.T. Leondes, Ed., Vol. 1, pp. 173-196. New York: Academic, 1964. H. Halkin, "A maximum Principle of the Pontryagin Type for Systems Described by Nonlinear Difference Equations,” J.6SIAM Control, Vol. 4, No. 1, pp. 90—111, February, 19 6. H. Halkin, B.W. Jordan, E. Polak, J.B. Rosen, ”Theory of Optimal Discrete Time Systems," Pro. 3rd Int'l Congress of Auto. Control, pp. 28B.l-28B.7, London, 1966. W.J. Hankley, J.T. Tou, "Note on Control of Multiple- Input Discrete Systems," IEEE Trans. Auto. Control, Vol. AC-12, pp. 469—470, August, 1967. Y.C. Ho, ”Solution Space Approach to Optimal Control Problems," Trans. ASME, Vol. 83, pp. 53-58, March, 1961. J. Holtzman, "Convexity and the Maximum Principle for Discrete Systems," IEEE Trans. Auto. Control, Vol. AC-11, No. 1, pp. 30-35, January, 1966. J. Holtzman, "On the Maximum Principle for Nonlinear Discrete-Time Systems,” IEEE Trans. Auto. Control, Vol. AC-11, pp. 273-274, April, 1966. J. Holtzman, H. Halkin, ”Directional Convexity and the Maximum Principle for Discrete Systems,” J. SIAM Control, Vol. 4, No. 2, pp. 263-275, May, 1966. P.R. Halmos, Finite-Dimensional Vector Spaces, D. Van Nostrand Co., Princeton, N. J., Second Ed., 1958. R.D._Hutcheson, ”The Computation of Optimal Controls by an Iterative Procedure," Thesis for the degree of Aeronautical and Astronautical Engineer, University of Michigan, Ann Arbor, Michigan, 1965. B.W. Jordan, E. Polak, "Theory of a Class of Discrete Optimal Control Systems,” J. Electornics and Control, Vol. 17, pp. 697-711, 1964. [K1] [K2] [K3] [K4] [K5] [K6] [L1] [N1] [N2] [N3] [N4] 89 R.E. Kalman, "Optimal Nonlinear Control of Saturating Systems by Intermittent Action,” IRE WESCON Convention Record, Part. 4, pp. 130-135, 1957. R.E. Kalman, "0n the General Theory of Control Systems," Pro. lSt Int'l Congress of Auto. Control, pp. 481-492, Moscow, 1960. S. Katz, "A Discrete Version of Pontryagin's Maximum Principle," J. Electronics and Control, Vol. 13, No. 2, pp. 179—184, August, 1962. S. Katz, "A General Maximum Principle for End—point Control Problems,” Vol. 16, No. 2, pp. 189-222, February, 1964. H.E. Koenig, Y. Tokad, H.K. Kesavan, Analysis of Discrete Physical Systems, McGraw-Hill Book Co., New York, N.Y., 1967. R.W. Koepcke, "A Solution to the Sampled, Minimum- Time Problem," Trans. ASME Vol. 81, No. 1, pp. 145-150, March, 1964. E.B. Lee, "A Computational Scheme for Discrete Systems," Trans. IEEE Auto. Control, Vol. AC-9, No. 1, pp. 115, 19 4. A. Nagata, S. Kodama, S. Kumagai, "Time Optimal Discrete Control System with Bounded State Variable," IEEE Trans. Auto. Control, Vol. AC-10, pp. 155—164, April, 1965. N.E° Nahi, L.A. Wheeler, "Discrete Terminal Control of Space Vehicles via Mathematical Programming," Univ. of Southern California, Electrical Engineering Department Report 141, October, 1965. N.E. Nahi, L.A. Wheeler, "An Iterative Procedure for Solving the Discrete Terminal Control Proolem," Era. Nat'l Electronics Conf., Vol. XXII, pp- 671-677, 9 6. L.W. Neustadt, "Discrete Time Optimal Control Systems,” Int'l Symposium on Nonlinear Differential Equations and Nonlinear Mechanics, Edited by J.P. LaSalle and S. Lefschetz, Academic Press, New York, N.Y., pp. 267- 283, 1963. [01] [P1] [P21 [P31 [Bl] [R2] [R3] [R4] [RS] [T1] [T2] [T3] [T4] 90 K. Ogata, State Space Analysis of Control Systems, Prentice-Hall, Englewood Cliffs, N.J., 1967. J.B. Pearson, R. Sridhar, "A Discrete Optimal Control Problem," Trans. IEEE Auto. Control, Vol. AC-11, No.2, pp. 171-174, April, 1966. J. Preminger, G.L. Park, "Analysis of Dynamic Stability of a Power System under Deterministic Load Changes," to be published, Proceedings 1969 I.F.A.C., Warsaw. A.I. Propoi, "Methods of Feasible Directions in Problems of Discrete O timal Control," Automation and Remote Control, Vol. 2 , No. 2, pp. 234-245, 1967. A. M. Revington, J. C. Hung, "Time Weighted Energy Control of Discrete- Data Control Systems," Trans. IEEE Auto. Control, Vol. AC-11,No. 4, pp. 758- 759, 1966. J.B. Rosen,"0ptima1 Control and Convex Programming," Nonlinear Programming, J. Abadie, Ed., North-Holland, Amsterdam, 1967. L I Rozonoer, ”L. S. Pontryagin Maximum Principle in the Theory of Optimal Systems 1," Automation and Remote Control, Vol. 20, No. 10, pp. 1288- -l302, October, 1959. L.I. Rozonoer, "L.S. Prontryagin's Maximum Principle in Optimal System Theory 11,” Automation and Remote Control, Vol. 20, No. 11, pp. 1405-1421, November, 1959. L.I. Rozonoer, ”The Maximum Principle of L.S. Pontryagin in Optimal-System Theory III,"Automation and Remote Control, Vol. 20, No. 12, pp. 1517-1561, December, 1959. H.C. Torng, ”Optimization of Discrete Control Systems Through Linear Programming," J. Franklin Inst., Vol. 277, No. 7, pp. 28-44, July, 1964. J.T. Tou, "Synthesis of Descrete Systems Subject to Saturation," J. Franklin Inst., Vol. 277, No. 5, pp. 401-413, May, 1964. J.T. Tou, "Optimum Control of Discrete Systems Subgect to Saturation,” IEEE Pro. , Vol. 52, No. 1, 1964. J.T. Tou, Optimal Design of Digital Control Systems, Academic Press, New York, 1963. [T5] [W1] [Zl] 91 J.T. Tou, B. Vadhanaphuti, "Optimum Control of Nonlinear Discrete-Data Systems," Trans. AIEE., Vol. 80, Pp- 166- 171, 1961. J. Wing, C.A. Desoer, "The Multiple-Input Minimal Time Regulator Problem: General Theory," IEEE Trans. Auto. Control, Vol. AC-8, pp. 125-136, April, 1963. L.A. Zadeh, B.H. Whalen, "On Optimal Control and Linear Programming," IRE Trans. Auto. Control, Vol. Ac-7, pp. “5‘46, 19620 92 Fig. la Intersection of R Fig. 1b Intersection of N with hyperplane a'x : 5: where RN Wlth hyperpLSFe a'X22b, where a'x S B x 6 R . a‘xN< BVXNE RN. x2 N N N /l p—J NH 1 H HA HTTIIHIIIH IIIWTIHHH Fig. 2 Closed half-spaces for Example 2.4.1. l I I 4 * O uN Fig. 3 luNl vs. u with luNl S l. Fig. 4 ufi is the minimum of luNl such that f:f +u z (with f e 6R3,N : 4) 0 ‘N Start l . 94 1 2A For N S n, does Compute u = L d, Zn = d for some YES 2> . d . . i 9 YES (N3<1)vector u? is u a misSio e. NO NO 2B N=N+1, is N:»n? Set fifizu, NO) YES and stop 3A . 9 _._... For N:>n, lS dERN. N=n+l NO YES 3C N-N'l' IS u uni uggl YES FiIld 11, set EN =11 _ [:1 q LJ and stop N0 N 3 Find u for which luNl = min. and stop Fig. 6 Computer Flow Diagram for Time-Optimal Control 1,2333”, Problem; Phases u2 = l A .2 1 2 l ,r”4Lf’fii? lu2| ‘ l ,,-””””/ Fig. 5 x2 6 532 with x1 K 8R1. Fig. 7 Minimum squared length of Fd can be improved by finding an appropriate ak’ if (Fd’akzk) < O. 96 4 Start set uN 2 L1Gd (N given) and stop YES 3 n > N? YES a’GdERN? ‘\ NO NO 5 IS dER ’ YES msN?m Use Gram-Schmidt, n-N, d-Gd _‘s uN not NO unique, can use 1 Sec.3.2 , Equivalent Problem Find one of with dimension n the closest and N = k vertices to d l . aLet J have .1: 0? NO k(Sn-l)elements YES 6 4. uN:[Gl:a29---:GN] and stop Fig. 8 Computer Flow Diagram for Terminal-Error Regulator Problem; Main Computational Steps 1, 2, 3, 4, 5 and 6) XE: x'Sx 2 B R4 Fig. 9 Intersection of R4 and the Target Set ¢£3 x'Sx 2 5 x2 j1(4) :x'S(4)szL+ ‘. ,5 [(3):X'S(3)X2[fi3 ".1 $9 i(2):x'S(2)x282 _ 1 x Q‘§\. .- Q1 1 i(l):x'S(1)x2lil \W V Fig. 10 Time-varying targets; intersection of x£(4) and R4 98 9x / R4[XO = O] Fig. 11 Translation of Coordinates When xO K O Resulting in a New Equivalent Problem with x0 = O. 99 (a) >>< (d) Fig. 12 Some Relations between RN and x£:){'SXSB (when xO )4 O): (a) RN OJ has one point; (b) RN OX, has an infinite number of points; (c) RNO,X, = 8 (empty set), (d) RN DJ] . >X