Matematisk diskusjon og forklaring

na qual o conservadorismo pode ser reduzido pelo aumento do grau do polinômio com correspondente aumento do esforço computacional. A idéia do procedimento a ser apresentado na próxima seção é o de reduzir o conservadorismo da condição suficiente LMI pela partição do politopo. Com isso, será mostrado que é possível resolver o problema de determinação da _{D-estabilidade robusta aplicando} formulações LMI menos complexas de forma mais eficiente que formulações LMI mais complexas.

3.3

Novo método de análise de

_{D-estabilidade robusta}

3.3.1

Descrição do procedimento proposto

Seja _{LMI(P) a função que implementa o problema de factibilidade com restrições LMI que}

caracteriza a_{D-estabilidade robusta, na qual o politopo P é representado por seu conjunto de vértices}

{A1, . . . , AN}. Dado um problema de factibilidade na forma L(x) ≺ 0, no qual x é o vetor de

variáveis de decisão,_{LMI(P) soluciona o problema convexo auxiliar: minimize t sujeito à L(x) ≺}

tI. Esta função retorna o escalar tmin obtido pelo problema de minimização. O problema é factível

se e somente setmin ≤ 0.

No procedimento de análise de_{D-estabilidade robusta apresentado a seguir, a idéia básica é dividir} o politopo e subpolitopos até que uma das seguintes condições de parada seja atendida:

• o politopo ou todos os subpolitopos obtidos pelas subdivisões atendam à condição suficiente de

D-estabilidade robusta;

• ou seja identificado um sistema correspondente a um vértice do politopo ou subpolitopos que não seja_D-estável;

• ou seja atingido o número máximo de iterações permitido.

Para escolher qual subpolitopo deva ser subdividido, pode ser utilizada a informação a respeito dos pólos do sistema nos vértices do politopo ou de forma mais simples, o valor de tmin retornado

pela função_{LMI(P). Foi adotada a segunda opção pela simplicidade e por ter o mesmo efeito da} primeira opção na maioria dos testes realizados.

No procedimento apresentado na seqüência,α pode representar ˆθ ou p, Ω pode representar ΩM ou

Ωp, o conjuntoL contém os simplexos cuja condição suficiente de estabilidade robusta não é atendida

(problema de factibilidade não possui solução), α(k) representa as coordenadas (ˆθ ou p) do k-ésimo

vértice do politopo_{P ou dos subpolitopos S e α}(u), se não for vazio, contém as coordenadas (ˆθ ou p)

Procedimento de Análise de_{D-Estabilidade Robusta} Passo 1. Inicialize_{L ← ∅, α}(u) ← ∅.

Passo 2. Computetmin =LMI(P). Se tmin ≤ 0, então vá para o passo 9.

Passo 3. Verifique se todos os vértices de _{P, A(α}(k)), são D-estáveis. Se existe i, k tal que

λi(A(α(k)))6∈ D, então faça α(u) ← α(k)e vá para o passo 9.

Passo 4. Se_{P é um simplexo, então faça L ← P, senão aplique a triangularização de Delaunay para}

decompor_{P em um conjunto de simplexos S = {S}1, . . . ,Sr} e vá para o passo 8.

Passo 5. Encontre o simplexo_Sm ∈ L com maior valor de tmin.

Passo 6. Gere os novos vérticesA(α(j)) sobre as arestas deSm requeridos pela técnica de divisão

orientada pelas arestas. Se existei, j tal que λi(A(α(j)))6∈ D, então faça α(u) ← α(j)e vá para

o passo 9.

Passo 7. Particione _Sm no conjunto de simplexos S = {S1, . . . ,Sr} usando a técnica de divisão

orientada pelas arestas e exclua_Sm deL.

Passo 8. Para todo_Si ∈ S, se tmin =LMI(Si) > 0, entãoL ← L ∪ Si.

Passo 9. Se_{L 6= ∅ e α}(u) =∅, então vá para o passo 5, senão finalize.

Ao fim do procedimento de análise proposto, se _{L e α}(u) são vazios, então o sistema incerto é

robustamente_{D-estável, senão α(u)}contém a coordenada do primeiro caso encontrado de sistema no politipo_{P que não é D-estável.}

Para que o procedimento proposto seja eficiente, é necessário uma escolha adequada da condição suficiente LMI para implementar a função_{LMI(P). Como será visto nos exemplos ilustrativos que} serão apresentados, tal escolha deverá levar em consideração o compromisso entre complexidade e conservadorismo.

