Self-conjugate differential and difference operators arising in the optimal control of descriptor systems [original]

TECHNISCHE UNIVERSIT¨

AT BERLIN

Self-conjugate differential and difference operators

arising in the optimal control of descriptor

systems

Volker Mehrmann Lena Scholz

Preprint 2012/26

Preprint-Reihe des Instituts f¨

ur Mathematik

Technische Universit¨

at Berlin

http://www.math.tu-berlin.de/preprints

Preprint 2012/26 August 2012

Self-conjugate differential and difference operators arising in

the optimal control of descriptor systems∗

Volker Mehrmann†Lena Scholz†

August 2, 2012

Abstract

We analyze the structure of the linear differential and difference operators associated with

the necessary optimality conditions of optimal control problems for descriptor systems in

continuous- and discrete-time. It has been shown in [27] that in continuous-time the associated

optimality system is a self-conjugate operator associated with a self-adjoint pair of coefficient

matrices and we show that the same is true in the discrete-time setting. We also extend

these results to the case of higher order systems. Finally, we discuss how to turn higher order

systems with this structure into first order systems with the same structure.

Keywords: Differential-algebraic equation, self-conjugate difference operator, self-adjoint pair,

discrete-time optimal control, necessary optimality condition, congruence transformation, higher

order systems.

AMS(MOS) subject classification: 93C05, 93C55, 93C15, 65L80, 49K15, 34H05.

1 Introduction

The linear quadratic optimal control problem with constraints that are given by differential-

algebraic equations (DAEs) has been discussed in several publications [2, 24, 27, 29]. This is

the problem of minimizing a cost functional

J(x, u) = 1

2x(t)TMex(t) + 1

2Zt

txTWx +xTSu +uTSTx+uTRudt, (1)

subject to the constraint

E˙x=Ax +Bu +f, x(t) = x∈Rn,(2)

with coefficient functions E, A ∈C0(I,Rn,n), W∈C0(I,Rn,n), B∈C0(I,Rn,m), S∈C0(I,Rn,m),

R∈C0(I,Rm,m), f∈C0(I,Rn), and Me∈Rn,n, where R=RT,W=WTand Me=MT

e. Here,

I= [t, t] is a real time-interval and C`(I,Rn,m) denotes the `-times continuously differentiable

functions from the interval Ito the real n×mmatrices. Note that for simplicity we omit the

argument tin all matrix and vector valued functions.

It has been shown in [24] that in the case that the differential-algebraic equation (2) has

some further properties, (i. e., if it is strangeness-free as a behavior system and if the coefficients

are sufficiently smooth), then the necessary optimality condition is given by the boundary value

problem





0E0

−ET0 0

0 0 0 

d

dt 



u

=



0A B

AT+d

dt ETW S

BTSTR





u

+



0

,(3)

2Institut f¨

ur Mathematik, Ma 4-5, TU Berlin, Straße des 17. Juni 136, D-10623 Berlin, FRG; email:

{mehrmann,lscholz}@math.tu-berlin.de

1Research supported by European Research Council, through ERC Advanced Grant MODSIMCONMP.

with boundary conditions x(t) = x,E(t)Tλ(t)−Mex(t) = 0.

If we denote the associated differential-algebraic equation (3) as E˙z=Az+˜

f, then the pair

of coefficient functions (E,A) has the property that ET=−E and AT=A+˙

E. Such pairs of matrix

functions are called self-adjoint pairs, since it has been shown in [27] that this is a property that

is associated with a linear self-conjugate differential-algebraic operator given by Lc:= E˙z− Az.

Note that there may be restrictions to the value xand the weighting matrix Methat need to be

satisfied to guarantee the existence of solutions for (3), see [24].

It has also been shown in [25] for strangeness-free DAEs, and in [2, 29] for special DAEs

with properly stated leading term, that if one just formally writes down the system (3) regardless

of the properties, and if this system is uniquely solvable, then the solution yields the optimal x, u,

but may give a different Lagrange multiplier function λ.

Remark 1. In many practical applications the state xis not directly accessible for measurements

or observations and typically an output equation

y=Cx +Du +g, (4)

with C∈C0(I,Rp,n), D∈C0(I,Rp,m), and g∈C0(I,Rp) is added to (2). The cost functional is

then typically also stated in terms of the output equation, i. e.,

J(y, u) = 1

2y(t)T˜

Mey(t) + 1

2Zt

tyT˜

Wy +yT˜

Su +uT˜

STy+uT˜

Rudt. (5)

In this case one can just insert the output equation (4) into the cost functional (5) and obtains a

cost functional of the form (1).

A typical approach in practice for the solution of optimal control problems is the first-

discretize-then-optimize or direct transcription approach, where the optimal control problem (1),

i. e., the constraint as well as the cost functional are discretized and then classical optimization

techniques are applied to the resulting constrained optimization problem, see e. g., [3, 4, 5, 7].

This method is easy to implement and it is also easy to include other constraints like switching or

inequality constraints, but, in general, not much can be said about the convergence of the solution

of this optimization problem to the optimal solution of the continuous time problem, see [6, 18].

Another viewpoint of the first-discretize-then-optimize approach is that of discrete-time op-

timal control. If we discretize the DAE (2) on a time grid t=t0< t1<· · · < tN=twith a

suitable discretization method [8, 19, 23] and approximate the cost functional (1) by an appro-

priate quadrature rule, then we obtain a discrete-time linear-quadratic optimal control problem of

minimizing

Jd((xi),(ui)) = 1

2xT

NMexN+1

N−1

j=0

(xT

jWjxj+xT

jSjuj+uT

jST

jxj+uT

jRjuj),(6)

subject to the difference equation

Ei+1xi+1 =Aixi+Biui+fi,for i= 0, . . . , N −1 and x0=x∈Rn,(7)

with Ei, Ai, Wi∈Rn,n,Bi, Si∈Rn,m,Ri∈Rm,m and Wi=WT

i,Ri=RT

ifor all iand

Me=MT

e∈Rn,n. Note that the matrices in (6) usually do not match to the corresponding

matrix functions in (1) at the discrete time points ti, e. g., usually Ei6=E(ti), Ai6=A(ti), etc.

Discrete-time optimal control problems of this form also arise when discrete modeling is

used right from the start or when the system is obtain by a sampling method, see e. g. [22, 30].

In the following x= (xi)N

i=0 and u= (ui)N

i=0 will denote sequences of vectors xi∈Rnand

ui∈Rmand we will use the notation

0,N := {(xi)N

i=0 |xi∈Rn}

to denote the vector space of sequences in Rn.

The discrete-time optimal control problem (6) can again be seen as a general optimization

problem in Banach spaces, such that necessary optimality conditions can be derived in the same

way as in [11, 24, 28, 34]. If the constraint equation (7) is strangeness-free, which in the discrete-

time case has been defined and analyzed in [9, 10], then we can extend previous results in the

constant coefficient case of [34] to show that the necessary optimality condition for ((xi),(ui))

to be an optimal solution is the existence of a sequence of Lagrange multipliers (λi) such that

