Introdução às LMIs - DT - Home Page
Transcrição
Introdução às LMIs - DT - Home Page
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 combinação descreve o segmento de reta entre x1 e x2. x1 PSfrag replacements x2 introLMI 1/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Um conjunto C é convexo se o segmento de reta entre dois pontos quaisquer do conjunto estiver em C , isto é, para quaisquer x1, x2 ∈ C e α ∈ [0, 1], αx1 + (1 − α)x2 ∈ C PSfrag replacements Convexo Convexo Não convexo ; Um conjunto C é um cone se para todo x ∈ C e α ≥ 0, αx ∈ C . ; Um cone convexo é um conjunto C tal que, para todo x1, x2 ∈ C e α1, α2 ≥ 0, α1 x 1 + α 2 x 2 ∈ C introLMI 2/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Um hiperplano é um conjunto na forma {x : c0x = b} para c 6= 0 ∈ Rn e b ∈ R. Um hiperplano divide o Rn em dois semi-espaços, {x : c0x ≤ b} e {x : c0x ≥ b}. ; Hiperplano separador introLMI ; Hiperplano suporte 3/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • O envelope convexo de um conjunto de N pontos x1, x2, . . . , xN no R2 é um poliedro. Um ponto descrito como α1x1 +α2x2 +· · ·+αN xN , com αi ≥ 0, i = 1, . . . , N e α1 +α2 +· · ·+αN = 1, é chamado de combinação convexa dos pontos x1, x2, . . . , xN . Um conjunto é convexo se e somente se contiver toda combinação convexa de seus pontos. ; Matrizes simétricas X = X 0 ∈ Rn×n definem um espaço vetorial de dimensão n(n + 1)/2. ; O conjunto das matrizes simétricas semidefinidas positivas é um cone convexo, pois se α1, α2 ≥ 0 e X1 > 0, X2 > 0, então α1X1 + α2X2 também é uma matriz simétrica semidefinida positiva. introLMI 4/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Uma função f : Rn → R é linear se para todo α1, α2 ∈ R e x1, x2 pertencentes ao domı́nio da função, f (α1x1 + α2x2) = α1 f (x1) + α2 f (x2) • Uma função f : Rn → R é convexa se seu domı́nio for um conjunto convexo e, para quaisquer x1, x2 pertencentes ao domı́nio da funçã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)) está sempre acima ou sobre o gráfico da função. x2 PSfrag replacements x1 introLMI 5/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Suponha f (·) diferenciável. Então, f é 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) é o gradiente da função calculado no ponto x, e a função afim em y dada por f (x) + ∇ f (x)0(y − x) é a aproximação de primeira ordem de Taylor da função f na vizinhança de x. f (y) PSfrag replacements f (x) f (x) + ∇ f (x)0 (y − x) x introLMI y 6/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie ; Para uma função convexa, a aproximação de primeira ordem está sempre abaixo do valor da função e, se a aproximação de primeira ordem estiver sempre abaixo do valor da função, a função é convexa. ; Se a função for convexa e ∇ f (x) = 0, então para todo y pertencente ao domı́nio da função tem-se f (y) ≥ f (x), e portanto x é um mı́nimo global de f . • A função f é 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 função f calculados no ponto x. Se a função for diferenciável, µ(x) = ∇(x) é único. Se f não for diferenciável em x, µ(x) é a inclinação de todos os hiperplanos suportes da função no ponto x. • A função f é côncava se − f for convexa. Se f é côncava e diferenciável em x, então f (y) ≤ f (x) + ∇ f (x)0(y − x) introLMI 7/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Considere a função f (W ) = λmin (W ) para matrizes W ∈ Rn×n simétricas definidas positivas. Pode-se mostrar que f (W ) é uma função côncava em relação aos elementos da matriz W . Note que f (W ) = λmin (W ) = min x0(W )x kxk=1 Considere uma matriz W0 > 0 qualquer. Então, f (W0) = λmin (W0 ) e W0 x0 = λmin (W0 )x0 para x0 autovetor associado ao autovalor λmin (W0 ). Entã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 é um subgradiente da função f (W ) calculado em W0. ; A restrição λmin (W ) ≥ ε, com ε > 0, define um conjunto convexo. introLMI 8/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Complemento de Schur ; Considere a matriz simétrica X particionada ¸ · A B X= B0 C com A = A0 ∈ Rn×n . Se det(A) 6= 0, a matriz C − B0A−1B é o complemento de Schur de X em relaçã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 é o complemento de Schur de X em relaçã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 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • O complemento de Schur surge na solução de equações lineares, quando se elimina um bloco de variáveis. Por exemplo, considere o sistema ¸· ¸ · ¸ · b1 x A B = y B0 C b2 Assumindo det(A) 6= 0, da primeira equação tem-se Ax + By = b1, e portanto x = −A−1By + A−1b1. Substituindo na segunda equaçã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 equação, tem-se x = (A−1 + A−1B(C − B0A−1B)−1B0A−1)b1 − A−1B(C − B0A−1B)−1b2 As expressões para x e y podem também ser obtidas da formula da inversa para uma matriz simé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 é a inversa da matriz do bloco (2, 2) em X −1 introLMI 10/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • O complemento de Schur surge também na minimização de uma forma quadrática em relação a algumas das variá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 função em relação a x vale zero, tem-se 2(Ax + By) = 0, e portanto x = −A−1By. Substituindo na função, tem-se ¸· ¸ · ¸0 · x x A B min = y0(C − B0A−1B)y 0 x y y B C • Caracterizaçã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 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie Complemento de Schur Definindo T = · ¸ I A−1B , tem-se 0 I Como T é uma matriz nã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 não singular define uma transformação de congruência. Duas matrizes simétricas A, B ∈ Rn×n são congruentes se existir T ∈ Rn×n não singular tal que A = T 0BT . Se A e B são congruentes, entã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 é igual ao rank de T , A > 0 ⇒ T 0AT > 0 se e somente se o rank de T for igual a m. ; Generalização da transformação de congruê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 é indefinida 1 0 0 −1 0 0 −1 introLMI 12/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Funcionais afins Um funcional f (·) = f (·)0 é 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 sã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 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Desigualdades Matriciais Lineares — LMIs ; Convexidade ; Existem programas computacionais especializados (algorimos convergem em tempo polinomial) na resolução de LMIs: LMI Control Toolbox (Matlab), Lmitool (Matlab e Scilab), SeDuMi, LMI Solver ; Inúmeros problemas de controle podem ser formulados como LMIs ; Outras aplicações (mecânica, otimização, etc.) ; Formular um problema em termos de LMIs equivale a resolver o problema! • Lyapunov, 1890. A equação diferencial ẋ = Ax é estável (trajetó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 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Desigualdades Matriciais Lineares — LMIs ; Empilhando as variáveis de decisão (incógnitas) em um ú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 simé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 é 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 é uma restrição convexa, isto é, o conjunto n o x : F(x) > 0 é um conjunto convexo. introLMI 15/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP 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 às restrições x1 > 0, x3 > 0 e x1x3 > x22 (não-linear!) ; X > 0 pode também ser expressa como um número infinito de restriçõ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 às restrições x1 > 0 ; x3 > 0 ; x1 + 2x2 + x3 > 0 introLMI 16/17 IA360E - Tópicos em Controle I - FEEC/UNICAMP Profs. Pedro/Sophie • Desigualdades convexas podem ser convertidas em LMIs atravé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 restrição sobre a norma da matriz kM(X)k < 1 (má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 quadrática convencional em x. ; Exemplo: A restriçã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
Documentos relacionados
• Estabilidade Robusta O sistema linear x(k+1 - DT
max |λi(A(α))| < 1 ; i = 1, . . . , n ∀A(α) ∈ A i
Leia maisCritério de Routh-Hurwitz A BIBO estabilidade de um sistema está
função ı́mpar ou uma função par em s, por exemplo, f (s), e D(s) pode ser fatorado na forma f (s)D̄(s). Como nem todas as raı́zes de uma função par ou de uma função ı́mpar podem ter parte r...
Leia mais