TIME- D?TIMAL CONTROL
OF MUiTIPLE INPUT LINEAR
SAMPLED-DATA SYSTEMS

Thesis for the Degree of Ph. D.
MICHIGAN STATE UNIVERSITY
RICHARD A. BEDNAR
1971

'Ȣr~-

 

This is to certify that the

thesis entitled
TDIE-OPTIIAL CONTROL OF MULTIPLE I? TPUT
LINEAR BANNED-DATA SYSTEMS

presented by

Richard A. Bednar

has been accepted towards fulfillment
of the requirements for

Ph- D. degree in W Engineering

2% Major professor
Datewq 7/

(#7639

2,. LIBRARY
Michigan State
University

  

 

 
  

   
 

 
 
  

E? aninno BY :9
e JUN & SUNS.
3' 8M BMW“ INC.

LIBRARY SINGERS [
srnlusroprmcmsg: I

  

     

 

 

 

I 7 .

 

ABSTRACT

TIME-OPTIMAL CONTROL OF MULTIPLE INPUT

LINEAR SAMPLED-DATA SYSTEMS
BY
Richard A. Bednar

This thesis is concerned with two problems from
the theory of time-optimal control of multiple input
discrete-time linear systems. The first and second prob-
lems differ mainly in the target set and the admissible
controls.

The subject of the first problem is the time-
optimal control of a linear system whose target set is
given by G = {x(NT): xT(NT)x(NT) _<_ R2} where x(NT) is
the state vector, T is the sampling period, R is a real
number and N is the fewest number of samples such that
x(NT) e G. The amplitude of the controller is assumed to
be unconstrained. Results are derived for determining
the minimum number of samples required to reach the target,
and whether the sequence is unique. If the sequence is
not unique, one is chosen which requires minimum energy

to reach the target. It is shown that this problem reduces

 

F————

 

Richard A. Bednar

to finding the roots of a polynomial of order less than or
equal to Zn where n is the order of the system. An alter-
nate formulation obtains the sequence of time-optimal
controls in the form of a feedback control law. The re-
sults for the open-loop controller are then extended to
include a system with a delay in the input and a stochastic
system.

In the second problem the initial state of the
sampled-data system is to be driven in the fewest number
of samples to a target set described by {xi(NT):

-Mi i xi(NT) 5 Mi , i=l,2,...,n},Mi 3 0, where xi(NT) are
the components of the state vector x(NT). The amplitude
of the controller may or may not be constrained. If the
sequence of controls is not unique, a sequence is chosen
to satisfy a minimum fuel criterion. This problem is
formulated as a linear programming problem. The theory

of the Simplex Method is used to determine whether a solu-
tion exists and if it is unique. A corresponding open—
loop stochastic system is considered, and the procedure
for obtaining a solution is given.

Several numerical examples are solved to illustrate

the theory related to each of the above problems.

 

 

 

.lt'u ' ‘ I ‘ .
‘T,. ' L “#5
”I . .
, :1 '
W34
I g'
I {I I" a
. ff g
:3 TIME-OPTIMAL CONTROL OF MULTIPLE INPUT ,u
.j 01 '
'3: LINEAR SAMPLED-DATA svs'rsns if:
1 1s.
By T L I ~
Richard Ayfigednar __
I
"I
i 4 o
L.
'. fix!
A THESIS I'f'
Submitted to fl'ig
Michigan State-University ,‘ <5
in partial fulfillment of the requirements '
for the degree of
l-\ 6 ,-

DOCTOR OF PHILOSOPHY

Department of Electrical Engineering and
Systems Science

1971

ACKNOWLEDGMENTS

The author would like to express his appreciation
to his major professors, Dr. John Kreer and Dr. Israel
Korn for their interest and valuable comments related to
this thesis. Gratitude is expressed toward the other
guidance committee members, Dr. J. Sutherland Frame, Dr.
H. E. Koenig, and Dr. R. O. Barr. A special note should
be made of the joint effort provided by Dr. Frame and the
author in developing Section 3.3 of this thesis.

Financial support was granted by Michigan State
University for one year in the form of a teaching assis-

tantship and for two years by a National Science Founda—

7-". -4 _

tion Fellowship. This support is gratefully acknowledged.

ii

 

 

TABLE OF CONTENTS

Chapter
I. INTRODUCTION . . . . . . . . . . . . . . . . .
II. PRELIMINARY ANALYSIS AND THEORETICAL
BACKGROUND . . . . . . . . . . . . . . . . . .
2.1 Matrix Theory . . . . . . . . . . . . . .
2.2 Properties of Degenerate Linear
Equations . . . . . . . . . . . . . . . .
2.3 Controllability and Observability of
Sampled-Data Systems . . . . . . . . . .
2.4 Linear Programming Theory . . . . . . . .
III. TIME OPTIMAL CONTROL WITH HYPERSPHERICAL
TARGET SET . . . . . . . . . . . . . . . . .
3.1 Statement of Control Problem and
Basic Assumptions . . . . . . . . . . . .
Solution of Control Problem . . . . . . .
. Minimization of Energy When Time—Optimal
Sequence of Controls is Not Unique . . .
3.4 Time-Optimal Control Using Feedback
Control . . . . . . . . . . . . . . . .
3.5 Statement and Solution of Time-Optimal
Control Problem with Single Input
Delay . . . . . . . . . . . . . . . .
3.6 Statement and Solution of Stochastic
Time—Optimal Control Problem . . . . . .
IV. TIME- OPTIMAL CONTROL WITH HYPERRECTANGULAR
TARGET SET . . . . . . . . . . . . . . . .
4.1 Statement of Control Problem . . . . . .
4.2 Formulation of Time-Optimal Control

Problem as a Solution to a Set of
Linear Inequalities . . . . . . . . . . .

Page

11

15
16

23

23
25

44

84

92

108

125
125

126

 

   
   
  

, =-SUMMARX AND EXTENSIONS . . . . . . . . . . . 2091:

35;. 1-
v5k2:
u NCES

Page

a Solution of Control Problem Using

Linear Programming . . . . . . . .7. . 149

Statement and Solution of-Stochastic
Time-Optimal Control Problem . .'. . . 180

Smary I I I I I I I I I I I I I I I I 2 o 0

Extensions 0 a o o o o o o o l o o o o 202; J

u“. o o o .' o o o I o o c o o o o c o o 209

I I I I I I I I O I I I I ‘I I I I I I I 213

iv

 

\

. :31... 1 1 '.' .'. P. .
-1 -.'r-.-‘ a -

s"

a.

'23- _

)
w

v:“
4;“.1

”335953 ~15

  
   
    
 
 

.-~
..0
O

l'.y‘

v \-
. .4
I

"I. I9 M‘

‘2
t

I ”31": 3.8er

33% (m)

K

v "I
r'fs.
.'. ‘V a)

3

‘ 1

V”.
.9.

.- mm--

 

LIST OF TABLES
Page
Linear Programming Tableau for Example

403-1 0 o a a o o c I o u I I u I o o o o o I 163

Linear Programming Tableau for
Example 4.3.1 I I I I I I I I I I I I I I I I 164

Linear Programming Tableau for
Example 4.3.1 I I I I I I I I I I I I I I I I 165

Linear Programming Tableau for
Example 4.3.1 . . . . . . . . . . . . . . . . 172

Linear Programming Tableau for
Example 4.3.1 . . . . . . . . . . . . . . . . 173

Linear Programming Tableau for
Example 4.3.1 . . . . . . . . . . . . . . . . 174

Linear Programming Tableau for
Example 4.3.1 . . . . . . . . . . . . . . . . 175

Linear Programming Tableau for
Example 4.3.1 . . . . . . . . . . . . . . . . 176

Linear Programming Tableau for
Example 4. 4. l . . . . . . . . . . . . . . . 193

Linear Programming Tableau for
Example 4.4.1 . . . . . . . . . . . . . . . . 194

Linear Programming Tableau for
Example 4.4.1 . . . . . . . . . . . . . . . . 195

Linear Programming Tableau for
Example 4.4.1 . . . . . . . . . . . . . . . . 196

 

 

LIST OF FIGURES

Figure Page

3.2.1 Flowchart for Determining Minimum Number
of Samples for Open—Loop System . . . . . . . 38

3.3.1 Loci of Time-Optimal Controls for
Example 3.3.1 . . . . . . . . . . . . . . . . 68

3.5.1 Flowchart for Determining Minimum Number
of Samples for System with Input Delay . . . 100

3.6.1 Flowchart for Determining Minimum Number
of Samples for Stochastic System . . . . . . 116

4.2.1 Constraints on the Control Sequence in the
y0 i—yl i and u(O)—u(T) Planes . . . . . . . 140
I I

4.3.1 Loci of Unconstrained Time-Optimal Controls
and Constraint Set for Example 4.3.1 . . . . 160

 

CHAPTER I

INTRODUCTION

Among the many types of optimal control design
problems is the problem of time-optimal control. In gen-
eral terms, this problem is concerned with determining the
system inputs which will take the system from an initial
state to a terminal state or collection of states in mini-
mum time, subject to possible constraints. Beginning in
the 1950's, modern control theory has provided insight and
methods of solving this type of problem. The growth in
optimal control theory was paralleled by that of computer
technology which led to the establishment of computer con-
trolled processes. This in turn led to the study of the
time—optimal control problem as a problem in sampled-data
or discrete-time control theory. Starting with the origi-
nal paper by Kalman [KALl], this problem has been studied
by many different authors [KAL2], [CADl], [DESl], [H011 [TOUlL
[TOU2], [GRAl], [FARl], [SARI]. One of the properties
related to this problem is nonuniqueness of the solution.
Suppose we are given a single-input n-th order linear
discrete-time system. If the number of samples N required

to reach the origin is greater than n, the sequence of

 

——————”

2

time-optimal controls is in general not unique. This led
to optimization according to an additional criterion such
as minimum fuel [TORI], [FEGl] or minimum energy [H01],
[CANI].

An additional property of the solution of the
single input discrete-time optimal control problem is that
if N i n, the solution is unique. With the structure of
the system fixed, this in turn implies that we are unable
to Optimize the system according to any additional cri—
teria. On the other hand, it may be acceptable to operate
at any of a collection of operating points; for example,
in a small region about the desired state. It is shown
in this thesis that in general the solution is now no
longer unique when N i n. This in turn provides the op-
portunity to optimize the system according to additional
criteria. The additional criteria studied here are mini-
mum fuel and minimum energy.

In this thesis several discrete-time optimal con-
trol problems will be studied with two types of target
sets: a hypersphere and a hyperrectangle. The problem
of determining the time-optimal control for a continuous-
time system (unsampled) with hyperspherical target set has
been studied previously [PLAl], [PLA2] using an iterative
technique. Chapter 3 is concerned with determining a
sequence of discrete time—optimal controls for the case

of a hyperspherical target set. Both open and closed loop

 

 

.7.

”—-

 

formulations are obtained. A test is given to determine
if the sequence is unique; if not, a sequence is chosen
that minimizes the energy required to drive the system to
the target set. A linear system with a single input delay
is also considered as well as an open-loop stochastic
system.

In Chapter IV the discrete time-optimal control
problem with a hyperrectangular target set is considered.
This problem is reduced to a linear programming problem.
Using the properties of the Simplex Method [HADl] of
linear programming, it is possible to determine if the
solution is unique. If not, a sequence is chosen which
minimizes the total fuel required to drive the initial
state to the target. An open-loop stochastic version of
this problem is also considered; the method of solution
is quite similar to that of the deterministic system.

The theory related to the problems discussed in

Chapters III and IV is illustrated by several examples.

 

 

CHAPTER II

PRELIMINARY ANALYSIS AND

THEORETICAL BACKGROUND

In this chapter some basic definitions and theorems
that will be used in the sequel are given. Section 2.1 is
concerned with certain theorems and definitions from matrix
theory. Section 2.2 is devoted to the study of the de-
generate system of equations Ax = y, and Section 2.3 dis-
cusses the concepts of controllability and Observability
of linear discrete—time systems. In Section 2.4 the
linear programming problem is stated and the Simplex
Method of solution is outlined. Some theorems of linear
programming pertinent to the control problems to be dis-

cussed later are given.

2.1 Matrix Theory
Basic definitions and well-known theorems from the
theory of matrices are given in this section [FRAl],
[FRAZ], [GANl], [PEDl], [HILl], [AYRl]. It shall always
be assumed that all matrices and vectors have only real

elements.

 

 

Definition The rank of an mxn matrix A, written r(A), is
the maximum number of linearly independent columns of A.
Theorem 2.1.1 Let A and B be conformal matrices. Then
r(AB) i min[r(A),r(B)].

Theorem 2.1.2 If A is of order pxq and B is of order qxr,
then r(AB) 3 r(A) + r(B) - q.

Theorem 2.1.3 Let A be an nxn nonsingular matrix denoted
by A = (a1,a2,...,an). If we remove 3 columns from A,

1 i s < n, then the remaining matrix is of maximum rank.
2529: The proof is by induction. Remove one column ak
from A. The remaining matrix is of order nx(n-l). We
need to show this matrix has rank r=n—1, that is, there
exists at least one (n-l)x(n-l) minor different from zero.
Suppose the opposite is true, that is, there are no
(n—l)x(n-1) minors different from zero. Expanding IAI

along its k th column, we get

n .
_ _ 1+k
|A| _ iilaik( 1) [Aikl

where ai is the i th element of the k th column of A and

k
IAikI is the corresponding (n—1)x(n—1) minor of A. By as-
sumption we have lAikl = 0 for i=l,2,...,n. Hence IAI = O
which is a contradiction since it was assumed that A was
nonsingular.

Assume now that 5 columns of A have been removed

and that the remaining matrix A' is of full rank, that is,

A' contains an (n-s)x(n-s) nonsingular matrix M'. Let us

 

remove the j th column from A'. We assume that there is
no (n-s-l)x(n-s-1) minor that is different from zero, that
is, the resulting matrix is not of full rank. Expanding
the matrix M' along the j th column, we have
n-s . .
+3
IM'I = 2 m2. (-1)1 lp'..|
i=1 13 13
where mij is the i th element of the j th column of M',
and Ipijl is the corresponding (n-s-l)x(n-s-l) minor of
M'. By assumption, all the pij have rank less than n-s—l.
Thus Ip!.

1]
which is a contradiction of the assumption that M' is

I = 0, i=l,2,...,n—s and therefore, IM'I = 0

nonsingular. Thus the matrix obtained by removing s+l
columns from A is also of maximum rank. By induction,
the proof 15 complete. QED
Definition The matrix A is positive definite if xTAx > 0

 

for all x f 0. It is positive semidefinite if xTAx Z 0.

 

Theorem 2.1.4 Let A be a symmetric matrix. Then A is
! positive definite if and only if all the eigenvalues of A
are positive. A is positive semidefinite if and only if
all the eigenvalues of A are nonnegative.
Theorem 2.1.5 Let F be a nxm matrix of rank m greater
than zero and A be a nxn positive definite symmetric mat-
rix. Then C = FTAF is positive definite and symmetric.
Theorem 2.1.6 Let A be a nxm matrix of rank n greater
than zero- Then C = AAT is a symmetric and positive

definite matrix.

 

 

 

Theorem 2.1.7 The rank of a real symmetric matrix is
equal to its number of nonzero eigenvalues.

Theorem 2.1.8 Every real symmetric matrix A is orthogon-
ally similar to a diagonal matrix whose diagonal elements
are the eigenvalues of A. That is, there exists a non—
singular matrix P such that A = PTAP where PTP = I,

A = diag(11Irl,l ,...,A I ) and Ir. is an rixr.

I

2 r2 5 r5 1
identity matrix. The ri and Ai can be found from the
expression

r r r
_ _ l _ 2 _ s
IAI - AI _ (1 Al) (1 A2) ...(A As)

Theorem 2.1.9 A real symmetric matrix A of rank r is
positive semidefinite if and only if there exists a matrix
C of rank r such that A = CTC. Similarly, A is positive
definite and symmetric if and only if there exists a non—
singular matrix C such that A : CTC.

Theorem 2.1.10 [KOEl], [FRAl] Let the characteristic
polynomial and adjoint equation for the kxk matrix P be
written as

_ _ _ k k-l
C(Y) — lyI PI - soy + le + ... + sk—lY + 5k

. _ k—l k-2
adj(yI - P) — GOY + Gly + ... + Gk-ZY + Gk-l

where so = 1, G0 = I. Then the scalar coefficients si and
the matrix coefficients Gi are given recursively by the

following equations:

 

8
G0 = I s0 = l
l = PGo + s11 51 = ~ tr(PG0)
- --1
G2 — PGl + 521 $2 - 2tr(PGl)
Gk-1=PGk-2 + Sk—lI sk = —l/k tr(PGk_l)
Gk = PGk-l + skI = 0

Theorem 2.1.11 Let A be a real nxn symmetric matrix with

eigenvalues Al, 12,...,An. Define f(A) = Ak + alAk-l

+ azAk_2 + ... + a A + a I where h is a positive integer

k-l k
and the ai are scalars. The eigenvalues 6i of f(A) are
k-l k—2
i

_ _ k
91 — f(Ai) — xi + all. + aZAi + ... + ak_1ki + ak.

Theorem 2.1.12 If A is a real symmetric matrix then Ak
is also symmetric for any positive integer k.
Definition Let b be an nxl vector and c be a mxl vector.

The outer product bcT of b and c is defined to be the nxm

matrix given by

bl [c1 c2 ... cm] blc1 blc2 ... blcm
T _ _
bc — b2 — b2cl . . . .
bn bncl bnc2 b cm

That is, if bcT = {a..} then a.. = b.c. for i=l,2,...,n
1] 13 1 3

and j=l,2,...,m.

Theorem 2.1.13 The outer product of a nonzero vector y
with itself is a symmetric matrix of rank 1.

2522: By definition, we have ny = {aij} i=l,2,...,n and

j=l,2,...,n where ai = yiyj. Therefore, aji = y.yi =

j J

 

 

yiyj = aij and the matrix is symmetric. To show that the

matrix is of rank 1, we use the above definition of outer

product to write
Y1Y1 yly2 -.- ylyn

ny = y2yl . . . . = AB

ynyl ynyz- - -ann

where
y1 Y1 "' Y1 y1 o ...
y2 y2 ... y2 9 y2 0 ... 9
A = I B = 2 6
yn yn ... yn 0 0 ... 0 yn

Then by Theorem 2.1.1, rank (ny) : min [rank(A), rank(B)].
By definition the rank of a matrix is the maximum number
of linear independent columns in the matrix. Thus rank

(A) = l and rank(ny) : 1. By assumption y # 0, so
rank(ny) Z l, and the result follows.

QED

Definition Given a polynomial in A. If the polynomial

vanishes when A is replaced by a matrix A, the polynomial

is called an annihilating polynomial of A.

Theorem 2.1.14 The characteristic polynomial D(A) = [AI-AI

is an annihilating polynomial of A, that is, D(A) = 0.
Definition A monic polynomial is a polynomial with unity

as the coefficient of the highest power of A.

 

"-1luuugIII-----I------------------....-........................

10

Definition The monic annihalating polynomial m(A) of
least degree in A is called the minimal polynomial of the
matrix A.

Theorem 2.1.15 The minimal polynomial m(A) of a nxn

matrix is given by

m(1) = ——91%L-
Dn-l A)
where D(A) = [XI - AI and Dn_l(1) is the greatest common

divisor of all the minors of order n-l of XI - A.
Theorem 2.1.16 [KOEl] Let the minimal polynomial of the

r
k)
If f(A) is an analytic function, then any analytic matrix

r1 r2 k
matrix A be given by m(A) = (A -11) (A - 12) ...(A - A

function f(A) can be written as

 

(rl-l)
(1) '
f( - 2 f A z £1511 + z f(Al)
A) ' 11 ( 1) + 12 11 + "' 1rlTE“=‘TTT
(l) }r§_l)
f(Az) f( 2)
+ Z21f(12) + z22 1! + ... + ZZrZT?;—:_TTT
+ ... (1) ~ (rk'l)
f(Ak) f(Ak)
+Zklf(xk) + Zk2_TT__ + ... + ZkrkT?;—:TTT_
where the matrices Zij’ i=l,2,...,k and j-l,2,...,r,

, called the constituent matrices, are independent of the
function f(A).
Theorem 2.1.17 The constituent matrices Zi1 (i=l,2,...,k)

in Theorem 2.1.16 are idempotent and sum to unity, that is,

2 _
Zil ‘ zil

[I le+Z21+...+Zkl=I

 

11

Furthermore, Zithq for i f j. If A is a symmetric mat-

rix, then Zij = 0 for i=l,2,...,k and j # 1.
Theorem 2.1.18 [DERl] Let A be a square symmetric mat—
rix with repeated eigenvalue Ai' If the root is repeated
k times, then k linearly independent columns of the P
matrix in Theorem 2.L3 can be obtained from the nonzero
columns of
dk'l .
TI [adfl I‘A” 1:1.
d1 1
Theorem 2.1.19 The trace of a square matrix is equal to
the sum of its eigenvalues.
Definition An nxk matrix A is said to have a right in-
verse AR if AAR = In where In is an nxn identity matrix.
Theorem 2.1.20 An nxk matrix A has a right inverse if
and only if A is of rank n.
Theorem 2.1.21 Given the matrices A,B and C. Then

T -l

(A-BCB ) = A—1

+ A_1B(C-l-BTA_1B)_1BTA_1

where the indicated inverses are assumed to exist.
This result can be verified by post multiplying

both sides by (A-BCBT) and collecting terms.

2.2 Properties of Degenerate Linear
Equations [FRAl], [FRAZ]

In this section the equation y = Ax where A is of
order mxn will be studied. This equation is called dege-

nerate if A is either not square or not invertible. If A

 

‘1‘!lIF"""""""""""""""""""""""'"""""""""TT"II

r___r___.__.,.r

12

and y are given then either many or no solutions exist.
In the case where no solution exists we may still be in-

terested in finding a vector xl such that

ll y - Ax”2 = minimum for x = x1
The determination of the vector x1 is facilitated by the
study of the generalized inverse of a matrix [PENl],
[GREl], [GRE2], [DEUl], [DEU2], [ZADl], [ACK1]. It is
assumed in the following that all matrices are real.
Definition A generalized inverse of an mxn matrix A is

any nxm matrix AI which satisfies AAIA = A.

 

Theorem 2.2.1 If A = BC is any rank factorization of the
mxn matrix A of rank r > 0, then AI is a generalized in-
verse of A if and only if CAIB = II where I1. is a rxr

identity matrix.

Proof [FRAl], [FRA2] If CAIB = Ir, then AAIA = BCAIBC
= BIrC = A.

On the other hand, assume AAIA = A = BC. The
equations B+B = CC+ = Ir are satisfied by B+ = (BTB)_1BT

— +

and c+ = CT(CCT) 1. Thus, CAIB = IrCAIBIr = B+BCAIBCC =
B+AAIAC+ = B+AC+ = (B+B)(CC+) = I .
QED

Definition A semi—inverse A§of an mxn matrix A of rank r

 

is any generalized inverse of the same rank r. That is,
a semi-inverse is defined by the conditions AASA = A and

rank(AS) = rank (A).

 

W—__—_—fi

13

Definition The matrix A is called idempotent if A2 = A.

Theorem 2.2.2 The matrices ASA and AA8 are idempotent.

2529; (ASA)(ASA) = AS(AASA) = ASA

(AAS)(AAS) = (AASA)AS = AAS
QED

. . . . . s .
Definition A semi—inverse A of an mxn matrix A of rank r

is called a right pseudoinverse of A if the left idempo-

 

tent AAS is symmetric, that is, (AAS)T = AAS. Similarly,

a semi-inverse is called a left pseudoinverse of A if the

 

right idempotent ASA is symmetric, that is, (ASA)T = ASA.
Theorem 2.2.3 There is a unique matrix A+ called the
(Moore-Penrose) pseudoinverse of A that satisfies the

following equations

AA+A = A
A+AA+ = A+
(AA+)T = AA+

(A+A)T = A+A
Theorem 2.2.4 The mxn matrix A with rank factorization
A = BC has for its pseudoinverse A+ = CT(CCT)-1(BTB)-1BT
for A f 0 and 0+ = 0T.

Some useful identities are given by the following
theorem.
Theorem 2.2.5 The matrix pseudoinverse has the following
properties [DEUl], [DEUZ]:

1) If A is nonsingular, then A+ = A_1 (2.2.1)

2) (21+)+ = A (2.2.2)

 

"1IIF5-'-"""""""""-"------IIII-IIIIIIIIIIIIII-IIIIIIIIIIIIIIIIIIII
14

3) If A = BC is a rank factorization of A, then

A+ = (BC)+ = c+B+ (2.2.3)
4) (A+)TAT = AA+ (2.2.4)
5) (AT)+ = (A+)T (2.2.5)

Proof

1) Since AA+A = A and A-1 exists, then A+A = I. Similarly,

AA+ = I. Therefore, A+ = A_1 by definition of A-l.

2) Let E = cT(ccT)'l and D = (BTB)—1BT. Then A+ = ED and

(A ) = DT(DDT)'1(ETE)'1ET

-1BTB(BTB)-l -l

]
cc'1'(ccT(ccT)'1]'l (ccT)'1c

= B(BTB)-1(BTB)(CCT)(CCT)-1C

= B(BTB)-l[(BTB)

[(CCT)'1

= BC

= A
3) Since by definition B has rank r, we can perform a
rank factorization on B as in Theorem 2.2.4: B = DI
where B is mxr, D is mxr and I is an rxr identity matrix.

Then by Theorem 2.2.4,

B+ = IT(IIT)-1(DTD)—1DT
= (DTD)‘1DT
= (BTB)_1BT
} Similarly, C+ = CT(CCT)_1. Therefore,
: C+B+ = cT(ccT)'1(BTB)‘13T = (BC)+ = A+.

4) Substituting the expression for A+ given in Theorem

2.2.4 into the expression (A+)TAT, we get

 

a.;.

,

o

— 4;...

 

I‘IIIIlIIIIIIIIIIIIIIIIllllI:::———--—————————_______

15
T
(Af)TAT = [?T(CCT) 1(BTB) 1BT] CTBT
= B(BTB)'1(ccT)'lccTBT

= B(BTB)_1BT

B ccT (ccT)1’B(BTB)l T

=AA+

REC)T]+ = (CTBT)+ = B(BTB)‘1(ccT)'lc
[CT(CCT)—1(BTB)—1BT]T = (A+) T

QED
Theorem 2.2.6 If the equation y = Ax has a solution
vector x1, then every solution x has the form x = AIy + x0
where AAIA = A and Ax0 = 0.
Theorem 2.2.7 The vectors x that minimize (for given y
and A) the quantity||y - Ax\\2 have the form x = Asy + x0
where A8 is any right pseudoinverse of A and Axo = 0.
(By definition, “ylz = y Ty)
Theorem 2.2.8 The unique vector x with“ x“2 minimum that

minimizes the quantity “y - Ax“2 is x = A+ y where A+ is

”the (Moore—Penrose)pseudoinverse of A.

2.3 Controllability and Observabilityo of
mpled- -Data Systems

 

 

 

Definition [BERl], [KALZ] A system is defined to be com—
pletely controllable if it is possible to find a sequence
of controls which will drive the system from an arbitrary

initial state to any desired state in a finite number of

sampling periods.

 

7‘vlIIIF-III"-"""'----'--------------------------f-III
16

Theorem 2.3.1 [BERl] Given the linear system x[(k+1)T]

= Cx(kT) + Du(kT), k=0,1,...,N-l, where C is of order nxn
and nonsingular and D is of order nxm. The system is com-
pletely controllable if and only if rank(G) = n where

G = [On—1D,Cn—2

D’Io-,D]I
Corollary The system is completely controllable if and
only if rank(Un) = n, where Un = [C-lD,C—2D,...,C-nD].

Proof of Corollary» By assumption, C is nonsingular. The

 

rank of a matrix is not changed by multiplying it by a
nonsingular matrix. Premultiplying G by C"n gives the

desired result.
QED

Definition Given a system described by x[(k+1)T] = Cx(kT)
+ Du(kT), y(kT) = Bx(kT). The state xi(kT) is said to be
observable if the input u(kT) and output y(kT),
k=0,l,...,N-l are sufficient to determine xi(0). If
every state of the system is observable, we say that the

system is completely observable.

 

Theorem 2.3.2 A necessary and sufficient condition for

a linear n-th order system to be completely observable is

that rank(H) = n where H = [CN_1B,CN-2B,...,B].

2.4 Linear Programming Theory

 

The Simplex Method [HADl] of solving linear pro-
gramming problems is outlined in this section. Theorems

concerned with existence and uniqueness of solutions that

————.~‘.—._—.——-

 

 

17

are pertinent to the problem to be solved in Chapter IV
are given here.

The basic problem to be solved in a linear pro-
gramming problem is to maximize a linear objective func—
tion

2
z = Z cjxj (2.4.1)
j=l

subject to m linear inequalities (or equalities) of the

form
1
-§ aijxj{<=>} bi i=l,...,m (2.4.2)
j—l
and the non-negativity restrictions
x. > 0 j=l,2,...,l (2.4.3)

3
All the bi must be non-negative. If required,

we can multiply an inequality by -1 to obtain bizo. The
next step in solving the problem is to add slack or sur-

plus variables to convert an inequality to an equality.

2
Thus 2 i'x ‘ b1
j=l J 3
becomes 2
jil aljxj + xr+i = bl xr+l > 0
and 2
Z i' > b1
j=l J 3
becomes 1
jil ijxj - xr+i = bi xr+i > 0
By defining A = {aij}, b = (bl,b2 ...,bm)T, and
c = (cl,c2,...,c£), the above problem can be written as

 

W

18

max 2 = cX
subject to Ax = b
X > 0
where X = (x ,x ...,x )T.
l 2 k
Definition Given a system of m simultaneous linear equa-
tions in n unknowns, AX = b (m<n) and rank of A equal to
m. If any mxm nonsingular matrix is chosen from A, and
if all the n-m variables not associated with the columns
of this matrix are set equal to zero, the solution to the
resulting system of equations is called a basic solution.
The m variables which can be different from zero are
called basic variables.
Definition Any set of xj which satisfy the set of con-
straints given by (2.4.2) is called a solution to the
linear programming problem. Any solution which satisfies
the non-negativity restrictions is called a feasible
solution. Any feasible solution which maximizes the value

of z is called an optimal feasible solution.

 

The problem is to determine an optimal feasible

solution. The steps in solving the problem by means of
the Simplex Method are now outlined [HADl].
1) Construct an initial tableau such as that given in
reference [HADl] or as shown in Section 4.3. The basis
vector xB in this case is given by xB = b. Except for
the last row the other columns yj in the tableau are

given by yj = aj where the aj are the columns of the A

 

19

matrix. The last row of the tableau gives 2 and zj»_ cj

where

z = cBb and zj — cj = cBaj - cj (2.4.4)

c:13

basis variables. The cj are sometimes called “prices."

is a row vector composed of those cj corresponding to

2) The optimality criterion is then used. This criterion

states that if all zj - cj 2 0 then a basic feasible solu-

tion is optimal. If one or more zj - cj < 0 then the
problem is not solved and we proceed to the next step.

3) Compute zk- ck = min (zj - cj) for zj - cj<0 (2.4.5)
The criterion implies that we add ak to the basis. (If
there is a tie we may choose either one.) Once ak has
been chosen there are two possibilities depending on yik

where yi are the elements of the yk vector:

k
a) If Yik‘o for all i then there is an unbounded
solution involving the vectors in the basis and
ak.

b) If yik>0 for at least one i then a new basis
feasible solution can be found having 222.
4) If at least one yik>0, then determine which vector is

to leave the basis. This vector is chosen by the follow-

ing criterion. Compute

X .
. Bl
_ = mln __ ’

> 0 (2.4.6)
Yrk 1 yik

yik
The vector in column r of the basis is removed and re-

placed by ak. If there is a tie, any one of the tied

columns can be removed and replaced by ak.

 

m-vn—FI_-_ -

r

20

5) The next step is to construct a new tableau. The ele-

ments §ij of the new tableau are related to those yij of
the old tableau by the relations
A Yik . . .
yij = yij - 5;; yrj all j, i=l,...,m+l i#r (2.4.7)
y . = iii all j (2.4.8)
r] yrk

xB = Yo, z=ym+l,ol zj _ cj = ym+l,j j=1,ooo'n (2.4.9)