((xi),(ui),(λi)) satisfy the discrete-time optimality system

Ei+1xi+1 =Aixi+Biui+fi,

−ET

iλi−1=Wixi+Siui−AT

iλi,(8)

0 = ST

ixi+Riui−BT

iλi,

together with the boundary conditions

E+

0E0x0=x, AT

0λ0=W0x0+S0u0,

NλN−1=−MexN,(9)

see Section 3.

If we reformulate system (8) as a second order difference equation of the form





0Ei+1 0

000

000





λi+1

xi+1

ui+1

+



0−Ai−Bi

−AT

iWiSi

−BT

iST

iRi





λi

ui

+



0 0 0

i0 0

0 0 0





λi−1

xi−1

ui−1

=



0

,

then again a special structure of the sequences of coefficient matrices (denoted in the following by

((Ki),(Ni),(Mi))) can be observed, with the middle coefficient being symmetric and the leading

and last coefficient being transposes of each other, except that the index is shifted by 1. A triple

of matrix sequences with such a structure will be called a self-adjoint triple of matrix sequences,

see Section 4.

The paper is organized as follows. In Section 2 we recall the main results of the theoretical

analysis for DAE optimal control problems as presented in [26] and [27]. In Section 3 necessary

optimality conditions for the discrete-time optimal control problem (6) are derived. Then, in

Section 4, we investigate self-conjugacy of difference operators and show that the operator associ-

ated with the discrete-time boundary value problem (8) fits into this framework. Since we obtain

higher order difference equations in the discrete-time case we also discuss the related optimal

control problem for higher order systems in Section 5, where also structure preserving first order

representations for continuous- as well as discrete-time self-adjoint systems are studied. We close

with some concluding remarks in Section 6.

2 Preliminaries

The theoretical basis for DAE optimal control problems has been studied in many different publi-

cations, see e. g., [2, 24, 27, 29, 34] and the references therein. We follow the approach in [24, 27]

in a behavior setting, see [36], and first summarize some of the main results that are needed in

the remainder of the paper.

The behavior approach proceeds by setting

E=E0,A=A B , z =x

u

and considering the system (2) in the form

E˙z=Az+f, (10)

with initial condition In0z(t) = x. Following the presentation in [24, 27], we assume that

the system (10) is already given in regular strangeness-free form, meaning that Eand Aare of the

form

E=E10

0 0 ,A=A1B1

A2B2, f =f1

f2

and satisfy the condition that E10

A2B2is pointwise non-singular. A system with these prop-

erties can always be obtained using certain regularization techniques. For details, see [23, 24].

Since the use of adjoint equations is only reasonable for regular systems we restrict ourselves

to this case. It has been shown in [23] that a regular strangeness-free system (10) has a well-defined

differentiation index ν= 1 for every sufficiently smooth input function uand every initial condition

that is consistent with fand that the chosen input function fixes a unique solution.

For a Banach space formulation of (10), in [24] the Banach spaces Z=X×Uand Ywere

defined, where

X=C1

E+E(I,Rn) = x∈C(I,Rn), E+Ex ∈C1(I,Rn),U=C(I,Rm),

Y=C(I,Rn)×range E(t)T,

and E+denotes the Moore-Penrose inverse, see e. g. [17], of the matrix function E=E1

0,

together with the dual spaces

Z∗=C(I,Rn)×C(I,Rm)×range E(t)T×range E(t)T,

Y∗=C1

EE+(I,Rn)×range E(t)T.

The linear quadratic optimal control problem (1), (2) can then be written as the abstract

optimization problem

2Q(z, z) = min! s. t. L(z) = c, z =x

u, c =f

E(t)+E(t)x,(11)

where Q:Z×Z→Ris a symmetric quadratic form defined by

Q(v, z) = v(t)TMe0

0 0 z(t) + ZI

vTW S

STRz dt,

and the linear operators L:Z→Yand its conjugate L∗:Y∗→Z∗are given by

L(z) = Ed

dt(E+Ex)−(A+Ed

dt(E+E))x−Bu, E(t)+E(t)x(t),

L∗(λ, γ) = −ETd

dt(EE+λ)−(A+EE+˙

E)Tλ, −BTλ, γ −E(t)Tλ(t), E(t)Tλ(t).

It has been shown in [27] that with

R(z)=(Wx +Su, STx+Ru, 0, Mex(t)) ∈Z∗,

and defining the operator

T:Y∗×Z→Y×Z∗,T(Λ, z)=(L(z),L∗(Λ) − R(z)),

the necessary optimality conditions (3) can be written as

T(Λ, z) = (c, 0) (12)

and that the operator Tis self-conjugate. Note that (12) coincides with (3) if we assume sufficient

smoothness of the data, see again [24].

Remark 2. The discussed approach can be easily extended to linear higher order optimal control

problems, where one minimizes

J(x, u) = 1

2x(t)TMex(t) + 1

2Zt

t



k−1

j=0

(x(j))TWjx(j)+xTSu +uTSTx+uTRu

dt, (13a)

(with k > 1) subject to a constraint given by a k-th order differential-algebraic equation

j=0

Ajx(j)+Bu =f, x(t) = x0,˙x(t) = x1, . . . , x(k−1)(t) = xk−1.(13b)

Here, Wj=WT

j∈C0(I,Rn,n) and Aj∈C0(I,Rn,n) for j= 0, . . . , k. If the leading coefficient

matrix Akis pointwise nonsingular, then we can apply the classical procedure to turn (13a) and

(13b) into first order systems by introducing new variables wi=x(i)for i= 0, . . . , k −1, see

also [35]. The formal necessary optimality conditions for the corresponding first order system

then lead to a two-point boundary value problem. With λ=λT

k−1. . . λT

0Tpartitioned as

w=wT

0. . . wT

k−1Twe can rewrite the system again as a high order system in (x, µ), where

µ=λk−1, yielding a boundary value problem for 2(k−1)th order equations of the form

j=0

Ajx(j)+Bu =f,

j=0

(−1)jdj

dtjAT

jµ+

k−1

j=0

(−1)j−1dj

dtjWjx(j)−Su = 0,

−BTµ+STx+Ru = 0,

(14)

with boundary conditions

x(i)(t) = xi, i = 0,1, . . . , k −1,

0 =

j=0

(−1)jdj

dtjAT

k−i+jµ+

i−1

j=0

(−1)j+1 dj

dtjWk−i+jx(k−i+j)t

, i = 0, . . . , k −2,

0 =

k−1

j=0

(−1)jdj

dtjAT

1+jµ+

k−2

j=0

(−1)j+1 dj

dtjW1+jx(1+j)t

−Mex(t).

In this way, we can always construct an even order boundary value problem and the corresponding

DAE operator is formally self-conjugate.

If the weighting matrices Wiare chosen to be zero for all i > k−1

2if kis odd, and for all

i > k

2if kis even, then all coefficients in front of derivatives higher than kvanish.

For constant coefficient problems (14) reduces to a system with an even matrix tuple of

coefficients.

Note that when Akin (13b) is singular, this approach cannot be applied in a formal straight-

forward way, because the first order formulation may change the index. In this case first a so-called

