Introdução às LMIs - DT - Home Page

Transcrição

IA360E - Tópicos em Controle I - FEEC/UNICAMP
Profs. Pedro/Sophie
• Conjuntos Convexos
Suponha x1 6= x2 ∈ Rn. Pontos descritos por
αx1 + (1 − α)x2 = x2 + α(x1 − x2)
com α ∈ R descrevem a reta que passa por x1 e x2. Para 0 ≤ α ≤ 1, a combinação descreve
o segmento de reta entre x1 e x2.
x1
PSfrag replacements
x2
introLMI
1/17
Profs. Pedro/Sophie
• Um conjunto C é convexo se o segmento de reta entre dois pontos quaisquer do conjunto
estiver em C , isto é, para quaisquer x1, x2 ∈ C e α ∈ [0, 1],
αx1 + (1 − α)x2 ∈ C
PSfrag replacements
Convexo
Convexo
Não convexo
; Um conjunto C é um cone se para todo x ∈ C e α ≥ 0, αx ∈ C .
; Um cone convexo é um conjunto C tal que, para todo x1, x2 ∈ C e α1, α2 ≥ 0,
α1 x 1 + α 2 x 2 ∈ C
introLMI
2/17
Profs. Pedro/Sophie
• Um hiperplano é um conjunto na forma {x : c0x = b} para c 6= 0 ∈ Rn e b ∈ R. Um
hiperplano divide o Rn em dois semi-espaços, {x : c0x ≤ b} e {x : c0x ≥ b}.
; Hiperplano separador
introLMI
; Hiperplano suporte
3/17
Profs. Pedro/Sophie
• O envelope convexo de um conjunto de N pontos x1, x2, . . . , xN no R2 é um poliedro. Um
ponto descrito como α1x1 +α2x2 +· · ·+αN xN , com αi ≥ 0, i = 1, . . . , N e α1 +α2 +· · ·+αN =
1, é chamado de combinação convexa dos pontos x1, x2, . . . , xN . Um conjunto é convexo se e
somente se contiver toda combinação convexa de seus pontos.
; Matrizes simétricas X = X 0 ∈ Rn×n definem um espaço vetorial de dimensão n(n + 1)/2.
; O conjunto das matrizes simétricas semidefinidas positivas é um cone convexo, pois se
α1, α2 ≥ 0 e X1 > 0, X2 > 0, então α1X1 + α2X2 também é uma matriz simétrica semidefinida
positiva.
introLMI
4/17
Profs. Pedro/Sophie
• Uma função f : Rn → R é linear se para todo α1, α2 ∈ R e x1, x2 pertencentes ao domı́nio
da função,
f (α1x1 + α2x2) = α1 f (x1) + α2 f (x2)
• Uma função f : Rn → R é convexa se seu domı́nio for um conjunto convexo e, para
quaisquer x1, x2 pertencentes ao domı́nio da função e para 0 ≤ α ≤ 1
f (αx1 + (1 − α)x2) ≤ α f (x1) + (1 − α) f (x2)
; O segmento de reta que une os pontos (x1, f (x1)) e (x2, f (x2)) está sempre acima ou sobre
o gráfico da função.
x2
PSfrag replacements
x1
introLMI
5/17
Profs. Pedro/Sophie
• Suponha f (·) diferenciável. Então, f é convexa se e somente se seu domı́nio for um conjunto
convexo e
f (y) ≥ f (x) + ∇ f (x)0(y − x)
para todo x, y pertencentes ao domı́nio de f . ∇ f (x) é o gradiente da função calculado no
ponto x, e a função afim em y dada por f (x) + ∇ f (x)0(y − x) é a aproximação de primeira
ordem de Taylor da função f na vizinhança de x.
f (y)
PSfrag replacements
f (x)
f (x) + ∇ f (x)0 (y − x)
x
introLMI
y
6/17
Profs. Pedro/Sophie
; Para uma função convexa, a aproximação de primeira ordem está sempre abaixo do valor
da função e, se a aproximação de primeira ordem estiver sempre abaixo do valor da função, a
função é convexa.
; Se a função for convexa e ∇ f (x) = 0, então para todo y pertencente ao domı́nio da função
tem-se f (y) ≥ f (x), e portanto x é um mı́nimo global de f .
• A função f é convexa se e somente se seu domı́nio for um conjunto convexo e
f (y) ≥ f (x) + µ(x)0(y − x)
para todo x, y pertencentes ao domı́nio de f e para todo µ(x) pertencente ao conjunto de
subgradientes da função f calculados no ponto x. Se a função for diferenciável, µ(x) = ∇(x)
é único. Se f não for diferenciável em x, µ(x) é a inclinação de todos os hiperplanos suportes
da função no ponto x.
• A função f é côncava se − f for convexa. Se f é côncava e diferenciável em x, então
f (y) ≤ f (x) + ∇ f (x)0(y − x)
introLMI
7/17
Profs. Pedro/Sophie
• Considere a função f (W ) = λmin (W ) para matrizes W ∈ Rn×n simétricas definidas positivas.
Pode-se mostrar que f (W ) é uma função côncava em relação aos elementos da matriz W .
Note que
f (W ) = λmin (W ) = min x0(W )x
kxk=1
Considere uma matriz W0 > 0 qualquer. Então, f (W0) = λmin (W0 ) e W0 x0 = λmin (W0 )x0 para
x0 autovetor associado ao autovalor λmin (W0 ). Então,
f (W ) ≤
≤
≤
≤
≤
x00 W x0
x00 W x0 + x00 W0x0 − x00 W0x0
f (W0) + x00 (W −W0)x0
¡
¢
f (W0) + Tr x0x00 (W −W0 )