The price in the rth position of the column headed "CB
should be replaced by ck and the vector in the rth posi-
tion under "vector in basis" should be replaced by ak.

6) Return to Step 3. The Simplex Method requires a
finite number of steps to reach an optimal (or unbounded)
solution. In general, the number of iterations required
to reach an optimal solution lies between m and 2m where
m is the number of constraints.

Let xB be the component of xB corresponding to
1

column bi of the basis. If x >0, we say that bi is in

B
the basis at a positive level and if xB_ = 0, bi is in
the basis at a zero level. The following theorems will
be used in Sections 4.3 and 4.4.

Theorem 2.4.1 [HADl]

a) If no artificial vectors appear in the basis and the

optimality criterion is satisfied, then the solution is an

optimal basic feasible solution to the given problem. The

 

 

21

constraint equations are consistent, and there is no re-
dundancy in the constraint equations. .

b) If one or more artificial vectors appear in the basis
atra zero level and the optimality criterion is satisfied,
then the solution is an optimal solution to the given
problem. The constraint equations are consistent, but in
this case redundancy may exist in the constraints.

0) If one or more artificial vectors appear in the basis
at a positive level and the optimality criterion is satis-
fied, the original problem has no feasible solution.

There may be no feasible solution either because the con-
straint equations are inconsistent, or because there are

solutions, but none is feasible.

Definition A basic solution to AX = b is degenerate if

one or more of the basic variables vanish.

Theorem 2.4.2 [HADl]

a) If the optimal solution represented by the last tab—
leau is not degenerate and if zj - cj > 0 for each aj not
in the basis, then the optimal basic feasible solution is
unique. No vector can be inserted into the basis without
decreasing the value of the objective function.

b) When zj - cj = 0 for one or more aj not in the basis,
any such vector aj can be inserted to yield a different
solution if yi. > 0 for at least one i and min(xB/yij),

J

yij > 0 is positive. If aj enters at a zero level we do

 

22

not obtain a different solution; the result is only a
different representation of the same degenerate extreme

point.

 

r...— ...-3“. .-

CHAPTER III
TIME-OPTIMAL CONTROL WITH HYPERSPHERICAL
TARGET SET

3.1 Statement of Cgptrol Problem and
Ba51c Assumptions

 

Given a linear time-invariant system described by

2': = Ax + Bu (3.1.1)
x(0) = x0
where x(t) is a nxl vector

u(t) is a mxl vector
A is a nxn matrix
B is a nxm matrix
It is assumed that u(t) is of the sampled-data
type so that
u(t) = u(kT) for kT < t < (k+l)T (3.1.2)
where T is the sampling period. We wish to determine the
fewest number of samples N and a corresponding sequence

of controls u(kT), k=0,l,...,N-l which drive the system

from the initial state xo to the target set described by

G = {x(fiT): xT(fiT)x(NT) g R2} (3.1.3)

where R is a real number and x0 ¢ G. If the solution is
not unique, we want to determine a sequence of controls
that drives the system to the set G with minimum energy.

That is, we want to minimize J where

23

 

24

-1 T
J = 2 u (kT)u(kT) (3.1.4)
k=0

2!

The problem shall be solved under the following
two assumptions wherein N denotes a running variable.
Assumption 1 It is assumed that the discrete-time system

is completely controllable. From Theorem 2.3.1 this means

 

n-lD

that rank[D,CD,...,C ] = n where C and D are defined in

equation.3.2.l.

1D]

Assumption 2 It is assumed that rank[D,CD,...,CN-
= maximum for all N > 0.
The second assumption does not follow automatically

from the first. This is shown by the following example.

Let
1 0 0 l l
C = 0 2 0 D = 2 2

Then n=3, m=2, and n/m = 3/2. We then have

111111

[D,CD,C2D] = 2 2 4 4 8 8

3 9 9 9 27 27
The determinant of the matrix formed by the first, third,
and fifth columns of the above matrix is twelve. Thus,
rank[D,CD,C2D] = 3, and the system is completely control-
lable. If we choose N = l < n/m, then ranle,CD,...,CN_1D] =
rank(D) = l # Nm. Thus the first assumption is satisfied

but not the second.

 

W*;;’ o .—4—

er.

25

If we let Assumption 1 hold, then Assumption 2 is the
same as Assumption 1 under any of the following conditions:
1) The system has a single input, that is, u(t) is a
scalar.

N'lnl ¢ 0. In

2) N = n/m is an integer and ID,CD,...,C
other words, the first n columns of the controllability
matrix [D,CD,...,Cn_1D] are linearly independent.

3) n/m < 2 and D is of full rank.

Condition 1) is a special case of condition 2). This
follows from the fact that for a scalar controller,
[D,CD,...,Cn-1D] is a nxn matrix and must be nonsingular
in order that the system be completely controllable. To
show that condition 2) implies that Assumption 2 is the
same as Assumption 1, we use Theorem 2.1.3. Under con-
dition 2 the matrix [D,CD,...,CN_1D] is nonsingular.
From Theorem 2.1.3, if we remove columns from the anm
matrix [D,CD,...,CN_1D], the remaining matrix is of maxi-
mum rank, that is, rank [D,CD,...,CN-1D] = Nm when

N < n/m. Let condition 3) hold. If we want N < n/m, we

must have N=l, and rank[D,CD,...,CN_lD] = rank(D) = Nm

because n > m if N < n/m.

3.2 Solution of Control Problem

 

The general solution to equation (3.1.1) is

t
x(t) = ¢(t—t0)x(to> +f ¢(t-T)Bu(‘r)dT
t
0

 

26

where ¢(t) is the transition matrix of the system described
by equation (3.1.1) [DERl]. Let t=(k+l)T and t0 = kT.
Then

(k+1)T
x[(k+1)T] = ¢(T)x(kT) + Jr ¢[(k+l)T—T]Bu(r) dT
kT

From equation (3.1.2) this becomes
(K+1)T
x[(k+1)T] = ¢(T)x(kT) + jr ¢[(k+l)T—T]BdTu(kT)
kT

If we let Y = T - kT, then

x[(k+1)T] = ¢(T)x(kT) + ng¢(T-Y)BdYu(kT)
or

x[(k+1)T] = Cx(kT) + Du(kT) (3.2.1)
where

T
D = f ¢(T-T)BdT (nxm matrix) (3.2.2)
0

and C = ¢(T) is nonsingular by the properties of the
transition matrix [ATHl].

By assuming k=0 and then k=1, we obtain respec-
tively, x(T) = Cx(0) + Du(0), x(2T) = Cx(T) + Du(T).
Thus, x(2T) = C2x(0) + CDu(0) + Du(T). Repeating this
argument for k=3,4,...,N-l, we arrive at the general

solution to equation (3.2.1):

k-l .
x(kT) = Ckx(0) + z ck‘1‘1Du(iT) (3.2.3)
i:
If we define
F. = - c'(l+1)o i=0,l,...,k-l (3.2.4)

1.

 

27

and

ui = D(iT) i=0’1,uoo,k-1

then equation (3.2.3) becomes

x(kT) = Ckx(0) - ck, .2 Fiu. (3.2.5)

i=0
It will be shown that if there exists a sequence
of controls which drives the initial state to the interior
of the target, there exists a sequence of controls which
drives the initial state to the boundary of the target in
the same number of samples or fewer. The problem will
then be restricted to determining a sequence of controls
such that
xT(NT)x(NT) = R2 (3.2.6)
Substituting equation (3.2.5) into (3.2.6), we get

N-l

T _T _T
x (NT)x(NT) — x0 wa0 2x0 wN jionuj
N—l T N-l
+ Z F.u. Z F.u.
(j=o J j) wN(i=0 1 l)
where
wN = (CN)TCN (3.2.7)
This can be rewritten as
T _T_T T
x (NT)x(NT) — U QNU ZdNU + x0 wa0 (3.2.8)
T
where U = (uo,ul,...,uN_1) (me1 vector) (3.2.9)
_ —T — '
QN — FN wNFN (memN matrix) (3.2.10)
F , = [FO’F1""’FN-l] (nme matrix) (3.2.11)

N
T - xTw E (lme vector) (3 2 12)
dN‘ ONN "

 

28

By defining

_ T _ 2
eN — xowao R (3.2.13)

equations (3.2.6) and (3.2.8) combine to give

_ T _ T =
f(U) — U QNU 2dNU + eN 0 (3.2.14)

Theorem 3.2.1 QN is a symmetric matrix with the following
prOperties:

1) If N g n/m, Q is positive definite.

N
2) If N > n/m, QN is positive semidefinite and singular.
Prggf By Theorem 2.1.6 we know that wN is symmetric and
positive definite. Thus by equation (3.2.10), OE =
(EEWNEfi)T = nggfifi = FngEfi = QN’ and QN is symmetric.
1) Assume that n 2 Nm. Since Efi is of order anm, it
follows from Assumption 2 of Section 3.1 that the rank of

Ffi is Nm. Thus Efi is of maximum rank and QN = FNwNFN is
positive definite by Theorem 2.1.5.
2) If n < Nm, it follows that QN is positive semidefinite
since UTQNU = UTfingfifiU = YTwN Y where Y = FfiU. Because
wN is positive definite, UTQNU = YTwN Y a 0. QN is not
positive definite because it is singular. This follows
from Theorem 2.1.1, that is, rank(QN) < min [rank(Ffi),
rank(wN)] < mN. On the other hand, QN is of order memN.
Hence QN is singular.

QED

Theorem 3.2.2 a) If N s n/m, the expression for f(U)

given in equation (3.2.14) can be written as

 

29

T _

where T -l

by the transformation
U = p Y + Q'1 (3 2 17)
N N dN O O

. T _
where PN is such that PNPN — I, and

AN = PgQNPN (3.2.18)
is a diagonal matrix with diagonal elements equal to the.
eigenvalues of QN.

b) If N=n/m = integer, equation (3.2.15) reduces to

YTANY - R2 = 0 (3.2.19)

Proof a) By Theorem 3.2.1, le always exists for N < n/m.

Substituting equation (3.2.17) into (3.2.14), we obtain

—1 T l T -l
(PNY + QN dN) QN(PNY + QN dN) - 2dN(PNY + QN dN) + eN
_ T T _ T -1 _
— Y PNQNPNY dNQN dN + eN - 0 (3.2.20)
By assumption PN is chosen to diagonalize QN. Such a mat-
rix exists by Theorem 2.1.8. Thus AN = PEQNPN is a diago-

nal matrix with the eigenvalues of QN along the diagonal,

and equation (3.2.20) becomes
T T —1 _
Y ANY dNQN dN + eN - 0 (3.2.21)

By equations (3.2.16) and (3.2.21) the first part of the

theorem follows.

 

30

b) If N = n/m = integer, then Efi given by equation (3.2.11)
is nonsingular by Assumption 2. Then by equations (3.2.10)-
(3.2.14)

T -1 _ _ T — —T — -14T
'eN ' dNQN dN ‘ eN XOwNFN(FNwNFN) FNwN x0

gN

_ T -l _ T _ 2 _ T = _ 2
6N xownwn wNXO ‘ xowao R xowao R

(3.2.22)

Substituting equation (3.2.22) into (3.2.15) gives the
second part of the theorem.

QED
Theorem 3.2.3 Let N g n/m. Then the following is true.
a) If eN = degl dN, the unique sequence of controls such
that x(NT)€ 8G (the boundary of G) is given by U = QNldN'

b) If e < dEQQIdN, a nonunique sequence of controls

N
exists such that x(NT)e G.
c) If eN > dgoéldN, no sequence of controls exists such
that x(NT)e G.

T - .
Proof a) If eN = dNQNldN, then by equations (3.2.15) and

(3.2.16)

YTANY = 0 (3.2.23)

The matrix AN is positive definite since it contains the
eigenvalues of QN (which must be positive by Theorem

2.1.4) along its diagonal. By definition of positive
definiteness, equation (3.2.23) holds only if Y = 0. Thus,
by equation (3.2.17) it follows that U = Q§ldN is the

unique sequence of controls.

 

31

b) If e < dgogldN, then by equations (3.2.15) and

N
(3.2.16)

YTANY = agogldN - eN > 0 (3.2.24)
If N > 1, equation (3.2.24) has an infinite number of
solutions. If N=l, there are two solutions. In either
case a solution exists but is not unique.
c) If eN > dgofildN, then be equations (3.2.15) and
(3.2.16)

YTANY = degldN - eN < 0 (3.2.25)
Since AN is positive definite, there is no value of Y
which satisfies (3.2.25). Thus, no solution exists for
this value of N.

QED
The previous two theorems were for the case when

N s n/m. We now consider the case when N > n/m.
Theorem 3.2.4 a) If N > n/m, a nonunique sequence of con-
trols exists such that x(NT)e 8G (the boundary of G). A
sequence of controls can be found from

-1

_ -T - —T
where
YTANY = R2 (3.2.27)
and P is chosen such that PTP = I and A = PTQ P is a
N N N ’ N N N N

diagonal matrix with diagonal elements equal to the eigen-

values of QN.

 

32

FT -1
N(F NFN N) xo
which require minimum energy to reach the origin.

b) If R=0, U = F is the sequence of controls

Proof From equations (3.2.10), (3.2.12) and (3.2.14)

f(U) = UTFT(CN)TCNFN U - 2xowN FN U + eN

“CNEfiU - CNx + e

2 T
o” ' xowao N

where “y”2 = yTy. From equation (3.2.13) the expression

for f(U) becomes

2

f(U) = ”CNEfiU - ch 2 — R (3.2.28)

0II
Minimizing f(U) with respect to U is equivalent to mini-

mizing h(U) where

h(U) = ”CNEfiU - ch ||2 (3.2.29)

0
By Theorems 2.2.7 and 2.2.8, we know that a value of U

that minimizes h(U) is given by U = (CNFfi)+CNx0. The

matrix CN is of order nxn and of rank n while ER is of

order anm and of rank n by Assumption 2 and the fact
that n < Nm. Thus CN and Ffi represent a rank factoriza-
tion of CNFfi. By equation (2.2.3) we then have

N + N _ —+
U N(C ) C x0 — FNx0 (3.2.30)

Returning to the expression for f(U) given by equation

(3.2.14), if we set

U = PNY + FNXO (3.2.31)

then the expression for f(U) becomes

 

33

F+

L(Y) (PN Y + FN x

0) TON
T T T -+ T —+ T
PNQNPNY + Y P NQNFNxo + x o(FN) QNPNY

xT —+ T
+ x0(FN) QNF Nx 0 - ZdNPN Y ZdNFN x0 + eN

(PN Y + FNXO) - 2dN(PN Y + FNXO) + e

N

By using equations (2.2.5) and (3.2.12), this becomes

(3.2.32)

L(Y) = YT FEQNFN Y + 2xT o(FN)T FNWNENPNY - 2xg¢hFNPNY
—+ T —+
ZXOWN FNF Nx0+ x0(FN) QNFNxo + eN

L(Y) can be simplified. For notational convenience, let

s = cN

(3.2.33)’

Using equation (3.2.10), the second to last term on the

right side of equation (3.2.32) then becomes

2.3
(3.2.34)

fi‘FN) TFFQN Nx o = fi‘FN)T_TSTSTSFNfl Nx o

= xgsT(F;s'l)T(sFfi)TsFfiF;s'1s x0
= ngT(F;S-1)T(8Ffi)TSFfi(SFfi)+Sx0
= xgsT [(sFN ) ] T(SEfi)TSFfi(SEk)+Sx0
= ngTSEfi(S§fi)+SEfi(SEfi)+Sxo by equa-

tion-(2.2.4) xT T
= x05 SFN (SFN ) +Sx0 by Theorem 2.

By Theorem 2.2.4, equation-(3.2.34) becomes

M3(F;)TQN+X Nx 0 = xgsTsFfiF§(FNFg) 1(STS) lSTSXO

= x'gSTSx0

34

= xowa by equations (3.2.33) and (3.2.7)
(3.2.35)
The second term on the right side of equation (3.2.32) can
be written as

T T T -1

2x08 (S ) (fim

N)

T —+ TAT ‘—
2xo(FN) FNwNFNPNY

T
0

+ T—T —
] FNS SFNPNY

2x sT[(sFfi)

T

T — T + '— T«—
2x08 [(SFN) ] (SFN) SFNPNY
_ T T — — + —
— 2x08 (SFN)(SFN) (SFN)PNY
by equation (2.2.4L

Using Theorem 2.2.3 in the above equation, we then have

T —+ T—T —» _ T T —
2x0(FN) FNwNFNpNY — 2x08 SFNPNY
= 2xTw‘F p Y (3 2 36)
o N N N ° '

The third to last term on the right side of equation.

(3.2.32) can be written as

T -.—+ _ T T<— .— +
_ T —+ T -+ .
- 2x0(FN) QNFNxo by equation (3.2.34)

2xngxo by equation (3.2.35) (3.2.37)

Substituting equations (3.2.35)-(3.2.37) into (3.2.32)

gives

_ T T _ T
L(Y) — Y PNQNPNY xowao + eN

35

Using equation (3.2.13), this becomes L(Y) = YTPEQNPNY - R2.

Since f(U) = 0, it follows that L(Y) = 0, and thus

T T _ 2 .
Y PNQNPNY - R (3.2.38)

T _ _ T .
We can choose PN such that PNPN — I and AN - PNQNPN 1a a
diagonal matrix with the eigenvalues of QN along the dia-
gonal.

The expression for U given in equation (3.2.31)

can be put in-a form not involving the pseudoinverse.

—+ _ ._ +
FN — (SFN) s
= F§(FfiFT)-I(STS)-ISTS by Theorem 2.2.4
N
_ —T‘—‘4T -1

Substituting equation (3.2.39) into (3.2.31) gives
equation (3.2.26). Equation (3.2.38) has an infinite

number of solutions since AN is positive semidefinite and

singular.

b) If R = 0, then by equations (3.2.28)-(3.2.29) it fol-
lows that f(U) = h(U) = 0. By Theorem 2.2.8, the value
of U given by equation (3.2.30) is the value of U that

minimizes h(U) with the additional property that ”U”2 is
F*

minimum. Moreover, this value of U is unique because N

is unique. By equations (3.2.30) and (3.2.39), we have
_ —T —'—T -1
that U - FN(FNFN)

is proven. This results when R = 0 has been derived by a

x0, and the second part of the theorem

different method [CADl], [CAD2].
QED

36

From Theorem 3.2.2b» a value of Y satisfying
(3.2.19) and (3.2.17) always exists. This fact plus
Theorem 3.2.4a) imply that the target can always be reached
in~fi samples where U is the smallest integer greater than
or equal to n/m. The following theorem shows that the
boundary of the target can be reached in the same number
or fewer number of samples than that required to reach
the interior of the target set.

Theorem 3.2.5 Assume a sequence of controls exists such

2 where R > 0. Then another se-

2

that xT(N1T)x(N1T) < R
quence of controls exists such that xT(N2T)x(N2T) = R
where N2 S N1.
REESE ‘Assume the hypotheses of the theorem to be true.
Furthermore, let N 4 n/m. Then by (3.2.8), UTQNU - ngU
+ x'ngxO < R2, or by using equation (3.2.13), UTQNU

-2ng + eN < 0. If we let U = U + OgldN: then this in-

l
equality becomes UEIL'QNUl - dgogldN + eN < 0 which implies
that eN < dgohldu

since QN is positive definite. By theorem 3.2.3 this in-
equality is just the condition for the existence of a
sequence of time-optimal controls to reach the boundary
of the target set. Thus the boundary can always be
reached in the same number of samples as that required

to reach the interior of the target. On the other hand,

by choosing an initial state close to the boundary of the

target it is possible to construct examples that require

37

fewer samples to reach the boundary than a point in the
interior of the target.

If we suppose that the interior of the target can
be reached in N > n/m, then by Theorem 3.2.4 we know that
the boundary of the target can also be reached in-N sam-
ples. Hence, for all N it follows that the boundary of
the target can be reached in the same or fewer number of
samples than that required to reach the interior of the

target.
QED

The theorems presented above give a straight—
forward method of determining the minimum number of sam-
ples N required to reach the target and a sequence of
time-optimal controls. It is noted that the value of N
can be determined without diagonalizing the ON matrix,
that is, PR and AN need not be computed. The procedure
for determining N is illustrated in Figure 3.2.1.

Except for the special cases when a unique solu-
tion exists or R:0, it is necessary to use equation
(3.2.15) if N < n/m or equation (3.2.27) if N > n/m to
determine a sequence of time—optimal controls. Similarly,
it is necessary to determine the diagonalizing matrix PN'
For purposes of hand computation the eigenvalues of Qfi
which form the diagonal elements of AN can be found from

the characteristic equation for QN' For the case when QN

has distinct eigenvalues, the columns of PN can be chosen

.Emumhm mooalcwmo How mmHmEMm mo Hones: Edfiflsflfi mcwcwfihwpwv How uumso3oam H.m.m .mflm

 

       

 

E
I Hmo + mam n o
sofluSHOm mowflcocoz

 

 

 

 

 

 

 

 

 

 

 

 

 

 

o a z z
uh I I. ..H
M oxalflmwmmvmm+wzm u D Huoam Mvam D sofluSHOm
, coauSHOm wovflcb x momamwm
GOfluSHow mdwflcssoz wmumcu Edfiacaz

 

 

 

 

Umuflzwmh mmHmEMm mo HwnEdc ESEMGHS
mmamfimm mo Hmnfidc ESEHCHE mo wsam> Hmflna n

39

to be the normalized eigenvectors of QN" If the eigen—
values are not distinct, other methods can be used [DERl].
For computer computation the PN and AN matrix can be found
by numerical methods based on the theory of Jacobi [RALl].
Prewritten FORTRAN programs exist for diagonalizing the
ON matrix, that is, for determining PN and Afi [KUOl], [IBMl].
Once AN is known, a solution of equation (3.2.15)
or (3.2.27) is easily found. The result is substituted
into equation (3.2.17) if N < n/m or (3.2.26) if N > n/m
to give a sequence of time optimal controls.
The theory presented thus far is illustrated by
the following example.

Example 3.2.1. Consider the two input systems described

 

by the following transfer function matrix and correspond-

ing block diagram.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

__ " l 1 — ‘1
CflSfl ‘ S + 2 0 01(3)
C2(S) s i l % 02(3)
_. .— L _1 L. .4
I 1 I "1
”1‘9"" [S + 2| 3 (31‘s)
1 "9
S + I ...
C2(S)
+
1 x3
U2“) Er:

 

40

It is assumed that the control signals ul(t) and u2(t) are
the output of zero-hold devices. The sampling period is
T=l second. The differential equations corresponding to.

(3.2.40) are

 

 

dcl
a?— + 201(t) = ul(t) (3.2.41)
dzc dc du (t) du (t)
2 + 2 = —l— + 2 + u (t)
dti at dt at 2
(3.2.42)
By defining _ _
"1
c1 1 0 0 x2 (3.2.43)
c2 0 1 1 x3
and by the above figure
x1 -2 0 0 x1 1 O
u1
x2 = 0 -1 0 x2 +» l 0 (3.2.44)
u2
x3 0 0 0 x3 0 l
L- _ _ A — J _ -

 

 

 

 

 

 

 

 

We want to find a sequence of controls which drive the
system from the initial state x(0) = (10 -10 10)T to the
target xT(NT)x(NT) c l in the fewest number of samples, N.
Solution The discrete-time system corresponding to 3.2.44)

is
x(k+l) = Cx(k) + Du(k) (3.2.45)
where
-2
(3.2.46)

0
ll
oom
(D
l—‘OO

41

(1-e‘2)/2 0
D = 1-e-1 0
0 1

L _

 

 

From (3.2.4), and (3.2.36)-(3.2.37)

 

 

-3.19453 0

F0 = -c‘10 = -l.71828 0

0 -1

r'-23.6045 0—
F1 = -c'20 = -4.6708 0
0 -1
Setting N=l, we find that

'0.018315 0 0
01 = cTc = 0 0.135335 0
0 0 1
L. _

 

0.58649 0'7

_-T-_T
Q1 ‘ F1‘”1F1 ‘ F0w1F0 0 1

_l

 

Q.-
I

T — _ T _
1 - xowlFl — xowlFo (1.74034 10.0000)

_ T _ 2 _ _ 2 _
el - xowlxo R — 115.365 1 - 114.365

By (3.2.51)-(3.2.53)

T -1 _ _
d1Q1 d1 -el — 9.2008
Thus
T -1
e1 > d191 d1

(3.2.47)

(3.2.48)

(3.2.49)

(3.2.50)

(3.2.51)

(3.2.52)

(3.2.53)

(3.2.54)

42

 

 

Also, n/m = 3/2 > N = 1. Therefore, we can use Theorem
3.2.3 which says that no solution exists for N=l. Setting
N=2, we obtain
"0000335 0 0-
02 = (c2)Tc2 = 0 0.018315 0 (3.2.55)
0 0 1'
L. J
0.05750 0 0.17229 0
«JT ‘_ T 0 1 0 1
02 = F2w2F2 = [F0, F1] w2[F0,F1] 0.17229 0 0.58649 0
0 l 0 1
(3.2.56)

Since N=2 > n/m = 3/2, we know that the target can be
reached in two sampling periods. The transformation-given

by (3.2.26) is then used where

 

 

0.28469 0 -0.95862 0 _-
0 0.70711 0 -0.70711
P2 = (3.2.57)
0.95862 0 0.28469 0
_ 0 0.70711 0 0.70711J
The eigenvalues of Q2 are
Y1 = 0.63765 72 = 2.0000 Y3 = 0.006333 Y4 = 0.0000
(3.2.53)
Then by (3.2.27) we have that
2 2 2 2
0.63765y0 + Zyl + 0.00633y2 + 0y3 = 1 (3.2.59)
One possible solution to (3.2.59) is
y0 ='0 y1 = 0.7071 y2 = 0 y3 = 0 (3.2.60)

43

In this case the transformation given by (3.2.26) yields

 

 

 

 

 

 

 

 

_ -T —'4T -1
I" 1 _' —
0.28469 0 -0.95862 0 0
0 0.70711 0 -0.70711 0.7071
= 0.95862 0 0.28469 0 0
0 0.70711 0 0.70711 0 *
'_0.18218 -.92067 0 " 10 511.0291
+ 0 0 -0.50000 10 == -4.500
-0.06702 0.12460 0 10 -l.916
0 0 -0.50000J -4.500
(3.2.62)
In the above we have used the fact that Nfi = [F0, F1]. 3

From (3.2.62) we have

11.029 -1.916
“(0’ = -4.500 “(1’ = -4.500 (3'2°63’

Substituting (3.2.63) into the state equation (3.2.45)

gives the following sequence of time-optimal states.

x(0) = (10 -10 10)T
x(1) = (6.1206 3.2926 5.500)T
x(2) = (0 0 1)T
and
2 2 2

xT(2)x(2) = 0 + 0 + 1 = 1
Thus the target is reached in N=2 samples.
Another sequence of time-optimal controls can be

found from (3.2.59) by choosing

Y0 = 1 y1 = 0 y2 = 7.5659 y3 = 10 (3.2.64)

44

Substituting (3.2.64) into (3.2.61) gives
4.0605 1.1964
“‘0’ = -12.0711 “(1) = 2.0711

This sequence of controls gives the following sequence of

states
x(0) = (10 -10 10)T
x(1) = (3.1088 -1.1121 -2.0711)T
x(2) = (0.93795 0.34712 0 )T

and xT(2)x(2) = 1.000 as required.

3.3 Minimization of Energy_When Time-
Optimal Sequence is Not Unique
In the preceeding section it was shown that in
general the sequence of time-optimal controls that drives
the initial state to the target was not unique. This al-
lows for the possibility of optimizing the system accord-
ing to another criterion. The criterion chosen here is to
minimize the energy required to drive the initial state to
the target. For computational purposes we would like a
method of determining this sequence of controls that is
adaptable to computer solution. The problem is now stated
more formally.
Problem Statement Given the discrete-time system described
by equation (3.2.1). Let N be any integer greater than
or equal to the minimum number of samples required to reach
the target described by (3.1.3). Find a sequence of con-

trols which minimize the total energy required to

45

drive the system to the target set; that is, we wish to
minimize J where
N-l T
J = 2 u (iT)u(iT)
i=0
Solution- Let U = (u(O),u(T),...,u[(N-l)T])T. Then J can
be written as
J = UTU (3.3.1)

From equation (3.2.8) we have
T _ T . _ T T
x (NT)x(NT) — U QNU ZdNU + xowao (3.3.2)

Adjoining equation (3.3.2) to (3.3.1) by means of a
Lagrange multiplier (-1/Y), we obtain for the Lagrangian L

UTU - (l/Y)(xT(NT)x(NT) - R2)

UTU - (l/Y)(UTQNU - ngU + xgtpNxo - R

L

2)

Setting %% = 0, we arrive at the following equation.

U = -(y1 - QN)'ldN (3.3.3)

Substituting equation (3.3.3) into (3.3.2) and setting

2

xT(NT)x(NT) - R = 0, the following equation is obtained

1 T -1 _
dN + 2dN(YI - QN) dN + eN — 0

(3.3.4)

T -1 -
dN(YI - QN) QN(YI - QN)

where eN is given by equation (3.2.13). Equation (3.3.4)

can be written as

d§adj(y1 - QN)QNadj(YI - 0N)dN + 2d§adj<vl - 0N)chN(v)

+ eNc§(Y) = 0 (3.3.5)

46

where
-1 _ , _ =
(71 - QN) CN(Y) - adJ(YI ON) GO)

Nm-2

+ Gly +...+G (3.3.6)

and

cN(Y) = lyl - QNI = some + slme-l +...+st_ly + st
(3.3.7)

The si and Gi can be found from Theorem 2.1.10.

Equation (3.3.5) is a polynomial of order 2Nm in y. The

problem is to reduce (3.3.5) to the form

2Nm 1 2Nm-1 _

where the 01 are constants to be determined. If N > 2,
the reduction of (3.3.5) to (3.3.8) by hand computation)
becomes very tedious. The bulk of this section is devoted
to finding the pi in a fashion that is adaptable to com-
puter solution and thus to cases where N is large. It
will also be shown that the polynomial given in Equation
(3.3.8) is actually of lower order than shown if N > n/m.
We begin by proving the following theorem.

Theorem 3.3.1 Let N 2 n/m. Then the expansion of the
conjoint matrix given in Theorem 2.1.10 for the matrix QN
has the property that Gn+1 = Gn+2 = ... = G = 0.

Nm

. _ -T —. . —
Proof By equation (3.2.10), QN — FNwNFN. The matrix FN
is of order anm and of rank n by Assumption 2 of Section

3.1. By Theorem 2.1.1 rank(QN) s min[rank(FN), rank(wN)]=

n. Since wN is nonsingular, wNFfi is of rank n because

47

multiplication of a matrix by a nonsingular matrix does

not change the rank. Berheorem 2.1.2,

—T _
rank(QN) 2 rank(FN) + rank( NFN) n
2 n + n - n =.n
Therefore rank(QN) = n. SinceQN is symmetric, Nm-n of

the eigenvalues of QN are zero 2y Theorem 2.1.7. The

characteristic equation (3.3.7) becomes cN(Y) = YNm-n(Yn
n—l .
+ le + ... + sn). That is,
s = s = ... =.s = 0 (3.3.9)

n+1 n+2 Nm

and the nonzero eigenvalues Yi of QN satisfy the equation

n n-l .
Yi + SiYi + 000 + Sn "' 0 l_l’2’000’n

(3.3.10)

By Theorem 2.1.10, the quantity QNGn can be written as

_ 2
QNGn _ QNGn-l + SnQN

2 .
QN(QNGn-2 + Sn-lI) + SnQN

3 2
QNGn-Z + Sn-lQN + SnQN

n+1 n n-l
QN + SlQN + SZQN + ... + anN

From Theorem 2.1.12 and the fact that the sum of symmetric
matrices is symmetric, we have that QNGn is symmetric. By

Theorem 2.1.11 the eigenvalues 0i of QNGn are

_ n - - _
ei—Yi(Yi+SlYi + co. +Sn) 1-1’2’000’Nm

48

where Yi are-the eigenvalues of QN. Thus for those eigen-
values of QN which are zero we have 01 = 0, and by equation
(3.3.10) we have thatvei = 0 also for the nonzero eigen-
values of QN. Thus QNGn is a symmetric matrix with all.

.zero eigenvalues. By Theorem 2.1.7 this implies that

QNGn = 0 (3.3.11)

From Theorem 2.1.10 we have that

Gi = QNGi-l + $11 1=n+l,n+2,...,Nm

By equations (3.3.9) and (3.3.11) this implies thatIGi = 0

for i 2 n+1.
QED

Theorem 3.3.2 a) The polynomial in equation (3.3.4) can.

 