trimmed first order formulation of the higher order system has to be considered, see [13, 39]. Then,

for the trimmed first order formulation we can formulate the necessary optimality conditions and

reformulation as a higher order boundary value problem leads again to a self-adjoint high order

system.

After briefly recalling the results for the continuous-time case, in the next section we prove

analogous results in the discrete-time case.

3 Necessary optimality conditions for discrete optimal con-

trol problems

In this section we derive necessary optimality conditions for the discrete-time optimal control

problem (6) subject to (7). Similar results have been obtained in [34] for systems with constant

coefficients and in [28] for system with properly stated leading term of tractability index one.

Again, we may assume without loss of generality that the difference equation (7) is already

given in regular strangeness-free form, i. e., using the behavior approach by setting

Ei+1 =Ei+1 0,Ai=AiBi, zi=xi

ui,

we consider the system (7) in the form

Ei+1zi+1 =Aizi+fi, i = 0, . . . , N −1.

with coefficients

Ei+1 =E1,i+1 0

0 0 ,Ai=A1,i B1,i

A2,i B2,i , fi=f1,i

f2,i ,

that satisfy the condition

E1,i+1 0

A2,i B2,i is regular for all i= 0, . . . , N −1.

Numerical methods for the computations of strangeness-free formulations of a discrete-time system

(7) have been presented in [9, 10].

To derive the necessary optimality conditions we use the classical approach of appending

the constraint equations (7) to the cost term by means of Lagrange multipliers and introducing

the discrete functional

L((xi),(ui),(λi), δ) = 1

2xT

NMexN+1

N−1

j=0

(xT

jWjxj+xT

jSjuj+uT

jST

jxj+uT

jRjuj)

N−1

j=0

(Ej+1xj+1 −Ajxj−Bjuj−fj)Tλj+ (E+

0E0x0−x)Tδ.

(15)

Here, as in [24], we apply the projection onto cokernel E0for the initial value x0in order to meet

the consistency requirements for algebraic components.

The necessary conditions for a minimum are given by the requirement that the gradients of

Lwith respect to all unknowns vanish. We have the following gradients

∇λiL= (Ei+1xi+1 −Aixi−Biui−fi)T= 0, i = 0, . . . , N −1,

∇x0L=W0x0+S0u0−AT

0λ0+ (E+

0E0)Tδ= 0,

∇xiL=Wixi+Siui+ET

iλi−1−AT

iλi= 0, i = 1, . . . , N −1,

∇xNL=MexN+ET

NλN−1= 0,

∇uiL=ST

ixi+Riui−BT

iλi= 0, i = 0, . . . , N −1,

∇δL= (E+

0E0x0−x)T= 0,

giving the necessary optimality conditions

Ei+1xi+1 −Aixi−Biui−fi= 0, i = 0, . . . , N −1,(16a)

Wixi+Siui+ET

iλi−1−AT

iλi= 0, i = 1, . . . , N −1,(16b)

ixi+Riui−BT

iλi= 0, i = 0, . . . , N −1,(16c)

together with the boundary conditions

W0x0+S0u0−AT

0λ0+ (E+

0E0)Tδ= 0,(17a)

MexN+ET

NλN−1= 0,(17b)

E+

0E0x0=x. (17c)

These necessary conditions can be written (in a rather formal way) as a three term recursion of

the form







0Ei+1 0 0

0 0 0 0











λi+1

xi+1

ui+1





+





0−Ai−Bi0

−AT

iWiSi0

−BT

iST

iRi0

0 0 0 0











λi





+





0 0 0 0

i000

0 0 0 0











λi−1

xi−1

ui−1





=









,

(18)

for i= 1, . . . , N −1, with boundary conditions







0E10 0

0 0 0 0











λ1





+





0−A0−B00

−AT

0W0S0(E+

0E0)T

−BT

0ST

0R00

0E+

0E00 0











λ0





=









,

and







0 0 0 0

0Me0 0

0 0 0 0











λN





+





0 0 0 0

N000

0 0 0 0











λN−1

xN−1

uN−1





=



0

.

Here, the additional Lagrange multiplier δis used to couple the initial condition to the functional

(15), in general is chosen as δ= 0. Since δis of no concern in (18), in the following we will omit

the last block row and column of (18).

If we look at the structure of the system (18), then we observe that the middle term is

symmetric while the leading term is the transpose of the last term with the index shifted by one.

Remark 3. In a similar fashion we can treat the discrete-time optimal control problem of mini-

mizing

Jd((x`),(u`)) = 1

2xT

NMexN+1

N−1

j=0 xT

jWjxj+xT

jSjuj+uT

jST

jxj+uT

jRjuj,(19a)

subject to the k-th order discrete-time control system

i=0

M[i]

i+jxi+j+Bjuj=fj, j = 0,1, . . . , N −k, (19b)

with given starting values for x0, x1, . . . , xk−1∈Rnand coefficient matrices M[i]

j∈Rn,n for

i= 0, . . . , k,Bj∈Rn,m,j= 0, . . . , N, see e. g. [11] for the constant coefficient case. In this case

the Lagrangian takes the form