®
f (W0) + x0x00 , (W −W0)
e x0x00 é um subgradiente da função f (W ) calculado em W0.
; A restrição λmin (W ) ≥ ε, com ε > 0, define um conjunto convexo.
introLMI
8/17
Profs. Pedro/Sophie
• Complemento de Schur
; Considere a matriz simétrica X particionada
¸
·
A B
X=
B0 C
com A = A0 ∈ Rn×n . Se det(A) 6= 0, a matriz C − B0A−1B é o complemento de Schur de X em
relação a A.
Note por exemplo que
¸
¸ ·
¸·
¸·
·
I
0
A
0
I A−1B
A B
=
X=
0 I
B0A−1 I
0 C − B0A−1B
B0 C
e portanto det(X) = det(A) det(C − B0A−1B).
Analogamente, se det(C) 6= 0, A − BC −1B0 é o complemento de Schur de X em relação a C e
¸·
¸ ·
¸·
¸
·
−1
−1 0
I
0
I BC
A − BC B 0
A B
=
X=
C−1B0 I
0
C
0 I
B0 C
introLMI
9/17
Profs. Pedro/Sophie
• O complemento de Schur surge na solução de equações lineares, quando se elimina um bloco
de variáveis. Por exemplo, considere o sistema
¸· ¸ · ¸
·
b1
x
A B
=
y
B0 C
b2
Assumindo det(A) 6= 0, da primeira equação tem-se Ax + By = b1, e portanto x = −A−1By +
A−1b1. Substituindo na segunda equação, tem-se (C − B0A−1B)y = b2 − B0A−1b1 e portanto
y = (C − B0A−1B)−1(b2 − B0A−1b1) = −(C − B0A−1B)−1B0A−1b1 + (C − B0A−1B)−1b2
Substituindo agora y na primeira equação, tem-se
x = (A−1 + A−1B(C − B0A−1B)−1B0A−1)b1 − A−1B(C − B0A−1B)−1b2
As expressões para x e y podem também ser obtidas da formula da inversa para uma matriz
simétrica particionada em blocos:
¸−1 · −1
¸
·
−1
0 −1 −1 0 −1
−1
0 −1 −1
+
A
B(C
−
B
A
B)
B
A
−A
B(C
−
B
A
B)
A
B
A
=
X −1 =
−(C − B0A−1B)−1B0A−1
(C − B0A−1B)−1
B0 C
; o complemento de Schur é a inversa da matriz do bloco (2, 2) em X −1
introLMI
10/17
Profs. Pedro/Sophie
• O complemento de Schur surge também na minimização de uma forma quadrática em relação
a algumas das variáveis. Por exemplo,
¸· ¸
· ¸0 ·
x
x
A B
= min x0Ax + x0By + y0B0x + y0Cy = min x0Ax + 2y0 B0x + y0Cy
min
0
x
x
x
y
y
B C
; Supondo A > 0 e impondo que a derivada parcial da função em relação a x vale zero, tem-se
2(Ax + By) = 0, e portanto x = −A−1By. Substituindo na função, tem-se
¸· ¸
· ¸0 ·
x
x
A B
min
= y0(C − B0A−1B)y
0
x
y
y
B C
• Caracterização da positividade de X
; X > 0 se e somente se A > 0 e C − B0A−1B > 0
; Se A > 0, X ≥ 0 se e somente se C − B0A−1B ≥ 0
introLMI
11/17
Profs. Pedro/Sophie
Complemento de Schur
Definindo T =
·
¸
I A−1B
, tem-se
0 I
Como T é uma matriz não singular:
·
·
A B
B0 C
A B
B0 C
¸
¸
= T0
>0
·
¸
A
0
T
0 C − B0A−1B
⇐⇒
·
A
0
0 C − B0A−1B
¸
>0
• T não singular define uma transformação de congruência. Duas matrizes simétricas
A, B ∈ Rn×n são congruentes se existir T ∈ Rn×n não singular tal que A = T 0BT . Se A e B são
congruentes, então A > 0 se e somente se B > 0.
Prova: B > 0 ⇒ ∀x 6= 0, x0Bx > 0. Definindo y = T −1x, tem-se x0Bx = y0T 0BTy = y0Ay > 0,
∀y 6= 0 ⇒ A > 0.
; Se T ∈ Rn×m , A > 0 ⇒ T 0AT ≥ 0. Como o rank de T 0AT é igual ao rank de T , A > 0 ⇒
T 0AT > 0 se e somente se o rank de T for igual a m.
; Generalização da transformação de congruência com T ∈ R n×m : A > 0 ⇒ T 0AT ≥ 0 mas
T 0AT > 0 6⇒ A > 0. Por exemplo,
¸
·
¸· ¸
·
£
¤ 1 0
1 0
1
= 1 > 0 , mas
é indefinida
1 0
0 −1
0
0 −1
introLMI
12/17
Profs. Pedro/Sophie
• Funcionais afins
Um funcional f (·) = f (·)0 é afim se, para matrizes quaisquer X,Y e escalares α1, α2 ∈ R,
f (α1X + α2Y ) = α1 f (X) + α2 f (Y )
; Funcionais afins definem conjuntos convexos
{X : f (X) ≥ 0} ; {X : f (X) > 0} ; {X : f (X) ≤ 0} ; {X : f (X) < 0}
; f (X) ≥ 0, f (X) ≤ 0, f (X) > 0 e f (X) < 0 são desigualdades matriciais lineares, ou Linear
Matrix Inequalities — LMIs
; Exemplos
A0X + XA + Q ≤ 0 ; A0XA − X + Q < 0 ;
introLMI
·
0
X AX
XA X
¸
>0
13/17
Profs. Pedro/Sophie
• Desigualdades Matriciais Lineares — LMIs
; Convexidade
; Existem programas computacionais especializados (algorimos convergem em tempo polinomial) na resolução de LMIs: LMI Control Toolbox (Matlab), Lmitool (Matlab e Scilab),
SeDuMi, LMI Solver
; Inúmeros problemas de controle podem ser formulados como LMIs
; Outras aplicações (mecânica, otimização, etc.)
; Formular um problema em termos de LMIs equivale a resolver o problema!
• Lyapunov, 1890. A equação diferencial ẋ = Ax é estável (trajetórias iniciando em qualquer
ponto convergem para x = 0) se e somente se existir P = P0 tal que
P>0 ;
introLMI
A0P + PA < 0
14/17
Profs. Pedro/Sophie
• Desigualdades Matriciais Lineares — LMIs
; Empilhando as variáveis de decisão (incógnitas) em um único vetor x ∈ R m, pode-se reescrever uma LMI na forma
F(x) , F0 + x1F1 + · · · + xmFm > 0
com Fi ∈ Rn×n , i = 0, . . . , m matrizes contantes simétricas. Note que F(x) > 0 significa que
F(x) deve ser definida positiva para todo x, ou seja, y0F(x)y > 0 para todo vetor y 6= 0.
; A LMI F(x) > 0 é equivalente a um conjunto de n desigualdades polinomiais em x, obtidas
impondo-se que os menores principais lı́deres de F(x) devem ser todos positivos.
; A LMI F(x) > 0 é uma restrição convexa, isto é, o conjunto
n
o
x : F(x) > 0
é um conjunto convexo.
introLMI
15/17
Profs. Pedro/Sophie
• Exemplo
X=
·
x1 x2
x2 x3
¸
=
¸
·
¸
·
¸
·
0 1
0 0
1 0
x1 +
x2 +
x >0
1 0
0 1 3
0 0
| {z }
| {z }
| {z }
F1
F2
F3
A0X + XA = (A0F1 + F1A)x1 + (A0F2 + F2A)x2 + (A0F3 + F3A)x3 < 0
; Note que X > 0 equivale às restrições x1 > 0, x3 > 0 e x1x3 > x22 (não-linear!)
; X > 0 pode também ser expressa como um número infinito de restrições lineares do tipo
a0ix ≤ bi, pois X > 0 ⇔ z0Xz > 0, ∀z ∈ Rn . Escolhendo por exemplo
· ¸
· ¸
· ¸
1
0
1
; z2 =
; z3 =
z1 =
0
1
1
e impondo z0iXzi > 0, chegam-se respectivamente às restrições
x1 > 0 ; x3 > 0 ; x1 + 2x2 + x3 > 0
introLMI
16/17
Profs. Pedro/Sophie
• Desigualdades convexas podem ser convertidas em LMIs através do complemento de Schur.
¸
·
Q(X) S(X)
> 0 ⇐⇒ R(X) > 0 , Q(X) − S(X)R(X)−1S(X)0 > 0
0
S(X) R(X)
; Exemplo: A restrição sobre a norma da matriz kM(X)k < 1 (máximo valor singular), com
M(X) ∈ R p×q dependendo de maneira afim em X, pode ser escrita como a LMI
¸
·
I p M(X)
>0
M(X)0 Iq
pois kMk < 1 equivale a I p − MM 0 > 0. O caso q = 1 reduz-se a uma desigualdade quadrática
convencional em x.
; Exemplo: A restrição c(X)0P(X)−1c(X) < 1, P(X) > 0, com c(X) ∈ Rn e P(X) = P(X)0 ∈
Rn×n dependendo de maneira afim em X, pode ser expressa em termos da LMI
¸
·
P(X) c(X)
>0
c(X)0 1
introLMI
17/17