be reduced to the form given by equation (3.3.8) where the

pi are as follows:

rheN for i=0

2(deN + eNsl) for i=1
=(

i-2
T T

 

1
+ eN jiosjsi-j for 2 c i 6 Nm
Nm-l T
Z [ (G.Q G._._ + ZG.s._._ ) + e s. s._._ ]
j=i-Nm-1 dN j N 1 j 2 j 1 j l dN N 3+1 1 j 1.
K. for Nm+1 < i < 2Nm

where the Gi and si are generated recursively by the

equations

49

G0=I 30:1
G1 = ON G0 + s1I s1 = - tr(QN)
.. ..-.1.
G2 - QNG1+ $21 52 - 2tr(QNG1)
GNm-l = QNG Nm-2 + 9‘Nm-1I SNm = “(l/Nm)tr(QNG Nm- -1)

GNm =GQN Nm- 1 + sNmI = 0

b) The quantities in the summations given above have the

following property.

GkQNGj = GjQNGk ],k=0,l,...,Nm‘l

c) If N 2 n/m, the polynomial given by equation (3.3.8)
reduces to a polynomial of order 2n, that is, equation

(3.3.4) becomes
007 + ply + ... + 02n_1 y + p2n = 0

where the?)-i are given by

 

F‘ .
eN for 1—0
'I‘ ...
2(deN + eNsl) for 1—1
T i-2
2dNGi-ldN+ j= E0 dN(Gj QNGi- -j-2 + 2sti- -j- -1)dN
31:1 1
+ e Z s. s. for 2 6 i 8 n
N j i j
j= —0
n-l T
._.Z [dN(GjQNGi-j-2 + 2sti- -j- -1)dN + eNSj+lSi-j-1]
j—1-n-l
K for n+1 < i 6 2n

Proof Let us expand the first term in equation (3.3.5) by

using (3.3.6).

50

adj(YI - Q N)QNadj(YI - QN)

= (IYNm l+G1YNm'2+GzYNm'3+...+Gmn2Y+GNNm_l)QN(IYNm'1

m-2 Nm-3
+leN +G2Y +...+GNm_2Y+GNm_l)

2Nm- 2 2Nm- 3

_ 2Nm-4

+ (QN G2 + GlQN G1 + GZQN)Y

2Nm-5
+ (QN G3 + GlQN G2 + GZQN G1 + G3QN)Y

+-°" + (QNG Nm- 2 + GlQNGNm-3 + "' + GNm-3QNG1+ GNm-ZQN)Y

+ (QNGNm-l + GlQNGNm-Z + GZQNGNm-3 + "‘ + GN MZQN

m-l
+ GNm-lQN )YNm

+ (GTQNG Nm- -1 + GZQNGNm-Z + G3QNGNm-3 + °" + GNm-ZQNGZ

Nm—2

+ GNm-lQNGl)Y + ...

+ ( + +

GGNm-BQN Nm-l GGNm-ZQN Nm-2 GNm-1QN GNm-3)Y

Y + G (3.3.12)

+ (GNm-ZQNGNm-1+ GGNm-loN Nm- -2) Nm- -IQNG Nm- -1
Since we Wish to find dNadj(YI - QN)QNadj(YI - QN)dN, we

can use equation (3.3.12) to write

d§adj(v1 - 0N>0Nadj(yr — 0N>dN

= eoY2Nm + elY2Nm-1 + 62Y2Nm-2 +

.00 + 6 (303013)

2Nm-1Y + e2Nm

where

51

0 for i=0,l

1—2
T .
< jio dNGjQNGi-Z-de for 2 < 1 < Nm
1 (3.3.14)
Nm-l
G. Q G. _2 _ for Nm+1 < i < 2Nm
\3_ -i-Nm- _lde N i 2de

 

Let us turn to the second term in equation (3.3.5), that

is, adj(YI - QN) CN(Y)-

adj(YI - QN) CN(Y)

Nm-l Nm-2 Nm-3

(GOY +G1Y +G2Y +...+GNm_zy+GNm_l)soy
Nm-l Nm-2
+le +S2Y +"°+SNm-1Y+SNm)
_ 2Nm-1 2Nm— 2 2Nm-3
_ GOY + (cos 31+ Glso)Y +(Gos 2+ Glsl+sto)Y + ...
+(Gs +G +G s + + G s + G s )YNm
OS Nm- -1 1 SNm-2 2 Nm-3 "' Nm-2 1 Nm-l 0
+(GosNm + GlSNm-l + GZSNm-Z + ... + GNm-353
Nm-l
+ GNm-ZSZ + GNm-lsl)Y
+(Gs G s + + G s + G s + G )YNm 2
1 3+Nm 2 Nm-l "' Nm-3 4 Nm-2 3 Nm- -1S 2
Nm-3
+ (GZSNm + GBSNm-l + ... + GNm-ZS4 + GNm-133)Y + ...
+ (G +G )Y2
Nm- -3 st Nm-ZSNm——1+GNm-lst-2
+ (GNm-Z $Nm+GNm-1$Nm-1)Y + GNm-lst (3'3'15)
The express1on for dNadj(yI - QN) dNoN(Y) can then be
. T .
written as ZdNadj(yI - QN) dNoN(Y)
2Nm 2Nm-1 2Nm-2 (3.3.16)

= CoY + ClY =;2y +°'°+C2Nm-1Y + 2:2qu

52

 

where
r. 0 for i=0
i-l T .
_ 2.5 dNsti-j-ldN for l s i S Nm (3.3.17)
Ci "' j-O
Nm-l T
2 Z G.S. . for Nm+1 s i c 2Nm
L?=i-1-deN J l J-ldN
Consider now the last term in equation (3.3.5), that is,
2
cN(Y).
2 _ Nm Nm-l Nm-2 Nm
cN(Y) — (soy + sly +szY +...+st_ly+st)(soY

+ leNm'1+szme-2+...+s

Nm-lY+ SNm)

_ 2 2Nm 2Nm-l 2Nm-2
_ S0Y +(sosl+slsO)Y +(sosz+slel+szso)Y

2Nm-3
+(5033+slsz+szsl+s3so)Y

+ ... + (SOSNm+Slst-1+SZSNm-2+'°'+SNm-232+st-lsl
Nm
+stso)Y
+ (s 3 +3 5 + +3 3 +3 s )meg1
l Nm 2 Nm-l '°° Nm-l 2 Nm 1
Nm-2
+ (SZSNm+SBSNm-1+“"+st-153+SNm32)Y
2
+ ... + (SNm-lst + SNmSNm-1)Y + st (3.3.18)
Therefore,
2 _ 2Nm 2Nm-l 2Nm-2
eNcN(Y) - ¢0Y +¢1Y +¢2Y +"'+¢2Nm-1Y+¢2Nm

(3.3.19)

53

 

where
f-
eN for i = O
i
2 .s. . for l < i < Nm (3.3.20)
_ eN . 831-3
¢i _ { 3:0
Nm
eN Z s.si_. for Nm+1 s i S 2Nm
L j=i-Nm J 3
Let
pi = ei + Ci + ¢i i = 0,1,...,2Nm (303021)

We then have by equations (3.3.5), (3.3.13), (3.3.16),
(3.3.19) and (3.3.21)

2Nm 2Nm-1 _
OOY + ply + ... + pZNm-lY + pZNm - 0

(3.3.22)
where by equations (3.3.14), (3.3.17), (3.3.20) and (3.3.21)

 

F' .
eN for l — 0
2 T + e (s s + s s ) for i=1
deN N o 1 1 o
i-2 1-1 TG
jiodNGj QNGi— 2- de+ 2:0: d'NGj Si- -j-1dN
i
pi =j + eN .E SjSi-j for 2 s 1 c Nm
j—O
Nm-l T Nm-l T
G. 06 .d + 2 Z d G.s._._
j=i-Nm-1dN j N i- -2- -j N j=i-Nm-1 N j 1 j ldN
Nm
+ eN X s.si_. for Nm+1 s i < 2Nm
k_ j i-Nm J

54

By reordering the subscripts, the above equations can be

2(deN + eN S1 for i=1
T
2dNG i- -ldN + ::o sz‘Gj QNG i- j- -2 + ZGjSi-j-l)dN

= i
pi < + eN Z s.si_.
j=0 J J

for 2 < i s Nm

Nm-l T
Z {dN(GjQNGi-j-2 + 2sti_j_l)dN

 

j=i-Nm-1
+ eNSj+lsi-j-l} for Nm+1 s 1 s 2Nm
K. (3.3.23)
Thus the first part of the theorem has been proven.
b) From Theorem 2.1.10, Gk can be written as
Gk = QNGk-l + SkI
= QN(QNGk-2 + Sk-lI) + SkI
= Q2G + s Q + s I
N k—2 k-l N k
i k k-1 k-2
_ QN + SIQN + SZQN + ... + SkI
From this last equation we see that
QNGk = GkQN (3.3.24)
Gij = Gij (3.3.25)

By equation (3.3.24)

55

GkQNGj = GijQN

(303.26)
Sim11ar1y, GjQNGk = GijQN' However, by equat1on (3.3.25),
this last equation becomes

GjQNGk = G G.Q

k 3 (3.3.27)

N
By equating the right sides of equations (3.3.26) and
(3.3.27), we have GkQNGj = GjQNGk' and the second part of
the theorem is proven.

c) Let N > n/m. From Theorems 2.1.10 and 3.3.1 we have

adj(YI - QN) = me'n'l(Goyn+Glyn'l +...+Gn_ly+Gn)
(3.3.28)
_ Nm-n n n-1
cN(Y) - y (soy +317 +...+sn_ly+sn) (3.3.29)

Let us again expand the first term in equation (3.3.5)

while using (3.3.28).

adj<vI - QN)QNadj(YI — QN>Y'2‘Nm‘n’

2n

_ -2 2n-3
- GOQNGdY +(GOQNG1+GIQNGO)Y

4

’ 2n-
+ (GOQNG2+GlQNG1+G2QNGO)Y +...+(GOQNGn_3+GlQNGn_4+...

n+1

"'Gn-IIQNc;1".C""n--BQNGO)Y +(GOQNGn-2+GlQNGn-3+'"

n
+Gn-3C2NG'14'G'n-ZQNGO)Y + (GOQNGn-1+GIQNGn-2+"'
n-l
+Gn-ZQNG1+Gn—1QNGO)Y +(GOQNGn+GlQNGn-1+GZQNGn-2+'"
n-2

+Gn_zQNG2+Gn_lQNG1+GnQNG0)Y +...

+ G 2
( n"3QNGn‘1+Gn-2QNGn-2+Gn--lQNGn-3)Y

56

+(G y+G (3.3.30)

n—ZQNGn-1+Gn-1QNGn-2) n-IQNGn-l
From equation (3.3.11) and the second part of this theorem,
we have

QNGn = GnQN = 0 (3.3.31)

If we substitute equation (3.3.31) into (3.3.30), we have

dgadj(YI - QN)QNadj(YI - QN)dNY-2(Nm-n)
- ‘ 2n - 2n-1 - 2n-2 _
‘ eoY +61Y +92Y + ~-- + 92n_lv+5§n (3.3.32)
where f—
0 for i=0,1
i-2 T
2 d G.Q G. .dN for 2 c i s n
‘ -. -_ N J N 1-2-3
91 ‘ fl 3-0
n-l T
.-.Z dNGjQNGi-Z-de for n+1 < 1 < 2n (3.3.33)
3—1-n-1 ’
K.

 

Expanding the second term in equation (3.3.5) while using
equations (3.3.28) and (3.3.29), we get

adj<YI - QN)cN(Y)Y‘2‘Nm‘n’+1

Yn-1+G Yn_2+...+Gn_

n-1 n-2
Y
1 2

+5 Y +...

_ n n
- (GOY +G lY+Gn)(soY +51 2

2n 2n-1 , 2n-2
+ = + + + + +

n+2

+...+(Gosn_2+Glsn_3+ ..+Gn_zso)Y +(Gosn_l+Glsn_2+...

n+1
+Gne251+Gn-1SO)Y +(Gosn+G s

n
l n- +...+Gn_lsl+GnsO)y

1

n-1 .
+...+Gn_lsz+Gnsl)y +...+(G 3 +6

5 n-3 n n-ZSn-l

+(Glsn+G2 n-1

57

3 2
+G +Gnsn_3)y +(G s +G +Gnsn_2)y

n-1Sn-2 n- -2 n n- -15 n- -l

+(G Sn+GnS n_1)Y+Gnsn (3.3.34)

n- -1

Since we are trying to determine dgadj(yI - QN)chN(y),
we show that this quantity can be simplified by showing

T . .
thatldNGnsidN = 0 for 1=0,1,...,n. To prove thlS, we have

by Theorem 2.1.10

Ill>

G. = Q G. + 811 for i=0,1,2,...,n with G

1 N 1-1 -1

Then by equation (3.3.31)

Therefore, by equation (3.2.12)

_ T
8i GgndN GnGidN - xOwNF-N Gn 6' 1FT Nwao

However, by equations (3.3.31) and (3.2.10)

_ - -T ‘-
0 QNG ’ FN‘DNFNGN
Therefore,
TFTw F on G. F Tw F = o for all
Y N N N N N N Y Y

Let x = FNy. Then xfiNFNGnGiFNwNX = 0. EN 18 of order

anm and be assumption N > n/m. This plus Assumption 2
of Section 3.1 imply that Ffi is of full rank and

x TwNFN Gn G. iFNwa = 0 for all x. Thus

dgsiGndN = o for 1=0,1,...,n (3.3.35)

Therefore, by equations (3.3.34) and (3.3.35)

0

58

d§adj(YI - QN)chN(Y)Y-2(Nm-n)
_ T 211-]. . 211—3
- leGosoy +(G M31+G150)Y -28+(Go 2+ Glsl+sto)Y +...
n+1
+(Gos n_ _2+ Glsn-3+°"+Gn—280)Y +(Gosn_l+Glsn_2+...
Gn-251+Gn-130)Yn+(GOSn+Glsn-1+G28n-2+'°°
+G s +G s )yn-l+(G1 s n+G s + +Gn 3 +6 s)Yn-2+
n-2 2 n-l 1 2 n- -1 "' -2 3 n- -1S 2 "°
2
+<Gn-3Sn+Gn-ZSn-1+Gn-1Sn-2)Y + (G n- -25n +Gn -lsn-l)Y
+Gn-lsnldN
T . _ -2(Nm-n)
or 2dNadj(YI QN)dNCN(Y)Y
_ — 2n _ —' 2n-l '— -
— COY — ClY + ..o + C2n_1Y + Czn (303036)
where
0 for i=0
_ i-l T
c. = 2 X G. s. d for l < i < n (3.3.37)
1 j=0 j i- j- -1 N

n- -1

L3: —i- -l- -n

Let us now expand the third term in equation (3.3.5) using

dNsti- j-ldN for n+1 < i < 2n

 

equation (3.3.29).

c§(Y)Y-2(Nm'n)

n -1 -2 n n-l -2
= (SOY +slyn +szyn +...+sn_ly+sn)(soy +sly +szyn +...

2 2n

_ 2n-1
+sn_ly+sn) - soy +(sosl+slso)y

2n-2
+(sosz+slsl+szso)y

59

n+1

+...+(s ...s s )Y

n-l 0 +(sosn+s s +...

osn-1+315n-2+ 1 n-1+SZSn-2

n-l

n
+3 3 +snso)y +(s s +szsn_l+...+sn_lsz+sn81)Y

n-l l 1 n

2
+(sn_lsn+snsn_l)y+sn

 

Therefore,
2 -2(Nm-n) _'— 2n1— 2n-1 1— —
eNCN(Y)Y - ¢0Y +¢1Y +'°'+¢2n-1Y+¢2n
(3.3.38)
where
r"
eN for i=0
_. _ < l .
¢i_- eN j:osjsi_j for 1 i 1 s n (3.3.39)
n
eN E s.si_. for n+1 S i s 2n)
j=i-n 3 3
Let
3: = 5i + Zi + 3i 1=0,1,...,2n

If we substitute equations (3.3.32), (3.3.36) and (3.3.38)
into (3.3.5) and multiply both sides by the common factor
Y-2(Nm-n)' we obtain the equation

— 2n ‘— 2n-1
DOY + OlY +

... + a2n-1Y + E2n = 0
where the 3i are given above. By reordering the terms in
the summation we obtain-the result given in the third part

of the theorem.

QED

60

Theorem 3.3.2 states that in order to find the sequence of
time-energy optimal controls it is necessary to find the
roots of a polynomial of order less than or equal to Zn
where n is the order of the system. Once the roots of
equation (3.3.8) have been found, the complex roots can be
discarded and the real roots Yi examined. The value of Y1
is substituted into equation (3.3.3) to obtain a candidate
for an energy optimal control sequence. The quantity UTU
corresponding to each value of Yi is computed. The root
that has the smallest value of UTU is the one requiring
minimum energy to reach the boundary of the target. Since
the expression for U was obtained by setting the first
derivative of the Lagrangian equal to zero, this condition
is also a necessary condition for determining the maximum
energy required to reach the target in N samples. Thus
one of the roots of the polynomial (3.3.8) corresponds to
the sequence of controls requiring maximum energy to reach
the target. For computational purposes the roots of the
polynomial (up t036 th order) can be computed by a pre-
written FORTRAN program [IBMl].

It has been shown that the target can always be
reached for some N such that Nm 2 n. If we choose N
such that Nm > n the minimum energy solution may require
considerably less energy (all illustrated in Example 3.3.1).
In this case the meNm matrices Gi appearing in Theorem

3.3.2 may be of large dimension requiring long computational

61

time. An alternate formulation is now given which miti-
gates this-problem. Some preliminary definitions are

given-first. Let

bN = CNx(0) (nxl vector)
W = ON? (anm.matrix)
N N
='W WT (nxn matrix)
KN , N N

Then by equations (3.2.10), (3.2.12), and (3.2.13)

_ T
QN ’ WNWN

_ T
dN ‘ WNbN

_ T _ 2
eN — bNbN R

The expression for U given in equation (3.3.3) then becomes

-1 _ _ _ T -1 T
) dN ‘ (YI WNWN) WNbN

Applying Theorem 2.1.21 to this last term with A replaced

U = -(YI - QN

by yl, B replaced by W3 and C replaced by I, we get an
alternate expression for U.

T -l
- WN(YI K ) b

U N N

From equations (3.2.5), (3.2.11) and the above definitions,

we have that

IID

x(NT) = b - W U

X N N

N

Therefore,
1

X
II

T - T
bN + WN(YI-WNWN) WNbN

62

-l T

_ _ T
— [I + WN(YI WNWN) WN]bN

We now apply Theorem 2.1.21 to the quantity in brackets

with A replaced by I, B replaced by WN and C replaced by

I/Y. This gives xN = (I-KNY-1)-1bN. Therefore, x§xN

b§(I-KNY-1)-2bN, and if the boundary of the target is to
be reached in N samples, we require that

T -1 -2 2 _
bN(I-KNY ) bN R — 0 (3.3.40)

This can be rewritten as

2 T -2 2 _
Y bN(yI-KN) bN R — 0
or
2 T . . 2 2 _
Y bNadj(yI-KN)adj(yI-KN)bN - cN(y)R — 0
where
_ _ _ — n — n-l — —
cNKY) - IYI KNI - de + siY + ... + Sn-lY + 3n
ad'(YI- )=EYn-l+EYn-2+ +6 Y+§
3 KN o 1 "' n-2 n-1

Making these substitutions and collecting terms, the above
polynomial reduces to the polynomial given in the follow-
ing theorem.

Theorem 3.3.3 a) If the sequence of time-optimal con-
trols is not unique, the sequence of energy-Optimal con-
trols for this value of N is given by

_ _ T _ -1
U - WN(YI KN) bN (3.3.41)

where y is a root of the polynomial

2n 2n-l _
aoY + aly + ... + 2n—1Y + dzn — 0

63

The ai are given by

T —-— 2-1— .
Z - , , . < <
j=0 bN(GjGi_j)bN R 3331-] for 0 1 Nm
(1. =
l N? T("" ) 2“ f 1 2
G.G. . b - R 3.5. . or Nm+ c i < Nm
j=i-Nm bN J 1 3 N 3 1 3
where 3. and 6i are given by
G0 = I s0 = 1
G1 = KNGo + SlI s1 = - tr(KNG0)
Gn-l - KNGn-Z + Sn-lI 5n = - (l/n) tr(KNGn_l)
Gn = KNGn-l + SnI = 0
b) If N > n/m, the ai become.
F .
1 T—'— 2—— ] .
j:O[bN(GjGi_j)bN -R SjSi-j- for 0 < 1 < n-1
n-1
T‘— — 2—-— 2
0t- = )3 E3(G.G. .)b - R 8.5. 3] -2R 3 s.
1 fl j=i-n+l N 3 1-3 N j 1- n 1-n
for n,£ i < 2n-2
-2 Sn-lsn for 1 = 2n-l
-R2§2 for i =-2n

 

K. n

The proof of this theorem is similar to that for Theorem
3.3.2 so it is not repeated. The advantage of this expan-
sion is that the 51 are of order nxn instead of meNm as
in Theorem 3.3.2. Thus when N is large the matrix multi-

plication is less likely to become prohibitive.

64

The results presented thus far have been for
determining time-energy optimal controls to the boundary
of the target. It has already been shown that the bound-
ary of the target can.be reached in less than or an equal
number of samples as to reach the interior of the target.
Theorem 3.3.2 gives a procedure for determining a sequence
of minimum energy controls to the boundary of the target.
The question might be asked if the minimum energy solution.
to the interior of the target could be less than that to
the boundary of the target. The following theorem shows
that this can only happen for the trivial case when
u(O) = u(T) = ... = u[(N-1)T] =_0. Heuristically, we see
this case could arise if the system had negative eigen-
values. By letting u(0)=u(T)=...=u[(N-1)T] = 0, the sys-
tem "coasts" towards the origin.and thus enters the target.
If the sampling period is such that x(NT) is contained in
G, then this is the minimum energy sequence.

Theorem 3.3.4 Let the initial state lie outside the target

 

set, and let N 2 Nm where Nm is the minimum number of sam-
ples required to reach the target. If eN < 0, U = 0 is
the sequence of minimum energy controls that drive the
initial state to the target. If eN > 0, the sequence of
minimum energy controls drives the initial state to the
boundary of the target.

Proof- By equations (3.1.3), (3.2.8) and (3.2.13) we have

that §EG={x(NT):xT(NT)x(NT)<R2} if and only if

65

fieHifU: UTQNU-2d§U+eN s 0} where E and § are related by
x[(k+1)T] = c§<kT)+Du(kT), '6 =_[(u(0),u(T),...,u[(N-l)T]]T.
The sequence U=0 is contained in H if and only if
eNSO. This sequence is, of course, the minimum energy
solution. Suppose eN>0. Then the sequence U=O does not
belong to H. Furthermore, the sequence with minimum IIUII2
must be a boundary point of H. To show this, assume that
an interior point p of H is such that lel2 = minimum of
“UHZ. Since p is an interior point, there exists a neigh-
borhood S about p that is contained in H. Consider the
line segment from the origin (U=0) to p. Let q be the
point of intersection of the boundary of S and the line
segment. Then by construction q must lie between p and
the origin. Therefore, Iqu2 < ”p”2 since q is closer to
the origin. Hence by contradiction, the sequence of
energy-optimal controls are boundary points of H. The
boundary points of H are those sequences of controls that
drive the initial state to the boundary of G, and thus the

result follows.
QED

The following examples illustrate the theory pre-
sented above.
Example 3.3.1 Consider the single input system described
by the following transfer function and corresponding block

diagram.

66

 

_ 1
G<S> — s(s + l)
u(s) I l I x2 l x1
1 s + l I " s

 

It is assumed that the control signal u(t) is the output
of a zero-hold device. The sampling period is T = 1
second. The differential equations corresponding to the

above system are:
x1 0 l x 0

22 O -l x

II
+

u(t) (3.3.42)

We want to find a sequence of controls which drive the
system from the initial state x(0) = (10,-12)T to the
target xT(NT)X(NT) <1 in the fewest number of samples

N. If the sequence is not unique, we want to determine a
sequence that minimizes the total energy to reach the
target. Compare the minimum energy for N samples with
that for N + 1 samples.

Solution The discrete-time system corresponding to equa-

tion (3.3.42) is:

x(k + l) = Cx(k) + Du(k) (3.3.43)
where -1
l l-e
C = -l (3.3.44)
0 e
-l
e
D = (3.3.45)
-1

67

Using the technique described in Section 3.2, we find
that the minimum number of samples required to reach the
target is N = 2. Moreover, the solution is not unique.

By routine calculations, we find that

0.6431 0.4293
Q2 = (3.3.46)
0.4293 0.5349
d2 = (0.6662 1.1649)T (3.3.47)
e2 = 1.7788 (3.3.48)
0.7500 -0.6615
92 = (3.3.49)
0.6615 0.7500
1.0217 0
A2 (3.3.50)
0 0.15627
From Theorem 3.2.2, we have
U = P Y 1 Q '1 d (3 3 51)
2 2 2 ' '
where
YTAZY = R2 (3.3.52)

If we substitute equation (3.3.50) into (3.3.52) and re-

call that R = l, we have

2 2
y0 y1
5797§§ + @7355: - 1 (3.3.53)

Equation (3.3.53) is that of an ellipse; the square of

the semiaxes are 0.9788 and 6.3992. The ellipse is shown
in Figure 3.3.la. The interpretation of this ellipse is
that every point on the ellipse corresponds to a sequence

of time-optimal controls. To determine the actual

68

 

 

 

 

Fig. 3.3.la. Locus of time-Optimal controls in yo-y1
plane for Example 3.3.1.

u(l)

 

 

 

: : + .L .1 11(0)
-3 -2 -l l 2

Fig. 3.3.lb. Locus of time-optimal controls in u(O)-u(l)
plane for Ekample 3.3.1.

69

sequence of controls U, we use the transformation given by
equation (3.3.51). This transformation rotates and shifts
the coordinates, but distances and angles are preserved.
Thus after the transformation, the locus of time-optimal
controls is again an ellipse. This ellipse is shown in
Figure 3.3.lb. Any point on this ellipse represents a
sequence of time—optimal controls to the boundary of the
target set. Points inside the ellipse map into points
inside the target. For example, if we take the point "p"
in Figure 3.3.lb, this gives the sequence of time-
optimal controls

u(O) -2.243

u(l) 3.049

If we substitute this sequence of controls into the state

equation (3.3.43), we find that

x(O) (10 -12)T x(1) = (1.59 -5.83)T

x(2) (—0.976 -0.218)T and xT(2) x(2) = 1 as desired.

Returning to the problem of determining the mini-
mum energy time-optimal controls, we see from Figure
3.3.lb, that this sequence is the one corresponding to
the point on the ellipse that is closest to the origin.
To determine this sequence we use the first part of
Theorem 3.3.2.

1 0 S = l

0 l S = -tr(Q = -l.l780

2)

70

-0.5349 0.4293
G1 = Q2 + $11 = (3.3.54)
= 0.15966

82

The polynomial discussed in Theorem 3.3.2 then becomes

4 3 2 2' _
DOY + DlY + sz + D3Y + 04 — 0 (3.3.55)
where
00 = e2 = 1.7788 (3.3.56)
_ T __
pl — 2(d2d2 + e231) — 0.58916 (3.3.57)

Similarly by Theorem 3.3.2

92 = —o,41598 p3 = 0.37616 04 =-0.02549 (3.3.58)

Substituting equations (3.3.56)-(3.3.58) into (3.3.55)

and solving for the roots of the latter, we obtain

Y2 0.07439 (3.3.60)

These values of Yi are substituted into equation (3.3.3)

to obtain a sequence of controls.

For Y = Y1, u(O) = 0.2125 u(l) = 0.9216 Energy=0.895
(3.3.61)

and for Y = Y2, u(O) = -2.492 u(l) = 4.853 Energy=29.76
(3.3.62)

Thus the sequence corresponding to Y1 is the minimum

energy solution while the sequence corresponding to Y2 is

the maximum energy solution. After substituting the

71

controls into the state equation (3.3.43), we obtain-the

following sequence of states:

x(0) = (10 -12)T x(1) = (2.493 -4.280)T
x(2) = (0.126 -0.992)T and xT(2)x(2) = 1
x(0) = (10 —12)T x(1) = (1.498 -5.990)T
x(2) = (-0.503 0.864)T and xT(2)x(2) = 1

The sequence of controls given by equations (3.3.61) and
(3.3.62) are shown as points P1 and P2 respectively in
Figure 3.3.lb. As mentioned previously, the minimum
energy solution (P1) is closest to the origin while the
maximum energy solution (P2) lies on the ellipse at the
farthest point from the origin.

We now turn to the second part of the problem,
that is, determining the minimum energy solution for N = 3

samples. In this case we find

”0.84354 0.72170 0.39043T
Q3 = 0.72170 0.64306 0.42933

 

 

_9.39048 0.42933 0.53491

9..
ll

(1.3337 1.2153 0.89361)T
1.3241

Since N > n, we can use the third part of Theorem 3.3.2.

We find

CH

S

Ol—‘O

1 = -tr(Q3)= -2.02152

6)

II

H

II
Po c> #4
H c:

 

 

72

-1.l7798 0.72170 0.39048
G +3 I = 0.72170 -1.37845 0.42933
0.39048 0.42933 -l.4866

_ _ 1 =

0.15966 -o.21840 0.05874
02 = 03G1+s2I = -0.21840 0.29874 -0.08034
' 0.05874 -0.08034 0.0216

_ , l _

From the third part of Theorem 3.3.2,

— 4 — 3 — 2 ._ — _
poY + plY + sz + p3Y + 04 — 0 (3.3.63)
where
30 = 1.3241, 31 = 2.7551, 32 = -4.8603,

The real roots of equation (3.3.63) are
Y1 = 0.25884, Y2 = 0.29313, Y3 = 0.69018, Y4 = -3.3229
(3.3.64)
If we substitute the Yi into equation (3.3.3) to obtain

the sequence of controls, we find

For Y = Y1, u(0)=-0.008189 u(l)=0.61190 u(2)=2.29686
and Energy = 5.650 (3.3.65)
For Y = Y2, u(0)=l.72465 u(l)=l.01916 u(2)=—0.899ll
and Energy = 4.8215 (3.3.66)
For Y = Y3, u(0)=1.3112 u(l)=l.l6l4 u(2)=-0.7539

and Energy = 3.6368 (3.3.67)

73

For Y = Y4, u(O) = 0.2619 u(l)=0.2395 u(2)=0.1785
and Energy = 0.15778 (3.3.68)

By comparing (3.3.65) - (3.3.68), we see the sequence of
controls given by (3.3.68) is the minimum energy solution.
The corresponding sequence of states using the Optimal

control is

x(0) = (10 -12)T

x(1) = (2.5109 -4.2490)T
x(2) = (-0.08689 -1.41176)T
X(3) = (-0.91363 -0.40654)T

and xT(3)x(3) 1

The minimum energy for N = 3 is 17.7% of that for N = 2.

Example 3.3.2 In this example we wish to determine the

 

sequence of minimum energy controls for N=2 in Example
3.3.1 by using Theorem 3.3.3 instead of Theorem 3.3.2.
Solution, Using the numerical values for C2, x(O), and D

in Example 3.3.1, we find that

b2 =-C2x(0) = (-0.37597 -1.62403)T
2_ 0.76746 -0.36788
w2 = c F2 =
0.23254 -0.63212
T 0.72432 0.41101
K2 = W2W2 =
0.41101 0.45366
Then
__ _ _ 1 0 E0 = 1
G0 - I - _
0 l s = - tr(K ) = -l.l7798
1 2
_ _ _ _ -0.45366 0.41101 _
G1 = K260 + s11 = 32 = 0.15966

0.41101 -0.72432

74

 

If we substitute these values of E: and 51 into the

second part of Theorem 3.3.3, we find that

aoY4 + a1Y3 + d2Y2 + a3Y + a4 = 0 (3.3.69)
where
do = 1.788, a1 = -0.58922, 02 = -0.41596, a3 = 0.37615,
04 = -0.02549 (3.3.70)