L((x`),(u`),(λ`), δ) = 1

2xT

NMexN+1

N−1

j=0

(xT

jWjxj+xT

jSjuj+uT

jST

jxj+uT

jRjuj)

N−k

j=0 k

i=0

M[i]

i+jxi+j+Bjuj−fj!T

λj+

k−1

j=0 (M[j]

j)+M[j]

jxj−xjT

δj,

(20)

and the necessary optimality conditions are given by

∇λ`L= k

i=0

M[i]

i+`xi+`+B`u`−f`!T

= 0, ` = 0, . . . , N −k,

∇x`L=W`x`+S`u`+

k−`−1

i=0

M[i]T

`λ`−i+(M[`]

`)+M[`]

`T

δ`= 0, ` = 0, . . . , k −1,

∇x`L=W`x`+S`u`+

i=0

M[i]T

`λ`−i= 0, ` =k,...,N −k,

∇x`L=W`x`+S`u`+

i=0

M[i]T

`λ`−i= 0, ` =N−k+ 1, . . . , N −1,

∇xNL=MexN+M[k]

NT

λN−k= 0,

∇u`L=ST

`x`+R`u`+BT

`λ`= 0, ` = 0, . . . , N −k,

∇u`L=ST

`x`+R`u`= 0, ` =N−k+ 1, . . . , N −1,

∇δjL=(M[j]

j)+M[j]

jxj−xjT

= 0, j = 0, . . . , k −1.

This yields the optimality boundary value problem





0M[k]

k+`0

0 0 0

0 0 0





λ`+k

x`+k

u`+k

+· · · +



0M[1]

1+`0

0 0 0

0 0 0





λ`+1

x`+1

u`+1

+





0M[0]

`B`

(M[0]

`)TW`S`

`ST

`R`









λ`

u`



+



0 0 0

(M[1]

`)T0 0

0 0 0





λ`−1

x`−1

u`−1

+· · · +



0 0 0

(M[k]

`)T0 0

0 0 0





λ`−k

x`−k

u`−k

=



0

,

for `=k,...,N−k, together with the corresponding boundary conditions. (Note that, as before,

we have omitted the variables δjfor better readability.) Again, we observe a symmetry of the

middle coefficient, while the leading and final coefficients have a transposed structure with shifted

indices.

In the following, we will show that the difference operator arising in the optimality system

(18) is self-conjugate with respect to suitably chosen dual system and corresponding Banach spaces.

4 Self-conjugate Difference Operators

In order to show that the difference operator arising in the optimality system (18) is self-conjugate,

we adapt the proof from the continuous-time case in [27] to the discrete-time case. As in the

continuous-time case we restrict ourselves to regular and strangeness-free systems. Then, we can

rewrite the discrete optimal control problem (6), (7) as

2Qd((zi),(zi)) = min! s. t. Ld((zi)) = (ci),

with (zi) =  xi

uiand (ci) =  fi

x, where Qd:Zd×Zd→Ris a discrete symmetric

quadratic form defined by

Qd((vi),(zi)) = vT

NMe0

0 0 zN+

N−1

j=0

jWjSj

jRjzj.

In view of the results from Section 3, we obtain that the linear difference operator Ld:Zd→Yd

for the constraint (7) is given by

Ld((zi)) = (Ei+1xi+1 −Aixi−Biui, E+

0E0x0),(21)

with the Banach spaces Zd=Xd×Udand Xd,Ud,Ydgiven by

Xd=Rn

0,N ,Ud=Rm

0,N−1and Yd=Rn

0,N−1×range ET

0.(22)

In the next step we need to define a dual system hZd,Z∗

diand hYd,Y∗

di. Keeping in mind

the necessary optimality conditions (16), we define the Banach spaces

Z∗

d=Rn

1,N−1×Rm

0,N−1×range ET

0×range ET

Y∗

d=Rn

0,N−1×range ET

0.(23)

to obtain the bilinear systems hZd,Z∗

diand hYd,Y∗

diwith the corresponding bilinear forms

h(zi),((ηi),(ϑi), δ, ε)i=

N−1

j=1

ηT

jxj+

N−1

j=0

ϑT

juj+δTx0+εTxN,(24)

h((gi), r),((λi), γ)i=

N−1

j=0

λT

jgj+γTr, (25)

for (zi)∈Zd, ((ηi),(ϑi), δ, ε)∈Z∗

d, ((gi), r)∈Yd, and ((λi), γ)∈Y∗

d. In the following we show

that these bilinear systems are dual systems, i. e., the corresponding bilinear forms satisfy the

conditions hx, x∗i= 0 for all xiff x∗= 0,

hx, x∗i= 0 for all x∗iff x= 0.

Theorem 4. The bilinear systems hZd,Z∗

diand hYd,Y∗

diwith Banach spaces as in (22), (23) and

corresponding bilinear forms as in (24), (25) are dual systems.

Proof. Consider the bilinear system hYd,Y∗

diwith its bilinear form given in (25). In the following,

we use the standard observation that if (fi)∈Rn

0,N and h(fi),(gi)i=PN

j=0 fT

jgj= 0 for all

(gi)∈Rn

0,N , then fi= 0 for all i= 0, . . . , N. Let y∗= ((λi), γ)∈Y∗

dbe fixed and assume that

hy, y∗i=

N−1

j=0

λT

jgj+γTr= 0

for all y= ((gi), r)∈Yd. Choosing gi= 0 for all i= 0, . . . , N −1 and r=γgives γTγ= 0, hence

γ= 0. Therefore, PN−1

j=0 λT

jgj= 0 for all (gi)∈Rn

0,N , and hence λj= 0 for all j= 0, . . . , N −1.

Let y= ((gi), r)∈Ydbe fixed and assume that

hy, y∗i=

N−1

j=0

λT

jgj+γTr= 0

for all y∗= ((λi), γ)∈Y∗

d. Choosing λi= 0 for all i= 0, . . . , N −1 and γ=rgives rTr= 0,

hence r= 0. Therefore, PN−1

j=0 λT

jgj= 0 for all (λi)∈Rn

0,N−1, where (gi)∈Rn

0,N−1and hence,

gj= 0 for j= 0, . . . , N −1.

The proof for hZd,Z∗

difollows the same lines.

If hZd,Z∗

diis a dual system, then we know that the operator Ldhas a unique conjugate

operator L∗

d:Y∗

d→Z∗

d(see also [27]) that is given by

L∗

d(((λi), γ)) = ((ET

iλi−1−AT

iλi),(−BT

iλi), γ −AT

0λ0, ET

NλN−1).(26)

Theorem 5. The operator L∗

d:Y∗

d→Z∗

ddefined by (26) is the unique conjugate of Ld:Zd→Yd

defined by (21).

Proof. Let (zi) = ((xi),(ui)) ∈Zdand Λ = ((λi), γ)∈Y∗

d. Using that E+

0E0γ=γ(since

γ∈range ET

0and E+

0E0is a projector onto cokernel(E0) = range(ET

0)), we have

hLd(zi),Λi=

N−1

j=0

λT

j(Ej+1xj+1 −Ajxj−Bjuj) + γTE+

0E0x0

N−1

j=1

(λT

j−1Ejxj−λT

jAjxj) + λT

N−1ENxN−

N−1

j=0

λT

jBjuj−λT

0A0x0+γTE+

0E0x0

N−1

j=1

(ET

jλj−1−AT

jλj)Txj+

N−1

j=0

(−BT

jλj)Tuj+ (γ−AT

0λ0)Tx0+ (ET

NλN−1)TxN

=h(zi),L∗

d(Λ)i.

Finally, we can define an operator Td:Y∗

d×Zd→Yd×Z∗

dof the form

Td(Λ,(zi)) = (Ld(zi),L∗

d(Λ) + Rd(zi)),(27)

with

Rd(zi) = (Wixi+Siui),(ST

ixi+Riui), W0x0+S0u0, MexN∈Z∗

That means, for (zi) = ((xi),(ui)) ∈Zdand Λ = ((λi), γ)∈Y∗

dwe have

Td(Λ,(zi)) = (Ei+1xi+1 −Aixi−Biui), E+

0E0x0,(ET

iλi−1−AT

iλi+Wixi+Siui),

(−BT

iλi+ST

ixi+Riui), γ −AT

0λ0+W0x0+S0u0, ET

NλN−1+MexN

and with γ= (E+

0E0)Tδthe necessary conditions (16), (17) can be written as

Td(Λ,(zi)) = ((ci),0).(28)

In order to show that the operator Tdis self-conjugate we introduce the spaces

Vd=Y∗

d×Zd,Wd=Yd×Z∗

and set V∗

d=Wd,W∗

d=Vd. Then, by construction, we have Td:Vd→Wdand also Td:W∗

d→V∗

Obviously, the pairs hVd,V∗

diand hWd,W∗

diare dual systems with respect to the so-called canonical

bilinear form

h(y∗, z),(y, z∗)i=hy, y∗i+hz, z∗i=h(y, z∗),(y∗, z)i.(29)

Theorem 6. The operator Tdas defined in (27) is self-conjugate with respect to the canonical

bilinear form (29), i. e., we have

hTd(v),˜vi=hv, Td(˜v)ifor all v, ˜v∈Vd.

Proof. Let v= (Λ,(zi)) ∈Vdand ˜v= (˜

Λ,(˜zi)) ∈Vd. Then

hTd(Λ,(zi)),(˜

Λ,(˜zi))i=h(Ld((zi)),L∗

d(Λ) + Rd((zi))),(˜

Λ,(˜zi))i

=hLd((zi)),˜

Λi+h(˜zi),Rd((zi))i+h(˜zi),L∗

d(Λ)i,

as well as

h(Λ,(zi)),Td(˜

Λ,(˜zi))i=h(Λ,(zi)),(Ld((˜zi)),L∗

d(˜

Λ) + Rd((˜zi)))i

=hLd((˜zi)),Λi+h(zi),Rd((˜zi))i+h(zi),L∗

d(˜

Λ)i.

Since L∗

dis the conjugate of Ldand because of

h(˜zi),Rd((zi))i=Qd((zi),(˜zi)) = Qd((˜zi),(zi)) = h(zi),Rd((˜zi))i

due to the symmetry of Qd, the two expressions are equivalent.

We want to emphasize again, that (28) coincides with (16), (17). In particular, the opti-

mality system (16) can be written as (18) with the corresponding boundary conditions, i. e., as a

three-term recursion of the form

Kivi+1 +Nivi+Mivi−1=gi, i = 1, . . . , N −1,(30)

with Ki,Ni,Mi∈R`,` and inhomogeneity gi∈R`for all i, together with the boundary conditions

K0v1+N0v0=g0,

NNvN+MNvN−1=gN(31)

This observation leads to the following definition.

Definition 7. Let ((Ki),(Ni),(Mi)) be a triple of R`,` matrix sequences, then the triple of matrix

sequences (MT

i+1),(NT

i),(KT

i−1)is called the adjoint triple of ((Ki),(Ni),(Mi)).

We have the following property of adjoint triples.

Proposition 8. Let ((Ki),(Ni),(Mi)) have the adjoint triple (MT

i+1),(NT

i),(KT

i−1). Then, the

matrix triple (MT

i+1),(NT

i),(KT

i−1)has an adjoint triple which is given by ((Ki),(Ni),(Mi)).

Proof. The adjoint of (MT

i+1),(NT

i),(KT

i−1)is given by

((KT

i−1+1)T),((NT

i)T),((MT

i+1−1)T)= ((Ki),(Ni),(Mi)) .

This observation leads to the definition of self-adjoint triples of matrix sequences.

Definition 9. A triple of matrices ((Ki),(Ni),(Mi)), is called self-adjoint if the following two

conditions are satisfied

Ki=MT

i+1 and Ni=NT

ifor all i. (32)

Note that for a triple of constant matrices, condition (32) reduces to M=KTand N=

NT, i. e., in this case a self-adjoint triple corresponds to a so-called palindromic matrix triple

(M,N,MT), see [31].

A self-conjugate system of the form

i+1vi+1 +Nivi+Mivi−1=gi, i = 1, . . . , N −1,(33)

with boundary conditions as in (31) can always be written in the form







N0MT

M1N1MT

M2N2MT

.........

MN−1NN−1MT

MNNN













vN−1













gN−1







(34)

with symmetric system matrix.

Remark 10. The described concept of self-conjugate difference operators is in accordance with

self-conjugate difference equations given in the form Ld((xi)) = (∆[Pi∆xi−1] + Qixi)i, where

∆xi:= xi+1 −xi, with Pi=PT

iand Qi=QT

i, see e. g., [1, 21]. Here we have L∗∗

d=Ld.

Remark 11. We can also consider linear difference operators of order k= 2µ,µ∈Ndefined by

Ld:V→W,Ld((xi)) =

j=0

Aj(i)xi−µ+j,for all i∈ I,(35)

for an index set I ⊂ Z, with matrices Aj(i)∈Rn,n for j= 0, . . . , k defined for all iand sequence

spaces Vand Wgiven by

V={(xi)i∈I , xi∈Rn|Bj((xi)) = 0 for j= 0, . . . , µ −1},

W={(yi)i∈I , yi∈Rn}.

With index set I={−µ, . . . , N +µ}the boundary terms are given by

Bj((xi)) = {A+

k−j(i−µ+j)Ak−j(i−µ+j)xi= 0 for i=N+ 1, . . . , N +µ−j,

A+

j(i)Aj(i)xi−µ+j= 0 for i= 0, . . . , µ −1−j}.

Then, the (formal) adjoint operator L∗

d:W∗→V∗is given by

L∗

d((yi)) =

j=0

k−j(i−µ+j)yi−µ+j,

with sequence spaces

V∗={(xi)i∈I , xi∈Rn},

W∗=(yi)i∈I , yi∈Rn|B∗

j((yi)) = 0 for j= 0, . . . , µ −1

and boundary conditions

B∗

j((yi)) = {Ak−j(i−µ+j)A+

k−j(i−µ+j)yi−µ+j= 0 for i= 0, . . . , µ −1−j,

Aj(i)A+

j(i)yi= 0 for i=N+ 1, . . . , N +µ−j}.

The difference operator (35) is (formally) self-conjugate if and only if

V={(xi)i∈I , xi∈Rn|Bj((xi)) = B∗

j((xi)) = 0 for all j= 0, . . . , µ −1}

and

Aj(i) = AT

k−j(i+j−µ) for all j= 0, . . . , k, i ∈ I0={0, . . . , N}.(36)

For constant coefficient systems, the condition of self-conjugacy (36) again reduces to Aj=AT

k−j

for j= 0, . . . , k and thus a self-conjugate difference operator is given by a palindromic system

Ld(x) = A0xi−µ+A1xi−µ+1 +· · · +Aµxi+· · · +AT

1xi+µ−1+AT

0xi+µ.

Following [9, 10] we can simplify matrix sequences associated with the coefficients of differ-

ence equations (30) by equivalence transformations that consist of scaling the equation (30) with

nonsingular matrices Pi∈R`,` and by performing a change of variables vi=Qiyiwith nonsingular

matrices Qi∈R`,`. This gives a transformed difference equation

Kiyi+1 +˜

Niyi+˜

Miyi−1=Pigi,

with ˜

Ki=PiKiQi+1,˜

Ni=PiNiQi,˜

Mi=PiMiQi−1.

Taking a look at the behavior of the adjoint of the triple of matrix sequences under equivalence

transformations and assuming that ((Ki),(Ni),(Mi)) possesses an adjoint triple, we see that

(( ˜

Ki),(˜

Ni),(˜

Mi)) possesses an adjoint triple as well, which is given by

(( ˜

i+1),(˜

i),(˜

i−1)) = ((QT

iMT

i+1PT

i+1),(QT

iNT

iPT

i),(QT

iKT

i−1PT

i−1)),

i. e., the adjoint triple of the transformed triple is equivalent to the adjoint triple of the original

triple.

In order to preserve self-conjugacy of the operator, i. e., self-adjointness of the triple of

coefficient sequences, we have to preserve the symmetry of Niand, hence, we have to require that

Pi=QT

i, i. e., that the transformation is a (time-varying) congruence transformation. We then

have the following Lemma.

Lemma 12. Consider a self-adjoint triple of matrix sequences ((Ki),(Ni),(Mi)) with Ki,Ni,Mi∈

R`,` and apply a congruence transformation with a sequence of nonsingular Qi∈R`,`, leading to

the triple

(( ˜

Ki),(˜

Ni),(˜

Mi)) = ((QT

iKiQi+1),(QT

iNiQi),(QT

iMiQi−1)).

Then the triple (( ˜

Ki),(˜

Ni),(˜

Mi)) is again self-adjoint.

Proof. The condition for ˜

Niis trivially satisfied and for ˜

Kiand ˜

Miwe get

Ki=QT

iKiQi+1 =QT

iMT

i+1Qi+1 =˜

i+1.

In order to understand the solution behavior of linear matrix sequences, one usually com-

putes canonical or condensed forms under the associated equivalence transformation. For constant

matrix pairs the general canonical form under equivalence is given by the Kronecker canonical form

see, e. g., [16] and the condensed form is the staircase or GUPTRI form [14, 15, 38]. The canonical

form under congruence transformations for even pencils has been given in [37] and the condensed

form in [12]. For palindromic pencils this form has been derived in [20]. The canonical form for

time varying pairs under equivalence has been presented in [10]. For matrix triples such canonical

forms in general are not known even for constant triples. Recently a condensed form which reveals

partial information has been presented [13], as well as special structured Smith forms [33, 32]. For

systems with variable coefficients such canonical or condensed forms are an open problem.

5 Structure Preserving First Order Formulations

The problem of deriving structure preserving first order formulations for higher order systems has

been an active research field in the last years, see e. g. [11, 31]. Since often numerical software

is only available for first order systems, it is important to preserve the specific structure of a

given problem when it is transformed into an equivalent first order formulation. In this section we

discuss first order formulations in the case of systems with self-adjoint coefficient triples.

Consider a linear k-th order differential-algebraic operator of the form

L:Z→Y, z 7→ L(z) =

i=0

Aiz(i),(37)

with a tuple (Ak, . . . , A0) of sufficiently smooth coefficient functions Ai∈C0(I,Rn,n) and function

spaces

Z={z∈C0(I,Rn)|A+

kAkz∈Ck(I,Rn), Bi(z, t)=0, i = 1, . . . , k},

Y=C0(I,Rn),

with boundary conditions given by

Bi(z, t) = n(A+

iAi)(`)z(i−j−1)|t= 0,for j= 0, . . . , i −1, ` = 0, . . . , jo.

for i= 1, . . . , k.

The unique conjugate operator L∗:Y∗→Z∗is then given by

L∗(y) =

i=0

(−1)idi

dti(AT

iy) =

i=0

(−1)i

j=0 i

j(AT

i)(j)y(i−j),

with function spaces

Z∗=C0(I,Rn),

Y∗={y∈C0(I,Rn)|AkA+

ky∈Ck(I,Rn), B∗

i(y, t)=0, i = 1, . . . , k}

and boundary terms

B∗

i(y, t) = n(AiA+

i)(`)y(j−`)|t= 0,for j= 0,...i−1, ` = 0 ...,jo.

In this setting, the conditions for self-conjugacy of the operator Lare given by

A`=

i=0

(−1)ii

i−`(AT

i)(i−`)=

i=`

(−1)ii

`(AT

i)(i−`)(38)

for `= 0, . . . , k (using that i

j= 0 for j < 0), defined on a domain

Z={z∈C0(I,Rn)|A+

kAkz∈Ck(I,Rn), Bi(z, t) = B∗

i(z, t)=0, i = 1, . . . , k}.

In the special case k= 1, these conditions simplify to

A0=AT

0−˙

1, A1=−AT

with boundary conditions

(A1A+

1)z|t= 0,(A+

1A1)z|t= 0.

For constant coefficient systems the conditions (38) read A`= (−1)`AT

`for `= 0, . . . , k, i. e., the

matrices are alternating symmetric/skew-symmetric. This corresponds to the case of even matrix

tuples, see [31, 33].

Note that in contrast to Definition 12, here for simplicity the zero boundary conditions are

incorporated into the domains Zand Y∗.

For these formal self-conjugate operators we obtain the following result.

Theorem 13. Any self-conjugate linear k-th order differential operator Las in (37) with coeffi-

cient functions that satisfy the conditions (38) can be written in the form

L(z) =

`=0

(−1)`d`

dt`AT

`z,(39)

where the leading coefficient matrix satisfies Ak= (−1)kAT

Proof. Using the condition for self-conjugacy given in (38), the differential operator can be written

Lz=

`=0

i=`

(−1)ii

`(A(i−`)

i)Tz(`)=

`=0

j=0

(−1)``

j(A(`−j)

`)Tz(j)=

`=0

(−1)`d`

dt`AT

`z.

For further investigations it turns out to be useful to split a self-conjugate differential

operator into even and odd order parts.

Theorem 14. Any self-adjoint linear k-th order differential operator Las in (37) with coefficient

functions that satisfy the conditions (38) can be written as a sum of differential operators of the

form

L2ν(x)=(P2νx(ν))(ν),(40a)

L2ν−1(x) = 1

2[(Q2ν−1x(ν−1))(ν)+ (Q2ν−1x(ν))(ν−1)],(40b)

with matrix valued functions P2ν=PT

2ν∈Cν(I,Rn,n)and Q2ν−1=−QT

2ν−1∈Cν(I,Rn,n)for

ν= 0, . . . , µ, where µ=k

2if kis even and µ=k+1

2if kis odd.

Proof. We prove the statement by induction. For k= 1 we have

L(x) = A1˙x+A0x=1

dt(A1x) + 1

2(A1˙x)+(A0−1

2˙

A1)x

with Q1:= A1skew-symmetric and P0:= A0−1

2˙

A1symmetric (due to (38)). Similar, for k= 2

we have

L(x) = A2¨x+A1˙x+A0x

dt(A2˙x)+(A1−˙

A2) ˙x+A0x

dt(A2˙x) + 1

dt((A1−˙

A2)x) + 1

2((A1−˙

A2) ˙x)+(A0−1

2(˙

A1−¨

A2))x,

with P2=A2and P0:= A0−1

2(˙

A1−¨

A2) symmetric, and Q1=A1−˙

A2skew-symmetric (due to

(38)).

Now let L(x) = Pk

i=0 Aix(i)be a self-conjugate differential operator and assume that k= 2µ

is even. The conditions in (38) imply that Ak=AT

k, and we can write the operator as

L(x) = dµ

dtµAkx(µ)−

i=1 µ

iA(i)

kx(k−i)+Ak−1x(k−1) +· · · +A1˙x+A0x

=dµ

dtµAkx(µ)+

k−1

i=0

Aix(i),

with ˜

Ai=Ai−µ

k−iA(k−i)

k, for i=k−µ, . . . , k −1, and ˜

Ai=Aifor i= 0, . . . , k −µ−1. If we

subtract from L(x) the self-conjugate expression

L2µ(x) = dµ

dtµ(Akx(µ)) = Akxk+

j=1 µ

jA(j)

kx(k−j),

(i. e., Pk=Ak), then we obtain again a self-conjugate expression

L(x) = L(x)− L2µ(x) =

k−1

i=0

Aix(i)−

j=1 µ

jA(j)

kx(k−j)

µ−1

i=0

Aix(i)+

k−1

i=µ

(Ai−µ

k−iA(k−i)

k)x(i)

of odd order k−1.

If k= 2µ−1 is odd, then we have Ak=−AT

k. By subtracting from L(x) the self-conjugate

expression

L2µ−1(x) = 1

2h(Akx(µ−1))(µ)+ (Akx(µ))(µ−1)i

=Akx(k)+1

2



j=1 µ

jA(j)

kx(k−j)+

µ−1

j=1 µ−1

jA(j)

kx(k−j)

,

(i. e., Qk=Ak), then we obtain a self-conjugate expression

L(x) = L(x)− L2µ−1(x) =

k−1

i=0

Aix(i)−1

2



j=1 µ

jA(j)

kx(k−j)+

µ−1

j=1 µ−1

jA(j)

kx(k−j)



of even order k−1.

Due to the inductive assumption, a self-adjoint operator of order k−1 can be written as a

sum of expressions of the form (40a) and (40b). This completes the proof.

In the following, we say that a self-adjoint differential operator is in partitioned form, if it

is given by

L(x) = (Pr

ν=0 L2ν(x) + Pr

ν=1 L2ν−1(x),if kis even with r=k

Pr−1

ν=0 L2ν(x) + Pr

ν=1 L2ν−1(x),if kis odd with r=k+1

2.(41)

Example 15. For a linear second order differential operator of the form

M¨x+C˙x+Kx =f, (42)

with coefficient functions M, C, K ∈C(I,Rn,n) that are sufficiently smooth and satisfy the condi-

tions

M=MT, C = (2 ˙

M−C)T,and K= ( ¨

M−˙

C+K)T,for all t∈I,

the formulation (39) is given by

dt2MTx−d

dt CTx+KTx=f,

and the partitioned form (41) by

P0x+d

dt (P2˙x) + 1

dt (Q1x) + 1

2Q1˙x=f. (43)

with P0:= K−1

2(˙

C−¨

M), P2:= M, and, Q1:= C−˙

In order to derive structure preserving first order formulations, we assume that the leading

matrix Akis pointwise nonsingular. Otherwise, the task is more complicated, and we have to

consider trimmed first order formulations, see [39].

In the second order case (using the notation of Example 15), introducing in (43) the new

variable v= ˙x, we get

dt(P2˙x) = d

dt(P2v) = P2˙v+˙

P2v,

yielding

P2˙v+˙

P2v+P0x+1

2˙

Q1x+Q1˙x=f.

This gives the first order system

0−P2

P2Q1˙v

˙x+P20

P2P0+1

2˙

Q1v

x=0

f

or equivalently 0−M

M C −˙

M

| {z }

˙v

˙x+M0

M K

| {z }

v

x=0

f

with a self-adjoint pair of coefficient functions (E,A).

Similar, for a third order system in partitioned form

P0x+d

dt(P2˙x) + 1

2d

dt(Q1x) + Q1˙x+1

2d2

dt2(Q3˙x) + d

dt(Q3¨x)=f,

with nonsingular leading matrix Q3=A3, by introducing v1= ˙x, and v2= ˙v1= ¨xwe get

dt(Q3¨x) = d

dt(Q3v2) = ˙

Q3v2+Q3˙v2,

as well as

dt2(Q3˙x) = d2

dt2(Q3v1) = d

dt(˙

Q3v1+Q3v2) = ¨

Q3v1+˙

Q3˙v1+˙

Q3v2+Q3˙v2,

dt(P2˙x) = d

dt(P2v1) = P2˙v1+˙

P2v1.

Altogether this yields the first order formulation





0 0 Q3

0−Q3−P2+1

2˙

Q3P2+1

2˙

Q3Q1





˙v2

˙v1

˙x

+



0−Q30

Q3P2−1

2˙

Q30

Q3˙

P2+1

2¨

Q3P0+1

2˙

Q1





x

=



f



or equivalently, using Q3=A3,P2=A2−3

2˙

A3,Q1=A1−˙

A2+¨

A3,P0=A0−1

2˙

A1+1

2¨

A2−1

...

A3,





0 0 A3

0−A3−A2+ 2 ˙

A3A2−˙

A3A1−˙

A2+¨

A3



| {z }





˙v2

˙v1

˙x

+



0−A30

A3A2−2˙

A30

A3˙

A2−¨

A3A0



| {z }





x

=



f



and again the matrix pair (E,A) is self-adjoint, since A0, . . . , A3satisfy the condition (38). It is

obvious, but rather technical, how to extend this construction to higher orders k > 3.

In the discrete-time case the situation is somehow different. For odd order difference opera-

tors there does not exist a self-conjugate operator corresponding to the definition given in Remark

11, since a two-term recursion can never be written in the form (34) with symmetric system matrix.

Nevertheless, we can derive an equivalent two-term recursion with similar structures as in

the constant coefficient case, see [11].

Example 16. For a second order self-adjoint difference operator with constant coefficients

Mxi−1+Nxi+MTxi+1 =fi,

by setting vi:= xi+1 we have the palindromic first order form

MTN − M

MTMTvi

xi+M M

N − MTMvi−1

xi−1=fi

fi,

see [31].

Proceeding like this in the case of variable coefficients, for a self-conjugate system (33) we

obtain MT

i+1 Ni− Mi

i+1 MT

i+1 vi

xi+MiMi

Ni− MT

i+1 Mivi−1

xi−1=fi

fi.

For the special case of difference equations from optimal control problems in (18) (omitting the

last row and column) by shifting the first block row we get





0Ek0

−AT

kWkSk

−BT

kST

kRk





λk

uk

+



0−Ak−1−Bk−1

k0 0

0 0 0 





λk−1

xk−1

uk−1

=



fk−1

0

, k = 0, . . . , N −1,

similar to the BVD-pencil structure introduced in [11].

6 Conclusion

We have shown that the necessary optimality conditions for discrete-time linear quadratic control

problems with variable coefficients leads to self-conjugate difference operators associated with self-

adjoint triples of coefficient functions, thus achieving a similar result as in the continuous time case.

We have also extended these results to higher order differential or difference equation constraints

and shown how first order reductions can be carried out that lead to first order systems with the

same structural properties.

References

[1] C.D. Ahlbrandt and A.C. Peterson. Discrete Hamiltonian Systems. Kluwer Academic Pub-

lisher, 1996.

[2] A. Backes. Extremalbedingungen f¨

ur Optimierungs-Probleme mit Algebro-

Differentialgleichungen. PhD thesis, Institut f¨

ur Mathematik, Humboldt-Universit¨

zu Berlin, Berlin, Germany, 2006.

[3] J. T. Betts. Path constrained trajectory optimization using sparse sequential quadratic pro-

gramming. J. Guidance Control Dyn., 16:59–68, 1993.

[4] J. T. Betts, M. J. Carter, and W. P. Huffman. Software for nonlinear optimization. Math-

ematics and Engineering Analysis Library Report MEA-LR-83 R1, Boeing Information and

Support Services, Seattle, USA, 1997.

[5] L. T. Biegler. Optimization strategies for complex process models. Adv. in Chem. Eng.,

18:197–256, 1992.

[6] K. Bobinyec, S. L. Campbell, and P. Kunkel. Maximally reduced observers for linear time

varying DAEs. In Proc. IEEE Multi-Conference on Systems and Control, Denver, 2011, pages

1373–1378, 2011.

[7] H. G. Bock, M. M. Diehl, D. B. Leineweber, and J. P. Schl¨

oder. A direct multiple shooting

method for real-time optimization of nonlinear DAE processes. In Nonlinear model predictive

control, Ascona, 1998, volume 26 of Progr. Systems Control Theory, pages 245–267, Basel,

2000. Birkh¨

auser.

[8] K. E. Brenan, S. L. Campbell, and L. R. Petzold. Numerical Solution of Initial-Value Problems

in Differential Algebraic Equations. SIAM Publications, Philadelphia, PA, 2nd edition, 1996.

[9] T. Br¨

ull. Existence and uniqueness of solutions of linear variable coefficient discrete-time

descriptor systems. Linear Algebra Appl., 431:247–265, 2009.

[10] T. Br¨

ull. Explicit solutions of regular linear discrete-time descriptor systems with constant

coefficients. Elec. J. Linear Algebra, 18:317–338, 2009.

[11] R. Byers, D.S. Mackey, V. Mehrmann, and H. Xu. Symplectic, BVD, and palindromic ap-

proaches to discrete-time control problems. In P. Petkov and N. Christov, editors, Collection

of Papers Dedicated to the 60-th Anniversary of Mihail Konstantinov, pages 81–102, Rodina,

Publications, Sofia, Bulgaria, 2009.

[12] R. Byers, V. Mehrmann, and H. Xu. A structured staircase algorithm for skew-

symmetric/symmetric pencils. Electr. Trans. Num. Anal., 26:1–33, 2007.

[13] R. Byers, V. Mehrmann, and H. Xu. Trimmed linearization for structured matrix polynomials.

Linear Algebra Appl., 429:2373–2400, 2008.

[14] J. W. Demmel and B. K˚agstr¨

om. The generalized Schur decomposition of an arbitrary pencil

λA −B, Part I. ACM Trans. Math. Software, 19:160–174, 1993.

[15] J. W. Demmel and B. K˚agstr¨

om. The generalized Schur decomposition of an arbitrary pencil

λA −B, Part II. ACM Trans. Math. Software, 19:185–201, 1993.

[16] F. R. Gantmacher. The Theory of Matrices II. Chelsea Publishing Company, New York, NY,

1959.

[17] G. H. Golub and C. F. Van Loan. Matrix Computations. The Johns Hopkins University Press,

Baltimore, MD, 3rd edition, 1996.

[18] W.W. Hager. Runge-Kutta methods in optimal control and the transformed adjoint system.

Numer. Math., 87:247–282, 2000.

[19] E. Hairer and G. Wanner. Solving Ordinary Differential Equations II: Stiff and Differential-

Algebraic Problems. Springer-Verlag, Berlin, Germany, 2nd edition, 1996.

[20] R.A. Horn and V. V. Sergeichuk. Canonical forms for complex matrix congruence and ∗

congruence. Linear Algebra Appl., 416:1010–1032, 2006.

[21] W.G. Kelley and A.C. Peterson. Difference equations: An introduction with applications.

Academic Press, San Diego, CA, USA, 2001.

[22] V. Kucera. The structure and properties of time-optimal discrete linear control. IEEE Trans.

Automatic Control, 16:375–377, 1971.

[23] P. Kunkel and V. Mehrmann. Differential-Algebraic Equations. Analysis and Numerical So-

lution. EMS Publishing House, Z¨

urich, Switzerland, 2006.

[24] P. Kunkel and V. Mehrmann. Optimal control for unstructured nonlinear differential-algebraic

equations of arbitrary index. Math. Control, Signals, Sys., 20:227–269, 2008.

[25] P. Kunkel and V. Mehrmann. Formal adjoints of linear DAE operators and their role in

optimal control. Electr. J. Lin. Alg., 22:672–693, 2011.

[26] P. Kunkel, V. Mehrmann, and W. Rath. Analysis and numerical solution of control problems

in descriptor form. Math. Control, Signals, Sys., 14:29–61, 2001.

[27] P. Kunkel, V. Mehrmann, and L. Scholz. Self-adjoint differential-algebraic equa-

tions. Preprint 13, Inst. f. Mathematik, TU Berlin, Berlin, Germany, 2011. url:

http://www.math.tu-berlin.de/preprints/, submitted for publication.

[28] G. A. Kurina. Linear-quadratic discrete optimal control problems for descriptor systems in

Hilbert space. J. Dynam. Control Systems, 10:365–375, 2004.

[29] G. A. Kurina and R. M¨

arz. On linear-quadratic optimal control problems for time-varying

descriptor systems. SIAM J. Cont. Optim., 42:2062–2077, 2004.

[30] H. Kwakernaak and R. Sivan. Linear Optimal Control Systems. Wiley-Interscience, New

York, 1972.

[31] D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann. Structured polynomial eigenvalue

problems: Good vibrations from good linearizations. SIAM J. Matr. Anal. Appl., 28:1029–

1051, 2006.

[32] D. S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann. Smith forms of palindromic matrix

polynomials. Electr. J. Lin. Alg., 22:53–91, 2011.

[33] D.S. Mackey, N. Mackey, C. Mehl, and V. Mehrmann. Jordan structures of alternating matrix

polynomials. Linear Algebra Appl., 432:867–891, 2010.

[34] V. Mehrmann. The Autonomous Linear Quadratic Control Problem. Springer-Verlag, Berlin,

Germany, 1991.

[35] V. Mehrmann and D. Watkins. Polynomial eigenvalue problems with Hamiltonian structure.

Electr. Trans. Num. Anal., 13:106–113, 2002.

[36] J. W. Polderman and J. C. Willems. Introduction to Mathematical Systems Theory: A Be-

havioural Approach. Springer-Verlag, New York, NY, 1998.

[37] R. C. Thompson. Pencils of complex and real symmetric and skew matrices. Linear Algebra

Appl., 147:323–371, 1991.

[38] P. Van Dooren. The computation of Kronecker’s canonical form of a singular pencil. Linear

Algebra Appl., 27:103–141, 1979.

[39] L. Wunderlich. Analysis and Numerical Solution of Structured and Switched Differential-

Algebraic Systems. Phd thesis, Institut f¨

ur Mathematik, Technische Universit¨

at Berlin,

September 2008.