Comentário 3.1 Ao invés de verificar todas as restrições de posicionamento de pólos simultanea- mente, nesta tese é adotada a estratégia de se verificar o posicionamento de pólos em cada região individualmente. Nota-se que é mais eficiente verificar uma região de cada vez. Os problemas de factibilidade envolvendo todas as restrições simultaneamente são muito mais complexos de serem resolvidos, envolvendo um número maior de variáveis de otimização e de restrições. Além disso, tra- tando de várias regiões simultaneamente, as formulações LMI consideradas são tais que as mesmas funções de Lyapunov devem atender às diferentes restrições, o que é uma restrição adicional desne- cessária. A verificação individual de cada região também possibilita a escolha da formulação mais adequada para cada tipo de região.

3.3 Novo método de análise de_{D-estabilidade robusta} 34

3.3.2

Complexidade do procedimento de análise proposto

A partição do espaço de incertezaΩ é realizada pelo procedimento descrito no Capítulo. 2. Con-

sidere um domínio de incerteza Ω no espaço d-dimensional com N vértices. O passo inicial do

procedimento proposto requer a verificação de uma condição suficiente LMI de _{D-estabilidade ro-} busta de um politopo_{P com N vértices e a verificação da localização de n autovalores de N sistemas} para testar se existeλi(A(α(j))) 6∈ D, para i = 1, . . . , n e j = 1, . . . , N. Caso o politopo inicial não

seja um simplexo, na primeira iteração é realizada a decomposição do politopo em um conjunto de simplexos. A Tabela 3.1 apresenta o número de simplexos gerados pela triangularização de Delau- nay considerando um hipercubo no espaçod_{−dimensional, que corresponde ao número de condições}

LMI que devem ser testadas de politopos comd+1 vértices. Neste caso não é necessária a verificação

de autovalores desde que não são incluídos novos vértices para a formação do conjunto de simplexos. No caso em que o politopo inicial já é um simplexo e nas iterações subseqüentes à triangularização, é empregada a divisão de simplexo orientada pelas arestas descrita na Seção 2.5, parak = 2. Com esta

técnica de subdivisão de simplexo, a cada iteração é necessário verificar osn autovalores de 1₂(d+1)d

sistemas, correspondentes aos novos vértices sobre cada aresta, e2d_{condições LMI de politopos com}

d + 1 vértices, conforme apresentado na Tabela 3.2.

No caso de modelos por dependência afim de parâmetros, uma vantagem significativa da decom- posição do hiper-retângulo em simplexos, que diferencia o presente trabalho de resultados anteriores de aplicação de algoritmos tipo branch-and-bound, é a significativa redução do número de vértices dos politopos a serem testados. Considere, por exemplo, um sistema comd = 5 parâmetros incertos

que podem assumir valores em um intervalo conhecido. Neste casoΩ∈ R5_{é um hiper-retângulo com}

N = 2d _{= 32 vértices. Trabalhando com simplexos, os subpolitopos passam a ter N = d + 1 = 6}

vértices. Esta diferença no número de vértices significa uma redução considerável no tempo compu- tacional requerido pela função_{LMI(P) que testa a condição suficiente LMI.}

Tabela 3.1: Número de simplexos gerados pela triangularização de Delaunay de um hipercubo.

Dimensãod 2 3 4 5 6 7

Número de simplexos 2 6 24 103 648 3642

Como discutido na Seção 2.4, uma opção mais simples de divisão do simplexo seria a técnica de bisseção com a subdivisão do simplexo ao meio com a inclusão de um novo vértice sobre a maior aresta. Com esta técnica, independente da dimensão do espaço de incerteza, a cada iteração, são necessários verificar os autovalores de apenas um sistema e verificar a condição LMI para apenas dois politopos. Apesar da simplicidade, tal técnica pode resultar em um tempo de processamento total maior sem garantia de convergência para espaços de maiores dimensões.

Tabela 3.2: Número de novos vértices e de sub-simplexos obtidos com a subdivisão de simplexo orientada pelas arestas.

Dimensãod 1 2 3 4 5 6 7 d

Novos vértices 1 3 6 10 15 21 28 (d + 1)d/2

Número de sub-simplexos 2 4 8 16 32 64 128 2d

Mais detalhes sobre o algoritmo proposto de divisão de simplexo, com exemplo de implementação pelo MATLABr, são apresentados em Gonçalves, Palhares, Takahashi e Mesquita (2006a).