Upon comparing the polynomial given by (3.3.69)-(3.3.70)
with the corresponding polynomial (3.3.55)-(3.3.58) in
Example 3.3.1, we see that they are the same except for
roundoff error. Thus the roots are the same and in par—
ticular, the root Y corresponding to the minimum energy
solution is the same. If we substitute this value of Y
into the expression for U given in Theorem 3.3.3, we ob-
tain the same sequence of controls as that given in
Example 3.3.1.

In Example 3.3.1 it is noted that the sequence of
energy optimal controls correSponds to the negative root
of a polynomial. It will be shown that this is always
the case. Furthermore, the negative root is unique imply-
ing that the sequence of energy Optimal controls is
unique. We begin by proving the following theorem.

Theorem 3.3.5 Assume there exists a sequence of controls

 

that drives the initial state to the target set. Then

75

a sequence of energy optimal controls is given by

_ _ T _ -l
where b = CNx(O) W = CNF’ and K = W WT and Y is a root
N ' N N N N N'
of the equation
Y 2 2
28471—3?) = R . (3.3.72)

Here the summation is over all the distinct eigenvalues

A. of K

J N' Moreover,

Bj = ZHPTbN)i]2 (3.3.73)
where the summation is over all entries 1 such that Ai=xj'
(If all eigenvalues are distinct, Bj is the square of the
j th element of PTbN.) P is any orthogonal matrix which
diagonalizes the KN matrix. That is, A = PTKNP, PTP = I
and A is a diagonal matrix with diagonal elements equal

to the eigenvalues of KN'

The minimum energy is
A.
= , -——:—l—F!.
J 281 (Y 11)
where the summation is over all distinct eigenvalues xi
of KN.
grgg£_ From equations (3.3.40) and (3.3.41), we have that

the sequence of energy Optimal controls is given by

_ _ T _ -1
U - WN(YI KN) bN (3.3.74)

where Y is a root of the equation

113” - KNv'lebN - R2 = 0 (3.3.75)

76

Since KN is a symmetric matrix, there exists a matrix P

T

such that KN = P A PT where P P = I and A is a diagonal

matrix with diagonal elements equal to the eigenvalues of

KN. The quantity (I - Kqu-J').2 in equation (3.3.75) can
then be written in a different way.
(I - 17113,)"2 = [I - Y—lP A PT]—2
= [PPT - y'lp A PTJ'2
= [P(I - y"l A)PT]'1[P(I - 7'1 MPTJ'l
= (PT)'1(I - v“1 A)’1P'1(PT)"1(I - y'1 A)?"1
= p(1 - Y-lA)-2PT (3.3.76)

From equations (3.3.75)-(3.3.76) we have

-1 2

(PTbN)T(I - y A)-2(PTbN) = R (3.3.77)

2

The quantity (I - Y-1 A)- is a diagonal matrix. Let

¢i = (7—:1x;)2, i=l,2,...,r where r is the number of dis-

tinct eigenvalues Xi of KN. Then if (PTbN)i, i=l,2,...,n

are the elements of the vector PTbN, we have

 

¢ - P _
1. 0 0 (PTbN)l
'¢
0 1 0 0 T
EPTbN)1,(PTbN)l,...,(PTbN)é] . 02. . . ‘P bN)2
: '92. : . =R2
'. 0
0 0 ¢r. 0
' T
_o . . . . 0 9i :? bN)E

 

 

 

77

This can be written as

Y 2 T Y 2 T
(m) 2 (P bN)i + (—"—") Z (P bN)i +...

1 all 13 Y ' A2 all 13
A1= l A1:)‘2
+ (T'Z—‘r’z Z ‘PTbN)° = R2
r all i9 1
xi=1r

By defining Bj as in equation (3.3.73), we have that

Y 2 _ 2
2 8347—777) 7 R
distinct J
A.
J
and the first part of the theorem is proven.
To determine the expression for the minimum

energy, we use the expression for U given by equation

(3.3.71).

UTU = b§(YI-KN)‘1wNw§(YI-KN)‘le
= b§(YI-KN)‘1RN(YI—KN)‘1bN
= Y'zb§(I-Y'1p A PT)-1P A PT(I-Y'1P A PT)'1bN
= y-2b§[P(I-Y—l A)PT]-1P A PT[P(I-Y-1A)PT]-1bN.
= y-szP(I-Y_1A)-l A(I-Y'l A)'1PTbN

 

:>:
’2
(Y Aj)

78

where the summation is over all the distinct eigenvalues

of KN.

QED
In general, the P matrix is not unique. However,
the results given above do not depend on this nonunique—
ness. A column pj of P corresponding to a distinct eigen-

H2 = 1. It follows

value is normalized so that IIij2 = "Pi
that pj can assume only two directions; the one opposite
the other. (PTbN)§is then the same for either choice of
Pj' If an eigenvalue is repeated q times, then there are
still q independent eigenvectors associated with this

eigenvalue since the matrix to be diagonalized, KN, is

g
symmetric. It then follows that Z (PTbN)§ is the same
i=1

regardless of the choice of P.
Theorem 3.3.5 can then be used to determine addi-

tional properties of the energy optimal sequence of con-

 

 

trols.
Theorem 3.3.6 Let eN > 0. Then equation (3.3.72) has a
unique negative root Y1. If u = -Yl, then
1min g u s Amax
a a
1

where a s [(eN+R2)/R2]z - 1. An approximation to the
negative root Yl is

tr(KN)

Y1 = - an

79

_ _ T T T
_ T T _ T
- bNP P bN — bNbN

Then by Theorem 3.3.5 and equation (3.2.13),

 

2 R2
R2 _ R‘;
Zg—(YY " X12=)bTb xT(cN)Tch= +RT= (1 +16.)2
bN bN 0 0
where a = [(eN + R2)/R2]2 - 1. If eN > 0, then —————7<
(1+a)
Let u = - Y >0. Then
2
:2: Bi (“E‘r‘) 1: ——l——7 < 1 (3 3 78)
‘F— u + i (1+a)

The quantity 81/8 6 land ZBi/B = 1. Therefore, since
(F5:Ex—)‘2 <1, it follows that there always exists a value
i

of p which satisfies (3.3.78). The value of u is unique
. 2
. u . . .
Sincd (U_:—x;) lS monotone increa31ng for u > 0, and the
sum of monotone increasing functions in monotone increas-
ing. Thus for a given a there is only one value of u such

that (3.3.78) is satisfied. Let Xi = A . Then

max

u + min B u + min (1+0I.)2
Let A. = A . . Then

1 min
2 2
B.
(+1 )=:—*—(——n )»——-w
“ + min B “ + min (1+6)

Therefore,

 

max min
or
u < l g H
u + X 1 + a u + X
max min

which implies that

max 2 1 + a >
or

Amin < pas Amax (3.3.79)

and the second part of the theorem is proven. From
(3.3.79) we see that no must lie between the smallest and
largest eigenvalue of KN. As an approximation, we could

choose the average value of the eigenvalues. Thus

By Theorem 2.1.19, the sum of the eigenvalues of KN is

just the trace of KN. Thus

tr( )
Y="--———-aKN
n QED

Theorem 3.3.7 Let TN > O. The unique sequence of mini-

mum energy controls is given by equation (3.3.71) where

 

Y is the negative root of (3.3.72).
Proof Let Ya be a root of (3.3.72). It is first shown

that Ya < Xmax' Suppose the opposite is true, that is,
1

max A max

 

 

> 0. Then 0 < < l and-l -

a a

Ya > )‘max 4 l.

81

1 _ 1§§§)-2 2 1. This implies that

Therefore, Y

 

Zsi Ya 2“ Bi
1 since = 1. This is a con-
8" y -7 3 23’
a max

tradiction since by assumption Ya is such that

a

281 Ya 2_ R2 < 1
FY -Xi ' ‘2

Therefore, Ya < Amax'
Let us return to the expression for the Lagragian
L given in the second equation after equation (3.3.2).

Taking the second derivative, we find that

2 Q
d L N
do2 Y

A necessary condition for a minimum energy solution is
that I - QN/Y be positive semidefinite. The sufficient
condition is that I - QN/Y be positive definite. If

Y < 0, then I - QN/Y is positive definite since QN is
positive semidefinite. Thus the negative root of (3.3.72)
corresponds to a minimum energy solution. Suppose that

Y > 0. By the above result we have that}.m > Y > 0.

ax
Then - QN/Y has a negative eigenvalue greater than 1 and
I - QN/Y has a negative eigenvalue. Thus I - QN/Y is not
positive.semidefinite and therefore no value of Y > 0 can
correspond to a minimum energy solution. Hence, the

minimum energy solution corresponds to the unique negative

root of (3.3.72)
QED

82

We can now compare the results given in Theorem
3.3.7 with those of Theorems 3.3.2 and 3.3.3. In the
latter, the sequence Of Optimum controls was found by
solving for all the roots of a polynomial. The coeffi-
cients pi of this polynomial are Obtained from a sequence
Of matrix multiplications and additions. Due to roundoff,
the values Of-the pi may be slightly in error. Sometimes
this can result in a large change in the value of the
roots. The formulation given in Theorem 3.3.7 does not
require the pi to be found. However, it is necessary to
determine the diagonalizing matrix P and the eigenvalues
of KN. If we define

’ 2
h(Y) = ZBj(V-:Y_}\—-) - R2 (3.3.80)
3

in equation (3.3.72) then by the above results we know that
h(Y) is monotone on (-O0,0). Furthermore, Y = Y1 =

- tr(KN)/dn is an approximate root of h(Y). This allows

us to find the negative root of h(Y) by a numerical
technique such as Newton's Method [JAMl] using Yl as a
starting value.

Example 3.3.3 We wish to determine the sequence of mini-

 

mum energy controls for Example 3.3.1 (N=2) by using
Theorems 3.3.5-3.3.7.
Solution A matrix that diagonalizes the K2 matrix in

Example 3.3.2 is

83

0.81017 -0.5862
0.58620 0.81017

The eigenvalues of K2 are

A1 = 1.02171 and 42 = 0.15627 (3.3.81)

From Example 3.3.2, h2 = (—0.37597 -1.62403)T. Thus

T 1.25661
P b2 =

-l.09535

T 2
81 = (P b2)1 = (1.25661) = 1.5791 (3.3.82)

and
_ T _

82 — (P b2)2 - 1.1998 (3.3.83)

Substituting (3.3.81)-(3.3.83) into (3.3.80) gives

 

. 2 2
= Y _____l___ _
h(Y) 1.5791(Y_1_02171) + 1.1998(Y_0.15627) 1
(3.3.84)

From Theorem 3.3.6, an approximate root of (3.3.84) is
tr(Kz)

Y=Y1='—2r'

2 2 1
where a = [(e2 + R )/R J? - 1.

(3.3.84)

From Example 3.3.1, e2 = 1.7788 and R = 1. From Example

3.3.2, tr(K2) = 1.1780. Thus Yi --0.88. Using Yl as an
initial guess of the root of h(Y), we find by Newton's

Method that the negative root of h(Y) is

Y = -0.62999 (3.3.85)

84

By Theorem 3.3.7 this value Of Y corresponds to the mini-
mum energy sequence Of controls. If we compare (3.3.85)
with the negative root given by (3.3.59) which was Obtained
by a different method, we see that they are the same ex-
cept for roundoff_error. Thus the sequence of energy
Optimal controls are the same as those Obtained in Exam-
ples 3.3.1 and 3.3.2.

3.4 Time-Optima11COntrol Using
Feedback Control

 

 

The previous sections of this chapter were con-
cerned with determining the minimum number of samples and
a corresponding sequence of controls which drive the sys-
tem from a given initial state to a hyperspherical target.
For each different initial state it is necessary to per-
form a new set Of calculations to determine a sequence of
time-Optimal controls. TO avoid these calculations, it
would be desirable to synthesize the controller as a sam-
ple function of the state Of the system. It was shown in
Section 3.1 that under the assumption that N = n/m =
integer and ID,CD,CZD,...,CNDl | ¢ 0 that the target
could always be reached in N samples. On the other hand,
if N < n/m the target can not always be reached for an
arbitrary initial state. Since we wish to synthesize the

controller as a function of an arbitrary state, the dis-

cussion will be limited to the case where N = n/m.

85

The problem of time-Optimal control using a feed-
back controller has been studied previously [TOU3], [KUOZ]
for the case when the target is the origin. It is shown
here that for the case of a hyperspherical target the Op-
timal control law can be put in a form that differs from
that Of the case when the target is the origin only by a
constant. The problem is now stated more formally.
Problem Statement Given the linear discrete-time system

described by

x [(k+1)T] = Cx(kT) + Du(kT) (3.4.1)
x(0) = x0

We wish to determine a sequence of controls u(kT), k =
0,1,...,N-1 which drives the system from an arbitrary

initial state xO to the target described by

{x(NT) : xT(NT) x(NT) 6 R2}

Where R is a real number. We require that the control be
a function of the state of the system. It is assumed
that N = n/m is an integer.
Solution The problem is solved under the same assumptions
as those given in the Open-loop case. That is, it is as-
sumed that the system is controllable and that ID,CD,...,
CNS1 | # 0. As discussed previously, the second assump-
tion is no assumption at all if the system has a single
input.

By using a technique similar to that used to

derive equation (3.2.3), we can write the solution to

(3.4.1) as

86

N-l .
x[(k + N)T] = CNx(kT) + cN 2 c"1 + 1’0 u[(k + i)T]
i=0
_N _N—
- C x(kT) C FNUk
where FN = [F0,Fl,...,FN_1] and the F1 are given by equa-

tion (3.2.4).

Uk = [u(kT),u[(k + 1)T],...,u[(k + N-1)T]]T

If we set x[(k + N)T] = 0, then

 

 

_u(kT) q
u[(k + 1)T] = igl x(kT) (3.4.2)
Lu[(k:+ N-1)T]_

F- exists by the assumption that ID,CD,...,CN5l I # 0.

N
Premultiplying both sides by the matrix [ImO] where Im is

an mxm identity matrix gives

u(kT) = [Im0]F;1x(kT) k = 0,1,...,N-1
(3.4.3)
This expression for u(kT) represents a sequence of time-
Optimal controls that drive the system to the origin.
For the case of a hyperspherical target we assume that

u(kT) has the following form
_ —-l
u(kT) — [Im0]FN x(kT) + vR

where v is to be determined. The following theorem pro-
vides a solution to the time-Optimal control problem.
Theorem 3.4.1 Given the system described by (3.4.1) and

the assumptions that ID,CD,...,CN-1D| # 0 and N = n/m =

87

integer. Then a sequence of feedback time-optimal con-
trols to the target is given by u(kT) = [Im0]F;1x(kT) + vR
k = O'lpooopN-l (3.404)

where v is any vector that satisfies the inequality

VTGTGV < 1 (3.4.5)
where
N'1 .—-1 i
G = X (C + D[I 0]F ) D (3.4.6)
i=0 m N

If we choose v such that

VTGTGV = 1
the sequence of controls given by (3.4.4) drives the sys-
tem to the boundary of the hypersphere. If we choose

v =.0, the controller drives the system to the origin.

Proof From (3.4.1) and (3.4-4)

 

x(T) = [c + 0(1m015§11x0 + DvR

x(2T)

Cx(T) + Du(T)

[C + D[Im0]§§l] x(T) + DvR

—-1 2 —-l
[C + D[Im0]FN ] x0 + [C + D[Im0]FN ] DvR

+ DvR

or in general

--1 i
[C + DIImOJFN ] DvR

——1 N N’1

x(NT) = [C + DIImOJFN ] x0 + -E
1-0

(3.4.7)

If we set R = 0

88

x(NT) = [ c + nlxmolfglleo

It has been shown that with R = 0, u(kT) = FN1x(kT),

k = 0,1,...,N-1 drives the system to the origin in N
samples. Thus

to + D[Im0]F;1]Nx = 0

0
Since x0 is arbitrary, it follows that

-l]N

9 =;[c + D[Im0]FN

C = 0 (3.4.8)

Thus 0C is a nilpotent matrix of index N. The prOperties
of TC have been studied by several authors [CAD3], [FARl].
(For a correction to the latter reference, see [TUEl].)
Substituting (3.4.8) into (3.4.7), we get
N-l

x(NT) = .2

[c + D[I 0]F—l]leR
1-0 m N

Since we require that the target be reached in~N samples,

we have

R2 2 xT(NT)x(NT) = R2 vTGTGv (3.4.9)

where G is given by (3.4.6). Thus we require that

vTGTGv < 1

From (3.4.9) we see that if we choose VTGTGV =41, then
x(NT) will lie at the boundary of the target. If v = 0,
it has already been shown that x(NT) = 0.

It is worth noting that neither FN

on x(kT) or R and that an expression for v can always be

nor v depend

found to satisfy (3.4.5). The technique is illustrated

by the following example.

89

Example 3.4.1 Given the system described in Example 3.3.1

 

with X(0) = (10 -12)T, and R = 1. We wish to determine
a sequence of time-Optimal control which drive the initial

state to the target using feedback control.

Solution From Example 3.3.1, we have for N = 2
_ 0.71828 3.67077
F = [F ,F ]
2 0 1 -1.71828 —4.67077
0.36788 1 0.63212
D = C =
0.63212 0 0.36788
Thus
T T _ T T —~1 T -1
v G Gv — v D [I2 + C + D[120]F2 ] [12 + C + D[I20]F2 ]Dv

Making the appropriate substitutions while noting that v
is a scalar in this case we have

VTGTGV = 0.39955 v2

By Theorem 3.4.1 we require that

0.39955v2 s 1

or
-1.582 S V < 1.582 (3.4.10)

If we choose v = l, the feedback controller is given by

u(kT) = [1 01551x(k) + 1
= [-l.582 —l.243]x(k) + 1 (3.4.11)
Thus with k = 0
10
u(O) = [—1.582 —1.243] + 1 = 0.0998

-12

90

From the state equation, we have

1 .63212 10 0.36788 2.4513
x(1) = + (0.0998) =
0 .36788 -12 0.63212 4.3515
From (3.4.11) the control at the next step is
2.4513

u(1) = [-1.582 -1.243] + 1 = 2.5323
4.351

and

1 .63212 2.451 0.36788 0.6322
X<2> =. + (2.5323) =

0 .36788 -4.3515 0.63212 0

Therefore, xT(2)x(2) = 0.3997 < 1 as desired. The energy
'required is u2(0) + u2(1) = 6.423.

From (3.4.10) and Theorem 3.4.1 a sequence of con—
trol to the boundary of the target can be found by choos-
ing v =,: 1.5820. If we repeat the above steps, we get

the following

For v = +1.5820 For V'= -l.5820
u(O) = 0.6818 u(O) = -2.4822
u(1) = 2.3182 u(1) = 3.4823
x(0) = (10 -12)T x(0) = (10 -12)T
x(1) = (2.665, -3.984)T x(1) = (1.5014, -5.9836)T

x(2) = (1.000, 0.000)T x(2) = (-1.000, 0)T
xT(2)x(2) = 1.000 xT(2)x(2) = 1.000
Energy = 5.839 Energy = 18.288

Thus the minimum energy feedback controller requires an
energy of 5.839. From Example 3.3.1, the minimum energy

Open—loop controller required an energy of 0.895. Thus

91

the optimum closed-loop controller requires 6.52 times
as much energy as the Open—loop controller. As an addi-
tional comparison, if we set R = 0 to find the sequence

of controls which drive the system to the origin, we get

u(O) = -0.9002 x(0) = (10 -12)T
u(1) = 2.9002 x(1) = (2.083, -4.984)T
x(2) = (0.000, 0.000)T

Energy = 9.2215
Using feedback control, the energy required to drive the
system to the origin is 1.579 times as much as that re-
quired to drive the system to the boundary using v =
1.5820.

The feedback controller has the advantage of a
simple form independent of the initial state. However,
there are two disadvantages. First, a certain period of
time is required to perform the matrix multiplication and
addition required to find u(kT). If the sampling period
is too short, this cannot be done. Second, it may turn
out in practice that not all the components Of x(kT) are
available for a measurement. In this case an estimate
can be made of the unmeasureable components of x(kT).

If the system is observable and all past inputs and out?
puts are available, then x(kT) can be determined exactly.
For example, let the state equation and output equation
be given by

x[(k + 1)T]
y(kT)

Cx(kT) + Du(kT)
Bx(kT) k

ll
0
‘
..-
‘
‘
Z

I
1.:

92

 

 

 

 

Then under the assumption that [BC-1, BC-2,...,BC'-n]_l
exists, it can be shown [K002] that
F- _l—-l ‘
BC 'y[(k - 1)T]
x(kT)= Bc“2 y[(k - 2)T]
130-“:L _y[(k - n)'I‘]__
r - q — —
+ BCFZD Bchn . '
_Bé'no BC-fi+1D . . .BC‘lD‘ u[(k - n)T]d

 

 

 

 

Thus if n past measurements of the output y(kT)
and input u(kT) are available, we can determine x(kT)
exactly. For example, if k = 0, we can determine x(O) if
we have the outputs y(-T),...,y(-nT) and inputs u(-T),...,
u(-nT). Once x(O) is determined, we can.find u(O) by
using Theorem 3.4.1.

3.5 Statement and Solution of Time-

thimal'Control Problem with Single
' Input Delay ' ‘

This section is devoted to the time-Optimal con-
trol problem when there is a time delay in the control
signal. Such a delay could occur when the control signal
is sent through long transmission lines. To simplify the
results, it is assumed that the delay time is an integral
multiple of the sampling period. Such an approximation
would be applicable when the sampling period is small

compared with the delay time. For the case when the

93

target set is the origin, the problem has been studied by
several authors [KURl], [KOPl], [KUOZ]. The problem is
now stated.

Problem Statement Given a linear time—invariant system
described by

R = Ax + Bu(t —pT) (3.5.1)
x(0) = x0

where
x(t) is a n x 1 vector
u(t) is a m x 1 vector
A is a n x n matrix
B is a n x m matrix
p is a positive integer described below

It is assumed that u(t) is of the sampled-data type so

that
u(t - pT) = u(kt - pT) for kT s t < (k + l)T.

(3.5.2)
where T is the sampling period. Since it is assumed that
the delay time Td is an integral multiple of the sampling

period, we have

where p is a positive integer. We wish to find the mini-
mum number Of samples N and a corresponding sequence of
controls u(t), u(2t),..., u[(N - p - 1)T] such that
x(NT)eG where G is given by {x(NT):xT(NT)x(NT) < R2}.

It is assumed that x(O) (assumed to lie outside the tar-
get) and the past controls u(-T), u(-2T),..., u(-pT) are

known.

94

Solution We make the same two assumptions as for the un-
delayed system. That is, it is assumed that (l) the sys-

tem is completely controllable and (2)

rank[D,CD,...,CNDl] = maximum (3.5.3)
for N > 0.
Proceeding in.a fashion similar to that used in
deriving the solution to the undelayed system, we write

the solution to (3.5.1) as
t
x(t) = 4(t - tomato) = [:20 Mt - T)Bu(r - pT)dr

Using equation (3.5.2), the above equation can be written

as the following difference equation.

x[(k + l)T] = Cx(kT) + Du(kT - pT) (3.5.4)
where
T
D = “I ¢(T - T)BdT (3.5.5)
0
C = ¢(T)

The solution of (3.5.4) is

k—l‘
x(kT) = Ckx(0) = ck z 0
i=0

1131' um - p)T]

As in equation (3.2.4), we define

Fj = -'C-(3 + 1)D j = 0,1,...,N - 1 (305.7)
Then
k k k-l
x(kT) = C x0 - C 2 Fiu[(i - p)T (3.5.8)
i=0

95

Assuming that the past initial sequence u(-T), u(-2T),...,
u(-pT) is known, then by equation (3.5.8),
k - l - p 2 0 (3.5.9)

We can then write equation (3.5.8) as

k k k-l
x(kT) = C 0 - C 2 F.u[(i - p)T] (3.5.10)
P i=p 1
where
p-l
0 = - 2 F.u i - T 3.5.11
p x0 1+0 1 [( p) 1 ( )

As in the undelayed system, it can.be shown that the
boundary of the target can be reached in less than or an
equal number Of samples as to reach the interior of the
hypersphere. The study will then be restricted to that
of the boundary of the hypersphere.

By using (3.5.10) we have that
XT(NT)X(NT) =
[ N-l ‘ T N-l .
0 - Z F.u[(i - p)T] w [6- Z F.u[(i - p)T]
p i=p 1 N p i=P 1
(3.5.12)

where, as in (3.2.7)

‘(N = (CN)TCN (3.5.13)
Expanding (3.5.12) and performing the same steps as in_
Obtaining (3.2.8), we get

T T— T T
NT NT =U U - 2 U + 8 6
x ( )x( ) p 0N p 35 p pr p

(3.5.14)

where

96

 

 

up = (u(O), u(T),..., u[(N - 1 - p)T])T (3.5.15)
_. _ —T _
QN ‘ FN,prFN,p (3.5.16)
FN,p = [Fp'Fp+l'°’°'FN-1] nx(N-p)m matrix (3.5.17)
Thus
..T T _
prNFp prNFp+l. . .prNFN_l
6 = FT 4 F -
N p+1 N p . (N-p)mx(N-p)m
: matrix
FT 4 F FT 0 F
N-l N p ‘ f ‘ N-l N N-l (3.5.18)
'6 = GT4: 5 (3 5 19)
N p N NIP O o

If p = 0 (no delay). then

U = U
P

QN = QN
EN = dN

where U,QN and dN are defined in Section 3.2.

 

Theorem 3.5.1' fifi is a symmetric matrix with the follow-
ing properties:
a) If N < n/m + p, 6k is positive definite

b) If N > n/m + p, 6 is positive semidefinite and

N
singular
—T -T — T —T T— —T — —
= F = F = F F =
PIOOf QN (FN,p wN NIP) N’p WNFN,p N,p wN N,p QN

Hence QN is symmetric since TN is symmetric.

97

a) By assumption (2),
'

rank[D,CD,...,CN TlD] = N'm if N' s n/m

Since C is nonsingular, this implies that

p+1 p+N'-

rank[CpD,C D,...,C 1D] = N'm if N' < n/m

'-
Thus [CpD, Cp+lD...,Cp+N l

D] is Of maximum rank
if N' < n/m.

Let N = N' + p. Then

rank (Ffi p) = rank[CpD, Cp+lD,...,CN-1D] = maximum
I
if N < n/m + p.
By Theorem 2.1.5, Fg’p ENFNIP is positive definite.

b) If N > n/m + p, then 6k is positive semidefinite
because

T- __ T—T

— _ T
wNFN'py - z wNz 2 0
where z = w y, and w is positive definite. 5 is not
N,p N N
positive definite because 6fi is not of rank (N-p)m.

This follows from Theorem 2.1.1:

rank (5&) g min [rank(F ), rank(wN)]

N,p

w is of rank n. F is of order nx(N-p)m where
N N,p
(N-p)m > n. Thus 6k is an (N-p)mx(N-p)m matrix of rank
less than (N-p)m. Hence 6k is singular and not positive
definite.

Since we are looking for the value of N and the

correSponding sequence Of controls such that

xT(NT)x(NT) = R2

we have that

T — — T —
< ) p 0N p p N ( )
where

N p wN ep
Equation (3.5.20) is of the same form as equation (3.2.14)
for the undelayed system. We can then apply the same
arguments as in Section 3.2 for Obtaining an Optimal
sequence Of controls. This leads to the following theorems
which correspond to Theorems 3.2.2 - 3.2.4. Since the
proofs are the same except that 6k, dfi, 3' replace QN' dN,

N

e , respectively, the proofs are not repeated.

N
Theorem 3.5.2 a) Let N s n/m + p. Then the expression

 

for f(U) given by equation (3.5.20) can be reduced to
YT JEN Y = E = 0 (3.5.22)
P P N

where

_ — ... _ _T _—1 _

by the transformation

_ __1 _
. T _ = T -
where PN 13 such that PN PN — I and.Ifi PN QNPN (3.5.25)

is a diagonal matrix whose diagonal elements are the
eigenvalues of 6&.
b) If N = n/m + p, equation (3.5.22) becomes

tr 3: 2
Y Y - R = 0 3.5.2
p Np ( 6)

99

Theorem 3.5.3 Let N s n/m + p. Then the following is
true.
a) If Eh = a: 5&13 , the unique sequence of controls such

that x(NT)s BC (the boundary of G) is given by

- —-1—
Up T QN dN

— —T —-l — .
b) If eN < dN QN dN, a.nonun1que sequence of controls
exists-such that x(NT)€ G.

._ T —-1 _ . _
c) If eN > Hfi QN dfi, no sequence Of controls ex1sts
such that x(NT)e G.

Theorem 3.5.4 a) If N > n/m + p, a nonunique sequence

 

of controls exists such that x(NT)678G (the boundary Of

G). A sequence of controls can be found from
up = PNY + ‘E'p (FN,pFN,p)-1XO (3.5.27)
where
YT.Ifi y = R2 (3.5.28)
P is chosen such that PTP = I and-7C- = PT 6 P
N N N N N N N

is a diagonal matrix with diagonal elements equal to the

eigenvalues of 6k.

-41‘ —. —T -1
I R = = F* F

h) f 0' Up N,p (FN.p N,p) x0

of controls which require minimum energy to reach the

is the sequence

origin in N samples.

The above theorems are combined together to give
Figure 3.5.1 which describes the method of determining
the value of N and a sequence of time-Optimal controls.

The procedure is illustrated in Example 3.5.1.

.hmaww
usmcfl nufl3 Emummm How mTHQEMm mo Hones: ETEHOAE mcflcflaumumw How pnmzozoah H.m.m .mfim

m

zmamb+wzmn D
cofludaom

a a 0535582

 

 

        

 

 

 

 

 

 

 

 

o .2 mi 21.2 e mi 6.2 6.2 z m
x I I I x I 1 I I 0
HM am we 9% TA an L am ITI a $9 3
wzmumn um: :OHDSHOm x mooammm
W coflusaom OOHDDHOm mavens
l msvflcscoz mmuwcm ESEHGHZ

 

 

 

 

 

OZ mww

 

 

H+mnx

 

OOHHSWTH mTHmEmm mo Hwnfisc ETEHGHE u
mmHmEmm Mo Hones: ETEAGHE mo msam> HMHHB l

E

N

101

The method of determining the minimum energy
solution when the time—Optimal sequence is not unique is
similar to that of the undelayed system. Theorem 3.3.1
for the undelayed system becomes the following theorem.

Theorem 3.5.5 Let N 2 n/m + p. The expansion of the

 

conjoint matrix given in Theorem 2.1.10 for the matrix

QN has the prOperty that Gn+1 = G = .. = 0.

n+2 ' = G(N-p)m
Similarly, Theorem 3.3.2 becomes the following theorem
for the delayed system. The proofs of these two theorems
are nearly the same as those for the undelayed system so

they are omitted.

Theorem 3.5.6 a) If the sequence Of time-Optimal cone

 

trols is not unique, the sequence of energy-optimal con-
trols for the same value of N is given by

-1_

in

where Y is a root of the polynomial

Up = -(YI - QN)

2(N-p)m 2(N-p)m-1
poY + plY +...+ 92(N-p)m-1Y

+ p2(N-p)m

The F3 are given by

102

(—

eN for 1=0

_T- _ .-
2(deN + eNsl) for 1—1
i-2_T _ __ _ i
dN(GjQ Gi-j—2+2GjSi-j-l)dN+eNjiosti-j

—JI' —
2dNGi-1dN +

Z

j=o *
for 2 C i 4 (N-p)m

(N-p)m-1 -T

2 (G.S’G._._ +2G.s._._ )"+3 3. s._._
j=i_(N-p)m_1dN J N l J 2 341 j 1,dN N 3+1 1 j 1,

 

K‘ for (N-p)m+1 < i < 2(N-p)m
where the Gi and si are generated recursively by the

equations

G = I s = 1

G1 = QNGo + 511 s = -tr(QN)

G _ _ =6 G _ _
(N p)m l N (N p)m 2 S(N-p)m

+ s I _ _ 1 —s
(N-p)m-l - mtr(QNG (N-p)m-l)

G(N-p)m = QNG(N-p)m-l

+ =
S(N-p)m 0

b) The quantities in the summations given above have the

following property.

deficj = GjQNGk j,k = 0,1,...,(N-p)m-1

c) If N z n/m + p, the polynomial in part a) above re-
duces to a polynomial of order 2n, that is, the poly-

nomial becomes

103

 

