Japan Advanced Institute of Science and Technology
JAIST Repository
https://dspace.jaist.ac.jp/
Title Numerical Methods for Solving Optimal Control Problems UsingChebyshev Polynomials
Author(s) Hussein, M, Jaddu Citation
Issue Date 1998‑09
Type Thesis or Dissertation Text version author
URL http://hdl.handle.net/10119/868 Rights
Description Supervisor:Milan Vlach, 情報科学研究科, 博士
Control Problems Using Chebyshev
Polynomials
by
Hussein M. JADDU
submitted to
JapanAdvancedInstitute ofScienceand Technology
inpartial fulllment of therequirements
forthedegree of
Doctorof Philosophy
Supervisor : Professor Milan Vlach
School of Information Science
Japan Advanced Institute of Science and Technology
September 1998
Copyright1998
by
Hussein Jaddu
Abstract
Many computational metho ds havebeen prop osed tosolveoptimalcontrol problems.
Thesemethodsareclassiedasindirectmethodsanddirectmethods. Thisthesisisbased
on solving optimal control problems using direct methods in which an optimal control
problem is converted into a mathematical programming problem. The direct methods
can b e employed by using the parameterization technique which can be applied in three
dierent ways: Control parameterization, control-state parameterization and state pa-
rameterization. Thecontrolparameterizationandthecontrol-stateparameterizationhave
been used extensivelytosolvegeneral optimalcontrolproblems. However,the use of the
state parameterization was limited to very special cases. In this thesis, wesolve general
optimal controlproblems by using the state parameterization.
This thesis presents numerical metho ds to solve unconstrained and constrained op-
timal control problems. The solution method is based on using the second method of
the quasilinearization to replace the nonlinear optimal controlproblem by a sequence of
time-varyinglinear quadraticoptimalcontrol problems. Eachof theseproblems is solved
by converting it into quadratic programming problem. To this end, the state parame-
terization technique is employedbyusing the Chebyshev p olynomialsof the rst typ e to
approximate the system state variables by a nite length Chebyshev series of unknown
parameters.
In addition, in this thesis we describe a method to determine the optimal feedback
control of nonlinear optimalcontrol problems. The metho d isbased onapplying the pa-
rameterizationusingChebyshevp olynomials. Tofacilitatethecomputationoftheoptimal
feedback control law,anew property ofChebyshevp olynomials calleddierentiationop-
erational matrix is derived.
The proposed methods have b een applied on several examples and we nd that the
proposed methodsgivebetter orcomparableresultscompared with someother metho ds.
Additionally,tomakesure thatthe prop osedmethodscanhandlerealcomplexproblems,
we applied these metho ds on two practical problems, F8 ghter aircraft and container
crane problems.
Acknowledgments
I would like to express my deep gratitude to my principle advisor Professor Etsujiro
Shimemura of Japan Advanced Institute of Science and Technology for his invaluable
guidance, many discussions and continuous encouragement during my PhD studies. I
am grateful for Prof. Shimemura's help, support, encouragementduring my rst daysin
JAIST.His help and encouragement are unforgettable.
I spentwith Professor Shimemura twoand halfyears since I started my PhD course.
Butduringthe last sixmonthsofmystudies,ProfessorShimemurabecome thepresident
of Japan Advanced Institute of Science and Technology. Due to this situation I spent
the last six months under the sup ervision of Professor Milan Vlach of Japan Advanced
Institute of Scienceand Technology.
I would like to thank Prof. Vlach for many invaluable commentsand suggestions on
my thesis. His commentsallowme toimprovemythesis signicantly.
Also I wouldlike to thank my advisor Associate Professor Masayuki Fujita of Japan
Advanced Institute of Science and Technology for his help and many discussions. Prof.
Fujitahas accepted me inthe rst place inJAIST and intro ducedme to optimalcontrol
and robotics.
I would like to thank Professor Shintaro Ishijima of Tokyo Metropolitan Institute of
Technology, Asso ciate Professor Taketoshi Yoshidaand Associate Professor HajimeIshi-
haraof JapanAdvancedInstituteof ScienceandTechnologyfortheirreview ofmythesis
and for their invaluable comments.
Manythankstomyfriendsand colleaguesofShimemura-Fujitalaboratoryformaking
my stay at JAIST a wonderful experience. In particular I would like to thank Dr. H.
MochiyamaandR.SuzukiformanytranslationsfromJapanesetoEnglishandviceversa.
I am gratefully acknowledgethe nancial supp ort of JapaneseMinistry of Education,
Science, Sports and Culture (MONBUSHO).
and encouragement.
My sincere thanks goes to my wife Siham,for her supp ort and encouragement. Also
I would like to thank my children Hiba, Haithem and Haifa for allowing me to spend so
muchtimeatscho ol. Hibaalwaysusedtosaytome\Otoosan,benkyouowattaraburanko
iku'.
Abstract ii
Acknowledgments iii
1 Intro duction 1
1.1 Motivationsand Goals : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 1
1.2 Thesis Contribution : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3
1.3 Thesis Organization : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 5
2 Optimal Control Problem: A Review 7
2.1 Intro duction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 7
2.2 Statement of the Optimal Control Problem : : : : : : : : : : : : : : : : : : 8
2.3 Dynamic Programming: : : : : : : : : : : : : : : : : : : : : : : : : : : : : 9
2.4 Necessary Conditions ofOptimality : : : : : : : : : : : : : : : : : : : : : : 10
2.4.1 Euler-LagrangeEquations : : : : : : : : : : : : : : : : : : : : : : : 10
2.4.2 Pontryagin Minimum Principle : : : : : : : : : : : : : : : : : : : : 13
2.5 Indirect methods : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 15
2.5.1 ClosedLoopControl Methods : : : : : : : : : : : : : : : : : : : : : 15
2.5.2 OpenLoop Control Metho ds: : : : : : : : : : : : : : : : : : : : : : 16
2.6 Direct Methods : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 16
2.6.1 Discretization Methods : : : : : : : : : : : : : : : : : : : : : : : : : 17
2.6.2 Parameterization Metho ds : : : : : : : : : : : : : : : : : : : : : : : 18
3 Linear Optimal Control Problem 23
3.1 Intro duction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23
3.2 Problem Statement : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 24
3.3 State Parameterization Using ChebyshevPolynomials : : : : : : : : : : : 25
3.3.1 Chebyshev Polynomials: : : : : : : : : : : : : : : : : : : : : : : : : 25
3.3.2 StateParameterization : : : : : : : : : : : : : : : : : : : : : : : : : 26
3.4 WhichState Variablesto Parameterize? : : : : : : : : : : : : : : : : : : : 28
3.5 Problem Reformulation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 30
3.6 Computational Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 35
3.7 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 40
4 Nonlinear Optimal Control Problem 41
4.1 Intro duction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 41
4.2 ProblemStatement : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42
4.3 Quasilinearization : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 42
4.4 ProblemReformulation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 44
4.5 Computational Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 50
4.6 PracticalApplication : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 51
4.7 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 57
5 Constrained Linear Quadratic Optimal Control Problem 60
5.1 Intro duction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 60
5.2 ProblemStatement : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 61
5.3 State ParameterizationUsing Chebyshev Polynomials : : : : : : : : : : : : 62
5.4 Optimal ControlProblem Reformulation : : : : : : : : : : : : : : : : : : : 63
5.5 Computational Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 66
5.6 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 68
6 Constrained Nonlinear Optimal Control Problem 70
6.1 Intro duction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 70
6.2 ProblemStatement : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 72
6.3 Proposed Method : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 73
6.3.1 Quasilinearization : : : : : : : : : : : : : : : : : : : : : : : : : : : 73
6.3.2 State Parameterization : : : : : : : : : : : : : : : : : : : : : : : : 74
6.4 Computational Results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 77
6.5 PracticalApplication : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 81
6.6 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 83
7 Construction of Optimal Feedback Control 86
7.1 Intro duction : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86
7.2 Dierentiation Op erational Matrix : : : : : : : : : : : : : : : : : : : : : : 87
7.3 Solution of Nonlinear Optimal ControlProblem : : : : : : : : : : : : : : : 89
7.4 Determination of Optimal FeedbackGain : : : : : : : : : : : : : : : : : : : 90
7.5 Computational results : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 96
7.6 Conclusion : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 99
8 Conclusions and Future Work 102
8.1 Conclusions : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 102
Bibliography 104
Publications 111
Introduction
1.1 Motivations and Goals
The optimal control problem is to nd a control function u 3
(t) which minimizes a
givencostfunctional(performance index)whilesatisfying thesystem stateequationsand
constraints. It has successful applications in many disciplines, economics, environment,
management,engineeringetc. Aparticularimportantclass ofoptimalcontrolproblemsis
thelinear quadraticoptimalcontrolproblem, whichhas found awide acceptancebecause
of the p ossibility of obtaining the feedback optimalcontrol law.
Generally,thesolutionsof optimalcontrolproblems, exceptforthe simplestcases, are
usuallycarriedout numerically. Therefore,numericalmethodsandalgorithms forsolving
optimalcontrolproblemshaveevolvedsignicantlyoverthepastthirty-veyears. Mostof
theearlymethodswerebasedonndingasolutionthateithersatisestheEuler-Lagrange
equations,whichare the necessary conditions of optimality, orsatises Hamilton-Jacobi-
Bellman equation, which is sucient condition of the optimality. These methods are
called indirectmetho ds.
The main drawbacks of the indirectmethodsare the following: (1) It is verydicult
to solve Hamilton-Jacobi-Bellman equation. (2) The introduction of articial costates.
(3) The lack of robustness, i.e. the iterations muststart close to alocal solution inorder
to solve the two-p oint boundary value problem. (4) The user must have a deep insight
intothe physicaland the mathematical natureof the optimalcontrolproblem.
To overcomethese drawbacks,many researchersproposed the use of the directmeth-
ods to solve the optimal control problems. In these metho ds, the optimal solution is
obtained by direct minimization of the performance index subject to constraints. This
can be achieved by approximating the dynamic optimal control problem by a nite di-
mensional nonlinear programming problem. The direct methodscan beapplied by using
the discretizationtechniqueorthe parameterizationtechnique (controlparameterization;
control-state parameterization;stateparameterization). Inthis thesis,we usethe param-
eterizationtechnique(stateparameterization)toconverttheoptimalcontrolprobleminto
mathematical programming problem.
Forthe parameterizationmethod,therearetwoissuestobeaddressed. The rstissue
is: Whichvariables(state,control)shouldbeparameterized? Thesecondissue is: Which
functions can be used to perform the parameterization?
Concerning the rst issue, a tremendous proliferation of papers have been published
which are based on either control parameterization or control-state parameterization.
These two approaches have some drawbacks such as: In control parameterization case,
there isaneed tointegrate the systemstate equationswhichisacomputationally expen-
sive. Whileincontrol-stateparameterizationcase,theoptimalcontrolproblem isreduced
to a large mathematical programming problem, i.e. has a large numb er of unknown pa-
rameters and alarge numb erof equality constraints.
There is a third typ e of parameterization, the state parameterization. Sofar the use
of this approach has been limited to special cases. For example, linear systems of equal
numb erofstate variablesandcontrolvariablesornonlinear systemsof asingleinputand
in controllability canonical form. This approach, in spite of some advantages that can
oer,has notb eennotusedextensivelybecauseitisdiculttoapplyittogeneraloptimal
controlproblems. Thisisbecauseitisnotclearwhichstatevariablestobeparameterized
in case of unequal numb er of state variables and control variables. Therefore the rst
goalof thisthesis istoapply the stateparameterizationtogeneraloptimalcontrol prob-
lems, linear and nonlinear, constrained and unconstrained.
Forthe secondissue,manyfunctionstoperformtheparameterizationhavebeen used.
In particular, the orthogonal functions used to solve some of the optimal control prob-
lems. Among the orthogonal functions, Chebyshev p olynomials have several advantages
compared with other functions. The Chebyshev polynomials have been used, in several
papers, to solve linear quadratic optimalcontrol problems. Also Vlassenbro eck and Van
Dooren [39,40] applied the Chebyshev polynomials to solve general unconstrained non-
linear optimal control problem and constrainedoptimal controlproblem. However,their
method has several disadvantages and drawbacks which will be discussed in the next
chapter. Hence the second goal of this thesis is to use the Chebyshev polynomials to
parameterize the system state variables to solve linear and nonlinear, constrained and
unconstrained optimalcontrol problems, and on the same time to avoid the problems of
Inapplyingthedirectmethods,mostoftheresearchers,convertthenonlinear optimal
control problem into a nonlinear mathematical programming problem and then the new
problem issolvedbyusing sequentialquadratic programming method. Thereare twoex-
ceptions: The workby Bashen and Inns[55] whichconverts the optimal control problem
into a sequence of quadratic programming problems. However,this method was applied
to a particular problem and the discretization method was used. Another approach was
proposed by Maand Levine [57]. In this case an upper bound of the optimal value only
wasobtainedand thediscretizationmethodwasalsoused. Thethird goal ofthis thesis
is to solve the optimal control problem by converting it directly, using state parameteri-
zation via Chebyshev p olynomials, into a sequence of quadratic programming problems.
This hastwoadvantages: the rstadvantageisthat the linearand the nonlinear optimal
control problems can b e solved in uniform way. The second advantage is that guessing
nominaltrajectories,whichweneedtoconvertthenonlinearoptimalcontrolprobleminto
a sequence of linear quadratic optimal control problems, is easier than guessing the pa-
rametersofthesetrajectories,whichweneedinordertosolvethe nonlinearmathematical
programming problem.
The direct methods were used to obtain open loop solution of optimal control prob-
lems. Butfrompracticalp ointofview,itisdesiredtoobtainthefeedbackoptimalcontrol
solutionsb ecause theyproviderobustness with respect to external disturbances,unmod-
eled dynamics and variations in the physical parameters of the system to be controlled.
Obtainingtheoptimalfeedbackcontrolofthenonlinearoptimalcontrolproblemsbyusing
the direct metho d, state parameterization,is the fourth goal of this thesis.
In summarythe goalsof this thesis are: Toprop ose anecientnumericalmethodsto
solve linear and nonlinear, constrained and unconstrained optimal control problems and
todetermine the optimal feedback control law.
1.2 Thesis Contribution
Inthisthesis,weproposenumericalmethodstosolveseveraloptimalcontrolproblems.
Thebasicidea ofthesemethodsistousethe secondmethodofthe quasilinearizationand
the stateparameterization. Thequasilinearization replacesthe nonlinear optimalcontrol
problem by a sequence of linear quadraticoptimal control problems. Then each of these
problems isapproximated by a quadraticprogramming problem, which can be solved by
parameterizing the state variablesbyChebyshev series ofunknown parameters.
The state parameterization has several advantages compared with other typ es of pa-
into a small mathematical programming problem, compared with control-state parame-
terization, inthesense ofthenumber ofunknown parametersandthe numb erof equality
constraints . The second advantage is that there is no need for numerical integration of
the system equations as in the case of control parameterization. The third advantage is
that the state constraintscan be approximated directlyand not as inthe control param-
eterization case.
The contribution of this thesis can b e summarized asfollows:
Presents a new method to solve the linear quadratic optimal control problem by
using state parameterization via Chebyshev p olynomials. This converts the linear
quadratic optimal control problem into a quadratic programming problem which
can besolved bymatrix-vector multiplication.
Derivesan explicit formulato approximate the quadratic performance index.
Describes numerical method to solve the nonlinear optimal control problem using
the quasilinearization and the state parameterizationvia Chebyshev polynomials.
Derivesa formula toperform Chebyshev series multiplications.
Presentsanumericalmethodtosolvethe nonlinearoptimalcontrolproblemsubject
to terminal state constraintsand control saturationconstraints.
Provides a numerical method to solve the linear quadratic optimal control prob-
lem subjecttostate and control constraints,terminalstate constraints and interior
pointsconstraints.
Intro duces and derives a new prop erty of Chebyshev p olynomials called dieren-
tiation operational matrix. This prop erty simplies the computations of optimal
feedback control law.
Derives an explicit formula to determine the optimal feedback control law. This
feedbackcontrollawhas someadvantagescomparedwiththepreviousknownmeth-
ods. The rst advantage is that the obtained optimal feedback control law can be
implementedeasier than the optimal feedback control obtained by using power se-
ries method. The second advantage is that we do not need to store the op en loop
optimal state and control trajectories as in the methods that give the neighb oring
optimal feedback control [3,19{22]. The third advantage is that the obtained op-
timal feedback control is a nonlinear one and, although it appears as a linear one,
1.3 Thesis Organization
The remaining chaptersof this thesis are organized asfollows:
Chapter 2 gives an overview of the optimal control theory, and reviews some com-
putational methods to solve optimal control problems. In this chapter, we classify the
computational methods into direct and indirect metho ds. The direct metho ds are, in
theirturn, also classiedintomethodsbased ondiscretizationand methodsbased onpa-
rameterization. Also the indirect metho ds are classied into methods that give anopen
loopsolutionand methodsthat giveaclosedloopsolution. Thischaptershowsthe place
of this thesis compared with other works.
Chapter 3 presents a numerical method to solve the linear quadratic optimal control
problem. Inthischapter,theconceptofthestateparameterizationusingChebyshevpoly-
nomials is intro duced. Also it describes the most appropriate way to perform the state
parameterization. This chapter also describ es a method of approximating the dynamic
optimalcontrolproblem intoa standardquadraticprogramming problem. In addition,it
showsthe derivation oftworesults: Therst resultis anexplicitformulatoapproximate
the quadratic performance index. The second result is the pro of that the Hessian of the
quadratic programming problem is positive denite. Finally, this chapter shows com-
putational results of a standard example and compares our results with those obtained
previously.
Chapter 4 generalizes the method of chapter 3 to solve the nonlinear optimal con-
trol problem and as a special case the time-varying linear optimal control problem. In
this chapterthe conceptof quasilinearization isintroduced. It also shows the reformula-
tion of the nonlinear optimalcontrol problem intoa sequence of quadratic programming
problems. A new resultis givenin this chapterwhichis aformulato compute the multi-
plication of twoChebyshev series. In addition to a standard example whichis solvedfor
the purposeof comparison, we present the computational results of a practical problem,
theautomaticightcontrolproblemasanapplicationofthischapterandthepreviousone.
Chapter 5 describes a numerical method, which is based onthe method describedin
chapter 3, to solve the constrained linear quadratic optimal control problem. The con-
straints which are considered in this chapter are: state and controlconstraints, terminal
state constraints and interior p oint constraints. It also shows the reformulation of the
constrainedoptimalcontrolproblem intoaquadratic programmingproblem. Moreoverit
showsthe computational results of a constrained optimalcontrol problem.
Chapter 6 presents a numerical method to solve the nonlinear optimal control prob-
lem subjecttoterminal stateconstraintsand controlsaturationconstraints. The dicult
constrained nonlinear optimal control problem is converted into a sequence of quadratic
programming problems. This method is applied on Van der Poloscillator problem sub-
ject to terminal state constraints and controlsaturation constraints. In addition, in this
chapter, we show the simulation results of a high dimension practical nonlinear optimal
control problem subject to terminal state constraints,control saturation constraintsand
state constraints.
Chapter 7 describ es a new method to determine the optimal feedback control law of
nonlinearoptimalcontrolproblems. AnewpropertyofChebyshevpolynomialsisderived.
This property,dierentiationop erational matrix prop erty,simplies the computations of
the optimal feedback control law. Also this chapter presents an explicit formula to de-
terminethefeedbackgainmatrix. Computationalresultsofanexamplearealsopresented.
Chapter8containstheconclusionsofthisthesisandrecommendationsforfuturework.
Optimal Control Problem: A
Review
2.1 Introduction
The optimalcontrol problem has been treatedin depth in many textbo oks [1{7] and
insomeimportantsurveypapers[8{10]. Theobjectiveofoptimalcontrol istodetermine
an optimal open loop control u 3
(t) or an optimal feedback control u 3
(x;t) that forces
the system tosatisfy the system physicalconstraintsand at the same time minimizes or
maximizesa p erformance index.
The basic optimal control problem consists of the followingthree elements:
1. A mathematical model of the system to be controlled: The dynamical system to
be controlled can be described by state equations which are a set of rst order
dierential equations
_
x=f(x(t);u(t);t) (2:1)
wherex(t)2R n
isthestatevector,u(t)2 R m
isthecontrolvector,fiscontinuously
dierentiablewithrespecttoallitsarguments. Thecontrolfunctionsuare assumed
tobethepiecewise continuousfunctionsfromt2[0;t
f
]intoR m
. LetU bethe class
of suchcontrolfunctions.
2. A set of boundary conditions on the state variables which gives the value of the
system states atthe initialtime
x(t
0 )=x
0
(2:2)
wherex
0
is a known vector of initial conditions.
3. A performance index which is to be minimized (maximized). The performance
index describes some desired specications, expressed mathematically in form of a
scalarfunction. Theoptimalcontrol problemhelpsthe designertoselectthe\best"
control, by minimizing a given p erformance index. The performance index which
we are interestedincan be expressedas
J =(x(t
f );t
f )+
Z
t
f
t
0
L(x(t);u(t);t)dt (2:3)
where and L are scalar functions, continuously dierentiable in all arguments.
The terminal cost (x(t
f );t
f
) and the \loss" function L(x(t);u(t);t) are selected
dependingontheperformanceobjectives. Thesefunctionsaregenerallynonnegative
functions of x and u, with(0;t
f
)=0 and L(0;0;t)=0.
2.2 Statement of the Optimal Control Problem
The unconstrained optimalcontrol problem can be stated asfollows:
Given f, x
0 , t
0 , t
f
, and L, nd an optimal open loop control or an optimal feedback
control that minimizes the p erformance index
J =(x(t
f );t
f )+
Z
t
f
t
0
L(x(t);u(t);t)dt (2:4)
subjectto the system state equations and the initial conditions
_
x=f(x(t);u(t);t) x(t
0 )=x
0
(2:5)
This problem, basically,can b e solvedby one of the following methods:
Bellman's dynamic programming method which is based on the principle of opti-
mality (Hamilton-Jacobi-Bellman equation).
Variational method and Pontryagin's minimum principle (Euler-Lagrange equa-
tions).
Direct methods using discretization or parameterization (nonlinear mathematical
programming)
These methods will briey be discussedin the followingsections.
In general it is not possible to solve the problem (2.4)-(2.5) analytically. However,
an analytical solution is possible for a special case of this problem, the linear quadratic
optimalcontrolproblem,inwhichtheperformanceindexisquadraticandthesystemstate
equationsarelinear. Thisproblemcanbestatedasfollows: Findtheoptimalcontrolthat
minimizes
J =x T
(t
f )Sx(t
f )+
Z
t
f
t0 (x
T
Qx+u T
Ru)dt (2:6)
subject to
_
x=A(t)x+B(t)u x(t
0 )=x
0
(2:7)
whereS,Qare p ositivesemidenitematrices andR isapositivedenitematrix. Forthis
problem the solution can be expressedin feedback form
u 3
(x;t)=0R 01
B T
(t)P(t)x (2:8)
where P(t) is the solution ofRiccati equation.
2.3 Dynamic Programming:
Hamilton-Jacobi-Bellman Equation
The useofthe principleof optimality,usually knownasdynamicprogramming, tode-
rive an equationfor solving optimalcontrol problem was rst proposed by Bellman [11].
The application of this principle on continuous optimal control problem has led to the
invention of the famous Hamilton-Jacobi-Bellman(HJB) equation. It is a nonlinear rst
orderhyp erbolicpartialdierentialequationwhichisusedforconstructinganonlinearop-
timalfeedbackcontrollaw. Fortheoptimalcontrolproblem(2.4)-(2.5),theHJBequation
isgivenby
@J 3
(x(t);t)
@t
=0min
u(t)
fL(x(t);u(t);t)+
@J 3
(x(t);t)
@x T
f(x(t);u(t);t)g (2:9)
and the b oundary condition is
J 3
(x(t
f );t
f
)=(x(t
f );t
f
) (2:10)
To obtain a solution to equation (2.9), we proceed in two steps. The rst step is to
perform the indicated minimization. This leads toa control lawof the form
u 3
= (
@J 3
@x
;x;t): (2:11)
The secondstep istosubstitute(2.11) backinto(2.9) andsolvethe nonlinear,partial
dierential equation
0
@J 3
(x;t)
@t
=L(x; ;t)+
@J 3
(x;t)
@x T
f(x; ;t) (2:12)
for J 3
(x;t),subjectto the boundary condition (2.10). Then the gradientof J 3
(x;t) with
respect tox is computed, and the optimalfeedback controllaw is obtained
u 3
= (
@J 3
;x;t)=8(x;t) (2:13)
The derivation of HJB equation can b e found in any standard optimal control text-
bo ok, seefor example [2,4{6]. This equation isa sucient condition for optimality. The
HJB equation is satised for all time-state pairs (x(t);t) by the optimal value function
J 3
(x(t);t), i.e. if the system starts in state x(t) at time t, the minimum value of the
performance index is J 3
(x(t);t).
AnadvantageofusingtheHJBapproachtosolvetheoptimalcontrolproblem,isthat
weobtainoptimal feedback control law. However,the HJBequationdoesnot ingeneral,
possessclassicalsolution, thatis,solutionsJ 3
(x(t);t)whicharedierentiablewithresp ect
to t and x. In recent years, a new notion of solution, called the viscosity solution, has
been intro duced. For more details of this approach, the reader can consult Ahmed [13]
and the relevantreferences cited therein.
In general it is not possible to solve (2.12) analytically. However, in the case of
linearquadraticoptimalcontrolproblem (2.6)-(2.7),theHJBequationreducestoRiccati
dierential equation, which is givenby
0 _
P(t) = A T
(t)P(t)+P(t)A(t)+Q0P(t)B(t)R 01
B T
(t)P(t) (2.14)
P(t
f
) = S (2.15)
Thisresult canb eobtainedif thevalueJ 3
=x T
P(t)xissubstitutedintheHJBequation.
2.4 Necessary Conditions of Optimality
2.4.1 Euler-Lagrange Equations
The necessary conditions can be derived by the methods of Calculus of Variations
whichare based onthe factthat, ateachstationarypoint,the variationinthe cost func-
tion should vanish for arbitrary variation inthe control [3].
To solve the optimal control problem (2.4)-(2.5), we shall use Lagrange multipliers
(t) 2 R n
to adjoin the system state equations (2.5), to the performance index (2.4).
Therefore, the augmented performance index is given by,
J
A
=(x(t
f );t
f )+
Z
t
f
t
0
[L(x(t);u(t);t)+(t) T
(f(x(t);u(t);t)0x)]dt_ (2:16)
Intro ducing the Hamiltonian function H denedby
H(x(t);u(t);(t);t) =L(x(t);u(t);t)+ T
(t)f(x(t);u(t);t) (2:17)
wecan rewrite equation(2.16)in the form
J
A
=(x(t
f );t
f )+
Z
t
f
t0
H(x(t);u(t);(t);t)dt0 Z
t
f
t0 (t)
T
_
x(t)dt (2:18)
The integrationof the last term onthe right hand side byparts yields,
Z
t
f
t
0 (t)
T
_
x(t)dt=(t
f )
T
x(t
f
)0(t
0 )
T
x(t
0 )0
Z
t
f
t
0 _
(t) T
x(t)dt (2:19)
and therefore equation(2.18) becomes
J
A
=(x(t
f );t
f
)0(t
f )
T
x(t
f
)+(t
0 )
T
x(t
0 )+
Z
t
f
t0
[H(x(t);u(t);(t);t)+ _
(t) T
x(t)]dt
(2:20)
The originalproblem (2.4)-(2.5) has been convertedto the problem of minimizing(2.20)
withoutconstraints.
To achieve the stationarity, the rst order eect of control variations on the cost
function mustbezero for0 t t
f
. Assuming that the initialtime t
0
and nal time t
f
are xed, then the rst variationof J
A
due to control variation is
J
A
=
(
@
@x 0
T
)x
t=t
f +
T
xj
t=t
0 +
Z
tf
t0
@H
@u
u+(
@H
@x +
_
T
)x
dt (2:21)
Since (t) isarbitrary so far,wemay set itto be
_
T
(t)=0
@H
@x
=0
T
@f
@x 0
@L
@x
(2:22)
with boundary condition,
T
(t
f )=
@
@x j
t=t
f
(2:23)
equation (2.22) is called costate equation and the Lagrange multiplier (t) is called the
costate.
Since theinitial conditionx(t
0
)isxed, this impliesx(t
0
)vanishes. Therefore, equa-
tion ( 2.21)reduces to
J
A
= Z
t
f
t
0
@H
@u u
dt (2:24)
Foralo cal minimum,it isnecessarythat J
A
vanishesforarbitraryu,hence itisneces-
sarythat
@H
@u
=
@f
@u
T
+
@L
@u
T
=0 (2:25)
for allt
0
t t
f .
Equations (2.5), (2.22),(2.23) and (2.25) are necessary conditions to b e satised by
optimalsolutionsofthe problem, whenthe nal timeis xed. Theseequationsare called
the Euler-Lagrange equations.
In summary, to nd the optimal control u 3
(t) that minimizes the performance index
(2.4) subjectto the system equation (2.5), the following equations mustbe solved
_
x = f(x;u;t) (2.26)
x(t
0
) = x
0
(2.27)
_
= 0
@f
@x
T
0
@L
@x
T
(2.28)
(t
f ) =
@
@x
T
(2.29)
where u 3
(t) is determinedby:
@f
@u
T
+
@L
@u
T
=0 (2:30)
Thus,thesolutionoftheoptimalcontrolproblemisdeterminedbyatwo-p ointb ound-
aryvalueproblem,expressedbythestateequation(2.26)withthe initialcondition (2.27)
and the costateequation (2.28) with the nal condition (2.29).
Remarks:
(1) If L(x(t),u(t),t) and f(x(t),u(t),t) are not functions of time explicitly , then the
Hamiltonian is constant alongthe optimalpath.
(2) Inthecaseoffreeendtime,inwhichthenaltimecanbechosentofurtherminimize
the cost function, another necessary condition must be provided. This condition
can bederivedfromthe rstvariationof thecost functionwithrespect tothe time.
Hence the following necessary condition is obtained for optimality with free end
time.
@
@t +H
!
t=t
f
=0 (2:31)
From this equation,itis clearthat if the terminalcost (x(t
f );t
f
)doesnot depend
on the time explicitly,then
H j
t=t
f
=0 (2:32)
Therefore,ifHalsodoesnotdependexplicitlyontime,thenH=0forall0tt
f .
(3) Itisassumedinthepreviousderivationsthatthenalstatex(t
f
)isfree. Ifthenal
state is xedi.e.
x(t
f )=x
f
(2:33)
then the previous necessary conditions still hold except (2.29) whichis replaced by
2.4.2 Pontryagin Minimum Principle
In real problems, the control variables are usually bounded, therefore we can not
dierentiatetheHamiltonianwithrespecttothecontrol,equation(2.30). Letthebounded
control lie inthe subset U 2R m
. In this case, the necessaryconditions are derived from
the Minimum Principlewhich wasdevelop ed by Pontryagin and his school[12].
Pontryagin Minimum Principle:
Supposethatu 3
(t)is theoptimal control with corresponding optimaltrajectories x 3
(t),
and let the Hamiltonian be dened by equation (2.17). In order that u 3
(t) and x 3
(t) be
optimal of the problem (2.4)-(2.5), then there must exist a costate vector 3
(t) such that
the following conditions hold:
_
= 0
@H
@x T
(2.34)
(t
f ) =
@
@x
T
(2.35)
(2.36)
and
H(x 3
;u 3
; 3
;t) H(x 3
;u;
3
;t) (2:37)
for any t 2[t
0
;t
f
] and for all controls u(t) 2U, which indicates that the optimal control
must minimize the Hamiltonian.
Inequality (2.37)isvery usefulto obtainthe optimalcontrol ifthe controlisbounded
by inequality constraints. It should be pointed out that Pontryagin'sminimum principle
isageneralization of the calculusof variations approach. The dierenceb etween the cal-
culusofvariationsapproachandtheminimumprincipleisthatequation(2.30)isreplaced
by (2.37).
From the previous discussion, it is clear that the variational approach and the mini-
mumprincipleleadtoanonlineartwo-p ointboundaryvalueproblemwhichisverydicult
tosolveanalytically.
Thereisaverylargenumb erofmetho dswhichhavebeenproposedtoobtainanumer-
ical solutionsof the HJBequation and the nonlinear two-p ointboundaryvalue problem.
Thesemethodsarecalledindirectmethods. Thereisanotherclassofmetho dstosolvethe
optimalcontrolproblem, calleddirectmethods. Thedirect methodsare basedonsolving
the optimal control problem by transforming it into a nonlinear programming problem.
In the following sections, we review these methods. A blo ck diagram which shows these
Chapter2.OptimalControlProblem:AReview
Parameterization
Programming Mathematical
Optimal Control Problem
(Riccati Equation)
Exact Solution
Algebraic Equations Mathematical Programming Discretization
Approximate
Parameterization
Approximate Solution N(L)TPBVP
Solution
HJB Equation
Nonlinear (Linear)
Figure 2.1: Computation methods of optimal control problem
2.5 Indirect methods
These are the methods that based onsolving the optimalcontrolproblem using HJB
equation or the nonlinear two-p oint boundary value problem. These methods can be
divided intotwo categories: closed loop methodsand openlo op methods.
2.5.1 Closed Loop Control Methods
Some ofthe metho dswhichwereprop osedtoobtainthefeedback optimalcontrol are
summarizedas follows
The rst approach toobtain feedback optimal control is based on using the power
seriesexpansiontosolveeithertheHJBequationorthe nonlineartwo-p ointbound-
ary value problem successively to obtain an approximate optimal feedback control
law. This approachhas been appliedby Lukes[14], tond anapproximate solution
of HJB equation of the innite horizon generalnonlinear optimalcontrol problem.
The solution of HJB equation is reduced to solving successively systems of linear
algebraic equation. Using the same idea, Willemstein [15] extended Lukes' work
to handle the nite time nonlinear optimal control problem. The work of Lukes
has been applied by Garrard and Jordan [16] to control F8 ghter aircraft. The
power series technique has also been used by Nishikawa et al. [17] to obtain the
approximate optimalsolutionofnite time quadraticperformance index subjectto
the perturbed system given by,
_
x=A(t)x+f(x;t)+B(t)u (2:38)
Thisoptimalcontrolproblem wassolvedbyexpandingthe costatebyapowerseries
withrespectto,andthesolutionwasreducedtosolvingasequenceoflinearpartial
dierential equations. Also, similaridea wasapplied by Yoshidaet al [18] tosolve
thenite and the innitetime quadraticperformance indicessubject tothe system
_
x=f(x)+Bu (2:39)
Inthiscase,thelexicographiclistingvectorx [k ]
wasusedtoexpressthefunctionf(x)
inapowerseriesabout the originand also toexpressthe costatesbyapowerseries
of unknown parameters. The solution of the nite time optimal control problem
was reducedto solving aRiccati equation and a sequence of ordinary linear dier-
entialequations,while thesolutionofthe innitetimeoptimalcontrolproblem was
reducedtosolving sequenceof algebraic equations.
Thesecond approachtoobtainthe optimalfeedback control istoobtainthe neigh-
necessary conditions of the optimality around the optimal solution or expanding
the p erformance index up to the second order and the constraints up to the rst
order around the optimalsolution [3,19{22].
The thirdapproachtondthe optimalfeedback controllawisbased onwritingthe
nonlinear state equations intoa linear formstate equations asfollows
_
x=f(x;u;t)=A(x;u;t)x+B(x;u;t)u (2:40)
and then the quadratic optimal control problem is solved by solving the following
Riccati equation
_
P(x;u;t) = P(x;u;t)A(x;u;t)+A T
(x;u;t)P(x;u;t)
0P(x;u;t)B(x;u;t)R 01
B T
(x;u;t)P(x;u;t)+Q (2.41)
and the optimalcontrolis given by
u 3
(x;t)=0R 01
B T
(x;u;t)P(x;u;t)x(t) (2:42)
Thus for a given state x the optimal control is found by simultaneously solving
equations (2.41) and (2.42).
This methodwas developedby Burghart [23], Wernliand Cook [24].
The fourth approach to nd the optimal feedback control solution is to solve the
inverse optimal control problem [25{28].
Someof otherapproachescan befound inNedeljkovic[29],Goh [30],and Longmuir
and Bohn [31].
2.5.2 Open Loop Control Methods
There is a great numb er of papers that present numerical methods for nding the
optimal open loop control. These methods are based on solving the nonlinear two-p oint
boundaryvalue problem. Some of these metho ds are: Gradient methods, quasilineariza-
tion,penaltyfunctionmetho ds,neighb oringextremalmethods. Thesearestandardmeth-
ods to solve the optimal control problems, for details of these methods, the reader can
refer to[3{5].
2.6 Direct Methods
This is another major class of methods for solving the optimal control problems.
rst advantage is that the dicult dynamic optimal control problem can be converted
into static parameters optimization problem which is easier than the original one; the
second advantage is that there are well-develop ed algorithms to solve the nonlinear pro-
gramming problems; the third advantage is that it is possible to treat dierent typ es of
constraintseasily.
Due to these attractive features of the direct methods and the drawbacks, men-
tioned earlier, of the indirect methods, a number of authors has used the direct meth-
ods to solve the optimal control problem. The direct metho ds are based on obtaining
the solution through a direct minimization of the performance index, subject to con-
straints, of the optimal control problem. These methods can b e applied by converting
thenonlinear optimalcontrolproblem intoanonlinear mathematicalprogramming prob-
lem [32{34,37,39{41,43,48,49,52,54,55,70,75{78].
The optimal control problem can b e converted into a mathematical programming
problem byusing eitherthe discretization orthe parameterization techniques. The work
in this thesis is based on using the parameterization technique to convert the optimal
control problem into mathematical programming problem.
2.6.1 Discretization Methods
All discretizationapproaches divide the time intervalinton
s
segments
t
0
<t
1
<t
2
<111<t
n
s
=t
f
where the time points are referred toas mesh points,grid p oints or nodes.
One approach to apply this method is to discretize both the state variables and the
control variables, therefore we have the following sequence of unknown values of state
variablesand control variables,
z =(x
0
;x
1
;111;x
n
s
;u
0
;u
1
;111;u
n
s 01
)
and the system state equations are replaced by a set of algebraic equations which are
considered as equality constraints. Hence this problem can be solved using any of the
nonlinearprogramming techniques. One ofthe disadvantages ofthisapproachisthe high
dimensionality of the vector z.
Another approachis to discretize the control variables only
z=(u
0
;u
1
;111;u
n
s 01
)
and then the system state equations have to be integrated to nd the state variablesas
a function of the control variables. For more details of these approaches the interested
2.6.2 Parameterization Methods
The parameterizationtechniqueisanessentialpart ofthis research,thereforewewill
explain this approachin somedetails.
The parameterizationtechniquecan beapplied inone ofthe following three forms
1. Control Parameterization:
The control parameterization is based on approximating the control variables by
choosinganappropriatestructurewithnitelymanyunknownparametersasfollows
u
l (t)=
N
X
i=0 b
(l )
i 8
i
(t) l =1;2;111;m (2:43)
where b
i
's are unknown parameters, 8
i
(t) denotes an appropriate set of functions
forming a basis of anite dimensional control space.
The state variables are obtained as a function of the unknown parameters of the
control variables, by integrating the system state equations. And by substituting
the approximated control variables and the corresponding state variables into the
performance index, the optimal control problem can be converted into a static pa-
rameters programming problem, whichcan besolved easier than the originalone.
Some of the functions that have been used to approximate the control variables
are [33]: Piecewiseconstant functions,piecewise linear functions,piecewise polyno-
mials, splines of a given order, or functions known to be well-suited for practical
realization.
The control parameterization approach is the most widely used parameterization
approach. It has b een used in many researchpapersand bo oks, [33,34,36{38]and
the cited thereinreferences. Applying this technique requires theintegrationof the
system state equations, whichis a computationally expensive process [73].
2. Control-State Parameterization
The control-state parameterization approach [39{42,48,52,54,70,71] is based on
approximating both the state variables and the control variables by a sequence of
known functionswith unknownparameters as follows
x
j
(t) = N
X
i=0 a
(j)
i 8
i
(t) j =1;2;111;n (2.44)
u
l (t) =
N
X
b (l )
i 8
i
(t) l =1;2;111;m (2.45)
wherea
i ,b
i
are unknown parameters, and 8
i
(t) isan appropriateset of functions.
Using this method, the optimal control problem can be converted into a nonlinear
mathematical programming problem.
The main disadvantages of this approach are: A large numb er of unknownparam-
eters which haveto bedetermined a
i and b
i
;the system state equationshave tobe
replaced by a large numb er of equality constraints. Therefore,using this approach
weend upwith alarge dimensionalnonlinearmathematical programming problem,
in the sense of the numb er of unknown parameters and the numb er of equality
constraints.
3. StateParameterization
The idea of the state parameterization is to approximate only the system state
variablesby asequence of givenfunctions with unknown parameters
x
j (t)=
N
X
i=0 a
(j)
i 8
i
(t) j =1;2;111;n (2:46)
and then the control variablesare obtained from the state equations.
In comparison with the previous two approaches, control parameterization and
control-state parameterization, this method has some advantages: (1) There is no
needtointegratethe systemstateequationsasincontrolparameterization. (2)The
numb er ofthe unknown parameters islowerthan those incontrol-state parameter-
ization. (3) The system state equations will be satised directly and will not be
replaced by equality constraints. (4) The state constraintscan behandled directly.
In spite of many advantages of this technique, it has not been used extensively
compared with the previous two approaches [43,49,77,79]. The main reasons for
this are the following:
(a) It isdiculttohandlethenonlinear systemsusing thestateparameterization,
because it is not always easy to nd the control variables as function of the
state variables.
(b) There isnosystematic way toapply this techniqueon generaloptimalcontrol
problems ofunequal numb erof state variablesand control variables.
Inthisresearch,weovercomethesediculties byusingthe secondmethodofquasi-
linearization and by proposing a method to help the user to decide which state
In the previous few works [43,49,77,79] concerning the state parameterization, this
technique was applied on special cases, for example linear optimal control problem with
equal numb er of state variables and control variables or single input nonlinear systems
which can be expressed in the controllability canonical form. Also there is no detailed
treatmentofthis techniqueforgeneraloptimalcontrolproblems, linearornonlinear,con-
strainedorunconstrained. Moreover,thereare nodetailsonhowtoapply thistechnique.
Therefore,the rst purposeofthis thesis istoclarify this approachshowinga systematic
way how we can apply it to convert the optimal control problem intomathematical pro-
gramming problem. Also we will generalize this technique to handle general, linear and
nonlinear, constrained and unconstrained, optimal control problems.
Aswementionedearlier,one ofthe problems ofthis techniqueis thedicultyofhan-
dling the nonlinear systems. Inthis work,weovercomethis problem by using the second
methodofthe quasilinearization [45]. Inthis research,allaspects ofthe state parameter-
izationwill be considered. Moreoverwewill showthe mostappropriate methodsofusing
this technique.
The state parameterization can b e employed using dierent basis functions [33]. In
this workthe Chebyshevpolynomialswill be usedto parameterizethe system state vari-
ables. The Chebyshev polynomials have several advantages. Some of these advantages
are fastconvergenceand minimaxproperty[44]. Vlach[46] statedthat, of allultraspher-
ical polynomials, the Chebyshevpolynomialsof the rsttyp ecan uniformly approximate
a much broader class of functions. This does not mean at all that we are saying that
the Chebyshev polynomials perform better than others in all applications, some other
orthogonal polynomials may perform better for certain applications.
TheuseoftheChebyshevpolynomialstosolvetheoptimalcontrolproblemsisnotnew.
Paraskevop oulos [66], Wang and Nagurka [69], Chou and Horng [62], Liu and Shih [64]
used Chebyshevpolynomials to solve linear quadratic optimal control problems. On the
otherhand,Vlassenbro eckandVanDooren[39,40,70,71]usedtheChebyshevpolynomials
to parameterize the state variables and the control variables to solve the unconstrained
nonlinearoptimalcontrolproblem, andthe constrainedoptimalcontrolproblem. Inspite
of their generalization to solve nonlinear optimal control problems, their metho d has
some severedisadvantages[48]. Some ofthese disadvantagesare: Extremely complicated
methodofapproximation;theoptimalcontrolproblemisreducedtoalargesizenonlinear
programming problem.
Thesecondpurposeofthisthesisistousethe Chebyshevpolynomialstoparameterize
trol problems. Moreover, we extend this approach to solve both the constrained linear
quadraticoptimalcontrolproblem subjecttoalltyp esofconstraints andthe constrained
nonlinear optimalcontrol problems subject toterminal state constraintsand control sat-
urationconstraints. Some of the advantages of our method are: (1) Easy approximation
method,(2) explicit formulato approximate the performance index, (3) small size math-
ematical programming problems.
Inallthedirectmethodsmentionedpreviously,the nonlinearoptimalcontrolproblem
was converted into a nonlinear mathematical programming problem. One of the meth-
ods tosolvethe nonlinear programming problem is asequentialquadratic programming.
There are two exceptions: the work of [55] and the work of [57]. In these papers the
nonlinear optimal control problem was converted directly into a sequence of quadratic
programming problems using the discretization technique. These two works have some
drawbacksasinthe rst workaspecicclassof problemswassolved, moreovertherewas
a need for special program to handle the control saturation constraints. For the second
work,itonlygivesanupperboundontheoptimalvalue,moreoverthestatesandcostates
haveto beintegrated ineachiteration.
The third purpose of this thesis is to reduce the nonlinear optimal control problem
directly to a sequence of quadratic programming problems using the state parameteri-
zation. Our method has the following advantages: (1) It can handle general problems,
(2) there is no need for special program to solve it,(3) there is noneed to integrate the
system states or the costates, (4) the optimal solution can be obtained, (5) due to the
use ofthestate parameterization,eachofthe quadraticprogrammingproblems isasmall
size problem, in the sense of the numb er of the unknown parameters and the numb er of
equality constraints.
Although the directmethods givethe openloopsolutionof the optimalcontrol prob-
lems, there are few works [61,62,64,66,67,69] in which the parameterization technique,
state-costate parameterization, was used to obtain the feedback solution of the linear
quadraticoptimalcontrolproblems. Thefourth purposeofthisthesisistoextendthe use
of the direct methods to obtain the feedback optimal solution of the nonlinear optimal
control problems using the parameterization technique viaChebyshev polynomials.
In short, we can say that this thesis answers unanswered questions in the previous
works, completes and extends previous works, and develops new direction of research
concerning the computations of optimal feedback controlof the nonlinearsystems.
technique is by applying this techniqueon the nonlinear two-p ointboundaryvalue prob-
lem, by parameterizing the states and the costates [61,62,64,66,67,69]. Hence, the
nonlinear two-pointboundaryproblem is reducedto solving a setof algebraic equations.
Linear Optimal Control Problem
3.1 Introduction
Ashasbeenshowninthepreviouschapter,thelinearquadraticoptimalcontrolprob-
lem is one of the few optimal control problems in which an optimal analytical feedback
solution can be obtained [2,3]. The solution of this problem can be obtained either by
solvingmatrix Riccatiequation,whichisanonlinearordinarydierential equation,orby
solving linear two-p oint b oundary value problem.
To avoid the diculties associated with the numerical integration of these methods,
there are two approaches: The rst approach is to convert the linear quadratic optimal
control problem into aquadratic programming problem, Razzaghi and Elnagar [84] used
shiftedLegendrepolynomialstoparameterizethe derivativeofeachofthestatevariables;
FrichandStech[41] usedthe Walshfunctionstoparameterizethe statevariablesand the
control variables; Elnagar and Razzaghi [86] parameterized the state variables and the
control variables in terms of their values atLegendre-Gauss-Lobatto points. The second
approachis to solve itbyconvertingthe linear two-p oint boundary valueproblem intoa
setoflinear algebraicequations by parameterizingthe system statevariablesandcostate
variables[61,62,64,66,67,69,85].
As has been mentioned in the previous chapter, most of the parameterization meth-
ods are based on either control parameterization or control-state parameterization. But
these two approaches have some drawbacks. Therefore, throughout this thesis the state
parameterizationmethodis employed.
Therstpurposeofthischapteristodiscussthestateparameterizationandshowhow
we can apply it in systematic way. The second purpose is to present the reformulation
method of the optimal control problem into a quadratic programming problem. The
third purpose is to derive an explicit formula to approximate the performance index.
For all of these objectives, in this chapter, we present a new numerical metho d to solve
the simplest optimal control problem, the linear quadratic optimal control problem, by
directly converting it into a quadratic programming problem. To this end we employ
the state parameterizationmethod byusingthe Chebyshevpolynomials ofthe rst typ e,
therefore the optimalcontrol problem is converted into quadratic programming problem
which can be solved in one iteration by performing matrix0vector multiplication. The
advantages of this numerical method are: There is noneed tointegrate the system state
or costate equations; the optimal control problem is converted into a small quadratic
programming problem.
3.2 Problem Statement
Consider the dynamical system describedby the followingstate equations:
_
x=Ax+Bu (3:1)
where x 2R n
, u2 R m
, m n; A and B are respectively, n2n and n2m real0valued
matrices. Wehaveassumedthat the process starts fromt=0 and endsat thexedtime
t
f
>0. Aprocesswhichstartsfromt
0
6=0maybetransformedtosatisfythis assumption
by suitableshifting the time axis.
The initial conditionfor the stateequations (3.1) are:
x(0)=x
0
(3:2)
where x
0
is agivenvector inR n
.
The optimal control problem is to nd an optimal control u 3
(t) on 0 t t
f
which
minimizes the quadraticperformance index,
J = Z
tf
0 (x
T
Qx+u T
Ru)dt (3:3)
subject to the state equations (3.1) and the initial condition (3.2). Here Q is an n2n
positivesemidenite matrix and R is anm2m p ositive denite matrix.
In this chapter, we propose a method to solve this optimal control problem by con-
verting it directly into a quadratic programming problem. This method is based on
approximating the system state variables by Chebyshev series of nite length but with
unknown parameters. This method will be generalized in the next chapter to solve the
3.3 State Parameterization Using Chebyshev Poly-
nomials
Before we start discussing the state parameterization, some imp ortant properties of
the Chebyshevpolynomialsof the rst typ e will b e summarized.
3.3.1 Chebyshev Polynomials
Because the Chebyshev polynomialshavesome advantages, compared with other or-
thogonalpolynomials, suchasfast convergenceand minimaxproperties[44], theywill be
usedinthisresearchtoperform thestateparameterization. Tofacilitatethepresentation
of the materials that follows, we present in this section some background on Chebyshev
polynomials.
The Chebyshev polynomials of the rst typ e are dened on the interval 2 [01;1].
These polynomialsare dened asfollows:
T
r
()=cos(r) cos = 01 1 (3:4)
Therefore,the rst three Chebyshev polynomialsare:
T
0
() = 1
T
1
() =
T
2
() = 2 2
01
(3:5)
The remaining Chebyshevpolynomials can b e obtained fromthe recurrence relation,
T
r +1
()=2T
r
()0T
r 01
() r1 (3:6)
The ChebyshevpolynomialT
n
()is a solutionof the Chebyshev equation
(10 2
) d
2
y
d 2
0 dy
d +n
2
y=0 (3:7)
The polynomials T
n
() and T
m
() are orthogonal in the interval 2 [01;1] with
respect tothe weighting function
w ()=
1
(10 2
) 1=2
(3:8)
and therefore
Z
1
01 T
n ()T
m ()
(10 2
) 1=2
d = 8
>
>
<
>
>
:
0 n 6=m
2
n =m 6=0
n =m =0
(3:9)
The Chebyshev polynomials have some interesting properties which will be used fre-
The product relation
T
n ()T
m ()=
1
2 (T
n+m
()+T
jn0mj
()) (3:10)
The initial and nal values
T
n
(1) = 1 (3.11)
T
n
(01) = (01) n
(3.12)
Integration property
Z
1
01 T
n
()d = 8
>
>
<
>
>
:
0 n odd
02
n 2
01
n even
2 n=0
(3:13)
A functionx() can be approximated by a Chebyshevseries of length N asfollows,
x()= a
0
2 +
N
X
i=1 a
i T
i
() (3:14)
where
a
j
= 2
K K
X
i=1
x(cos(
i
))cos(j
i
) j =0;1;111;N (3:15)
where
i
= 2i01
2K
;i=1;2;111;K ;and K >N
The derivativeof x()with resp ect to is givenby
_ x()=
b
0
2 +
N01
X
i=1 b
i T
i
() (3:16)
where
b
N01
= 2Na
N
b
N02
= 2(N 01)a
N01
b
r 01
= b
r +1 +2ra
r
r=1;2;111;N 02
(3:17)
3.3.2 State Parameterization
The state parameterization has several advantages over the other parameterization
methods. But so far its use was restricted to special problems. In this section, dierent
aspects of state parameterizationsare discussed.
The idea of the state parameterization, using the Chebyshev p olynomials of the rst
typ e, isto approximate the state variablesby anite length Chebyshevseries
x
j ()=
a (j)
0
2 +
N
X
a (j)
i T
i
() j =1;2;111;n (3:18)
where T
i
() is the i-th order Chebyshev polynomial of the rst typ e and a
i
's are the un-
known parameters. Thecontrolvariablesaredeterminedfromthe systemstateequations
asafunction ofthe unknownparametersof the statevariables. Therefore,allthe system
state equations, in most cases, are satised directly. By substituting these approxima-
tionsofthe statevariablesandthe controlvariablesintotheperformanceindex, itcanbe
convertedintoaquadraticfunction ofthe unknown parametersa
i
. The initialconditions
are replaced by equalityconstraints.
In applying the state parameterization,wedistinguish two cases:
1. The number of the state variables is equal to the numb er of control variables i.e.
n=m.
Ifthe numb ers of the state variablesand the control variables are equal, then each
state variable will be approximated by a nite lengthChebyshev series
x
j ()=
a (j)
0
2 +
N
X
i=1 a
(j)
i T
i
() j =1;2;111;n (3:19)
and the control vector can be obtained as a function of these state variables as
follows, assuming that the matrix B is nonsingular,
u()=B 01
[ 2
t
f dx
d
0Ax()] (3:20)
whichcan be expressed inseries form as
u
l ()=
b (l)
0
2 +
N
X
i=1 b
(l )
i T
i
() l=1;2;111;m=n (3:21)
whereb (l )
0 , b
(l)
1 , b
(l)
2
, 111,b (l)
N
are expressedin terms ofa (j)
0 , a
(j)
1 ,a
(j)
2
, 111,a (j)
N .
2. The numb er of the control variablesis less than the numb er of the state variables
m<n.
Ifthenumb erofthe control variablesislessthanthe numb erofthe statevariables,
then there is no need to approximate all the state variables. This is because if all
the state variablesare approximatedthen many ofthe state equations are replaced
by a large numb er of equality constraints. Therefore, in this case, we cho ose and
directly approximate a set of the state variables which will enable us to nd the
remainingstatevariablesandthe controlvariablesasafunctionof thisset. Assume
that this setis x
1
;x
2
;111;x
q
and q<n , then this setcan beapproximatedby
x
j ()=
a (j)
0
2 +
N
X
a (j)
i T
i
() j =1;2;111;q (3:22)
and the remainingn0q state variables andthe controlvariablesare obtained from
the system equations
x
j
() = a
(j)
0
2 +
N
X
i=1 a
(j)
i T
i
() j =q+1;q+2;111;n (3.23)
u
l
() = b
(l )
0
2 +
N
X
i=1 b
(l )
i T
i
() l=1;2;111;m (3.24)
where a (j)
0
;a (j)
1
;111;a (j)
N
, j = q +1;111;n and b (l )
0
;b (l )
1
;111;b (l)
N
, l = 1;2;111;m are
functions of the parametersa (j)
0
;a (j)
1
;111;a (j)
N
, j =1;2;111;q. The advantage of not
approximatingall state variablesis that the optimal control problem is reduced to
a quadraticprogramming problem with fewerunknown parameters.
For the special case of a single input single output systems expressed in controlla-
bility canonical form, weneed toapproximate onlyone state variableand all other
statevariablesandthe controlvariablecanbefound asafunctionofthis statevari-
able. This special case is the main interestof previous works [43,49,77]. Also [79]
proposed, if the number of control variables is less than the numb er of state vari-
ables, to add n0m new articial control variables to the system. This technique
has two disadvantages: (1) There are a large numb er of unknown parameters, (2)
The original problem is changed.
Remarks:
In some cases, we may face the situation that all the state variables and the control
variablesare approximated but not all the state equations are satised. In this case, the
unsatised state equations will be convertedintoequality constraints.
3.4 Which State Variables to Parameterize?
It is clearfrom the previous section that if the numb erof the state variablesis larger
than the numb er of the control variables, then the set of state variables which can b e
selected and approximated is not unique. We can cho ose dierent sets, eachof them can
giveusthe remainingstatevariablesandthe controlvariablesasinthefollowingexample
_ x
1
= x
2
(3.25)
_ x
2
= x
1 +x
2
+u (3.26)
Forthis simple example,wehavetwop ossibilities: The rst possibility istoapproximate
x
1
by a nite length Chebyshev series and x
2
can be found from the rst state equation
by dierentiatingx
1
, while u can be found from the second state equation as a function
of both x ;x . The second p ossibility is to approximate x and to nd x fromthe rst