- 2n -' 2n-l - - _
DOY + olY + ... + DZn-lY + 92n - 0
where the;i are given by
r—
eN for 1 = 0
“T- — _
2(deN + eNSl) for 1 - l
—T — i2"—T
3. = { szGl_l dN + jz ojdN(G .Q NGi_ _j_ _2 +203 1 3 l)d
1
_ i
+ e 2 s. s. for 2 S i g n
N j i' j
j= -0
n-l ._ ._
j=i§n_14 (GjQNGi- -j- -2 ZGjSi-j-l)dN+eNSj+lSi-j-1

for n+1 c i i 2n
where the G1 and si are given in part a).

Examples 3.5.1 and 3.5.2 show how the above re-
sults can be used.
Example 3.5.1 Given the system
x(k+1) = Cx(k) + Du(k-1)T (3.5.29)
x(0) = (10 12)T
u(-1) = 0
where C and D are given by (3.3.44) and (3.3.45), respec-
tively.
We wish to determine the minimum number Of sam-
ples N and a corresponding sequence Of controls such that

xT(NT)x(NT) c 1.

II
N

Solution Using Figure 3.5.1, we have that N 2 p+l

Let N=2. Then by (3.5.21) and (3.5.11),

104

— _ T _ 2 _ T _ 2
e2 _ 810281 R — x (0)02x(0) R

Using equation (3.5.13), this becomes
_ 1 0.8647 10
e2 = (10 12) - 1 = 416.82
0.8647 0.7660 -12

From equation (3.5.19),

—T _ T - _ T
1 0.8647 3.6708'
= (10 12)
0.8647 0.7660 -4.6708
= -8.5225

— _ -T —. 3 T _
02 — 82,10282 1 910281 — 0.53491

Thus 3T‘7T‘

— _ — T—-l—
202 d2 - e2 - -281.03. Therefore e2> 202 d2, and
we know by Theorem 3.5.3 that N is not large enough.

Setting N=3, we Obtain

33 = xT(0)03x(0) - R2 = 457.426

-41' _ T — _ T __ _ _

d3 — x (0)w3F3’1 — x (0)w3[F1,F2] — ( 16.5644 8.2511)
(3.5.30)

_, _T _ 0.6431 0.4293

Q3 = F3'lw3F3pl = (3.5.31)

0.4293 0.5349

—T——1— 4— _ - -T—-l—I
We then have d3Q3 d3-e3 — 1.000. Therefore, e3<d3Q3 d3

and by Theorem 3.5.3 we know that N=3 is Optimal, and
that the sequence Of controls is not unique. To obtain
the controls we use the transformation given by Theorem

3.5.2. For this example we have

105

A1 0 1.0217 0
TKB 0 A 0 0.15627

where Al and )2 are the eigenvalues of 63. The P3 matrix,
composed of the normalized eigenvalues of 53, is
0.7500 -O.6614

P = (3.5.32)
0.6615 0.7500

From the second part of Theorem 3.5.2, we then have

1.0217y3 + 0.15627yi = 1 (3.5.33)

One solution of (3.5.33) is

Y1 = (yo,y1)T = (0.7500, 1.6497)T (3.5.34)

The controls are found from Theorem 3.5.2,

- —-1-
U — P3Yl + Q3 (13 (3.5.35)

1
Substituting equations (3.5.30)-(3.5.32) and (3.5.34) into
(3.3.35) gives

u(O) -33.835

U1 = = (3.5.36)
u(1) 13.042
2 2 2
Energy = u (-l) + u (0) + u (l) = 1145

When the controls given by (3.5.36) and the past control
u(-l) = 0 are substituted into the state equation (3.5.29),

we have the following sequence Of states

x(0) = (10 12)T
x(1) = (17.585 4.146)T
x(2) = (7.9288 -19.764)T

x(3) (0.2335 0.9732)T

106

and xT(3)x(3) = 1.00 as desired.

Example 3.5.2 Determine the sequences of controls for

 

the system described in Example 3.5.1 which require mini-
mum and maximum energy to reach the boundary of the target.
Solution From Theorem 3.5.6, the sequence of controls is

given by

_ _ _‘- -1-
Up — (YI Q3) d3 (3.5.37)

where Y is a real root of the polynomial
BY +EY3+EYZ+EY+3 =o
0 4 1 2 3 4 (3.5.38)
and we have used the fact that N=3,m=l, and n=2. The

values of the 3i are found from the information given in

Example 3.5.1 and Theorem 3.5.6.

s0 = l
_ 0.6431 0.4293
s1 = - tr(Q3) = - tr = -1.178
0.4293 0.5349
1 o
G =
0 0 1
_ _ -0.5349 0.4293
G = Q G + s I = Q + s I =
1 3 ° 1 3 1 0.4293 -0.6431
s = - 1 tr(6 G ) = 0 1597
2 2 3 1 °
Thus by Theorem 3.5.6
p0 = e3 = 457.43 (3.5.39)
pl = 2(3363 + e351) = -392.78 (3.5.40)

107

___rr__)r_. ....
02 — 2d3G1d3+d3(G0Q3G0+2Gosl)d3+e3(3032+5181+SZSO)
= 157.85 (3.5.41)

33 and?)-4 are found from the equation

1
_. _ —T _ _
pi ‘ j=i393‘GjQ3Gi-j-2+2GjSi-j-1)aE+e3Sj+1Si-j-1
Thus
53 = 0.3450 and 54 = -0.0260 (3.5.42)

Substituting (3.5.39)-(3.5.42) into (3.5.38) gives

457.43y4 - 392.78y3 + 157.85),2 + 0.3450y - 0.0260 = o
The real roots Of this equation are
Y1 = -0.01351 (3.5.43)
Y2 = 0.01159 (3.5.44)
If we substitute (3.5.43) into (3.5.37), we get
u(-l) = 0 u(O) = -31.53 u(1) = 9.637 (3.5.45)

The energy required is u2(-l) + u2(0) + u2(1) = 1087.

The sequence of states resulting from the application of

these controls is

x(O) (10 12)T
x(1) = (17.59 4.415)T

x(2) = (8.777 -18.31)T
x(3) = (0.750 -0.643)T
XT(3)x(3) = 1.00

If we choose y2 given by (3.4.44), we get

u(-1) = 0 u(O) = -35.07 u(1) = 13.01 (3.5.46)

108

The energy required is 1399, and the corresponding se-

quence Of states is

x(0) = (10 12)T

x(1) = (17.59 4.415)T

x(2) = (7.473 -20.55)T

x(3) = (-0.730 0.664)T
xT(3)x(3) = 1.00

From the above we see that the sequence of con-
trols given by (3.5.45) requires minimum energy while

that Of (3.5.46) requires maximum energy.

3.6 Statement and Solution of Stochastic
Time-Optimal Control Proglem

 

In the preceding sections it has been assumed
that the state of the system could be determined exactly.
In some cases due to noise this can not be done. This
section is devoted to studying a stochastic version Of
the problem discussed in Section 3.1.

Problem Statement Given the system described by

 

ka+1)T]= Cx(kT) + Du(kT) + Ew(kT) k=0,l,...,N-l
(3.6.1)

where
x(kT) is a nxl state vector
u(kT) is a mxl nonrandom vector to be determined
C is a nonsingular nxn matrix
D is a nxm matrix
E is a nxr matrix

w(kT) is a sequence of rxl zero mean independent
random vectors.

109

The initial state is given by

x(0) = x0 + v (3.6.2)

where x0 is a known vector and v is a zero mean random
vector assumed to be independent Of w(kT) for k = 0,1,...,
N-l. We wish to find the smallest value of N and a cor-
responding sequence Of controls u(kT) such that

E(xT(NT)x(NT)) < R2

In the Appendix it is shown how equation (3.6.1)
is Obtained from the corresponding continuous-time system
when the noise is "white."

Solution In preparation to solving this problem, the
following definitions and assumptions are given.

Definition Let W = (w(O), w(T),...,w[(N-1)T])T. The

 

matrix MN is defined by
MN = E(WWT) (erNr matrix) (3.6.3)

Definition The covariance matrix, V, is defined by

 

v = g(va) (nxn matrix) (3.6.4)
The matrix MN and V describe the noise disturbance and
are assumed to be known.

Assumption 1 It is assumed that the deterministic system

 

corresponding to (3.6.1) and (3.6.2) is completely con-
trollable. That is, if w(kT) = 0, k = 0, 1,..., N-l and
v = 0, then the resulting deterministic system is com-
pletely controllable. From Theorem 2.3.1 this means that

rank[D, CD,...,Cn-1D] = n.

110

Assumption 2 It is assumed that
N—l

 

rank[D,CD,...,C D]= maximum for N > 0.
These two assumptions are the same as those given pre-
viously in Section 3.1 and thus the comments concerning

the second assumption apply here also.

The solution to equation (3.6.1) is

N-l .
x(NT) = ch(0) + CN 2 c1'NDu[(N-1-1)T]
i=0
N-l .
+ CN 2 cl NEW [(N-l-i)T] (3.6.5)
i=0

This result follows by the same argument as that used to

Obtain equation (3.2.5).

Let Hj = -C_(3+1)E for j = 0,1,...,N-1 (3.6.6)
Fj = -c“3+1’0 for j = 0,1,...,N-l (3.6.7)
Then by (3.6.5)-(3.6.7)
N NN'1
x(NT) = C x(O) - C E F . u[(N-l-i)T]
. N-l-1
1=0
NN-l
—C .2 HN_1_i w[(N-l-1)T]
1-0
N-l N-l
= ch(0) - cN 2 F1 u(iT) - CN 2 Hi w(iT)
i=0 i=0

Thus xT(NT)x(NT) is given by

T N-l N-l ‘
x (NT)x(NT) = [x(O) - Z Fiu(iT) - Z Hiw(iT) w NEHO)
i=0 i=0

N-l N-1
- z F.u(jT) - z H.w(jTfl (3.6.8)
j=0 3 j=0 3

111

where, as previously,

N T N

W (C ) C (3.6.9)

N
Expanding (3.6.8), we obtain

T T T N'1
x (NT)x(NT) = x (01wa10) - 2x (0)wN.20Fiu(iT)
1:
N-1
- 2xT(0)wN.Z

H.w(iT)
1-0 1

(N-l T N-1 ( )
+ 2 F.u(iT)) 0 ( 2 F.u jT)
i=0 1 N i=0 1 ,

N-l . T N-l .
+ 2(02 Fiu(1T)) UN ( : ij(jT))

i=0 j 0
N-l N-l
I T ’ (306.10)
+ )3 H.W(1T)) 1p ( 2 H.w(jT))
(i=0 1 N j=0 3

Taking the expected value Of (3.6.10) while noting the
assumptions of independent and zero mean, we Obtain

N-l

E[xT(NT)x(NT)] = xngxo + E(vaNv) - 2xng 2 Fiu(iT)
i=0
(N-l T N-l
+ 2 F.u(iT)) q) ( 2 F.u(jT))
i=0 1 N j=0 3
N-l T N-l T
Z . ' . ' =
+ E[:(i=0H1W(1T)) UN (jioHJw(jT))] xowao

+ E(vaNv) - 2d§U+UTQNU+E(WTANW) (3.6.11)

where

QN = F TU F (meNm matrix) (3.6.12)

112

F8 = [F0, Fl""'FN-l] (anm matrix) (3.6.13)

AN = HNTwN HN (meNm matrix) (3.6.14)

HN = [Ho, Hl,...,HN_l] (anm matrix) (3.6.15)
T T -

dN = xowNFN (1 x Nm vector) (3.6.16)
u = (u(O), u(T),...,u[(N-1)T])T (3.6.17)

It is noted that QN and Ffi are the same as for the deter-
ministic system of Section 3.1. The vector dN given
above is the same as that of Section 3.1 except that x0
is interpreted here as the nominal initial state.

Since wN is positive definite and symmetric, AN
is symmetric and at least positive semidefinite. The last
term in equation (3.6.11) can then be written in an alter-
nate fashion. Since AN is positive semidefinite, it
follows by Theorem 2.1.9 that there exists a matrix S
such that AN = 813.

T

Thus E(WTANW) = E (wTs s W) = E(ZTZ)

where Z = SW

Therefore, E(WTANW) = tr[E(zzT)]

where tr[E(ZZT)] denotes the trace of the E(ZZT) matrix.
Therefore,

E(WTANW) = tr[E(SWWTST)] = tr (smNsT)

where MN is defined by (3.6.3). Since tr (AB) = tr (BA)

for conformal matrices A and B, it follows that

113

E(WTANW) = tr (sTs MN) = tr (ANMN) (3.6.18)
By the same argument
T —
E(v wNv) - tr (TNV) (3.6.19)

where V is defined by (3.6.4). Substituting (3.6.18) and
(3.6.19) into (3.6.11) gives

T

o wNXO + tr(ANMN)

E(xT(NT)x(NT)) = UTQNU-ngu + x

+ tr(wNV) (3.6.20)

Using the same argument as for the deterministic system,

it can be shown that if there exists a number Nl such

that E(xT(NlT)x(NlT)) < R2, then there exists a number

N S Nl such that
T 2
E(x (NT)x(NT)) = R (3.6.21)
If we let
.. T __ 2
SN - xowaO + tr(ANMN) + tr(wNV) R (3.6.22)
then equations (3.6.20)-(3.6.21) give
f(U) é UTQ U — 2 TU + e = o (3 6 23)
N an -N - -

Thus, we are looking for the smallest value of N and a
corresponding sequence of controls U such that (3.6.23)
is satisfied. Because this equation is of the same form

as equation (3.2.14) except that e replaces eN, we have

N
by the same argument the following theorems.

114

Theorem 3.6.1 a) Let N < n/m. The expression for f(U)

 

given in equation (3.6.23) can be reduced to the form

YgaNY + Efi = 0
where

— _ _ T -1

by the transformation

_ —1
U — PNY + QN dN (3.6.25)

. T_ _T.
where PN is such that PN PN - I andJ\.N - PN QNPN 1s a

diagonal matrix with diagonal elements equal to the eigen-
values of QN.

b) If N = n/m, equation (3.6.23) reduces

231NY + tr(ANMN) + tr (wNV) - R2 = 0

Theorem 3.6.2 Let N s n/m. Then the following is true.

 

_ T -1 .
a) If EN - dN QN dN, the unique sequence of controls

such that E(xT(NT)x(NT)) = R2 is given by

T -l .
b) If EN < dN QN dN’ a nonunique sequence of controls

exists such that E(xT(NT)x(NT)) 6 R2.

> d TQ-ld , no sequence of controls exists such
N N N N
2

that E(xT(NT)x(NT)) g R .

c) If e

Theorem 3.6.3 If N > n/m and a solution to the optimal

 

control problem exists, a sequence of controls is given

by

_ T —-- T -l
U — PNY + FN (FNFN ) x0
where
T _ 2 _ _
YANY - R tr (ANMN) tr(wNV)
and P is such that P TP = I andJL = P TQ P is a dia-
N N N N N N N

gonal matrix with diagonal elements equal to the eigen-

values of QN.

Theorem 3.6.4 a) Let N > n/m and tr(ANMN) + tr(wNV) =

R2. 'Then a sequence of controls such that E(xT(NT)x(NT)) =
R2 is given by U = §:(§N§§)—lxo. This value of U has the

property that ”U”2 is minimum.
b) If tr(ANMN) + tr(wNV) < R2, a nonunique sequence of
controls exists such that E(xT(NT)x(NT)) 6 R2.
c) If tr(ANMN) + tr(wNV) > R2, then no sequence of con-
trols exists such that E(xT(NT)x(NT)) < R2.
A significant difference between the solution to
the stochastic and deterministic problems is that for the
latter the target can always be reached in a number of
samples equal to the smallest integer greater than or
equal to n/m while the stochastic system has the addi-
tional requirement given by Theorem 3.6.4. It is pos-
sible that the noise and system parameters may be such
that the third part of Theorem 3.6.4 would not hold for
any N. Theorems 3.6.1-3.6.4 are combined into the flow

chart given in Figure 3.6.1.

.Emumwm

owpmmnooum How mmHmEMm mo Hogans EdSHcHE mcwcflfiumumc How unmno3oam .H.m.m .mHm

\

 

I

 

 

TH

+ x an
oomamom

 

116

 

oz

 

m

 

g a

we 120+»zenn

 

0%

HI

 

 

 

av 96.33122er 3

 

 

       

 

 

 

 

Ammfimvmm+wzmua cowusHOm
coausaom . msvflcscoz
msvficscoz
E x)
E. oz , a
oxauxmmnmvmmuo ,
cofiunaom BU zou
mmumcmassflcwz. mm» coammaom
mow mmvwcn
WH.
mow

 

 

 

pmuflsvmu mmHmEMm mo Hogan: ESEHQHS
onEMm mo Hones: ESEHQHE mo mcam> amass

E

117

It should be noted that although we have found a

2, this

sequence of controls such that E(xT(NT)x(NT)) = R
does not imply that E(x(NT)) lies on the boundary of the
hypersphere (as in the deterministic case). Instead, we
shall have E(xT(NT))E(x(NT)) s R2.

To show this, let x(NT) = (x1(NT),x2(NT),...,

xn(NT))T and 0x2 equal the variance of xi(NT). Then
i

E(xT(NT)x(NT)) E(xi(NT)) + E(x§(NT)) +...+ E(x:(NT))

2 2 2 2
E (x1(NT)) + Ox + E (x2(NT))+Gx2

1
+...+ E2(x (NT) + 02
n X
n
T n 2
= E(x (NT))E(x(NT)) + 2 OX
i=1 1
Therefore,
n
R2=E(xT(NT))E(x(NT))+ 2 0x2 a E(xT(NT))E(x(NT))
i=1 i

E(x(kT) can be found from equation (3.6.5). Tak-
ing the expected value of this equation, we obtain
k kk-l
E(x(kT)) = C x0 - C 2 Fiu(iT) (3.6.26)
i=0
The method of determining the sequence of minimum
energy controls once N is known is similar to that for
the deterministic case. To determine the sequence of
N-l

controls such that J = 2 u(iT)u(iT) is minimum subject
i=0

118

to the constraint E(xT(NT)x(NT)) = R2, we have only to

replace eN by §N in Theorem 3.3.2. We then find the co-

efficients pi and the roots Yi of the polynomial (3.3.8).
The Yi are substituted into equation (3.3.3) to determine
the sequence of energy-optimal controls.

An example is given to illustrate the above theory.

Example 3.6.1 Consider the system described by

 

x(k+1) = Cx(k) + Du(k) + Ew(k) k=0,l,...,N-1 (3.6.27)

x(0) = x0 (3.6.28)
where
1 1-e"l
C = _1 (3.6.29)
0 e
e-l
D = E = -1 (3.6.30)
l-e
_ T
xo — (10, -12) (3.6.31)

The expressions for C, D and x0 correspond to the values

given in Example 3.3.1 for the deterministic system.

From previous results we know that the deterministic sys-

tem is controllable. We assume that v, w(k), k=0,l,...,

N-l are independent Gaussian random variables such that
E(v) = 0 (3.6.32)

E(w(kT)]=0 k=0,l,...,N-1 (3.6.33)

T [4.8 -1
V = E(vv ) = (3.6.34)
-4. 4

119

 

 

MN =1 E(WWT) + 1 2 IN i = Opl'ooo’N-l

10 + (1+1)

_1 _

fi 0 o o o 0

l
0 0 ... 0
= - TE , (3.6.35)

' I 0
0 0. o o l 2

L 10+N _(

 

 

Equation (3.6.35) can be intrepreted as meaning that the
noise variance decreases as time increases.

The sampling period is T=l. We wish to determine
the smallest value of k and the corresponding sequence of
controls such that E(xT(kT)x(kT)) 6 1.

Solution To determine the minimum number of samples N,
we use the procedure outlined in Figure 3.6.1. Setting

k=1, we obtain

_ T
Ql ‘ FowlFo
1. 0.63212 0.71828
= (0.71828 -l.71828) =o.5349
.63212 0.53491 -l.71828
(3.6.36)
__ T
d1 ’ x0‘91Fo
1. 0.63212 0.71828
= (10 -12) =1.90226

.63212 0.53491 -1.71828

(3.6.37)

120

_ T _
e1 - xowlx0 + tr (PlMl) + tr (WIV) — 26.2497

T -1 _ _
and de1 d1 - e1 - 19.485. Therefore,

T -1
e1 > de1 61 (3.6.38)

Thus by Theorem 3.6.2, k=1 is not large enough. If we

try k=2 we arrive at the same conclusion. Letting k=3,

we obtain

_T T T '—

F01’3Fo F0"”3F1 F01352
_ T T T

Q3 ‘ F11’3Fo F11311 F11312
T T T

E2w3F0 F2‘”3F1 F213F2

 

 

0.84354 0.72169 0.390;;

= 0.72169 0.64306 0.42932 (3.6.39)

 

 

0.39048 0.42933 0.53490

1. 0.95021

0.95021 0.90538

From (3.6.34), (3.6.35), (3.6.39) and (3.6.40)
tr(A3M3) + tr(w3V) = tr(Q3M3) + tr(w3V)

= 0.15077 + 0.81983 = 0.9706 (3.6.41)

Since R = l, tr(A3M3) + tr(w3V) < R2. Thus by Theorem

3.6.4, we know that N=3.

121

A sequence of optimal controls is found from
Theorem 3.6.3.

_ T
A3 — P3 03193 (3.6.42)
The eigenvalues of Q3 are

A1 = 0.2748 A3 = 1.7467 A3 = 0

The corresponding normalized eigenvectors form the columns

of the P matrix:

 

 

 

 

 

 

3
--0.4678 0.6698 0.5767”
93 = -0.1061 0.6053 -0.7889
L 0.8774 0.4303 0.2122
and
2 — _
tr(A3M3) + tr(w3V) - R — 0.0294
From Theorem 3.6.3 we have Y?A3Y + tr (A3M3) + tr (w3V)-R2=0
or
'0.2748 0. 0.“ 'y06
[y0 y1 y2] 0. 1.7467 0. y1 = 0.0294
b0. 00 00-— by}‘
or
2 2
0.2748 yo + 1.7468 y1 = 0.0294
01'
2 2
y0 y1
6716666 + 671666 ‘ 1 (3°5°42’

From (3.6.42) it is seen that as far as the time optimal

sequence of controls is concerned y2 is arbitrary. The

122

choice of y2 does affect the energy required, however. A

possible solution of (3.6.42) is
yo = 0.3271 y1 = 0 y2 = 0
The sequence of controls is found from Theorem 3.6.3.

— T - - T -1

—+ —
U — P Y + F3x0 — P Y + F3 ( 3F3 ) (3.6.43)

3 X

3 0
Substituting the known quantities into the right side of

(3.6utm,we obtain a sequence of time-optimal controls.

u(0) = 0.5657 u(1) = 0.6509 u(2) = 0.8826
(3.6.44)

To check the result a computer simulation of the
system was made. Gaussian random variables were generated
by means of the IBM subroutines RANDU and GAUSS [IBMl].
Although no claim was made about the sequence being in-
dependent, the sample auto-correlation indicated this to
be the case. We then have the problem of determining the
covariance matrix given by (3.6.34), i.e.,

4.8 -40

E(va) (3.6.45)
-4. 4.

Because of the independence of the random variables the
covariance matrix will be diagonal unless a transforma-
tion is made. To overcome this problem let

v = 82 (3.6.46)

where S is to be determined. Let us also set

123

 

 

 

T 11 0
E(zz ) = (3.6.47)
0 a22
L. 1
S11 S12
and S = (3.6.48)
3 S
L_21 22
We then have
—1

E(va) = SE(zzT)ST =

 

(3.6.49)
Equating the right-hand sides of (3.6.45) and (3.6.49),

we have

2 2 _
allsll + 0223 12 — 4.8
S11321111 + S12522122 = ’4'
2 2 _
S 21“11 + S 22“22 ‘ 4'

A solution to these three equations and six unknowns is

all = 2/3 311 = 2 $12 = -1 522 = 5/4 s21 = -l azz=32/15
Therefore,
2/3 0
E(zzT) = (3.6.50)
0 32/15
and ‘3 _f‘
v = 82 = 2 (3.6.51)

 

 

:1 5/4

124

The independent random variables 2 are generated in the
computer and multiplied by S to give the random variables
with covariance matrix given by (3.6.45). Because of the
assumption of independence, there is no problem in generat-
ing the w(iT) random variables.

By using the controls given in (3.6.44) and the
state equations (3.6.27) and (3.6.28) a sequence of states
can be found. In order to determine if the sequence of
controls is correct, a monte carlo technique can be used.
For this example, this consisted in simulating the system

500 times using different noise sequences. The following

-0.04919
0.16058

sample means were obtained.

10.056
E(X(l))
-12.058

0.3102
E(x(3))
-l.0832

E(XT(3)) E(x(3))

E(X(0))

E(x(2))

0.0282

E(xT(3) x(3)) = 1.007

The results check since E(xT(3)x(3))kd. as desired.

CHAPTER IV

TIME-OPTIMAL CONTROL WITH HYPERRECTANGULAR

TARGET SET

4.1 Statement of Control Problem

In this chapter the following problem is con-
sidered. Given the linear discrete-time system
x[(k+1)T] = Cx(kT) + Du(kT) (4.1.1)
x(0) = x0

where

x(kT) is a nxl vector
u(kT) is a mxl vector
D is a nxm matrix

C is a nxn nonsingular matrix
It is assumed that the initial state lies outside the

target described by-

H = {x(NT):-Mi g xi(NT) < Mi 1 = 1,2,...,n}
(4.1.2)
where x(NT) = (xl(NT),x2(NT),...,xn(NT))T,Mi 2 0, and N
is the minimum number of samples such that x(NT)eH. We
wish to determine N and a corresponding sequence of con-
trols. If the sequence is not unique, we want to

choose a sequence which minimizes the total

125

126

fuel required to reach the target, that is, we want to
minimize
N-l m ‘
J = 2 2 |u.(kT)| (4.1.3)
k=0 j=1 3

where u(kT) = (u1(kT),u2(kT),...,um(kT))T. It is assumed
that the magnitude of the controls is constrained, that is,

[ui(kT)| g Gi’k (4.1.4)

where Gi k > 0. (The case where inequality (4.1.4) need
I
not hold will also be discussed.)
It is assumed that a solution exists for some
value of N. No other assumptions will be made.
4.2 Formulation of Time-Optimal Control

Problem as a Solution to a Set of
Linear Inequalities

 

 

 

It has been previously shown (equation (3.2.5))

that the solution of equation (4.1.1) is

k-l
x(kT) = Ckxo - CR 2 F.u(jT).
'_ 3
3-0
Let
c: = i-th row of Ck (4.2.1)
k k k-l
Then x.(kT) = c.x - c. z F.u(jT) i = 1,2,...,n and
1 1 0 1 j=0 j

2 k-l T k-l
xi(kT) = [E0 - jionu(3Tfl wi,k [R0 - jionu(jTfl

where

_ k T k k . .

wi,k - (ci) ci (outer product of ci w1th itself)
(4.2.2)

127

Letting k = N where N corresponds to the time at which the

target is reached, we have

2 _T-T-_T— T
xi(NT) — U FNwi’NFNU 2xowi’NFNU + xowi'Nx0 (4.2.3)
where
FN = (F0, Fl,...,FN_1) (4.2.4)

U = (u(0),u(T),...,u[(N-1)T])T (me1 vector)
(4.2.5)
and the Fi are given by equation (3.2.4).
From equation (4.1.2) we are looking for N and

u(iT) such that

2

2
xi(NT) i Mi (4.2.6)

From equations (4.2.3) and (4.2.6) we then have

T T ._
U Qi,NU 2di,NU + ei,N S 0 1-l,2,...,n (4.2.7)
where
Q =§Tw F (428)
i,N Ni,NN ° °
T _ T -
di,N — X0w1,NFN (4.2.8)
_ T _ 2
ei,N - xowi'Nx0 Mi (4.2.10)

Equation (4.2.7) represents a constraint on the controls
which must be satisfied in order that the target be
reached in N samples.

Theorem 4.2.1 Let Q. # 0. Then Q. is positive semi-
l'N lIN

 

definite, symmetric and of rank 1.

128

Proof From equation (4.2.2) we see that wi N is formed
_— I

from the rows of the matrix CN. Since this latter matrix

is nonsingular, it follows that all the rows are nonzero.

Then by Theorem 2.1.13, it follows that wi is symmetric

and of rank 1. Since Qi,N

is symmetric and by Theorem 2.1.1 rank (Qi N)‘
I

= F Nwi N FN, we have that Qi

m1n{rank(FN), rank(wi'N)} S 1. By assumption, Qi,N # 0.

Therefore, rank(Qi N) > 1. Consequently, by the above,
I

rank(Qi N) = 1. We also have for an arbitrary vector

T- _ T- T N T CN- T _ N-
y, y FNwi N FN y y FN (ci ) FNy= z z 2 0 where z - ciFNy.
Thus Qi,N = FT NW1 N FN 1s p051t1ve sem1def1n1te.

QED

It is because rank(Q. = 1 that much of the

i,N)
succeeding results depend. This fact is used to show
that (except in a degenerate case) inequality (4.2.7)
represents the equation of two hyperplanes and the region
between the hyperplanes. (In the degenerate case the
two hyperplanes come together to form a single hyperplane.

This case occurs only when Mi = 0 in equation (4.1.2).)

It shall be assumed at present that Qi N # 0. The case
I

when Qi N = 0 will be considered later.
I
Let us set
f(U) = UTQ U - sz U + e. (4.2 11)
iIN i,N l’N .

We would like to perform a linear transformation on f(U)

to convert it into a simpler form [FRA2] as was done in

129

Chapter III. In this case, advantage will be taken of

the fact that rank(Qi N) =11. Let
I

U = P. Y. + C. (4.2.12)

Then f(U) becomes

_ T
9(Yi) ’ (Pi,NYi + Ci,N) Qi,N(Pi,NY1 + C1,N)
T _ T T
2di,N(Pi,NYi + C1,N) + el,N ‘ YiP1,NQi,NYi
T T T
+ 2(Ci,NQi,N di,N) 1,NY1 + Ci NQi,N i,N
- 2dT c + e. (4.2 13)
i,N i,N i,N '
By letting
L = pT (Q c - d ) (4.2 14)
i,N i,N i,N i,N i,N '
g =«cT Q c — 2dT c + e (4.2.15)
i,N i,N i,N i,N i,N i,N i,N
equation (4.2.13) becomes
_ T T T
g(Yi) — YiPi’NQi’NPi'NYi + 2Li’NYi + gi'N (4.2.16)

We would like to choose Ci,N N

(4.2.14) and (4.2.16) is zero. If Qi N had an inverse,
I

such that Li in equations
I

_ -l _
we could choose Ci,N - Qi,Ndi,N but, except when N - l,

we know by Theorem 4.1.1 that Q;1 does not-exist. From
I

Theorem 2.2.7 we know that a vector of the form

_ +
Ci,N - Qi,Ndi,N + aAi’Ndi'N a a scalar (4.2.17)

130

minimizes the length of Qi NCi N - di N where Q: N is the
I I I I

pseudoinverseof Q- and Ai is any matrix such that
I

Qi,NAi,Ndi,N = 0 (4.2.18)

An expression for A.
l,N

in equation (4.2.16).

will be found such that Li N = O
I

is

Theorem 4.2.2 The positive eigenvalue Yi of Qi N
I

Yi = tr(Qi,N) (4.2.19)

Furthermore, in the expansion of adj(AI - Qi N) given in
I
Theorem 2.1.10 we have

Gi = 0 for i 2 2 (4.2.20)

Proof Since Qi is positive semidefinite, symmetric

N
I
and of rank 1 by Theorem 4.2.1, we have

_ Nm _ Nm-l
IAI - Qi,Nl — A yix where yi > 0

(4.2.21)

Comparing equation (4.2.21) with the similar expression

in Theorem 2.1.10, we see that

50 = 1 (4.2.22)
31 = —Yi (4.2.23)
sj = 0 for j > 1 (4.2.24)

A comparison of equation (4.2.23) with that for s1 given
in Theorem 2.1.10 shows that Yi = tr(Qi,N) as desired.
Also, from Theorem 2.1.10 and equation (4.2.24) we see
that

_ ..-.1.
O — 52 — 2tr(Qi,NG1) (4.2.25)

131

Then by Theorem 2.1.19 we know that

tr(Q. + z

1,NGl) = Z1 +...+ z = 0 (4.2.26)

2 Nm
where the zi are the eigenvalues of Qi NGl' By Theorem
I
2.1.1 rank(Qi’NGl) S m1n[rank(Qi’N), rank(Gl)] i 1. Thus

we know that Qi N61 has at most one nonzero eigenvalue
I

21. However, by equation (4.2.26) we have that 21 = 0

also, Slnce 22 =,23 = ... = 2Nm = 0. By Theorem 2.1.10

we also have that Qi NG1 = Qi NQ + s10i N' Therefore,
I I I

i,N
Qi NGl is a symmetric matrix with all eigenvalues equal~
I

 

 

 

to zero. By Theorem 2.1.7 it follows that rank(Qi NGl)
I
and
If we substitute equations (4.2.27) and (4.2.24) into
Theorem 2.1.10 we have 62 = 0. This, plus equation
(4.2.24) imply that Gi = 0 for i 2 2.
QED
Theorem 4.2.3 The constituent matrices 211 and 221 for
Qi,N are
YiI ' Qi,N
Zll — Y- (4.2.28)
1
Q.
_ 1,N
221 - Y- (4.2.29)
1
where
Y1 = tr(Qi,N) (4.2.30)

is the nonzero eigenvalue of Qi N'
I

Proof By Theorem 2.1.15 the minimal polynomial m(l) is

= 0

132

D(A)
m(A) = ““‘TIY (4.2.31)
DNm-l
where D(A) = [XI - Qi,N| and DNm-1(A) 15 the greatest

common divisor of all the minors of order Nm-l of
XI - Qi,N' Thus DNm_l(A) is the greatest common factor

of adj(AI - Qi N). By Theorem 2.1.10, adj (AI - Qi ) =
I

Nm-2 Nm-3
+ G11 + G21 +...+GNm_1.

4.2.2 this reduces to

,N

IANm-l Then by Theorem

N

adj(AI - Qi'N) = A m—2(AI + G1)

From Theorems 2.1.10 and 4.2.2 we have G1 = Qi,N 1
Therefore,

Nm-2[(

adj(AI - QiIN) = A 1 - yi)1 + Qi'N]

The greatest common divisor, D (A), of adj(AI - Qi N)
I

Nm-l
is then

Nm-Z

D (A) = A (4.2.32)

Nm-l
Substituting equations (4.2.21) and (4.2.32) into

equation (4.2.31), we obtain

 

 

(A “YiMNm-l
m(A) + ANm-Z = x(k - yi) (4.2.33)
Then if h(A) is a polynomial
h(l) _ k1 + k2
m ‘ T r77—
where
k _ hm =_h(0)
1 ‘ (X - Yi) A = 0 Y1

 

 

k = h(A) = h(Yl)
2 X IA=Y Yi
Therefore,
h(Y-)
h(l) _ _ h(O) l '
ETTT _ x7:— + Yi(1 _ Y1) or by equat1on (4.2.33),
(X -Y.)
______1_ .1
h(A) — Yi h(O) + Yi h(Yi)

Using the properties of h(A) [KOEl], we can substitute

Qi,N for A and obta1n

(Q, - v.1) Q-
1,N 3- h(O) + _J'AE h(yi) (4.2.34)

Y1 Y1

 

From Theorems 2.1.16 and 2.1.17,

h(Qi,N) = leh(0) + ZZlh(Yi) (4.2.35)

Comparing equations (4.2.34) and (4.2.35), we see that

 

 

 

 

Z = YiI - Qi’N and Z = Qi'N
ll Yi 21 Yi
QED
Theorem 4.2.4 We may choose Ai N in equation (4.2.18)
I
to be
y.I - Q.
_ 1 l,N
Ai,N — Y. (4.2.36)
1
where Y1 = tr(Qi,N)'

Proof It suff1ces to show that Qi,NAi,N 0. By equa-
tions (4.2.28) and (4.2.36) we have Ai,N = 211. From
Theorem 2.1.17, 221211 = 0. Therefore, by equations

(4.2.28) and (4.2.29)

 

Q. Y-I- Q.
1'N [ 1 l'N:] = 0 (4.2.37)

*1 i

which implies that

Qi,NAi,N = 0 (4.2.38)
QED

Theorem 4.2.5 The pseudoinverse Q: N of Qi N is given by
I

 

I

 

Q.

+ _ 1,N

Qi'N - 2 (402.39)
Y1

where Yi = tr(Qi,N)'

Proof We need to show that the four identities in Theorem

2.2.3 are satisfied. From equation (4.2.37) we have

yiQi'N = Qi'N (4.2.40)
which implies that
3 _ 2

Then by equations (4.2.39) and (4.2.41),

 

Q.
+ _ 1,N =
Qi,NQi,NQi,N ' 2 Qi,N
Y1

and the first identity is satisfied. Similarly,

 

3
Q+ Q Q+ = Q_1LIS. = Qi'N = Q+
i,N i,N i,N 4 2 i,N
Y1 Y1

and the second identity is satisfied. Since Qi N is sym-
I
+
Qi,N

the form of Q: N' Therefore,
I

metric, will also by symmetric by the assumption on

Q QT
+ T_ i,N T= T i N = +
(Qi,NQi,N) ‘(Qi,N Y2 ) Qi,N Y'2 Qi,NQi,N
i i

and the third identity is satisfied. Also,

T
Q. Q.
+ T _ 1 N T _ 1 N T _ +
(Qi,NQi,N) ' ( y2 Qi,N) ' 2 Qi,N ' Qi,NQi,N
i i

and the fourth identity is verified.

QED

Using the expression for Ci N given by equation (4.2.17),
I

we obtain

- d. = +

Qi,NCi,N 1,N (Qi,NQi,N ' I>di,N + aQi,NAi,Ndi,N

By equation (4.2.38) this reduces to

d. = +

Qi,NCi,N ' 1,N (Qi,NQi,N ' I)d (4'2'42)

i,N

From equation (4.2.39)

 

 

2
Q Q+ = Qi,N
i,N i,N 2
y.
1.
Q.
= $IN by equation (4.2.40)
1

=9A. + I by Theorem 4.2.4 (4.2.43)
JLet.us substitute equation (4.2.43) into equation (4.2.42).

d. = - A

Qi,NCi,N ' 1,N i,Ndi,N (4°2°44’

136

h = (-Ai,Ndi,N) (-Ai,Ndi,N)

_ T
‘ di,NAi,NAi,Ndi,N

Recalling from equations (4.2.28) and (4.2.36) that

Zll = Ai,N and uSing Theorem 2.1.17, we have

2 = dT A d (4.2.45)

h i,N i,N i,N

Theorem 4.2.6 h=0 in equation (4.2.45), and equation

 

(4.2.16) reduces to

_ 2 _ 2
g(Yi) - Yiy0,i Mi (4.2.46)
where
Y = (y - y y )T° Y = tr(Q )
i 0,1’ 1,i"'°' Nm-1,i ’ i i,N
(4.2.47)
. _ -T - _
Proof From equations (4.2.8) and (4.2.2), Qi,N - FNwi,NFN —
-T N T N- _ _ -T N T = N- .
FN(ci) CiFN — BE where B - FN(ci) and E CiFN' Qi,N is

of rank 1. Thus B = ET # 0. Then B is of order me1 and
of rank 1 while E is lme and of rank 1. Thus BB is a

rank factorization of Qi From Theorem 2.2.1 we have

IN.
4.
EQi,NB - I or

N- + -T N T _
CiFNQi,NFN(ci) ‘ I

Premultiplying this equation by (c?)T and postmultiplying
it by c?, we get

+ .—T

wi,NFNQi,NFNwi,N = wi,N (4'2'48)

From equations (4.2.45) and (4.2.9)

137

= xgw F A FT

i,N N i,N Nwi,Nx0 (4'2‘49)

Substituting equation (4.2.48) into (4.2.49) yields

2

h + -T - -T

T _.
x0w1,NFNQi,NFNwi,NFNAi,NFNwi,NXO

- +

_ T -T .
- xowi,NFNQi,NQ A FNwi'Nx0 by equation (4.2.8)

i,N i,N
From equation (4.2.38), Qi,NAi,N = 0 in the above equation.
Thus h = 0,.and the first part of the theorem is proven.

Since h=0, then by equation (4.2.45)

Ai,Ndi,N = 0 (4.2.50)

Substituting equation (4.2.50) into (4.2.44) gives
Qi,NCi,N “ di,N N
tion (4.2.14). This in turn implies (by equation (4.2.16))

= 0 which implies that Li = 0 by equa-
I

that
_ T T
9(Yi) ‘ YiPi,NQi,NPi,NYi + gi,N
= y? A. y. + g (4.2 51)
1 1,N i i,N '
. T _ _
where Pi,N is chosen such that Pi,NPi,N — I and Ai,N -

T . . . . .
Pi,NQi,NPi,N is a diagonal matrix With the eigenvalues of
Q. along the diagonal. From equation (4.2.15), 9. =

i,N i,N

T T .

Ci,NQi,NCi,N 2di,NCi,N + ei,N' By equations (4.2.17)

and (4.2.50) this becomes

138

+ T + T +

= - . . . - . . . + .

gi,N (Qi,Ndi,N) Ql,NQi,Ndi,N 2d1,N91,Nd1,N el,N

_ T + + _ T +

‘ di,NQi,NQi,NQi,Ndi,N 2di,NQi,N i,N + el,N

_ T + _ T +

‘ di,NQi,Ndi,N 2di,NQi,Ndi,N + ei,N by The°rem

2.2.3

_ _ T +

' di,NQi,Ndi,N + ei,N

= _xTw E QT ETw. x + e. by equation (4.2.9)
0 i,N N 1,N N i,N 0 i,N

T .
-x0wi,Nx0 + ei,N by equation (4.2.48)

_ _ T T _ 2 .
- xowi’Nx0 + xowi'Nx0 Mi by equation (4.2.10)
_ _ 2

Let us substitute equation (4.2.52) into (4.2.51).

g(Yi) = y”? A. Y. - M. (4.2.53)

Since Qi N is symmetric and of rank 1 by Theorem 4.2.1,
I

Ai N will have only one nonzero element which is the non-
I,
zero eigenvalue of Q. . The columns of P. can be

1,N 1,N

ordered such that this nonzero element appears as the

first element on the diagonal of A.i Thus equation

N.
I
_ 2 _ 2 _
(4.2.53) reduces to g(Yi) - Yiy0,i Mi where Yi — tr(Qi,N)

_ T
and Y1 ‘ (y0,i’yl,i"°"me-l,i) '

QED

From equations (4.2.50), (4.2.17) and (4.2.12) we see that

139

+
U ‘ Pi,NYi + Qi,Ndi,N

_ P + Qi,Ndi,N
‘ 2

Y1

i,N i by Theorem 4.2.5
(4.2.54)
Equation (4.2.54) represents a rotation and shift between

the Y1 and U coordinates. All angles and distances are

preserved by this transformation. Let g(Yi) = 0. Then
2 M:
y o = — (402055)
0,1 Yi

For the case when N=2 and m=l, equation (4.2.55) repre-
sents two parallel lines as shown in Figure 4.2.la. In
the higher dimensional case the lines are replaced by
hyperplanes. If g(Yi) < 0, equation (4.2.46) gives

’Mi 1

77: g y0,i g 77; (4.2.56)
When N=2 and m=l, the inequality in (4.2.56) represents
the region between the two lines Y0,i = : Mi/Jvi' The
transformation given by equation (4.2.54) will rotate and
shift the hyperplanes. Thus the expression for U (the
sequence of optimal controls) corresponding to inequality
(4.2.56) will lie in the shaded region shown in Figure
4.2.lb. The problem to be considered next is the general
expression for the hyperplanes in the U coordinates given

the hyperplanes in the Yi system.

140

 

SH 3
P- "T"

—Mi
V Y1

 

 

 

Fig. 4.2.1a. Constraints on the control sequence in the
Yo,i‘Y1,i Plane

u(1)

u(0)

 

W .

Fig. 4.2.1b. Constraints on the control sequence in the
u(0)-u(l) plane

 

141

From equation (4.2.54) we see that U is related

to Yi by the Pi matrix. We have chosen Pi such that
I

N ,N
A = pT Q p (4 2 57)
i,N' i,N i,N i,N . .
”FT 9 = I (4 2 53)
i,N i,N) H . .

Because Qi is of rank 1, Pi can be found easily as

1N :N
shown by the following theorem.
i
3'
matrix. Then we can choose

 

i i 1
Theorem 4.2.7 Let Pi, (pl,p2,...,me) where the p

N:
are the columns of the P.
1,N

the p; as follows.

. i
. +1 . +2.
1 _ 1 _‘ - -=
p1 ’ “<1an2 pi ’ ”21W2 3 2'3""'Nm
j

q1 is any nonzero column of Qi 2;, j=2,3,...,Nm are
I

N.
any Nm-l nonzero columns of Qi,N - YiI and Yi = tr(Qi,N)
is the positive eigenvalue of Qi N' (The norm is given by
I
2
Ilwll = wTw.)

Proof From Theorem 2.1.18 we know that Nm—l columns of

the Pi matrix can be found from the nonzero columns of

,N
de-Z
d1 A—O
From Theorem 2.1.10 we have
. _ Nm-l Nm-2
adj(AI Qi,N) — I) + G11 + ... + GNm-ZX + GNm-l

By Theorem 4.2.2 this becomes

adj(lI - Qi'N) = Ime-1 + Glme'Z (4.2.60)

142

Taking the derivative as indicated in (4.2.59), we have

Nm-2
d { .
————2- adJ(AI - Q. )} = (Nm-1)1>.I + (Nm-ZHG
= (Nm-2)1G1 (4.2.61)

By Theorems 2.1.10 and 4.2.2
G1 = Qi,N

- Y-I (402062)

Let 2;, j=2,3,...,Nm be any Nm-l nonzero columns of
Qi N - YiI. Then by the above, these columns are indepen-
I

dent and can be used to determine Nm-l columns of the Pi

N
I
matrix. By equation (4.2.58) we require the columns to
be normalized. Thus we can set

i {12?

p' = j= 2’3'000,Nm
3 Ilzillin
J
and we have Nm-l columns of Pi N that satisfy equation-
I

(4.2.58). The remaining column of P. can be found from

1,N

any nonzero column of adj(AI - Qi N) where Yi is the
I

'A=Yi

nonzero eigenvalue of Qi By Theorem 4.2.2 we know this
I

N.
to be Y1 = tr(Qi N). From equation (4.2.60) we then have
I

. _ Nm-l Nm-2
i
_ Nm-2
— Yi (YiI + Gl)

N -2 .
Yim (YiI+Qi,N-Y1I) by equation

(4.2.62)

143

_ Nm-2
'Yi Qi,N

An eigenvector is then proportional to any nonzero column
of Qi N. Let ql be one of these nonzero columns. To

I
satisfy equation (4.2.58) we normalize ql. Thus we can

choose
+ i

1..
p1 ‘ u i”172

q QED

Let us now find the inequalities in the U coordi-
nates which correspond to the inequalities in (4.2.56).
Theorem 4.2.8 If a sequence of time-Optimal controls

exists, it is a solution of the following set of inequali-

ties.
_Mi
VY—i- + ri i pl’iu1(0) + p2,iu2(0) + ... + pm'ium(0)

+ Pm+1,iul(T) + Pm+2,i“2‘T’ + "' + 92m.ium(T)

+ 0.0 + me—m+l'iul[(N-1)T] + 000
Mi
+ PNm,ium[(N'1)T] ‘ 7?: + r1 i=l,2,...,n
. Q. .
_ 1 T 1,N i»_‘ T
Where ‘1 ' (Pi) 'T;2‘ di,N and Pi ‘ (pl,i'p2,i'°"’me,i)
i
is the first column of the Pi N matrix and is given by
I
i + 1
p1 = nqluӤ

i .
where q is any nonzero column of Qi Moreover, the

,N'

solution does not depend on which nonzero column of Qi N
I

144

we choose or whether we choose the plus or minus sign in

the expression for pi. If Nm=l, we get Yi

 

 

 

= Qi,N and
i _ .
p1 - 1’1. It is assumed that Qi,N # 0.
_ i i i
PrOOf Let Pi'N — (pl’p2'...'me) 0 Then
_ i T ._
(p1)
_ i T
Pi,N - (p2) (4.2.63)
1 T
(me)
Qi N
From equation (4.2.54), U = P. Y. + ——L—d. . Thus Y. =
i,N 1 2 1,N 1
Y1
_ Q.
P.1 (U - —iL§-d. ). Using equation (4.2.58), this becomes
1,N Y2 1,N
i
P 1
y0,1
T 91,14
Y1 1 - Pi N(U " —T all N) (4.2.64)
. I I Yo I
. i
YNm-l,i
L— _—

 

From (4.2.7) and (4.2.11), we require that f(U) s 0. This

in turn leads to g(Yi) c 0 where g(Yi) is given by equation

(4.2.13). From Theorem 4.2.6 we then must have

-M. M.

1 i
‘ o g . .
w; Yo,1 w; <4 2 55)
From (4.2.64) and (4.2.65), we then have
M.

l 9 Q0 M.
1 T 1 N 1
W1 1 y: 1,N Wi

145

where p: is the first column of P. Therefore,

i,N'
M. . Q. . M. . Q.
i i T 1 N 1 T 1 l T i N
_ ___ + (p ).__L— d. < (p ) U < ——— + (p ) ’ d.
r—- 1 2 i,N ‘ l ‘ l 2 1,N
Y1 Y1 “Y1 Y1
(4.2.66)
1 i i 1
From Theorem 4.2.7 we know that p1 = ——I9F77-where ql is

any nonzero column of Qi The value of pi does not

N.
I
depend upon which nonzero column we choose. This follows

from the fact that the Q1 N matrix is of rank 1 so that
I

the nonzero columns of Qi N are related by the equation
I

q3 = aq1 where q

3 and q1 are nonzero columns of Qi N and
I

a is a nonzero scalar. Then

 

j i j iqu t i sgm(a) i
p = 2 = f 1. = = plsgm(a)
1 H43 IF7 llaqlll ”7 nqln

(4.2.67)

Thus pi and pi can differ at most only in sign.

To show that Theorem 4.1.8 does not depend on which sign

we choose for pi in equation (4.2.67), let us substitute

(-pi) for pi in equality (4.2.66). This gives

M. . Q. . M. . Q.
‘ 4 +('p1)T :2}! d1 N S (“PPTU S _i +('91)T :25 d1 N
“*1 Y1 ' "Y1 Y1 '

or after multiplying through by (-l), we obtain

M. ° Q- - M. . Q.
- __:..+(p1)T -l&N-d.'N s (pi)TU s -—£ +(pi)T -if§ d

i N

146

This inequality is the same as inequality (4.2.66), and
therefore, the result is independent of whether we choose

the plus or minus sign in equation (4.2.67).

For Nm=l, Q: since the pseudoinverse equals
I

_ -l
N ' Qi,N .
the inverse when the latter exists. If we choose pi = i l

and set u1(0) = i y0,i + di,1/Qi,l’ then the inequality

2 .
Qi,1“1‘°) - 2di'1u1(0) + 91,1 5 0 transforms into

2

 

 

 

 

2 . . . .
y0,i 5 Mi/Qi,l' This in turn implies that
M. d. M. d.
- 1 + 1'1 s u1(0) s l + 1'1
"91,1 Q1,1 "91,1 Q1,1

With Yi = tr(Qi N) the same result as given in the
I

= Qi'N’
statement of the theorem follows.
QED
Theorem 4.2.8 provides a means of determining a

sequence of time-optimal controls. Before proceeding

further it should be noted, however, that the Pi N matrix
I

which diagonalizes the Qi matrix is not unique. To show

’N
this, let
_T
A ‘ Pi,NQi,NPi,N
where P? P. = I and A is a diagonal matrix with the
1,N 1,N
eigenvalues of Qi N along the diagonal. Let R be any
I

matrix such that RTR = I and RA = AR. The matrix R always

exists since we can choose R to be a diagonal matrix.

Then Pi'NR.w1ll also diagonalize Qi,N Since

147

_ _ TT _ TT
- Po AP. - Po NARR Pi "' Pu RAR Pi

Qi,N 1,N 1,N 1, ,N 1,N ,N

T

(Pi,NR)A(Pi,NR)

Because Pi N is not unique, it may seem that the solution
I

to the inequalities given in Theorem 4.2.8 depends on how

we choose P. .
1,N

interested in the first column of Pi N which corresponds to
I

the single nonzero eigenvalue Yi of Pi
I

This is not-the case since we are only

N‘ This column is
equal to a normalized eigenvector corresponding to Yi'
Thus it can assume only two values, the one differing from
the other only in sign. That is, the only possible values
of pi are given in Theorem 4.2.8. By this same theorem we
knbw that we get the same set of inequalities regardless
of whether we choose the plus or minus sign. The conclu-
sion, therefore, is that the solution to the time-Optimal
control problem does not depend on how we choose the non-

unique Pi matrix; Theorem 4.2.8 is the same for any

,N

choice of Pi which satisfies equations (4.2.57)-(4.2.58).

,N
Theorem 4.2.8 is the main result when it is as-

sumed that Qi,N # 0. The following theorem gives the

corresponding result when Qi,N = 0.

Theorem 4.2.9 If Qi,N = 0, then the following is true.

 

a) If a solution exists, then a time-optimal sequence of
controls is a solution of the following set of inequali-

ties.

“1,iu1(0)+“2,iu2(0)+'°'+am,ium(°)+a 'u1(T)

m+l,1

148

+0. (T)+...+

OLm+2, i u2 (T)+'°°

2m, 1 um

+aNm-m+1 i u1[(N- 1)T]+...+aNm um [(N-1)T]
2 T ._
S Mi Xo‘yi'NX 0 l—l,2'ooo'n (4.2.72)
_ _ T —
where (al,i'a2,i""’aNm,i) — Zxo‘Pi'NFN (lme vector)

(4.2.73)

b) If N a n/m and the anm matrix Ffi is of rank n, then

we have the following two cases.

1) If xgwi Nx0 s Mi, i=l,2,...,n, then the sequence of
I

time-optimal control is arbitrary. In particular, the

sequence U = 0 is energy and fuel optimal.

2) If xTw. x > M? for some i, then no solution exists
0 1,N 0 i

for this value of N.

Proof From inequality (4.2.7), we are looking for a se-

T T
quence of controls U such that U Qi,NU 2di,NU + ei,N s 0

for i=l,2,...,n. With Qi N =.O, this reduces to
I

Using equations (4.2.9) and (4.2.10), this inequality be-

come S

T - T 2
_zxowi’NFNU + xowi'Nxo Mi s 0 (4.2.74)

From (4.2.73) and (4.2.74), inequality (4.2.72) follows.
b) For N 2 n/m, inequality (4.2.74) still holds. From

equation (4.2.8) Qi,N= Fgwi,NFN = 0. By assumption the

anm matrix FN is of rank n. From Theorem 2.1.20, it

149

...—R—

- . . -R -
follows that FN has right inverse FN. Thus FNwi’NFNFN - 0
-T . . .

or FNwi,N - O which implies that

wi'NFN = 0 (4.2.75)
Substituting equation (4.2.75) into (4.2.74) yields

T 2

xowi’Nxo 4 Mi (4.2.76)

If x0, wi,N and Mi' i=l,2,...,n are such that inequality
(4.2.76) is satisfied, then U is arbitrary and U = 0 is
the minimum fuel and minimum energy sequence of controls.
On the other hand, if for some i we have xgwi,Nx0 > Mi,
then no solution exists because inequality (4.2.76) must
be satisfied.
QED

Theorems 4.2.8 and 4.2.9 are the main results.
They provide a means of determining a solution if it ex-
ists. Thus far no systematic method of determining the
fewest number of samples N to reach the target has been
given. The constraint on the amplitude of the controllers
given by equation (4.1.4) has not been taken into consid—
eration. However, both of these problems shall be over-
come by defining new variables and using the linear
programming method of solution.

4.3 Solution of Control Problem Using
Linear Programming

 

 

In the previous section the Optimal control prob-

lem with no constraints on the amplitude of the controller

150

was reduced to finding a solution to a set of linear in-

equalities. In this section the control problem is formu-
lated as a linear programming problem. Theorems from the
Simplex Method [HADl] of linear programming are used to
determine if a solution exists for a particular value of
N, and whether the solution is unique. If the solution
is not unique, a trajectory is chosen that minimizes the
total fuel to reach the target.

From Theorem 4.2.8 we have that the solution to
the Optimal control problem is a solution to the follow-
ing set of inequalities.

N 1

- m
1
Z 2 p . u. (kT) c + r
k=0 i=1 km+i,l 1 7Y1 l
N-l m . Mn
2 2 p . u (kT) s + r (4.3.1)
=0 i=1 km+1,n 7Yn n
N']. m -M1
2 X p . u (kT) 2 TV— + r
N-l m . “Mn
2 2 p . u. (kT) 2 + r
k=0 i=1 km+1,n 1 7Yn n

From equation (4.1.4), we also require that

for i=l,2,...,m (4.3.2)
k=0,lpo o o 'N-l

lui(kT)I é Gi,k

151

The constraint given in equation (4.3.2) can be taken into
consideration in two ways [TORl]. The first method con-
sists of letting

ui(kT) = ui,p(kT) - ui,q(kT) (4.3.3)

If we substitute equation (4.3.3) into (4.3.1), we obtain

the following set of inequalities.

N-l m M1
2 Z . . kT — . kT ‘ + r
k=0 1-1pkm+1rl(ui,p( ) ul'q( )) 77; l
N-l m . Mn
— 1—1 n
(4.3.4)
N-l m -M
E E kaTI+i,l(ui,p(kT) - ui,q(kT)) 3 77-1 + r1
-0 1—1 1
N-l m ”Mn
k=0 i=lpkm+l'n( 1IP( ) 1:q( )) 77;. n

The constraint given in (4.3.2) is equivalent to

0 g ui'p(kT) g Gi,k i=l,2,...,n k=0’1'ooo'N-l

0 s ui'q(kT) < Gi,k

Once N is known and a linear objective function is speci-
fied, the inequalities given in (4.3.4)-(4.3.5) represent
a standard linear programming problem. This formulation-
has the disadvantage that it doubles the number of un-
knowns. For purposes of determining the value of N, we
make the following substitution. Let

ui(kT) = ui,k - Gi,k (4.3.6)

152

The inequalities in (4.3.1) then become the following.

N-l m
2 2 p C b
=0 i=1 km+i, lu i, k l
N-l m
2 2 p g b
k=0 i=1 km+i, nu i, k n
N-l m (4.3.7)
2 X p 2 B
k=0 i=1 km+i, lu i, k l
N-l m
2 . 2
k=0 l_lp,m+1,n 1 k 8n
where
M. N-l m
= 71— + + Z 2
b3 Yj r3 k=0 1=1pk1111’1'jG 1 k
-M. N-l In
. = 7—1 + . + Z Z
83 Y1 r3 k=0 1=1pk’1‘”1'jG 1 k

and rj is given in Theorem 4.2.8.
The inequalities given in (4.3.2) transform into
the following:

0 i ui,k é ZGi,k (4.3.8)

This method does not increase the number of unknowns to
be determined. In order to solve the problem using linear
programming, the next step is to convert the inequalities

to equalities by adding slack or surplus variables qim+i

153

If we add Nm slack variables to the inequalities in (4.3.8),

we have
ul,k + qkm+1 = 2Gl,k
. k=0’1'ooo,N-1 (4.309)
“mm +qkm+l = 2Gm,k

where qkm+i 3 0 for i=l,2,...,m

In general we do not know which of the bi and Bi in in-
equalities (4.3.7) are positive. If a bi or Bi is nega—
tive, we can multiply both sides of the inequality by

(-l) to put it in the prOper form. We then add the
necessary slack and surplus variables to convert the in-
equalities into equalities. To form an initial basic
feasible solution we add the necessary artificial variables

21, say q of them, to form an identity submatrix. The
value of N is then found by using Phase I of linear pro-
gramming [HADl]. This consists of maximizing the objec-
tive function

q _
J = - X 2. (4.3.10)

By using the simplex technique and Theorems 2.4.1 and
2.4.2, we can tell whether a solution to the linear pro-
gramming problem exists for that value of N. If not, we
increase N by one and try again. When a solution is
found, the Simplex Method also indicates whether the
solution is unique. Assuming the solution is not unique,

‘ve return to the formulation given by inequalities (4.3.4)

154

and (4.3.5) to determine the time-optimal sequence that
requires minimum fuel. The objective function is chosen

to be
N-l
J = X

b (u (kT) + ui q(kT)) (4.3.11)
k-O 1

1 1'9

":45

It is claimed that if u. (kT)‘and u. (kT) minimize J ,
i,p _1,q b

then they also minimize the fuel, that is,

N-l m
J = 2 Zlui (kT)I
k=0 i=1

It suffices to show that if ui'p(kT), ui,q(kT) and ui(kT)

minimize Jb’ then

ui(kT) 1f ui(kT) > O

i (RT) =
'P o if fii(kT) s o
o 11 fik(kT) 2 o
“1,q(kT’ = -fii(kT) if fii(kT) < o

where Gip (kT), ui q(kT), and ui (kT) are.the values of
p(kT), ui q(kT) and ui (kT) that minimize Jb. To show
this, it is sufficient to show that both “i,p(kT) and
fii,q(kT) cannot simultaneously be positive. The proof is
by contradiction. Assume an optimal value of Jb has been
found. Suppose for some k, Gip (kT) > 0 and fii,q(kT) > 0.
First assume that 61 p(kT) > ui q(kT). Define two new

variables “i,p(kT) and ui'q(kT) by

ui'p(kT) = fii,p(kT) - ui'q(kT) > 0 and ui’q(kT) = 0

Then

155
E. - fi'. = ". - ". = “.
l'p (kT) 1,q(kT) u1,p(kT) u1,q(kT) ul(kT)

' ' '. . kT '.
Then 1f we subst1tute u1,p(kT) for fi1,p( ) and ul'q(kT)
for fii q(kT) into the optimal solution, the constraints
I
are still satisfied. However,

'. +'. =". -". 'r< ". T
u1,p(kT) u1,q(kT) u1,p(kT) “1,q(k ) u1,p(k )

+ fii,q(kT)

since by assumption fii q(kT) > 0. This is a contradiction
I
of-the assumption that fii p(kT) and 61 q(kT) are optimal.
I I
The case where G. (kT) < u. (kT) leads to the same re-
1,p 1,q

sult. It then follows that the minimizing Jb minimizes
the fuel J.

The discussion given above was for the case when
Qi N f 0. However, by Theorem 4.2.9 the solution to the

I

optimal control problem for Qi = O is again a solution
I

N
to a set of linear inequalities. Thus the same arguments
can be repeated for this case also.

If we assume that the constraint on the amplitude
of the controller as given by (4.1.4) does not apply, the
only modification is to not include equations (4.3.9) in

the set of linear equations to be solved.

Example 4.3.1 Given the discrete-time system

 

x(k+l) = Cx(k) + Du(k) (4.3.13)

where

C = (4.3.14)

156

-1 l T

D = (e l-e- )

x(0) = (10 -12)T (4.3.16)

(4.3.15)

It is assumed that

Iu(kT)| c 0.5 k=0,l,...,N-1 (4.3.17)
We wish to find the minimum number of samples N and a
corresponding sequence of controls that drive the system
to the target described by

-1 < xj (kT) < 1 j=1,2

If the sequence of controls is not unique, we want to

choose a sequence that minimizes the fuel, that is,

N-l
J = z Iu(iT)I
i=0
Solution Let N=l. From equations (4.2.2) and (4.3.14)
‘1‘ l E 1-e:l] 1 0.63212
’ 1-e 0.63212 0.39958
0 IE- e3E] o o
CTC = _1 (4.3.19)
2 2 e 0 0.13534
The expression for F1 is found from equations (4.2.4) and
(3.2.4)
-1 0.71828
-1.71828
_2 3.67077
-4.67077
_3 11.6965
12.6965

From equations (4.2.9), (4.3.16), (4.3.18) and (4.3.20)

157

_ T - _ T = _
dl'l - x0w1,lFl _ x0w1,lFO 0088826 (403023)
d = xTw F = xTw F = 2 7905 (4 3 24)
2,1 0 2,1 1 0 2,1 0 ° ° °
Equation (4.2.8) gives
Q = FTw E = FTw F = 0 135335 (4 3 25)
1,1 1 1,1 1 0 1,1 0 ° ° °
Q = ET) E = FTw F = 0 39958 (4 3 26)
2,1 1 2,1 1 0 2,1 0 ' ° °

From equations (4.3.23) and (4.3.25),

_ '1 _ _
r1 — Ql,ldl,1 — 6.5634

Similarly, by equations (4.3.24) and (4.3.26)

r = 6.9836

_ -l
2 ‘ Q2,1dz,1
Thus by Theorem 4.2.8 and the fact that M1 = 1, we have

1 1

 

 

 

 

 

 

- - 6.5634 c u(O) s ' - 6.5634
JUTI35335 V0.135335
1 l
— + 6.9836 g u(0) < + 6.9836
/0.39958 /0.39958
These inequalities simplify to
-9.282 g u(O) g -3.845 (4.3.27)
5.402 < u(0) < 8.566 (4.3.28)
In addition, by (4.3.17) we require that
|u(0)| g 0.5 (4.3.29)

By inspection there is no value of u(O) that will satisfy
(4.3.27)-(4.3.29). We then increase N by 1. For N=2 we

have

1 0.63212 2 1 0.86466

0 0.36788 0 0.13534

158

w. = (c2)Tc2 = 1 E 0.86463 = 1 0.86466
1'2 1 1 0.86466 0.86466 0.74764
(4.3.30)
_ 2 T 2 1 [0 0.1353El_ 0 0
$2 1 ‘ (C2) C2 = ‘
' 0.13534 0 0.018316
(4.3.31)
_ 0.71828 3.67077
F2 = [F0,Fl] = (4.3.32)
1.71828 -4.67077
_T _ 0.58899 0.2823
Q = P w P = (4.3.33)
1'2 2 1'2 2 0.28233 0.1353
_T _ 0.05408 0.14700
2'2 2 2'2 2 0.14700 0.39958
dT = xTw F’ = (0 28855 0 13831) (4 3 35)
1,2 0 1,2 2 ° ° ' '
dT = xTw ‘F = (0 37766 1 02658) (4 3 36)
2,2 0 2,2 2 ° ° ° ‘
Y1 = tr(Ql'z) = 0.72433 (4.3.37)
Y2 = tr(Qz'Z) = 0.45366 (4.3.38)

Therefore, by equations (4.3.33), (4.3.35) and (4.3.37)

01 2 0.39837
-——§— d1 2 = (4.3.39)
yl ' 0.19096

Similarly, by equations (4.3.34), (4.3.36) and (4.3.38)

Q 0.83248
2,2 d
y: 2'2 2.26291

(4.3.40)

159

 

 

 

1 T0.28233
g 1
p = =
1 ”q H [(0.28233)2-|-(0.13534)211/2 0.1353fl
0.90175
= (4.3.41)
0.43227
In a similar fashion
2 0.34526
p1 = (4.3.42)
0.93851 -

Substituting equations (4.3.37)-(4.3.42) into Theorem
4.2.8 gives
-0.7332 s 0.90175u(0) + 0.43227u(1) 6 1.6168
(4.3.43)
0.9265 s 0.34526u(0) + 0.93851u(1) < 3.8959
(4.3.44)
If we ignore the constraint on the amplitude of the con-
troller, a solution to inequalities (4.3.43) and (4.3.44)
(if it exists) is a sequence of time-optimal controls.
The region described by these inequalities is shown as
the region enclosed by the parallelogram in Figure 4.3.1.
For example, if we choose sequences of controls corres-
ponding to points A, B, C, and D in this figure, we get.
-3.4032 1.6022

u(O u(O)

) = . = .
“(0) = '°°2392 - u(O) = -1.5617 .
U(l) = 4.2392 POlnt B u(1) = 1.5513 P01nt D

160

 

 

 

 

 

11(1)
A
57
B
~~4
3.
2.
D
-1
C
*“— ‘ § 1 4 1 4 u(O)
-4 -3 -2 -l 1 2
-1 _

 

Fig. 4.3.1. Loci of unconstrained time-optmal controls
and constraint set for Example 4.3.1

161

Using the state equation (4.3.13), these sequences of

controls give the following sequences of states:

x(0) = (10 ~12)T

x(1) = (1.1626 -6.5658)T Point A
x(2) = (-1.000 1.000)T

Fuel = 8.806

x(0) = (10 -12)T

x(1) = (3.004 -3.4018)T Point C
x(2) = (0.9999 -0.9999)T

Fuel = 2.000

x(0) = (10 -12)T

x(1) = (2.3266 -4.5658)T Point B
x(2) = (0.9999 1.0000)T

Fuel = 4.4784

x(0) = (10 -12)T

x(1) = (1.840 -5.4017)T Point 0
x(2) = (0.9999 -0.999)T

Fuel = 3.1235

The constraint on the amplitude of the controller given by
inequality (4.3.17) is also shown in Figure 4.3.1. In
order for a solution to exist, the two sets shown in this
figure must share a common point. Since this is not the
case, we could conclude that no solution exists for this
value of N also. However, in order to illustrate the
linear programming technique, we shall not use Figure
4.3.1 and derive the same result.

To determine if N=2 is sufficiently large by using

linear programming, we use the formulation given by

inequalities (4.3.7) and (4.3.8).

162

Since this system has

only a single input, we simplify the notation by letting

k u

14k

k=0

[lye-o’N-l

From (4.3.43)-(4.3.44) and (4.3.17), we have

0.90175u +

0.90175u +

0
0
0 +

0.34525u

0.34525u0

+
0 <

0 <

0.43225u
0.43225u
0.93851u
0.93851u

F' r4 (H H

W

u0

u1

g

V

< 2

i 2

1.6168 + 0.5(0.90175
0.7332 + 0.5(0.90175
3.8959 + 0.5(0.34525
0.9265 + 0.5(0.34525

(0.5)
(0.5)

+

+

+

0.43225)
0.43225)
0.93851)
0.93851)

After simplifying the above inequalities, adding slack and

surplus variables qi and an artificial variable 21’ these

inequalities are converted into the following equalities.

u0

C

F‘lJ F‘F‘ H

0.90175u
0.34525u
-0.90175u
0.34525u

+0.43225u
+0.93851u
-0.43225u
+0.93851u

0000

The purpose of the artificial variable is to
initial basic feasible solution.

then constructed as shown in Table 4.3.1.

+ql

+q2

+q3
+q4
+q5

-q6 + 21

1
1

= 2.28376
= 4.53776

0.06622
1.56837

(4.3045)
help form an

The initial tableau is

Since we are

trying to determine the value of N, we use Phase I of

linear programming.

163

 

 

 

mug
NHH
o H o o o o o Hmmmm.ou mmmvm.ou ammmm.Hu
H H- o o o o o Hmmmm.o mmmvm.o ammmm.H Hm H-
o o H o o o o mm~m4.ou maHom.ou Nmmmo.o me o
o o o H o o o Hmmmm.o mmmvm.o whamm.v 46 o
o o o o H o o mmmmq.o thom.o mamm~.~ ma 0
o o o o o H o AHV o H me o
o o o o o o H o H H H6 o
mflmmm
Hm_ 66 ma «6 ma ma HHU H: on a :H mo
muouom>
n
H- o o o o o o o o .o

 

 

H.m.v mam2¢xm MOW degmflfi UZHZSfiMUOmm M¢MZHA

H.m.v mqmflfi

 

164

 

 

HuH
Huh
o H o o o Hmmmm.o o o mmmvm.o- ommmm.o-
H H- o o o Hmmma.o- o o mmmvm.o mmmmm.o Hm H-
o o H o o mmmmv.o o o mAHom.o- sqmmv.o m6 0
o o o H o Hmmmm.o- o o mmmwm.o mmmmm.m «a o
o o o o H mmmmv.o- o o msHom.o HmHmm.H me o
o o o o o H o H o H H5 0
o o o o o o H o H H H6 0
mammm
HIN- mmu mU vmv MU WU HU H5 05 Q Cw. m0
muogom>
n
H- o o o o o o o o .0

 

 

 

H.m.v mqmz<xm mom denmfifi UZH22<mwomm mdmZHfl

N.m.v mqmdfi

 

165

 

 

 

o H o o o Hmmmm.o mmmvm.o o o Howm~.o-
H H- o o o Hmmmm.o- mmmvm.o- o o Hm8m~.o Hm H-
o o H o o mmmm¢.o thom.o o o mmmov.c m6 o
o o o H o Hmmmm.o- mmmwm.o- o o ovm~.m 86 o
o o o o H mmmmv.o- maHom.o- o o mamvm.o m6 0
o o o o o H o H o H H: o
o o o o o o H o H H on o
mammm
an mg mg vw mU mq ad ad on Q Ca mo
I. muouom>
n
H- o o o o o o o o .o

 

 

H.m.v mam2<xm mom Dflmflmda UZHSZflmUQmm m4MZHA

m.m.v mqm<9

 

166

For this reason we assign a "price" of (-l) to the arti-
ficial variables and zero "price" to the other variables.
This is indicated in the first row and first column of
Table 4.3.1. In columns "b" through "21" we place the
coefficients given in equation (4.3.45). The last~row of
the table is found as follows. The last quantity in the

"b" column (-1.56837) is found from equation (2.4.4),

 

that is,
l
1
2.28376
2 = cBb = (0 0 0 0 0 -1) 4.53776 = -l.56837
0.06622
L1.56837
The remaining terms in the last row are found by computing
zj - cj as given by equation (2.4.4). For example, the

quantity (-0.34525) at the bottom of the column 110 is found

from

1 1
0
0.90175
= (0 0 0 0 0 -1) 0.34525 - 0 = -0.34525
-0.90175
0.34525
L.—

 

where a1 is the column headed by uo.
Similarly, the quantity (0) at the bottom of the column
headed 51 is given by

10 ' c10 ' c8&10 ’ C10 '-

 

 

0
0
0
= (0 0 0 O 0 -1) 0 - (-1) = 0
0
1

167

where alo denotes the column headed by 21.

By examining the last row of Table 4.3.1 (exclud-
ing the term in the column headed by "b"), we see that
some of the quantities zj - cj are negative. By Step 2)
of the Simplex Method described in Section 2.4, we know
that an Optimal basic feasible solution has not been

found. From Step 3) we see that u should be added to the

1
basis because (-0.93851) has the most negative value.

From Step 4) the vector to be removed is determined by

H_, _ _ - l

x8r min 1 2.28376 4.53776 1.56837 _
1' 0.43225' 0.93851’ 07938§I

Thus q2 is to be removed from the basis. The "pivot ele-
ment" yrk = 1 is circled for convenience. By Step 5) the
new table is determined by equations (2.4.7)-(2.4.9).

Sample calculations:

Yrj Yzj '

In particular,

y20 - 1 and y21 - 0
Also,
. Yiz .
yij ‘ Yij ’ §;;'Y2j = Yij ' Y12Y2j 1 6 2
Therefore,
y10 ‘ y10 ‘ Y12Y20 = 1 ' (0’1 = 1
A _ - = -1.56837 - (-0.93851)1 = —0.62986

y70 " y70 y72Y20

168

In a similar fashion the rest of Table 4.3.2 is
completed. By examining the last row of this table we
see that we should add 110 to the basis. From Step 4) the
vector to be removed is ql. After another set of calcula-
tions similar to those above, we obtain Table 4.3.3. By
examining the last row (excluding to the column headed by
"b") we see that all terms are nonnegative, that is, the
"optimality condition" has been satisfied. Moreover, the
artificial variable 21 is in the basis at a nonzero level
(0.28461). By Theorem 2.4.1, part c), this problem has
no feasible solution. This means that the target can not

be reached in N=2 samples.

We now set N=3 and proceed as before. For this

 

 

case
0.83622 0.70180 0.33641
01,3 = 0.70180 0.58899 0.28233
(0.33641 0.28233 0.1353fl
10.007318 0.019894 0.054077
02 3 = 0.019894 0.054077 0.146996
I
(0.054077 0.146996 0.399576
61 3 = (1.28257 1.07640 0.515971)T
I
62 3 = (0.05111 0.13893 0.377657)T
I
Y1 = tr(Ql'B) = 1.56055
72 = tr(02,3) = 0.46097
0.821872
0* d — Q1 3 d = 0 689758 (4 3 46)
1,3 1,3 ~ 2 1,3 ' ' °

Y1 0.330635

169

 

0.110875
0* d = 02'3 d =. 0 301390 (4 3 47)
2,3 2,3 “2’ 2,3 ' ° °
Y2 0.819263
1 0.83622
1 _
Pl = “I3I72 = 2 2' 2 1/2 0’70180
”q H [(0.83622) +(0.70180) +(0.33641) 1 0.33641
0.73202
= 0.614349 (4.3.48)
0.294488
Similarly,
0.126000
pi = 0.342506 (4.3.49)
0.931028
From Theorem 4.2.8 and equations (4.3.46)-(4.3.49),
_ 1 T + _
r1 — (p1) 01,361’3 — 1.12275 (4.3.50)
_ 2 T + _
r2 — (p1) Q2'3d2'3 — 0.879955 (4.3.51)
Thus
M1 1
r1 + 7—— = 1.12275 + -———————-= 1.92325 (4.3.52)
*1 /I756055’
M1
r1 " 7Y-l = 0.32246 (4.3.53)
Similarly,
M2 1
r2 + 77; = 0.879955 + 0.46097 = 2.35282 (4.3.54)
M2

13y Theorem 4.2.8 we require that

170

-7$%+ ri < pl'iu(0)+p2'iu(l)+p3'iu(2) g 7:? + ri i=l,2
Substituting (4.3.48), (4.3.49), (4.3.54) and (4.3.55)
into this set of inequalities gives

0.322246 < 0.73202u(0)+0.614349u(l)+0.294488u(2)61.92325

(4.3.56)
-0.592909 8 0.12600u(0)+0.342506u(l)+0.931028u(2)(2.35382
(4.3.57)
To determine if N is large enough we make the substitution
given by equation (4.3.6), that is,

u(k) = uk - 0.5 k=0,l,2 (4.3.58)

Substituting (4.3.58) into (4.3.56) and (4.3.57), we obtain
the following inequalities.

1.142674 i 0.73202u + 0.614349u + 0.294488u

0 1 2 i 2.74368

0.106859 S 0.12600u + 0.342506u

0 + 0.931028u

l < 3.05259

2
In addition by (4.3.8) we require that

0 < uj s 1 for j=0,1,2

By adding slack, surplus and artificial variables, these

inequalities are converted to the following equalities.

uo +q1 =:.

1.12 +q3 =10
0.73202u0+0.614349ul+0.294488u2 +q4 =2-74363
0.12600u0+0.342506ul+0.931028u2 +q5 =3-05259
0.73202u0+0.614349u1+0.294488u2 -q6+zl =1.142674

0.12600u0+0.342506ul+0.931028u2 -q7+22=0.106859

171

The linear programming initial tableau is then constructed
as shown in Table 4.3.4. In this case we attempt to maxi-

mize

Z.
11.

2
J = -

i
As the bottom row of the tableau indicates, we have not
found the optimal basic feasible solution. By using the
simplex technique discussed previously, we continue to
change bases until we arrive at the one indicated in Table
4.3.8. Examination of the last row shows that all terms
are nonnegative. Furthermore, the artificial variables
51 and 52 have been removed from the basis. By Theorem
2.4.1 this means that we have found an Optimal basic
feasible solution. Thus the target can be reached in N=3
samples. From Table 4.3.8 we can also obtain a set of

time-optimal controls:

u0 = 1 u1 = 0.6684 u2 = 0 (since u2 1s nonbasic)

Substituting these quantities into (4.3.58), we get the
following sequence of time-optimal controls.

u(0) = 0.5000 u(1) = 0.1684 u(2) = -0.5000 (4.3.59)
These controls are substituted into the state equation

(4.3.13) to give the following sequence of states.

x(0) = (10 -12)T

x(1) = (2.5985 -4.0985)T
x(2) = (0.0697 -1.4013)T
x(3) = (—1.000 -0.8316)T

172

 

 

max
5"“
o o H H o o o o o mmmm~.H- mmmmm.o- ~ommm.o- nmmqm.H-_
H o H- o o o o o o mOHmm.o Hmmwm.o ooomH.o mmmmOH.o mm H-
o H o H- o o o o o m4¢m~.o mmva.o mommn.o «hmmvH.H Hm. H-
o o o o H o o o o mOHmm.o Hmmvm.o oommH.o mmmmo.m ma 0
o o o o o H o o o m¢vmm.o mm¢Hm.o ~o~m5.o mmmvn.~ «a o
o o o o o o H o o H o o H m6 o
o o o o o o o H o o H o H «a o
o o o o o o o o H o o H H H6 0
mammm
NIN- HIN. hwy 0U mmu vmu MU NU Hmo N5 H5 05 Q Gun m0
muouom>
n
H- H- o o o o o o o o o o .0

 

 

 

H.m.v mqum mom Dflmqmfiwfi UZHZEGOMQ m<mZHHH

v.m.v mam—«H.

 

173

 

 

 

 

Hug
any
HmmHm.H o mommHm.o-. H .o o o o o o Howom.o- mmHmmm.o- HammoH.H-
movao.H o movno.H- o o o o o o H mmnmm.o wmmmmH.o masvHH.o N: o
momem.o- H mommHm.o .H- o o o o o o Homom.o mmHmmm.o ammOH.H Hm H1
H- o H o H o o o o o o o mamvm.~ m6 o
mommHm.o- o mommHm.o o o H o o o o Homom.o mmHmmm.o mmmoa.~ 46 o
movao.H- o movno.H o o o H o o o mmsom.o- wmmmMH.o- mmmmm.o m6 o
o o o o o o o H o o H o H me o
o o o o o o o o H o o H H H6 0
mammm
NW Hum N.U mU mU WU mU NU HU NS H5 05 3 3H mu
muouom>
n
H- H- o o o o o o o o o o .o

 

 

H.m.v mqum mom DANNAQB GZHEEUONHQ m<mZHA

m.m.v mqmda

 

174

 

 

Hun
memom.o o ammom.m- H o o o o o omeH.m Hmmsm.H o mmHmm.o-
:mmmm.a o Hmmmm.6- o o o o o o Hamm.6 HmmH6.N H smomwm.o on o
ammom.m- H mmmom.m H- o o o o o omVHH.m- Hmmnm.H- o mmmHmm.o Hm H-
H- o H o H o o o o o o o mhmvm.m m6 0
ammom.m- o momom.m o o H o o o omvHH.m- Hmmhm.H- o wmmmH.m H.6 o
o o o o o o H o o H o o H m6 o
o o o o o o o H o o H o H N6 0
wmomm.6- o Hmmmm.6 o o o o o H HHmmm.6- HmmH6.- o mHmHmH.o H6 o
mammm
mm. H.m 66 m6 m6 46 m6 m6 H6 N6 H6 06 H 6H mo
mnouom>
.no
H- H- c o o o o o o o o o

 

 

 

H.m.v mqmzdxm mom D<m4m<fi UZHSZ<MUQmm m£MZHA

m.m.v mam¢9

 

175

 

 

max
mun
H o o H o o o o ~o~m6.o {mmvvmm.o- omm¢Hm.o- o mvaH6.o-
o o o o o o o o H o o H H on o
o H o H- o o o o mo~m6.o- mmvvm~.o omm¢Ho.o o mVSOHv.o Hm H-
o o o o H o o o oomNH.o OMOHmm.o nommvm.o o mmmmm.m m6 0
o o o o o H o o mo~m6.o- mqumm.o omHVHm.o o mmHHo.~ 46 o
o o o o o o H o o H o o H m6 o
o o o o o o o H o o H o H N6 0
H- o H o o o o o oomNH.o OHOHmm.o- sommvm.o- o OH6H6H.o 66 o
mammm
NW Hm. NU mU mU vU MU NU HU N5 H5 5 Q Gun m0
muouom>
H
H- H- o o o o o o o o o o .o

 

 

 

H.m.¢ mqmzflxm mom deqmdB UZHZSflmmem m<mZHq

h.m.

v mamdfi

 

176

 

 

 

H H o o o o o o o o o o
o o o o o o o o H o o H H on o
o 466N4.H o 466N4.H- o o o o 4mHmH.H- mmm>4.o H o ~4mmm.o H6 0
o Hmamm.o- o Hmsmm.o H o o o HH4mm.o 44446.o o o mmnmm.m m6 o
o H- o H o H o o c o o o OHom.H 46 o
o o o o o o H o o H o o H m6 o
o 466N4.H- o 46664.H o o o H 4mHmH.H 4mms4.o- o o mmHmm.o N6 0
H- Hmnmm.o H Hmamm.o- o o o o HHmmm.o- 4mmma.o- o o mom4m.o 66 o

mammm
mu HN 66 46 m6 46 m6 «6 H6 N6 H: on 6 6H mo
l I muouoo>

H

H- H- o o o o o o o o o o .o

 

 

 

H.m.v mnmz<xm mom Dflmqmfifi UZHZEflMOQmm m<MZHq

m.m.v mqmde

 

177

Fuel = 0.5000 + 0.1684 + 0.5000 = 1.1684

Thus the sequence of controls given by (4.3.59) does
drive the initial state to the target in three samples.

Returning again to Table 4.3.8, we note that the
terms in the last row are zero, that is, zj - cj = 0
for j=2,3,...,10. Also, there are yij > 0 terms in these
columns. By Theorem 2.4.2, part b) this implies that the
basis can be changed, and again we will have an optimal
basic feasible solution. In other words, the time-
optimal sequence of controls is not unique. We now con-
sider the problem of determining a sequence of controls
that minimizes the fuel. Now that N=3 is known we can-
use the formulation given by inequalities (4.3.4) and
(4.3.5). After adding slack, surplus, and artificial
variables, these inequalities are converted to the follow-

ing equalities. Because the system in this example has

only one input, the notation is simplified by setting

up(kT) u.,p(kT)

l

u(kT)

. kT
uqu( )

1378

mmmmm.ouHm+
Hammm.ou
mmmmm.~u

mNMNm.Hu

O

A‘

A

-H

v
Q.

:3

HHH165+HH1651

TNHEmeE on nmfl3 m3 .mfl umcu .HHH.m.vv cofiumovm kn cw>flo ma cofluocsw T>Huowmno one

OH6- H~16sm44m~.o-HH166mm4H4.o-H016smo~m6.o-HNV664444~.o+HH166mm4H4.o+Hovms~ommn.o
m6+ H~16sMOHHm.o+HHV6sHm~4m.o+Hov6soomNH.o+HN1QDHOHmm.o-HHvasHm~4m.o-HovasoommH.o-
MW6+ HNV6:HOHmm.o-HHV6sHmm4m.o-Hos6soom~H.o-HmvmsHOHmm.o+HHvasHmN4m.o+HovmsooomH.o
h6+ HNV656444~.o-HHV66mm4Ho.o-Hov6s~o~mh.o-Hmvmsm44am.o+HHVQSmM4H4.o+Hovasmomm6.o
wv+ ANVUD
mq+ HHVUD
vv+ Hovws
m6+ Hmvds
Nq+ Haydn
H6+ 1016:

179

The above equations represent a well-formulated linear

programming problem; the solution of which is the follow-

ing.
p q
u 1 - 0.0000 1 " 0.0000

Substituting these quantities into (4.3.3), we get the
following sequence of fuel-optimal controls: 2-
u(O) = 0.4402 u(1) = 0.0000 u(2) = 0.0000

The corresponding sequence of states is

x(0) = (10 -12)T

x(1) = (2.576 -4.136)T
x(2) = (-0.0381 -1.522)T
x(3) = (-1.000 -0.5598)T
Fuel = 0.4402

For purposes of comparison, a sequence of controls which
requires maximum fuel is the following.
u(0) = u(1) = u(2) = 0.5

The corresponding sequence of states is

x(0) = (10 -12)T

x(1) = (2.598 -4.098)T
x(2) = (0.1917 -1.917)T
x(3) = (-0.3777 -0.1223)T

Fuel 1.5

180

The maximum fuel trajectory requires approximately 3.4

times as much fuel as the minimum fuel trajectory.

4.4 Statement and Solution of Stochastic
Timejgptimal Control Problem

 

 

This section is devoted to the study of a stochas-
tic version~of the problem considered in the previous
section.

Problem Statement Given a system described by

 

x[(k+1)T] = Cx(kT) + Du(kT) + Ew(kT) k=0,l,...,N-l
(4.4.1)

where

x(kT)is a n x 1 state vector

C is a n- n nonsingular matrix
D is a n m matrix
u(kT) is m x 1 nonrandom vector to be determined
w(kT) is

zero mean independent random vectors

x
x

E is a n x r matrix
a
a

sequence of r x l

The initial state is

x(0) = + v

x0
wherex0 is a known n x 1 vector and v is a random vector
whose components are independent of w(kT) for k=0,l,...,
N-l. We want to find

1) the smallest value of N such that

2

E(xiz(NT)) 4 Mi i=l,2,...,n. (4.4.2)

where the xi(NT) are the components of x(NT) and

181

2) The sequence of open-loop controls that drive the
initial state to the target described by inequality
(4.4.2). By open-loop we mean that the controls are as-
sumed nonrandom and can.be precomputed. If the sequence
of controls is not unique, we want to choose one that

minimizes the fuel, that is, minimizes

N-l m
J = 2 2 |ui(kT)|
k=0 i=1

where the ui(kT) are the components of u(kT). It is as-
sumed that the amplitude of the controls is constrained,
that is,

Iui(kT)l < Gi' i=l,2,...,m k=0,l,...,N-1 (4.4.3)

k

Solution As in the problem with the hyperspherical target,

 

we make the following preliminary definitions.

Definition Let W = (w(O),w(T),...,w[(N-1)T])T. The matrix

 

RN is defined by

RN = E(WWT) (Nr x Nr matrix) (4.4.4)

Definition The covariance matrix V, is defined by

 

V = E(va) (n x n matrix) (4.4.5)

The solution of equation (4.4.1) is

N N N-l N N-l
x(NT) C x(0)-C Z F.u(jT)-C Z H.w(jT) (4.4.6)
~= J -= J
3 0 J 0
where
Fj = -c“3+1)0 j=0,1,...,N-l (4.4.7)
H. = -C—(j+1)E j=0,1’ooo'N—l (404.8)

182

The solution is obtained in the same way as that for the
deterministic system described in Section 3.2.

If x(NT)=(x1(NT), x2(NT),...,xn(NT))T, then

N N-1 . N-l .
xi(NT)-ci[x(0)-jionu(jT) - jionW(JT)]

where c? is the i-th row of CN. Thus

2 Ngl N51 N-l
. NT = - F. 'T - H. ' . - z . °
x1( ) [x(O) j=0 Ju(J ) j=0 3W(JT)]W1’N[X(0) j=0F3u<JT)
N-l
i=0 3

where

_ N T N .
wi,N — (Ci) ci (n x n matrix) (4.4.10)

Expanding equation (4.4.9), we get

2(NT)- T(0)0 (0)-2 T(0))- 1518 ('T)
Xi —X i'Nx x i,Nj=0 ju J
T( ) N-l ( (Nn1 ( T (N-1
-2x 0 w. 2 H.w jT)+ z F.u jT)) w. 2 F.u(jT))
lle=0 J j=0 J. 1IN'j=o J

N-l N-l

. T .
+2(j:0Fju(JT)) wi’N.(jionW(JT))

N-l N-l

. T .
+ (jionw(JT)) wilN (jiOHjW(JT)) (4.4.11)

Taking the expected value of both sides of equation (4.4.11)

while noting the assumptions of independence and zero

mean,

183

we get
E(x2(NT))-xT x + E(vT v) - 2x(0) N-1F u('T)
i ‘ Owi,N 0 wi,N w1'Nj50 j J
N-l T N-l
+( 2 F-MjTH (pi N12 F.u(jTH
j=0 J I j=0 J
N-l T N-l
+EH2Hmfim)%JflXHmUMH
j=0 3 ' j=0 3
_ T T _ -T
— xolPiINx0 + E(v wi’Nv) 2di,NU
+ UTQ U + E(WTS W) (4 4 12)
i,N i,N ° '
where
_. _ T .-
di,N — x0w1,NFN (4.4.13)
FN = [FO,F1,...,FN_1] (4.4.14)
Si'N = [H0,Hl,...,HN_1]Wi’N[HO,Hl,...,HN_1]
(4.4.15)
Q. = 810. 5 (4.4.16)

1,N N 1,N N
Using the same argument as that used in obtaining equa-
tions (3.6.18) and (3.6.19), equation (4.4.12) can be

written in the following way.

2 _ T _ -T T
E(xi(NT))-U Qi,NU 2di,NU+x0wi,Nx0+tr(Si,NRN)
+ tr(w V)-M2 (4 4 17)
i,N i ’ '

Since we require that E(x§_(NT))-M.i < 0, we are looking

for N and U such that

 

184

T

+ e. < 0 (4.4.18)

‘T
U-2di 1,N

U
,N

where

_ T _ 2
ei,N - xowi’Nxo+tr(Si’NRN)+tr(wi’NV) Mi (4.4.19)
By comparing inequality (4.4.18) with the corresponding

deterministic inequality (4.2.7), we see they are the

same except that di is replaced by 51 and e. is re-
I I

,N N 1 N

placed by 31 Thus the form of the solution in the
I

N'
stochastic case is similar to that of the deterministic
case. Starting with inequality (4.4.18), we can then

repeat the steps used in obtaining the sequence of con-
trols in the deterministic system after substituting

ai,N for di,N and éi’N for ei,N'
simplify inequality (4.4.18) by substituting

In particular, we

U = Pi,N Yi + Ci,N (4.4.20)
where
PE,N Pi,N = 1
into (4.4.18) to give
T T - -
g(Yi)=YiPi'NQi’NPi,NYi+Li’NYi+gi'N < 0 (4.4.21)
where
ii,N=P1,N(Qi,NCi,N ' ai,N) (4'4'22)
- T. -T -
91,N " Ci,NQi,NCi,N ’ 2di,N Ci,N + ei,N (4°4'231

By using the same steps as those used to obtain Theorem

4.2.6, we have the following theorem.

 

185

Theorem 4.4.1 The expression for g(Yi) in (4.4.21) re-

 

duces to
2 2
:37 + + V - é

_ _ T
where Yi - tr(Qi,N) and Yi - (y0,i'yl,i"°"me-l,i)

Since Yi 3 0, it follows from inequality (4.4.24) that in

order for a solution to exist, it is necessary that 4
2 .
o I g I = 0..
tr(Sl’NRN)+tr(wl’NV) M1 for 1 1,2, ,n

For the stochastic case, Theorem 4.2.8 is replaced by the
following theorem.

Theorem 4.4.2 Let Qi N f 0. If a sequence of time-
I

 

Optimal controls exists, it is a solution to the following

set of inequalities.

M.
1

_ 77; + ri < pl’iul(0)+p2,iu2(0)+...+pm’ium(0)+pm+1'iu1(T)

+. . .+p2m’ium(T) +. u1[ (N-1)T]

"+me-m+l,i

M.
1 -_
+...+me’ium[(N—1)T] < 79—14- ri l_1’2'ooo'n

 

where

r = ( i)T Qi,N a

1 p1 2 i,N

Y1

. i .

1 _ + 1 .
pl - _1311175 and q 15 any nonzero column of Qi,N°
_ 2 .1.
Mi = (Mi - tr(Si,NRN) - tr(wi’NV))2

186

The solution does not depend on which nonzero column of
Qi N we choose or whether we choose the plus or minus
I
sign in the expression for pi. If Nm=1, we set Yi = Qi N

I
and p111 =:1.
Similarly, Theorem 4.2.9 for the deterministic system
becomes the following theorem.

Theorem 4.4.3 If Qi N = 0, the following is true.
I

 

a) If a solution exists, a time-Optimal sequence of con-

trols is a solution of the following set of inequalities.

(0)+E .u (0)+...+6’- .u (0)+6-' .u (T)+...

OLl,iul 2,1 2 m,1 m m+l,1 1

+5 (T)+...+

02m 1 11m [(N-1)T]+...

aNm-m+1, i u1

- 2 T
+0 aNm ium[(N-1)T] < Mi -x0wi’Nxo-tr(si'NRN)

-tr(wi’NV) i=l,2]... n

_ T -
2,i""'aNm,i) — 2xotpi'NFN (lme vector)

where a a
( 1'1-

b) If N 2 n/m and the anm matrix F is of rank n, then

N
we have the following two cases.

2

T .
1) If x +tr(Si NRN)+tr(tbi NV) < Mi’ 1=1,2,...,n,

01’1,N"0
then the sequence of time-Optimal controls is arbitrary.
In particular, the sequence U = 0 is the minimum energy
and fuel solution.

T 2
2) If xowi 1,N H0+tr(s 'NRN)+tr(wi NV) > Mi for some i, no

solution exists for this value of N.

5777-71

187

By comparing Theorem 4.4.2 with Theorem 2.4.8, we
see that the only difference is that in the stochastic
case Mi replaces Mi' From Theorem 4.4.2 we see that
Mi 4 Mi' In other words, the effect of the noise is the
same as that of reducing the dimensions (Mi) of the target
set of the corresponding deterministic system.

Example 4.4.1 Consider the system described by

 

x(k+l) = Cx(k) + Du(k) + Ew(k) k=0,l,...,N-l (4.4.25)

x(0) = x0 + v (4.4.26)
where _
1 l-e
c = _1 (4.4.27)
0 e
D = E = (e‘1 1-e‘1)T (4.4.28)
x = (10 -12)T (4.4.29)

0
C, D, and x0 have the same values as those given in Example
4.3.1 for the deterministic system. It is assumed that v,
w(k) for k=0,l,...,N-1 are independent Gaussian random

variables such that

E(V) = E(W(k)) = o k=0'l’ooo'N-1 (4.4030)
0.1 0
V = (4.4.31)
0 0.1
RN = E(WWT) = 0.51N (IN is an NxN identity matrix)
(404.32)
M. = 1 i=l,2 (4.4.33)

We wish to determine the smallest value of N and a cor-

responding sequence of controls such that E(xi(NT)) < 1.

 

188

If the sequence is not unique, we want to choose one that

minimizes

N-l

2 Iu(iT)| (4.4.34)
i=0

q
II

It is assumed that the amplitude of the controls is con-
strained, that is,
Iu(iT)I < 1 i=0,l,...,N-l (4.4.35)

Solution Setting N=1, Theorem 4.4.2 requires that

M. M.
- 77% + ri < u(O) “7V% + ri i=l,2 (4.4.35)
1. .‘L
where
Qi 1 -
I
*1

Q. and w. are the same for the deterministic and
1,N 1,N

stochastic systems since C and D are the same.‘ Thus,

from Example 4.3.1,

yl = 01 1 = 0.135335 (4.4.38)
I
y2 = 92 1 = 0.39958 (4.4.39)
I
1 0.63212
wl'l = (4.4040)
0.63212 0.39958
0 o
w = (4.4.41)
2'1 0 0.13534
_ T 1 0.63212 0.71828
Also, d1 1=x0wl lF0 = (10 -12)
' ' 0.63212 0.39958 -l.71828

= -0.88826 (4-4-42)

 

189

_ T _
dz'l—xowz'lF0 — 2.7905 (4.4.43)
Thus by (4.4.37)
_ -0.88826 _ _
rl - m - 6.5634 (4.4.44)
and
_ 2 1
Ml=(M1-tr(Sl'lR1)-tr(wl'1V))2
1/2
1 0.63212 0.1 0

1-tr(0.135335)(0.5)-tr
0.63212 0.39958 0 O.

= 0.89015 (4.4.45)
Similarly,
r2 = 6.98358 (4.4.46)
fiz = 0.88695 (4.4.47)

Substituting equations (4.4.38)-(4.4.39) and (4.4.44)—
(4.4.47) into (4.4.36) gives

0.89015 0.89015

- —ETT§533§ - 6.5634 6 u(O) é fiffggggg ' 5-5534
0.88695 0.88695
‘57§§§§§' + 6.98358 < u(O) <-57§§§§§ + 6.98358

After simplification, the above inequalities become
-8.9831 S u(O) 6 -4.1437 (4.4.48)
5.5800 < u(O) < 8.3867 (4.4.49)
In addition we require that
-l g u(0) g 1 (4.4.50)
By inspection, there is no value of u(O) which satisfies
(4.4.48)-(4.4.50) so we must increase the value of N by 1.

For N=2 we have

 

190

 

1 0.86467
01,2 =w (4.4.51)
0.86467 0.74765
0 0
02,2 = (4.4.52)
0 0.18316
.58899 0.28233
Q =
1,2 (4.4.53)
0.28233 0.13534
0.05408 0.14700
02,2 = (4.4.54)
0.14700 0.39958
61 2 = (0.28855 0.13831)T (4.4.55)
I
52 2 = (0.37766 1.02658)T (4.4.56)
I (
Y1 = tr(Qllz) = 0.72433 (4.4.57)
y2 = tr(Qz’z) = 0.45366 (4.4.58)
0.90175
pi = (4.4.59)
0.43227
0.34526
0.93851
Then
r1 = 0.44177 and Ml = 0.68049 (4.4.61)
Similarly,
r2 = 2.39535 and E2 = 0.86882 (4.4.62)

191

Therefore, by Theorem 4.4.2 and equations (4.4.57)-(4.4.62),

_ 0.68049

+ 0.44177 < 0.90175u(0)
V0.72433

0.68049
V0.72433

+ 0.43227u(1) £ + 0.44177

_ 0.86882

+ 2.39535 S 0.34526u(0)
"0.45366

0.86882

+ 0.93851u(l) <
“0.45366

+ 2.39535

After simplification, these inequalities become
-0.35780 < 0.90175u(0) + 0.43227u(1) < 1.24133 (4.4.63)
1.10542 < O.34526u(0) + 0.93851u(1) < 3.68528 (4.4.64)
To determine if N is large enough, we use the linear pro-
gramming technique discussed in Section 4.3. From (4.3.6)
we define

u(O)

- 1 (4.4.65)

u(1)

II
I:
I
|_|

(4.4.66)

Substituting equations (4.4.65)-(4.4.66) into (4.4.63)-
(4.4.64) and adding the necessary slack, surplus, and

artificial variables, we obtain the following equations.

u0 +q1 = 2.

ul +q2 = 2.
0.90175uO + 0.43225ul +q3 = 2.57533
0.34526u0 + 0.93851u1 +q4 = 4.96905
0.90175u0 + 0.43225u1 -q5+E1 = 0.97620
0.34526uo + 0.93851ul -q6+'z'2 = 2.38919

(4.4.67)

192

For a performance index we choose to maximize

2
J = - z 2. (4.4.68

where the 2i are the artificial variables.

The initial tableau for the linear programming
solution is shown in Table 4.4.1. Examination of the
bottom row indicates we have not found an Optimal basic
feasible solution. By repeatedly changing bases we arrive
at Table 4.4.4. Since the bottom row is nonnegative and
no artificial variables appear in the basis, we have
satisfied the optimality criterion and a solution exists
for N=2. From Table 4.4.4 we see that

110 = 1.4834 u1 = 2.

From equations (4.4.65) and (4.4.66) we have that

u(O) = 0.4834 (4.4.69)
u(1) = 1. (4.4.70)
Fuel = 1.4834 (4.4.71)

Table 4.4.4 indicates that the solution is not unique. To
determine a sequence that requires minimum fuel we use the
formulation given in equations (4.3.3) and (4.3.4)(with Mi
replaced by Hi). That is, we make the substitution

u(O)

up(0) - uq(0) (4.4.72)

u l u l - u 1 4.4.73
() p() q() ( )
in the inequalities given by (4.4.63) and (4.4.64). After
adding slack, surplus, and artificial variables, these in-

equalities become the following equalities.

193

 

 

 

Nun
max
o o H H o o o o maonm.H- H0Ȣ~.H- mmmmm.m-
H o H- o o o o o Hmmmm.o mmmvm.o mHmmm.~ mm H-
o H o H- o o o o m-m4.o mAHom.o ommam.o Hm H-
o o o o H o o o Hmmmm.o mmmvm.o mommm.v 48 o
o o o o o H o o m-m4.o mAHom.o mmmhm.~ me o
o o o o o o H o H o N me o
o o o o o o o H o H m He o
mammm
NW Hm. mU mmv Vmu MU NU HU H5 05 Q CH m0
muouom>
n
H- H- o o o o o o o o .o

 

 

H.v.¢ "mm—”gm mom deqmdh. UZHSEflmwomm MANMZHA

H.v.v "mu-H93.

 

194

 

 

 

mum
Hug
o o H H o ‘o whosm.H o o HON¢N.H- NNmNm.o-
H o H- o o o Hmmma.o- o o mvam.o NHNHm.o Nm H-
o H o H- o o mNNm¢.o- o o thom.o ONHHH.o Hm H-
o o o o H o Hmmmm.o- o o mwam.o ONmo.m «v o
o o o o o H mNNm¢.o- o o thom.o NOHN.H me o
o o o o o o H o H o N H: o
o o o o o o o H o H N H8 0
mammm
N-NI HIN. mmu mU wU MU NmV HU H5 05 Q GH m0
mnouow>
H
H- H- o o o o o No C o .o

 

 

 

H.v.v mqmz<xm mom Dfiflqm¢9 UZHZSdeQmm MdmZHQ

N.v.v mqmda

 

195

 

 

ovam¢.ol

 

o NNNNN.H H NNNNm.o- o o Homea.o o
H NNNNm.o- H- mNNmm.o o o HomNN.o- o ovame.o Nm. H-
o omOH.H o omOH.H- o o «mav.o- o NNNNH.o on o
o NNNNm.o- o NNNNm.o H o Homep.o- o vao.m 48 o
o H- o H o H o o Hamm.H me o
H
o o o o o o H o N s o
o omOH.H- o omOH.H o o mmmaw.o H HmNN.H H8 0
mammm
NN HN @U mU vU MU NU HU Q Gfl m0
l I mHOpom>
N
H- H- o o o o o o (.o

 

 

 

H.v.¢ quzflxm mom Dfimnmdfi UZHZSdmwomm mGMZHA

m.v.v mamma

 

196

 

 

 

H H o o o o o o o o o
HHm.N H- NHHm.N- H o o mmHo.N- o o o omNN.H me o
mmN.N o memm.N- o o o 8NHN.N- o o H emmv.H on o

H- o H o H o o o o o maam.N 68 o

aHHm.N- o NHHm.N o o H mNHo.N o o o Hmam.o m8 0

o o o o o o H o H o N H5 0

ammN.N- o momN.N o o o NNHN.N H o o mmHm.o He 0

Nm. Hm ow me 68 me Ne H8 H5 oz 9 mHmmm mo

muouom>

H- H- o o o o o o o o flo

 

 

 

H.v.v mqmzdxm mom Dflmqmfla GZH22¢m00mm MdmZHA

w.v.v mnm¢8

 

35.8.:

8 8 m m
NvaH.HuHm+N8+ AHV sHmNmm.o-on nmvam.o-AHV sHmNmm.o+AoV amNm8N.o
7
m“ N 8 8 a m
omamm.ou 8+ AHV smNva.o+on smbHom.o+1Hv smNNm8.o-on smNHom.o-
8 8 . 8 m . a .
mNmmm.mn 8+ 1H1 sHmmma o-xov smNm8m.o-AHV sHmmmm o+xov smvam o
m w m m m
mmHvN.Hu 8+ 1H3 smNNm8.o-Aoc smNHom.o-AHV smNNm8.o+on smNHom.o
H- 88+ 1Hc85
Hu m8+ on8s
Hn N8+ Avas

m
H" H8+ on s

198

By equation (4.3.11) we wish to maximize

2
J = - i:l(up(i) + uq(i)) (4.4.75)
subject to
up(i),uq(i) 2 0 i=l,2 (4.4.76)

The expressions in (4.4.74)-(4.4.76) represent a well-
formulated linear programming problem; the solution of

which is

0.0000

up(0) 0.4834 uq(0)

0.0000

up(l) 1.0000 uq(1)

By equation (4.4.72)-(4.4.73) these equations imply that

u(O) 0.4834 (4.4.77)

u(l)

1.0000 (4.4.78)
u(O) and u(1) given by equation (4.4.77) and (4.4.78) are
the time-Optimal controls that require minimum fuel. By
comparing these values with those of (4.4.69)and (4.4.70),
we see that they are the same. This is not true in-
general.

To check the above results the discrete-time system
was simulated using Gaussian noise with statistics given by
equations (4.4.31) and (4.4.32). Using different noise
sequences, the system was simulated 500 times to determine

the following sample means.

199

E(x(0)) = (10.0 -11.99)T

E(x(l)) = (2.58 -4.14)T

E(x(2)) - (0.344 -0.873)T

E(xi(2)) = 0.69 (4.4.79)
E(x§(2)) = 1.00 (4.4.80)

Equations (4.4.79) and (4.4.80) indicate that E(xi(2)) < 1,

i=l,2 as desired.

 

CHAPTER V

SUMMARY AND EXTENSIONS

In Section 5.1 some of the main results obtained in

Chapters III and Diare briefly summarized. Certain possible

 

extensions of these results are given in Section 5.2.

5.1 Summary

 

For the case when the target set is a hypersphere
(Chapter III), the procedure for determining a sequence of
open-loop time-optimal controls is most easily described
by using Figures 3.2.1, 3.5.1 and 3.6.1. Depending on the
parameters of the system and the initial state, we may or
may not have a unique solution. In general, the solution
is not unique if N S n/m and is never unique if N > n/m.
Because of the nonuniqueness of the solution, we have an
opportunity to optimize the system according to another
criterion. The criterion chosen here is to minimize the
total energy required to drive the initial state to the
target set. It is shown in Section 3.3 that except for
the case when all the controls are zero the minimum energy
sequence that drives the system to the boundary of the

target also is the minimum energy sequence to the entire

200

201

target. A method of determining the minimum energy seqence
of controls is given in Section 3.3. The method is readily
adaptable to computer solution, and the problem reduces to
finding the roots of a polynomial of order less than or
equal to Zn where n is the order of the system. It is
shown in Section 3.4 that the time-optimal controller-can
be synthesized as a feedback controller. The sequence of
optimal controls is proportional to the state of the system,
plus a bias term proportional to the radius of the target.
Using arguments similar to that for the open-loop system,
the time-optimal control problem for a system with a single
delay in the input is solved. In Section 3.6 a stochastic
version of the original problem is solved. Since the
controller is assumed to be open-loop, it is shown that
the sequence of controls can be-found in a manner similar
to that of the deterministic system. It is also shown
that for the undelayed deterministic system the target can
also be reached in a number of samples equal to the smallest
integer greater than or equal to n/m but that this need not
be true for the stochastic system.

In Chapter IV the target set is changed to that of
a hyperrectangle, and constraints on the amplitude of the
controller are added. By means of a linear transformation
it is shown that this problem reduces to finding the solu-
tion to a set of linear inequalities. By defining new

variables, the original problem is reduced to a linear

 

202

programming problem for which the method of solution is
well-known. The procedure for determiningaasequence of time-
optimal c0ntrols begins by assuming N=l and using Phase I
of linear programming to determine if a solution exists

for this value of N. If no solution exists, N is increased
by l and the procedure repeated. Assuming a solution
exists for some value of N, the theory of linear pro-
gramming indicates whether the solution is unique. If it
is not, the linear programming problem is reformulated
with a different cost functional which is taken to be the
total fuel required to reach a point contained in the
target. By solving this new linear programming problem

we determine the sequence of time-optimal controls that
require minimum total fuel required to reach the target.
Corresponding to this deterministic problem is the
stochastic system described in Section 4.5. Because of

the assumption that the controller be open-loop, this
problem is reduced to a problem quite similar to that of

the deterministic system.
5.2 Extensions

There are several extensions to the problems con-
sidered in Chapters III and IV which can be considered.

These extensions are given here.

203

(l) Time-Varying Linear Systems
It is assumed that the system to be considered is

described by the following difference equation.

x[(k+1)T] x(kT) + Dku(kT) (5.2.1)

= Ck+1,k

x(0) = x0 (5.2.2)

where Ck+1 k has the properties of a transition matrix,
I

that is,
Ck,k = I for all k
Ck,jCj,i = Ck,i
C811 = Cj.k

These assumptions on Ci,k are automatically satisfied if the
state difference equation is derived from a linear system des-
cribed by a time-varying differential equation. Such is

the case in a sampled-data system.

The solution of equations (5.2.1) and (5.2.2) is

N-l
X(0) + 22C
i=0

x(NT) = C u(iT)

N,0 N,i+lDi+l

Using the second property of Cj k given above, this can
I

be written as

. N-l
x(NT) = CN,0 x(O) + iiocori+lDi+1U(lTZ]

_ CN,0[}(0)+(€0,1D1U(0)+C0,2D2u(T)+°°'+C0,NDNu[(N-1)T]]

204

CN,0E“°"(’C0,1D1"C0,2D2“°'"C0,NDN'°°"

r-
u(0)

-C0,NDN)] u (T)

(FIN-l)T]

 

 

= CN,0[X(O) - EfiU]

where

and

Then

and

where

"11

—N = [IC0,1D1"C0,2D2" ° °'-C0,NDN] (5.2.3)

0 = (u(0).u(T).....u[(N-1)T1)T

T—T E U - ZXTW

T _ -— T
x (NT)x(NT) - U ENwN—N o NENU + xo‘nyo
T 2 T T
x (NT)x(NT) - R — £(U) — U QNU - ngU + 9N
(5.2.4)
9 - (c )Tc (5.2 5)
N N,0 N,0 '
Q = fiTw F’ (5.2.6)
-N —N N—N
T T —
EN = XOWNEN (5.2.7)
_ T _ 2
EN — XOWNXO R (5.2.8)

205

Equations (5.2.3)-(5.2.8) are similar to equations (3.2.11),
(3.2.14), (3.2.7), (3.2.10), (3.2.12) and (3.2.13). The
only significant difference is that E& replaces Eh in the
time-invariant system. Thus the steps used in solving the
optimal control problem for the time varying system are
the same as those given in Chapter III. The two assumptions
given in Section 3.1 for the time-invariant system are
replaced by the following assumptions.

(i) It is assumed that

rank (Efi) = rank (D1,Cl 2D2""’Cl nDn) = n
I I

(ii) It is assumed that

rank(Dl,C = maximum for

1,2D2'°°"C1,NDN)
all N > O

Assumption (i) is the same as the assumption of
complete controllability of a time varying system [SORl].
With these assumptions the optimal control problem for the
time varying system reduces to replacing C by Ck,k-l and
D by Dk in the time-invariant system of Chapter III.

With regard to the problem of Chapter IV (hyper-
rectangular target set), no assumptions of controllability
were made. In this case we can substitute Ck,k-l for C
and Dk for D, and all the results given in Chapter IV can

be used.
N-l T

(2) Cost functional of the form J = 2 u (iT)Su(iT) where
i=0

S is positive definite and symmetric.

206

Section 3.3 was concerned with minimizing the total
energy required to reach the boundary of the hyperspherical
target set. In some case it may be desirable to assign a
heavier cost to certain components of u(kT). One possible
way to do this is to express the cost in the form given by
J above. To solve this problem it is noted by Theorem 2.1.9
that S is positive definite if and only if there exists a

nonsingular matrix L such that s = LTL. Therefore,

N-l T
J = Z Y (kT)y(kT) (5.2.9)
k=0
where y(kT) = Lu(kT). We can rewrite the state equation
(5.2.1) as
Y[(k+l)T] = Cy(kT) + D'y(kT) (5.2.10)
where D' = DL-l. We then have the problem of minimizing J

given by equation (5.2.9) subject to equation (5.2.10).

This is the same type of problem as that solved in Section

3.3 except that D' replaces D, and y(kT) replaces u(kT).

Once y(kT) is determined, we can find u(kT) by the equation

u(kT) = L'1y(kT).

(3) Minimum Energy Solution for Hyperrectangular Target Set.
In Chapter IV it was shown that minimization of the

fuel when the solution to the time-optimal control problem

was not unique led to a linear programming problem. In

equation (4.3.3) we let

ui (kT) = ui p(kT) - ui

I

q(kT) i=l,2,...,n k=0,l,...,N-1

I

207

If we wish to minimize the energy, the performance index

could be taken to be

N-l m
J = X Z ui(kT)ui(kT)
k=0 i=1
N-l m
= Z Z . kT - . . - . kT
k-O i=1[u1.p( ) ul-qu‘Tfl Ell-pun) u1.<1( )]
N-l m 1 -l ui'p(kT)

 

= z 2 EL (kT)u. (kTfl (5.2.11)
k=0 i=1 1'9 1'q -1 1 ui q(kT)

The performance index given by equation (5.2.11) and the
inequality constraints given by (4.3.4)-(4.3.5) represent
a well-formulated quadratic programming problem; the
method of sOlution of which is well-known [B001], [CANl],
[GUEl].
(4) Moving target Set

It was assumed in Chapter III that the target re-
mained centered at the origin. The modification for a
moving target set is straight forward. Let the target set
be described by
{x(NT): (x(NT) - xC(NT))T(x(NT) - xc(NT)) 6 R2}
Then by the same argument that was used to obtain equation.

(3.2.8), we have

T

(x(NT) - xC(NT))T(x(NT) - xC(NT)) = UTQNU - 2(dN

T N T T N
+ xC(NT)C Ffi)U + xo‘i’NxO 2xC(NT)C x0

+ XZ(NT)XC(NT)

208

where QN, Efi and dN are defined by equations (3.2.10)-

. T_T T N— =
(3.2.12). By letting 9N - dN + xc(NT)C FN and EN

xTW x - 2xg(NT)CNx + xg(NT)xc(NT) and restricting the

o N o 0

problem to finding the minimum number of samples to reach
the boundary of the target, we have
2

, z _ T _ _ _ T
f (U)_(x(NT) xC(NT)) (x(NT) xc(NT)) R - U QNU

T _
- ZQNU + EN - 0 (5.2.12)
Equations (5.2.12) is similar to equation (3.2.14) except
We can then repeat

that 9N replaces dN and g replaces e

N N'
the same arguments and derive theorems analogous to those
of Section 3.2 after replacing dN by dN and EN by eN. The
same type of argument can be applied to the problem con-

sidered in Chapter IV.

 

REFERENCES

[AOKl]

[ATHl]

[AYRl]

[BERl]

[B001]

[CADl]

[CAD2]

[CAD3]

[CANl]

[CULl]

[DERl]

REFERENCES

M. Aoki, Optimization of Stochastic Systems,
Academic Press, New YoEk} .

 

M. Athans, P. Falb, O timal Control, An Introduc-
tion to the Theory ang Its AppIications, McGraw-
HTII’EEoE Company, New York, 1966.

 

F. Ayres, Theory and Problems of Matrices, Schaum
Publishing Co., New York, I962.

J. Bertram, P. Sarachik, "On Optimal Computer
Control", Proc. First International Congress of
Automatic Control, Butterworth, pp. 419-422, 1960.

J. C. Boot, Quadratic Programming, North-Holland
Publishing Co., Amsterdam, 1964?

 

J. A. Cadzow, H. R. Martens, Discrete-Time and
Com uter Control S stems, Prentice-HaII Inc.,
EngTewood CIiffs, New ersey, 1970.

J. A. Cadzow, "An Extension of the Minimum Norm
Controller for Discrete Systems", IEEE Trans. on
Automatic Control, Vol. AC-12, No. 2, pp. 202-203,
April, 1967.

J. A. Cadzow, "Nilpotency Property of the Discrete
Regulator", IEEE Trans. on Automatic Control,
pp. 734-735, December, 1968.

M. D. Canon, J. H. Eaton, "A New Algorithm for a
Class of Quadratic Programming Problems with
Application to Control", J. SIAM Control, Vol. 4,
No. 1, pp. 34-45, 1966.

C. Cullen, Matrices and Linear Transformations,
Addison-wesIey PfiBIisfiing Co., Reading,
Massachusetts, 1966.

P. Derusso, J. Rob, C. Close, State Variables for
Engineers, John Wiley & Sons, Inc., New York, 1967.

 

209

 

[DESl]

[DEUl]

[DEUZ]

[FARl]

[FEGl]

[FRAl]

[FRA2]

[GANl]

[GRAl]

[GREl]

[GREZ]

[GUEl]

[HADl]

210

C. A. Desoer, J. Wing, "The Minimal Time Regulator
Problem for Linear Sampled-Data Systems: General
Theory", J. Franklin Inst., Vol. 272, No. 9,

pp. 208-228, 1961.

R. Deutsch, S stem Anal sis Techni ues, Prentice-
Hall, Inc., Eng ewood CTlfTS, New ersey, 1969.

R. Deutsch, Estimation Theory, Prentice-Hall, Inc.,
Englewood Cliffs, New Jersey, 1965.

 

J. B. Farison, F. Fu, "The Matrix Properties of
Minimum-Time Discrete Linear Regulator Control",
IEEE Trans. on Automatic Control, pp. 390-391,
June, 1970.

K. A. Fegley, M. I. Hsu, "Optimum Discrete Control
by Linear Programming", IEEE Trans. Auto. Control,
Vol. AC-10, No. 1, pp. 114-115, January, 1965.

J. S. Frame, "Matrix Functions and Applications",
IEEE Spectrum, pp. 208-220, 102-108, 100-109,
123-131, March-July, 1964.

J. S. Frame, Matrix Theory and Linear Algebra with
Applications", (Mathematics 831 Class Notes),
Department of Mathematics, Michigan State Univer-
sity.

F. R. Gantmacher, The Theory of Matrices, Chelsea
Publishing Co., Vol. 1, New York, 1960.

J. J. Grainger, K. G. Pandy, "Time-Optimal Control
of Sampled-Data Systems", Proc. of IEEE, pp. 1295-
1297, August, 1970.

T. Greville, "The Pseudoinverse of a Rectangular
or Singular Matrix and its Applications to the
Solution of Systems of Linear Equations", SIAM
Review, Vol. 1, No. 1, pp. 38-43, January, 1959.

T. Greville, "Some Applications of the Pseudoin-
verse of a Matrix", SIAM Review, Vol. 2, No. 1,
pp. 15-22, January, 1960.

R. L. Gue, M. E. Thomas, Mathematical Methods in
Operations Research, The Macmillan Company, fofidon,
I968.

 

G. Hadley, Linear Programming, Addison-Wesley Pub-
lishing Co., Inc., Reading, Massachusetts, 1962.

 

[HILl]

[H01]

[IBMl]

[JAMl]

[KALl]

[KALZ]

[KOE1]

[KOP1]

[KU01]

[KU02]

[KURl]

[PEDl]

211

 

F. B. Hilderbrand, Methods 9: Applied Mathematics,
Prentice-Hall, Inc., Englewood Cliffs, New Jersey,
1965.

Y. C. Ho, "Solution Space Approach to Optimal
Control Problems", Trans. ASME, Vol. 83, pp.
March, 1961.

53-58,

IBM Application Program, 1130 Scientific Sub-
routine Package (1130-CM-02X), Programmer's Manual,
International Business Machine Corp., White Plains,
New York, 1968.

M. James, G. Smith, J. Wolford, A lied Numerical
Methods for Digital Computation_ witH FORTRAN,
Internationa Textbook Company, Scranton,
Pennsylvania, 1967.

R. E. Kalman, "Optimal Non-Linear Control of
Saturating Servo-Mechanisms by Intermittent
Action", IRE Wescon Record, Part 4, pp. 130-135,

.1957.

R. E. Kalman, "On the General Theory of Control
Systems", Proc. First International Congress of
Automatic Control, pp. 481-492, Moscow, 1960.

H. E. Koenig, Y. Tokad, H. K. Kesavan, Maly51s
of Discrete Physical Systems, McGraw-Hi Boo

Company, New York, 1967.

 

"On the Control of Linear Systems
J. Basic Engineering,

R. W. Koepcke,
with Pure Time-Delay",

S. S. Kuo, Numerical Methods and Computers,
Addison-Wesley Publishing Co., Reading, Mass-
achusetts, 1965.

 

 

 

B. C. Kuo, Discrete-Data Control Systems, Prentice-
Hall, Inc., Englewood Cliffs, New Jersey, 1970.

F. Kurzweil, "The Control of Multivariable
Processes in the Presence of Pure Transport
Delays', IEEE Trans. on Automatic Control, Vol.
AC-8, pp. 27-34, January, 1963.

D. Pedoe, IX Geometric Introduction 22 Linear
Algebra, John Wiley & Sons, Inc., New YorE, I963.

[PENl]

[PLAl]

[PLAZ]

[RALl]

[SARl]

[SORl]

[TORl]

[TOUl]

[TOU2]

[TOU3]

[TUEl]

[ZADl]

[ZAD2]

212

R. Penrose, "A Generalized Inverse of Matrices",
Proc. Cambridge Philos. Soc., Vol. 51, pp. 406-413,
1955.

J. B. Plant, M. Athans, "An Iterative Technique
for the Computation of Time Optimal Controls",
Paper 13D, IFAC Congress, London, 1966.

J. B. Plant, "An Iterative Procedure for the
Computation of Fixed-Time Fuel-Optimal Controls",
IEEE Trans. on Automatic Control, Vol. AC-11,

No. 4, pp. 652-660, October, 1966.

A. Ralston, H. Wilf, Mathematical Methods for
Digital Computers, Chpt. 7, John WiIey & Sons,
New York, 1962.

 

P. E. Sarachik, G. M. Kranc, "Optimal Control of
Discrete Systems with Constrained Inputs", J.
Franklin Institute, Vol. 277, No. 3, pp. 237-255,
March, 1964.

H. W. Sorenson, "Controllability and Observability
of Linear, Stochastic, Time-Discrete Control

Systems", Advances in Control Systems, Vol. 6,
pp. 95-158, I968. _—

H. C. Torng, "Optimization of Discrete Control
Systems Through Linear Programming", J. Franklin
Institute, vo1. 278, No. 1, pp. 28-44, July, 1964.

J. T. Tou, "Synthesis of Discrete Systems Subject
to Control-Signal Saturation", J. Franklin Insti-
tute, Vol. 277, No. 5, pp. 401-413, May, 1964.

J. T. Tou, O timal Design of Di ital Control
Systems, Aca emic Press, NEW YorE, I963.

J. T. Tou, Modern Control Theory, McGraw-Hill Co.,
New York, 1964.

W. G. Tuel, Jr., "Comments on 'The Matrix Proper-
ties of Minimum-Time Discrete Linear Regulator
Control'", IEEE Trans. on Automatic Control,

Vol. AC-l6, No. l, p. 105, February, 1971.

L. Zadeh, C. Desoer, Linear S stem Theory, McGraw-
Hill Book Co., Inc., New York, I963.
L. Zadeh, B. H. Whalen, "On Optimal Control and
Linear Programming", IRE Trans. Automatric Control,
Vol. AC-7, pp. 45-46, 1962.

 

APPENDIX

213

APPENDIX

In this appendix the conversion from continuous to
discrete-time systems is given for a system with white
noise input.

Let the system be described by the following
equations

x = A(t)x + B(t)u + v(t) (1)

x(0) = x0

E(v(t)) = 0
E(v(s)vT(T)) = R6(s - T)

where 0(t) is the dirac delta function. With @(t,r) as

the transition matrix, the solution of (l) is

t t
x(t) = ©(t,to)x(to) +J/;(t,T)B(T)u(T)dT +J/;(t,T)V(T)dT
to to
(2)
Setting t = tk+1 and to = tk, equation (2) becomes
' tk+1
x(tk+l) = ¢(tk+l,tk)x(tk) + ©(tk+l,T)B(T)u(T)dT
t tk
k+1
tJ/;(tk+l-T)V(T)dT (3)

tk

214

Since it is assumed that the system is of the sampled-data

type, u(1) = u(tk) for tk s T < tk+l° Equation (3) then

becomes
xk+1 = ¢kxk + Dkuk + wk k=0,l,...,N-1 (4)
where
xk = x(tk) and ¢k = @(tk+1,tk)
tk+1 tk+1
Dk =fi(tk+l,T)B(T)dT wk =fi(tk+l,1)v(r)d1
tk tk
Also, t
tk+1 3+1
E(w wT) = <I>(tk T)V(T)dT VT(y)¢T(t y)dy
k j +1' j+1'
tk tj
tk+1 tj+1
_ _ T
._ ./F u/g(tk+1,r)R-S(r v)9 (tj+1-Y)deY
tk tj
tk+1
_ T
— @(tk+1,T)R¢ (tk+l,T)dT0k,j
tk

Therefore,

T —
E(wkwj) — Qk6k,j (5)

 

215

where
tk+1
Qk =J/;(tk+l T)R¢T(t -)d- 6 if k=j
' k+l' k,j=
tk 0 if k#j
and
E(wk) = 0 (6)

Equations (4), (5) and (6) represent the sampled-data system
corresponding to the continuous time system given in (1).

If A(t) = A and B(t) = B, then 4k and Dk also become con-

stants, that is, @k = C and Dk = D. Equation (4) then

becomes

xk+1 = ka + Duk + wk