método de euler e método pseudoespectral usando pontos

KARLA CRISTIANE ARSIE
MÉTODO DE EULER E MÉTODO PSEUDOESPECTRAL
USANDO PONTOS LEGENDRE GAUSS RADAU PARA
UMA CLASSE DE PROBLEMAS DE CONTROLE ÓTIMO
Curitiba
2013
KARLA CRISTIANE ARSIE
MÉTODO DE EULER E MÉTODO PSEUDOESPECTRAL
USANDO PONTOS LEGENDRE GAUSS RADAU PARA
UMA CLASSE DE PROBLEMAS DE CONTROLE ÓTIMO
Dissertação apresentada ao Programa de PósGraduação em Matemática Aplicada da Universidade Federal do Paraná, como requisito
parcial à obtenção do grau de Mestre em Matemática Aplicada.
Orientadora: Dr.a Elizabeth Wegner Karas.
Coorientador: Dr. Miguel A. Dumett Canales.
Curitiba
2013
iii
iv
v
Agradecimentos
Agradeço primeiramente à minha famı́lia, pelo apoio,
compreensão, ajuda e por todo carinho ao longo deste percurso.
Amo vocês.
Ao meu noivo Rodrigo, que esteve sempre ao meu lado, que me
apoiou, incentivou, ajudou e participou comigo dos momentos de
angústias e alegrias. Neoqeav.
Aos meus amigos, especialmente Izabela, Janaina, Keilla,
Leonardo e Priscila, pela ajuda e pelo carinho.
Agradeço aos meus orientadores Elizabeth e Miguel, pelas
orientações, conversas, por estarem sempre dispostos a me ajudar.
Obrigada pelo esforço, tempo dedicado e por sempre acreditarem
no meu trabalho.
Aos membros da banca, professores Dr. Antonio Carlos Gardel
Leitão, Dr. Saulo Pomponet Oliveira e Dr.a Ailin Ruiz Zarate
Fabregas obrigada por aceitarem fazer parte deste momento e dar
suas contribuições valiosas.
Ao Programa de Pós-Graduação em Matemática Aplicada da
UFPR pela oportunidade e formação de qualidade propiciada.
A CAPES pelo apoio financeiro.
E finalmente, mas não menos importante, a Deus pela capacitação
concedida, pela força espiritual e por seguir ao meu lado.
vi
“ A mente que se abre a uma nova ideia jamais
voltará ao seu tamanho original.”
Albert Einstein
vii
Resumo
O objetivo deste trabalho é discutir o método pseudoespectral com pontos
de colocação de Legendre-Gauss-Radau (LGR) apresentado em [22], para
determinar soluções numéricas de algumas classes de problemas de controle ótimo. Nesta dissertação revisa-se [22], e se deriva a discretização do
método pseudoespectral LGR, de problemas de controle ótimo (sem restrições nas variáveis de estado e de controle) utilizando notação tensorial.
Adicionalmente se derivam as condições de otimalidade de Karush-KuhnTucker (KKT) associadas ao problema.
Para avaliar a precisão do método em problemas de controle ótimo especı́ficos, é necessário conhecer a solução exata dos problemas escolhidos.
Procurando replicar os resultados em [22], trabalhou-se num primeiro exemplo com um Problema de Bolza (tipo LQR) sem restrições nas variáveis de
estado e de controle. Se apresenta uma derivação detalhada da solução exata
deste problema quadrático, utilizando o Princı́pio do Máximo de Pontryagin. O problema de minimização resultante foi resolvido através da rotina
quadprog do MATLAB. A precisão do método pseudoespectral LGR é comparada, com bons resultados, com o método de Euler (aplicado ao problema
de otimização quadrático produto da discretização por Euler do problema
de Bolza tipo LQR original).
Para evidenciar que o método pseudoespectral LGR de discretização pode
ser aplicado a problemas de controle ótimo com restrições nas variáveis de
controle e de estado (o que não é abordado em [22]), dois exemplos adicionais, apresentados em [31], são discutidos nesta dissertação. No segundo
exemplo a função custo é não quadrática e a rotina fmincon do MATLAB é
encarregada de fazer o trabalho de otimização a partir das equações discretizadas pelo método pseudoespectral LGR. No terceiro exemplo, o problema
de otimizção foi resolvido pela rotina quadprog. Existem poucos problemas
nao-lineares de controle ótimo (com restrições) cujas soluções exatas são conhecidas. Usualmente argumentos de convexidade e outros, são necessários
para encontrar as soluções exatas.
Palavras-chave: Controle ótimo; problema tipo Bolza; método pseudoespectral; pontos de colocação LGR; método de Euler.
viii
Abstract
The goal of this work is to present the details of the Legendre-Gauss-Radau
(LGR) pseudoespectral numerical method. This method was published in
[22] and it is utilized to find numerical solutions of certain classes of optimal
control problem. In this dissertation, we review [22], and derive the discretization of the LGR pseudoespectral method of optimal control problems
(without restrictions in the state and control variables) using tensorial notation. In adition, the associated Karush-Kuhn-Tucker (KKT) optimality
conditions are derived. To assess the accuracy of the LGR method in specific
optimal control problems, it is necessary to know the exact solution of the
selected problems. Aiming to replicate the results in [22], we worked initially
a Bolza problem (LQR type) without restrictions in the state and control
variables. The process of finding the exact solution of this quadratic problem is derived in detail, utilizing the Pontryagin Maximum Principle. The
LGR pseudoespectral discretization technique was successful when applied
to the Bolza problem without restrictions. The corresponding MATLAB
code is included in the Appendix, and utilizes mainly the quadprog routine.
The accuracy of the LGR pseudoespectral method is compared successfully
against Euler method (applied to the quadratic optimization problem which
is obtained from the forward Euler discretization of the LQR type original
Bolza problem). To point out that the LGR pseudoespectral discretization
method could be applied to optimal control problems with restrictions in the
state and control variables (something not attempted in [22]), and outside of
the Bolza problem class, two additional examples from [31] are presented in
this dissertation. There are few non-linear optimal control problems (with
restrictions) whose exact solutions are known. Usually, convexity arguments
and others, are necessary to find the exact solutions.
Palavras-chave: Optimal control; Bolza problem; pseudoespectral method;
LGR collocation points; Euler method.
ix
Sumário
Introdução
1
1 O problema de Controle Ótimo
1.1 Princı́pio do Máximo de Pontryagin . . . . . . . . . . . . . . . .
1.2 Método Pseudoespectral usando Pontos Legendre Gauss Radau
1.2.1 Fundamentação . . . . . . . . . . . . . . . . . . . . . . .
1.2.2 Discretização do problema . . . . . . . . . . . . . . . . .
1.2.3 Condições de Karush-Kuhn-Tucker . . . . . . . . . . . .
1.2.4 Sistema Adjunto Transformado . . . . . . . . . . . . . .
1.2.5 Formulação Integral . . . . . . . . . . . . . . . . . . . . .
1.3 Método de Euler . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4 Outros métodos . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.4.1 Comparação com o método de Kameswaran e Biegler . .
1.4.2 Comparação com o método de Fahroo e Ross . . . . . .
1.5 Problema de Bolza . . . . . . . . . . . . . . . . . . . . . . . . .
2 Exemplos
2.1 Exemplo 1 . . . . . . . . . . . .
2.1.1 Solução Exata . . . . . .
2.1.2 Solução aproximada pelo
2.1.3 Solução aproximada pelo
2.2 Exemplo 2 . . . . . . . . . . . .
2.2.1 Solução aproximada pelo
2.3 Exemplo 3 . . . . . . . . . . . .
2.3.1 Solução aproximada pelo
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
método pseudoespectral
método de Euler . . . .
. . . . . . . . . . . . . .
método pseudoespectral
. . . . . . . . . . . . . .
método pseudoespectral
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
4
5
6
7
10
12
15
18
20
21
21
22
23
.
.
.
.
.
.
.
.
24
24
25
28
30
35
35
37
38
Conclusão
41
Apêndices
42
A Revisão de Conceitos
42
A.1 Matriz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
A.1.1 Produto direto de Matrizes . . . . . . . . . . . . . . . . . . . . . . . 42
x
A.1.2 Exponencial de matriz . . . . . . .
A.2 Solução de um sistema de EDOs . . . . . .
A.3 Tópicos de otimização contı́nua . . . . . .
A.3.1 Método de gradientes conjugados .
A.3.2 O Teorema de Karush-Kuhn-Tucker
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
43
45
46
47
49
B Códigos em Matlab
52
Referências Bibliográficas
67
xi
Introdução
O objetivo da teoria de controle ótimo é determinar o controle, que fará com que
um sistema satisfaça um conjunto de restrições fı́sicas e ao mesmo tempo minimize algum
critério de desempenho. Normalmente, os problemas de controle ótimo têm restrições
nas variáveis de estado e de controle. As soluções para problemas de controle ótimo
(sem restrições) podem ser encontradas, por exemplo, através da aplicação do cálculo
variacional ([11, 20, 31]) e da aplicação do Princı́pio do Máximo de Prontryagin ([11, 18]).
Em [11] se faz uma analogia entre problemas de controle ótimo e os problemas do cálculo
de variações, mostra-se também uma estratégia de como o Princı́pio do Máximo pode, em
alguns casos, ser utilizado para efetivamente determinar uma solução de um determinado
problema de controle ótimo. Porém, em [31, Cap. 10], se menciona que em geral não é
uma boa ideia trabalhar com a estratégia antes mencionada, pois ela se baseia em definir
U = Y 0 e trabalhar com a variável estado estendida W = (Y, U ), nos problemas de
cálculo de variações para tentar encontrar as soluções de problemas de controle ótimo. A
dificuldade principal está no fato que Y 0 é conhecida explicitamente, mas U 0 não é. Várias
técnicas foram desenvolvidas para resolver os problemas de controle ótimo. Estes métodos
numéricos são divididos em duas categorias: métodos indiretos e métodos diretos [3, 17].
Os métodos indiretos consistem em converter o problema de otimização em um
sistema de equações algébrico-diferenciais de valor no contorno a partir da aplicação do
Princı́pio do Máximo de Pontryagin. A principal vantagem desse método é a alta precisão e
garantias de soluções que satisfazem as condições necessárias de otimalidade. No entanto,
há uma desvantagem significativa. As condições necessárias de otimalidade devem ser
encontradas analiticamente, e para a maioria dos problemas esta busca não é trivial.
Os métodos diretos utilizam a parametrização na variável de controle ou a parametrização nas variáveis de estado seguida da solução do problema de programação nãolinear resultante. Nestes métodos polinômios podem ser usados para aproximar a equações
diferenciais em pontos de colocação ([4, 24, 28]). Estas técnicas baseiam-se em métodos
pseudoespectrais que consistem em encontrar soluções numéricas de equações diferenciais.
Métodos pseudoespectrais são uma classe de métodos de colocação direta, onde o problema de controle ótimo é transcrito para um problema de programação não-linear através
de uma parametrização do estado e do controle utilizando polinômios de Legendre ou
Chebyshev em conjunto com pontos de colocação. Tal problema de programação nãolinear pode então ser resolvido com uso de algoritmos de Otimização para obter soluções
Introdução
2
aproximadas localmente ótimas.
Neste trabalho aborda-se um método pseudoespectral que consiste na parametrização do estado e do controle utilizando polinômios de Legendre em conjunto com
a discretização utilizando pontos de colocação LGR. O método fornece, também, uma
maneira precisa de encontrar as condições de otimalidade de KKT associadas ao problema. Mostra-se que o método apresentado está relacionado a método de integração
global implı́cita. Isto é feito provando que a inversa da matriz de diferenciação obtida
no método pseudoespectral coincide com a matriz associada a um método de integração
global implı́cito [16].
Este trabalho está organizado da seguinte forma. No Capı́tulo 1, se apresenta brevemente o que é um problema de controle ótimo (sem restrições) e se enuncia o resultado
fundamental da teoria de controle ótimo, o teorema do Princı́pio do Máximo de Pontryagin. Em seguida, se apresenta o método pseudoespectral LGR, seguindo a sequência
estabelecida em [22], mas com demonstrações diferenciadas das encontradas nessa referência. Adicionalmente se menciona o método de Euler e se apresenta o problema de
Bolza.
O Capı́tulo 2 inicia especificando o tipo LQR do problema de Bolza e encontrando
a solução exata desse problema utilizando o Princı́pio do Máximo de Pontryagin. Logo, a
discretização pseudoespectral LGR é utilizada para encontrar uma solução numérica do
problema de Bolza LQR. A precisão do método é comparada com a precisão do método
de Euler aplicado ao mesmo problema de Bolza sem restrições. Os códigos MATLAB
necessários para construir os pontos de colocação LGR e para calcular os pesos de quadratura da discretização pseudoespectral LGR, assim como também a chamada da rotina
QUADPROG, para encontrar explicitamente, as soluções numéricas do estado e do controle do problema de Bolza, são apresentados no Apêndice da dissertação.
Adicionalmente, são incluı́dos dois problemas de controle ótimo com restrições
não-lineares, para testar a discretização pseudoespectral LGR (isto não é feito em [22])
Ambos os problemas, com suas respectivas soluções exatas, são apresentados em [31, Cap.
10]. O método pseudoespectral LGR é bem sucedido em encontrar uma solução numérica.
Os códigos em MATLAB correspondentes são dados no Apêndice da dissertação e estarão
disponı́veis no site da pós-graduação em Matemática Aplicada.
Finalmente, nos Apêndices apresentam-se alguns resultados básicos da teoria
abordada no trabalho, bem como os códigos implementados em Matlab para resolver
numericamente os exemplos discutidos.
Introdução
3
Notação.
xT
k.k∞
k.k
ẋ, x0
ẋj (τ )
hx, yi
ej
AT
Ak
diag(α1 , . . . , αn )
AB
∇f
∇φ
C(I)
ˆ
C(I)
C 1 (I)
Cˆ1 (I)
transposto do vetor x
norma infinito
norma 2
derivada de x
derivada da j-ésima componente de x em relação a τ
produto interno de x por y
vetor canônico com 1 na componente j e as demais componentes nulas
transposta da matriz A
k-ésima linha da matriz A
matriz diagonal quadrada cujos elementos da diagonal são α1 , . . . , αn
multiplicação da matriz A pela matriz B
gradiente da função f : IRn → IR. A mesma notação será adotada
para indicar a matriz m × n cuja i-ésima linha é ∇fi , quando
f : IRn → IRm
.
matriz m × n cujo elemento (i, j) é (∇φ(X))ij = ∂φ(X)
∂Xij
Aqui φ : IRm×n → IR e X ∈ IRm×n
Espaço das funções contı́nuas em I.
Espaço das funções contı́nuas por partes do intervalo I.
Espaço das funções continuamente diferenciáveis em I.
Espaço das funções continuamente diferenciáveis por partes no intervalo I.
Capı́tulo 1
O problema de Controle Ótimo
Um problema de controle ótimo consiste em minimizar um certo funcional que
depende de dois tipos de variáveis: variáveis de estado ou próprias (x ∈ IRn ) e variáveis
de controle (u ∈ IRm ). As duas variáveis estão parametrizadas por uma variável real
independente t, usualmente associada ao tempo, isto é, x = x(t), u = u(t). Formalmente
x ∈ Cˆ1 é uma função x : IR → IRn diferenciável por pedaços e u ∈ Cˆ é uma função
u : IR → IRm contı́nua por pedaços em cada intervalo de tempo. A variável de estado x(t)
obedece a uma dinâmica dada pela seguinte equação diferencial, denominada equação de
estado
ẋ(t) = f (x(t), u(t)),
(1.1)
onde f : IRn×m → IRn é uma função contı́nua. A variável de estado pode estar ainda
sujeita a condições x(t0 ) = x0 e x(tf ) = xf . A variável de controle u(t) é uma função que
pertence a um certo espaço de funções U, chamado o conjunto de controles admissı́veis.
Por exemplo, em [18] considera-se U = {u : [0, ∞) −→ IRm | u(.) é mensurável}.
No caso que (1.1) não depende de u, então (1.1) vira uma equação diferencial. É
conhecido que sob a condição de continuidade de f , o teorema de Peano [30] garante a
existência de soluções de (1.1). Adicionalmente, se a função f é localmente Lipschitziana
em x, o teorema de Picard[30] garante a existência de uma solução única de (1.1). Quando
a função u(t) é constante, em [30, Cap.2] encontram-se condições similares às de Peano e
Picard, para garantir existência e unicidade de soluções de (1.1).
Usualmente, o funcional a minimizar em um problema de controle ótimo é composto de dois termos: o primeiro deles depende do estado final x(tf ) e o segundo é da
forma
Z t
f
r(x(t), u(t))dt.
t0
Adicionalmente, são impostas restrições por desigualdade nas variáveis de estado
e de controle. Por exemplo, x(t) ≥ 0 e |u(t)| ≤ 1, para t0 ≤ t ≤ tf .
Condições gerais para existência e unicidade de um problema de controle ótimo
podem ser encontradas em [31]. Em geral, estas condições são do tipo f ∈ C 1 , r ∈ C 1 , x ∈
4
5
C 1 , u ∈ C 0 por partes. Neste trabalho assumimos a existência de uma única solução. Nos
exemplos a serem considerados no próximo capı́tulo, a solução exata é conhecida.
Em geral, encontrar analiticamente uma solução exata de um problema de controle ótimo com restrições é muito difı́cil e métodos numéricos são necessários. No entanto,
quando o problema de controle ótimo não tem restrições, o Princı́pio de Máximo de
Pontryagin é uma ferramenta muito útil para procurar soluções exatas.
Como em [22], considera-se o caso de problema de controle ótimo sem restrições
para apresentar a correspondente discretização pseudoespectral LGR.
Pode-se formular o problema de controle ótimo descrito acima, segundo [11], por
Rt
minimizar t0f r(x(t), u(t))dt
sujeito a u ∈ U
ẋ(t) = f (x(t), u(t))
x(t0 ) = x0
x(tf ) = xf .
(1.2)
No problema acima, os instantes de tempo inicial e final são dados (problema de
tempo fixo), porém, há problemas em que o tempo final é uma das incógnitas no problema
de controle ótimo (problemas de tempo livre) ou as vezes o tempo tf é dado mas xf (o
estado final) é desconhecido (problema de tempo fixo com estado final variável) [18]. Este
trabalho restringe-se nos problemas de tempo fixo. Para mais detalhes consultar [31] e
[11, Cap.10].
Neste capı́tulo será apresentado um dos principais resultados na teoria de controle ótimo, o Princı́pio do Máximo de Pontryagin, que neste trabalho será utilizado
para obter a solução exata de um problema de controle ótimo. Em seguida, para se
obter a solução aproximada deste problema, apresenta-se um método pseudoespectral,
que consiste na parametrização do estado e do controle utilizando polinômios de Legendre
em conjunto com a discretização com pontos de colocação LGR - Legendre Gauss Radau.
São discutidas as condições de otimalidade de Karush-Kuhn-Tucker (KKT) associadas ao
problema discretizado e mostra-se que este método pseudoespectral pode ser visto como
um método de integração global implı́cito. Por fim, apresenta-se o método de Euler, um
método alternativo, para obter uma solução aproximada.
1.1
Princı́pio do Máximo de Pontryagin
O princı́pio de Pontryagin estabelece um conjunto de condições para que uma
curva seja solução de um problema de controle ótimo. Esse princı́pio se expressa em
termos da função H : IRn × IRn × IRm → IR definida por
H(x, p, u) = hf (x, u), pi + r(x, u),
6
onde f : IRn × IRm → IRn , r : IRn × IRm → IR (as mesmas funções dadas no problema do
controle ótimo) e p ∈ IRn . Essa função é conhecida como Hamiltoniano de Pontryagin.
O teorema abaixo, que é baseado em [11, Teorema 178] e [18, Teorema 4.3], é
apresentado de uma forma conveniente para que, na obtenção da solução exata de um
problema de controle ótimo, se possa utilizá-lo diretamente.
Teorema 1.1 - Princı́pio do Máximo de Pontryagin Considere um sistema de controle ótimo, sendo u = ω(t) o controle e x = γ(t) a trajetória correspondente. Se
(γ(t), ω(t)) é uma solução ótima então existe uma função µ : [0, tf ] → IRn tal que, para
todo t ∈ [0, tf ] vale que:
• A curva p = µ(t) satisfaz
µ̇i = −
∂H
(γ(t), µ(t), ω(t)),
∂xi
• A trajetória x = γ(t) satisfaz
γ̇i = −
∂H
(γ(t), µ(t), ω(t)),
∂pi
• O controle u = ω(t) maximiza o Hamiltoniano, ou seja,
max H(γ(t), µ(t), u) = H(γ(t), µ(t), ω(t)).
u∈U
Demonstração. [11, Apêndice B].
Utiliza-se o princı́pio do máximo para determinar a solução de um problema.
1.2
Método Pseudoespectral usando Pontos Legendre Gauss Radau
Nesta seção estuda-se a formulação do método pseudoespectral usando pontos
LGR - Legendre Gauss Radau, proposto em [22] para resolver o problema de controle
ótimo (1.2). Inicialmente o problema é discretizado, tendo como referência [8]. Em
seguida, as condições de KKT são estabelecidas para o problema discretizado, seguindo
uma abordagem diferente, mas equivalente, à apresentada em [22]. Enquanto em [22] fazse o uso do Lagrangeano, aqui opta-se pela forma discutida no Apêndice A.3.2, ou seja,
encontram-se as condições de otimalidade relacionando o oposto do gradiente da função
objetivo com o gradiente das restrições do problema e da condição inicial com relação a
cada uma de suas variáveis. Cabe ressaltar que ambas as abordagens são equivalentes.
Por fim, mostra-se que a restrição do problema tem uma formulação equivalente através
7
de integrais, mostrando que este método pseudoespectral pode ser visto como um método
de integral global implı́cito.
1.2.1
Fundamentação
Pontos de colocação LGR
Um dos objetivos deste trabalho é discretizar um problema para que se possa
encontrar sua solução aproximada através de um método de colocação, que consiste em
encontrar a solução numérica de equações diferenciais ordinárias, equações diferenciais
parciais e equações integrais. A ideia é escolher um espaço de dimensão finita de soluções
canditadas, que são obtidas, geralmente, através de polinômios aplicados em uma quantidade de pontos no domı́nio, chamados de pontos de colocação. A discretização proposta
por [22] utiliza pontos de colocação Legendre-Gauss-Radau (LGR).
Além do conjunto de pontos de colocação LGR, outros dois conjuntos são apresentados em [22] e muito utilizados: Lengendre-Gauss(LG) e Legendre-Gauss-Lobatto(LGL).
Esses três conjuntos de pontos são obtidos a partir de raı́zes de um polinômio de Legendre
e\ou combinações lineares desses polinômios e suas derivadas.
O polinômio de Legendre de grau n, Pn , é dado por:
[n/2]
Pn (x) =
X
k=0
(−1)k
(2n − 2k)!
xn−2k ,
− k)!(n − 2k)!
2n k!(n
(1.3)
onde
 n

se n é par
2
[n/2] =
 n−1
se n é ı́mpar.
2
Há algumas relações entre os polinômios de Legendre Pn com valores de n consecutivos e também entre os Pn e suas derivadas. Estas relações de recorrência permitem
obter um novo Pn ou relacionar derivadas, a partir de outros. Apresentam-se a seguir
algumas destas relações de recorrência. Os detalhes podem ser consultados em [6]. A
primeira relação, bastante utilizada, permite obter um polinômio a partir de outros dois
de menor ordem,
nPn (u) = (2n − 1)uPn−1 (u) − (n − 1)Pn−2 (u).
(1.4)
A próxima, relaciona o polinômio e as derivadas de polinômios consecutivos
0
uPn0 (u) − Pn−1
= nPn (u).
(1.5)
Por fim, tem-se a relação de polinômio com a derivada de outros dois
0
0
(2n + 1)Pn (u) = Pn+1
(u) − Pn−1
(u).
(1.6)
8
Por (1.3), P0 (u) = 1 e P1 (u) = u. A relação (1.4) permite a obtenção rápida de
P2 (u) = 23 u2 − 21 , a seguir P3 (u) = 25 u3 − 32 u, e assim por diante. Geralmente, esse é o
processo usado em computação, para se evitar os fatoriais de ordem alta, sendo que estes
têm grande custo computacional.
A figura abaixo mostra os polinômios de Legendre de graus 0, 1, 2 e 3.
4
3
2
Solução
1
0
−1
−2
P0(u)
P1(u)
−3
P2(u)
P3(u)
−4
−1.5
−1
−0.5
0
t
0.5
1
1.5
Figura 1.1: Polinômios de Legendre Pn (u).
O conjunto de N pontos de colocação Legendre-Gauss-Radau (LGR), LengendreGauss(LG) e Legendre-Gauss-Lobatto(LGL) são definidos no domı́nio [−1, 1] como:
LG :
raı́zes de PN ;
LGR : raı́zes de PN −1 + PN ;
LGL : raı́zes de ṖN juntamente com os pontos − 1 e 1,
onde ṖN denota a derivada do polinômio de Legendre PN . Note que os pontos de LG
não incluem nenhum dos extremos do intervalo [−1, 1], os pontos LGR incluem um dos
seus extremos, e os pontos LGL incluem ambas as extremidades do intervalo. Outra diferença é que os pontos de LGR, ao contrário dos outros dois conjuntos, são relativamente
assimétricos em relação à origem. Neste trabalho concentra-se a atenção nos pontos LGR.
Forma de Lagrange do Polinômio de Interpolação
Interpolar uma função f consiste em aproximar essa função por uma outra função
g, escolhida entre uma classe de funções definida a priori e que satisfaça algumas propriedades. A necessidade de se fazer esta aproximação surge em várias situações, como por
exemplo, quando são conhecidos somente os valores numéricos da função f para um conjunto de pontos e é necessário calcular o valor da função em um ponto que não se saiba
seu valor ou ainda quando a função f tem uma expressão tal que operações como a diferenciação e a integração são difı́ceis, ou impossı́veis, de serem realizadas. Considera-se
9
aqui o caso de interpolação polinomial [27] ou seja em que a função é aproximada por um
polinômio.
Dados n pontos (x1 , f (x1 )), ..., (xn , f (xn )), o objetivo é aproximar f por um polinômio pn−1 , de grau menor ou igual a n − 1, tal que, para k = 1, 2, ..., n:
f (xk ) = pn−1 (xk ).
Teorema 1.2 Existe um único polinômio pn−1 , de grau menor ou igual a n − 1, tal que,
para k = 1, 2, ..., n
pn−1 (xk ) = f (xk ),
desde que xk 6= xj , j 6= k.
Demonstração. [27, Teo.8.1].
Considere que os n pontos x1 , . . . , xn pertencem a um intervalo (a, b). Considere f
contı́nua e sendo n vezes diferenciável nos n pontos no intervalo (a, b). Denote yi = f (xi )
para i = 1, . . . , n. Seja pn−1 o polinômio de grau menor ou igual a n − 1 que interpola
f em x1 , . . . , xn . Pode-se representar pn−1 na forma pn−1 (x) = y1 `1 (x) + ... + yn `n (x),
onde os polinômios `k são de grau n − 1. Para cada i, a condição pn−1 (xi ) = yi deve ser
satisfeita, ou seja
pn−1 (xi ) = y1 `1 (xi ) + ... + yn `n (xi ) = yi .
A forma mais simples de se satisfazer esta condição é impor
(
0 se k =
6 i
1 se k = i,
`k (xi ) =
e assim define-se `k (x) por
`k (x) =
n
Y
x − xj
xk − xj
j=1
j6=k
que satisfaz a condição acima. Como o numerador de `k (x) é um produto de n − 1 fatores,
então `k é um polinômio de grau n − 1 e além disso, para x = xi com i = 1, . . . , n tem-se
pn−1 (xi ) =
n
X
yk `k (xi ) = yi `i (xi ) = yi .
k=1
Então, a forma de Lagrange para o polinômio interpolador é
pn−1 (x) =
n
X
k=1
yk `k (x).
(1.7)
10
n
Y
x − xj
onde yk = f (xk ) e `k (x) =
.
xk − xj
j=1
j6=k
1.2.2
Discretização do problema
O objetivo aqui é discretizar o problema de controle ótimo (1.2), e para isto
utilizam-se os pontos de colocação LGR, que são pontos definidos no domı́nio [−1, 1],
como visto na Seção 1.2.1. Note que o problema (1.2) está definido em um intervalo [t0 , tf ],
o qual pode ser facilmente transformado no intervalo [−1, 1], através da transformação
afim
t0 + tf
tf − t0
τ+
,
(1.8)
t=
2
2
para t ∈ [t0 , tf ] e τ ∈ [−1, 1]. Derivando a igualdade (1.8) tem-se que
tf − t0
dt
=
,
dτ
2
e pela regra da cadeia,
dx
dx dτ
2 dx
=
=
.
dt
dτ dt
tf − t0 dτ
(1.9)
De (1.8) e (1.9), o problema (1.2) pode ser reescrito em função da nova variável da seguinte
forma
R1
minimizar −1 r(x(τ ), u(τ ))dτ
dx
tf − t0
sujeito a
=
f (x(τ ), u(τ ))
(1.10)
dτ
2
x(−1) = x0
x(1) = xf .
Discretização da condição diferencial
O intervalo [−1, 1] é discretizado considerando N pontos de colocação LGR,
τ1 , τ2 , · · · , τN ∈ [−1, 1], com τ1 = −1 e τN < 1, vistos na Seção 1.2.1.
Utilizando (1.7), a j-ésima componente de estado é aproximada por uma soma
da forma:
N
X
xj (τ ) ≈
xij `i (τ )
(1.11)
i=1
N
Y
τ − τm
, para i = 1, · · · , N, são polinômios de Lagrange. Derivando a
onde `i (τ ) =
τi − τm
m=1
j6=i
aproximação em relação a τ tem-se que
N
X d`i
dxj
(τ ) ≈
xij (τ ).
dτ
dτ
i=1
(1.12)
11
Avaliando (1.12) em τk e denotando `˙i (τk ) = Dki , tem-se
ẋj (τk ) ≈
N
X
Dki xij .
(1.13)
i=1
A matriz DN ×N = [Dki ] cujo elemento (k, i) é dado por
Dki = `˙i (τk )
(1.14)
é chamada de Matriz de Diferenciação.
Agora seja XN ×n a matriz formada pelos coeficientes xij de (1.11). Multiplicando
a matriz D por X, tem-se uma matriz [DX]N ×n . Por (1.13) o elemento (i, j) dessa matriz
pode ser visto como
[DX]ij ≈ ẋj (τi ).
(1.15)
Seja UN ×m = [uij ] uma matriz cujo elemento (i, j) denota a aproximação discreta
para a j-ésima componente de controle avaliada no i-ésimo ponto de colocação, ou seja,
uij ≈ uj (τi ).
A seguir um lema que permitirá relacionar a linha da matriz X com x(τ ).
Lema 1.3 Para todo i = 1, . . . , N , a i-ésima linha Xi da matriz X contém as componentes da aproximação discreta x(τi )T .
N
Y
τ − τm
tem-se que,
Demonstração. Lembrando que `i (τ ) =
τi − τm
m=1
j6=i
(
`i (τk ) =
0 se i 6= k
1 se i = k
e por (1.13) conclui-se que a j-ésima componente de x(τi )T é xij , que é exatamente a
j-ésima componente de Xi .
Considere agora a matriz
F (X, U )N ×n = [Fij (X, U )] = [fj (Xi , Ui )],
(1.16)
onde fj é a j-ésima componente da restrição do problema (1.10). Pelo Lema 1.3, (1.10) e
1.15 conclui-se que
tf − t0
DX =
F (X, U ).
(1.17)
2
Discretização da função custo
A função custo do problema (1.2) envolve uma integral. Recorre-se então às
técnicas de integração numérica. Nesta seção apresenta-se a regra da quadratura, que
pode ser vista com detalhes em [9, Cap.4].
12
A ideia básica da quadratura consiste em escrever uma aproximação da integral de
uma função, geralmente estabelecida como um somatório com pesos dos valores assumidos
pela função em pontos especı́ficos dentro do domı́nio de integração.
Uma regra de quadratura de N pontos é construı́da para produzir um resultado
exato para polinômios de grau 2N − 1 ou menor para uma escolha adequada dos pesos
wi para i = 1, ..., N associado a cada ponto. O domı́nio de integração de tal regra é
por convenção tomado como [−1, 1]. Sejam wi , com 1 ≤ i ≤ N , os pesos da quadratura
associados com os pontos LGR. Esses pesos têm a seguinte propriedade
Z
1
P(τ )dτ =
−1
N
X
wi P(τi )
(1.18)
i=1
para qualquer polinômio P de grau no máximo 2N − 2. Por [1], os pesos associados a
cada valor de P (τi ) são calculados por
Z
wi =
N 1 Y
−1
k=1
k6=i
τ − τk
τi − τk
dτ.
(1.19)
Assim, usando (1.17), o problema (1.10) é escrito na forma discretizada como
minimizar
N
X
wi r(Xi , Ui ))
i=1
sujeito a
DX =
tf − t0
F (X, U )
2
(1.20)
X 1 = x0
XN +1 = xf
onde XN +1 refere-se à variável de estado no ponto τN +1 = 1.
1.2.3
Condições de Karush-Kuhn-Tucker
Como em [22], considere o problema na forma
minimizar Φ(x(1))
sujeito a dx
= f (x(τ ), u(τ )
dτ
x(−1) = x0 ,
(1.21)
minimizar Φ(XN +1 )
sujeito a DX = F (X, U )
X 1 = x0 .
(1.22)
e em sua forma discretizada
13
Nesta seção são desenvolvidas as condições de KKT (ver Apêndice A.3.2) para o problema
(1.22) de uma maneira distinta de [22]. Considere Λ ∈ IRN ×n a matriz composta pelos
multiplicadores de Lagrange associados às restrições do problema (1.22) e seja o vetor
linha µ ∈ IRn composto pelos multiplicadores de Lagrange associados à condição inicial
X1 = x0 . Assim, tem-se
• Gradiente da função objetivo com relação a X.
∇X Φ(XN +1 ) = eN +1 ⊗ ∇Φ(XN +1 )T
(N +1).n×1
.
• Gradiente da função objetivo com relação a U
∇U Φ(XN +1 ) = 0.
• Produto do multiplicador de Lagrange Λ ∈ IRN ×n pelo gradiente da restrição
F (X, U ) − DX = 0.
– Gradiente de DX em relação a X.
T
(∇D(X)) Λ =
N X
N
X
Djk Ek ΛTj ,
j=1 k=1
onde Ek = ek ⊗ In .
– Gradiente de DX em relação a U : nulo.
– Gradiente de F (X, U ) em relação a X
(∇X F (X, U ))T Λ =
N
X
ei ⊗ ∇X f (Xi , Ui )ΛTi .
i=1
– Gradiente de F (X, U ) em relação a U .
T
(∇U F (X, U )) Λ =
N
X
ei ⊗ ∇U f (Xi , Ui )ΛTi .
i=1
• Produto do multiplicador µ ∈ IRn pelo gradiente de x0 − X1 = 0.
(∇X X1 )T µ = e1 µ.
14
Com todas as parcelas apresentadas, pode-se expressar as condições de KKT do problema
(1.22):
N
X
Dj1 Λj = Λ1 ∇X f (X1 , U1 )T − µ;
(1.23)
j=1
N
X
Djk Λj = Λk ∇X f (Xk , Uk )T ,
2 ≤ k ≤ N;
(1.24)
j=1
T
∇φ(XN +1 ) = DN
Λ;
(1.25)
Λk ∇U f (Xk , Uk )T = 0,
1 ≤ k ≤ N.
(1.26)
Mas as igualdades (1.23) e (1.24) podem ser reescritas de forma conjunta como
T
D1:N
Λ = ∇X hΛ, F (X, U )i − e1 µ.
(1.27)
Seja Dj:k a submatriz de D formada pelas colunas j até k e seja Xj:k a submatriz
de X formada pelas linhas de j até k. Utilizando essa forma, as restrições do problema
(1.22) podem ser escritas como
D2:N X2:N = F (X, U ) − D1 x0 .
(1.28)
O próximo resultado garante que a matriz D2:N , obtida pela omissão da primeira
coluna matriz D tem inversa.
Proposição 1.4 A matriz D2:N obtida deletando a primeira coluna de D é invertı́vel.
Demonstração. Tome p0 ∈ IRN −1 não nulo e considere p = (0, p0 ) ∈ IRN . Suponha agora
que Dp = 0. Mostra-se que D2:N p0 = 0 admite apenas solução trivial e assim que D2:N é
não-singular.
Seja P um polinômio de grau N tal que P(τk ) = pk para 1 ≤ k ≤ N , onde pk é o
N
X
k-ésimo elemento de p, ou seja, o polinômio escolhido deve ter a forma P(τ ) =
pk `(τ ).
k=1
Note que para i = 1, . . . , N
(Dp)i =
N
X
k=1
Dik pk =
N
X
pk `˙k (τi ) = Ṗ(τi ),
k=1
ou seja, cada componente de Dp é a derivada de P avaliada nos pontos de colocação. Por
hipótese Dp = 0, e assim (Dp)i = 0 para todo i = 1, . . . , N , logo
Ṗ(τi ) = 0.
Por Ṗ ser um polinômio de grau N −1 e se anular em N pontos segue que Ṗ é identicamente
nulo e portanto P é um polinômio constante. Como P(τN ) = pN = 0 segue que P é um
15
polinômio identicamente nulo. Ou seja, se Dp = 0, com a primeira coordenada de p
nula, que é equivalente a ter D2:N p0 = 0 isto implica que p = 0, ou seja, p0 = 0 e assim
D2:N p0 = 0 admite apenas a solução trivial e desta forma D2:N é não-singular.
1.2.4
Sistema Adjunto Transformado
Agora reformula-se as condições de KKT do problema (1.22), utilizando os pesos
da discretização, de modo que se tornem condições transformadas para o problema (1.21).
Desta forma, tem-se as condições de KKT para o problema contı́nuo e para o problema
discreto.
Seja W ∈ RN ×N matriz diagonal cujos elementos são wi . Seja λ ∈ IRN ×n definido
por
λ = W −1 Λ.
(1.29)
A fim de relacionar as equações discretas às equações contı́nuas, utiliza-se uma matriz
D+ ∈ IRN ×N , uma versão modificada de D definida como:
+
D11
= −D11 −
1
w1
+
Dij
=−
e
wj
Dji .
wi
(1.30)
Usando (1.24), (1.29), (1.30), tem-se para i = 2, . . . , N ,
Λi ∇X f (Xi , Ui ) =
N
X
Dji Λj =
j=1
N
X
−
j=1
N
X
wi +
+
Dij Λj = −
wi Dij
λj .
wj
j=1
Pela igualdade acima e (1.29), tem-se
N
X
j=1
+
Dij
λj = −
Λi
∇X f (Xi , Ui ) = −λi ∇X f (Xi , Ui ).
wi
Por outro lado, usando (1.23), (1.29) e (1.30), obtém-se:
Λ1 ∇X f (X1 , U1 ) − µ =
N
X
Dj1 Λj .
j=1
= D11 Λ1 +
N
X
Dj1 Λj
j=2
N
X
1
w1 +
+
Λ1 +
− D1j
Λj
= −D11 −
w1
w
j
j=2
=
+
−D11
Λ1
− λ1 −
N
X
j=2
+
D1j
w 1 λj .
(1.31)
16
Dividindo ambos os membros da igualdade por w1 e usando (1.29) tem-se
N
+
λ1 −
−D11
λ1 X +
µ
−
,
D1j λj = λ1 ∇X f (X1 , U1 ) −
w1 j=2
w1
donde segue que
N
X
+
D1j
λj = −λ1 ∇X f (X1 , U1 ) +
j=1
1
(µ − λ1 ),
w1
(1.32)
que é análoga a (1.23).
Para cada i = 1, . . . , N , dividindo a igualdade (1.26) por wi e usando (1.29),
resulta que
λi ∇U f (Xi , Ui ) = 0.
(1.33)
Agora discute-se a igualdade (1.25). Tome um polinômio P tal que P(τi ) = 1,
para 1 ≤ i ≤ N . Pela definição dos polinômios de Lagrange discutidos na Seção 1.2.1,
tem-se que P(τ ) = 1 para todo τ , e assim Ṗ(τ ) = 0. Considere v ∈ IRN um vetor de
componentes unitárias e (Dv)k a k-ésima componente do produto Dv. Assim
(Dv)k =
N
X
Dki vi =
i=1
Consequentemente 0 = Dv =
N
X
Dki =
i=1
N
X
Dj =
j=1
N
−1
X
N
X
`˙i (τk ) = Ṗ(τk ) = 0.
i=1
Dj + DN . Logo
j=1
DN = −
N
−1
X
Dj .
(1.34)
j=1
Utilizando (1.34) tem-se
T
DN
Λ
=
N
X
Λi Di,N = −
i=1
N X
N
X
Λi Dij .
i=1 j=1
Com (1.30) e fazendo mudança de ı́ndices vem que
−
N X
N
X
i=1 j=1
N
Λi Dij =
N
N
N
Λ1 X X
Λ1 X X
+ wj
+ wi
+
Λi Dji
=
+
Λj Dij
.
w1 i=1 j=1
wi
w1 i=1 j=1
wj
17
Utiliza-se (1.29) e se isola λ1 de (1.32) daı́
N
N
Λ1 X X
+ wi
+
Λj Dij
w1 i=1 j=1
wj
= λ1 +
N X
N
X
+
wi λj Dij
i=1 j=1
=
−w1
N
X
!
+
D1j
λj
− λ1 w1 ∇X f (X1 , U1 ) + µ
+
j=1
N X
N
X
+
wi λj Dij
.
i=1 j=1
Finalmente, com (1.31) e reorganizando as contas segue que
−w1
N
X
!
+
D1j
λj − λ1 w1 ∇X f (X1 , U1 ) + µ
+
j=1
N X
N
X
+
wi λj Dij
= −λ1 w1 ∇X f (X1 , U1 ) + µ
i=1 j=1
+
N
X
(−λi wi ∇X F (Xi , Ui ))
i=2
= µ−
N
X
λi wi ∇X f (X1 , Ui ).
i=1
Tem-se, finalmente, as condições transformadas de KKT:
µ = ∇Φ(XN +1 ) +
N
X
wi λi ∇X f (Xi , Ui )
i=1
D+ λ = −∇X hλ, F (X, U )i +
1
e1 (µ − λ1 )
w1
∇U hλ, F (X, U )i = 0.
Considere agora o seguinte resultado.
Teorema 1.5 [22, Teo.1] Considere P um polinômio de grau no máximo N − 1, com
N ≥ 1, e p ∈ IRN um vetor cuja i-ésima componente é dada por pi = P(τi ). Se D+
satisfaz, para todo i = 1, . . . , N ,
(D+ p)i = Ṗ(τi ),
então D+ é a matriz de diferenciação para o espaço de polinômios de grau N − 1 definida
em (1.30).
Demonstração. Sejam P um polinômio de grau no máximo N com P(1) = 0 e Q um
polinômio de grau no máximo N − 1, com N ≥ 1. Usando integração por partes, vale a
seguinte igualdade
Z
1
Z
1
Ṗ(τ )Q(τ )dτ = −P(−1)Q(−1) −
−1
P(τ )Q̇(τ )dτ.
(1.35)
−1
Note que, ṖQ e P Q̇ são polinômios de grau no máximo 2N − 2. Assim, pela Seção
18
1.2.2, a quadratura de Gauss é exata e consequentemente as integrais em (1.35) podem
ser substituı́das por suas quadraturas equivalentes, ou seja,
N
X
wj ṗj qj = −p1 q1 −
j=1
N
X
wj pj q˙j ,
j=1
onde pj = P(τj ) e p˙j = Ṗ(τj ). De forma compacta, isto pode ser reescrito como
(W ṗ)T q = −p1 q1 − (W p)T q̇.
Substituindo ṗ = D1:N p e q̇ = D+ q,
T
W q + p1 q 1 + pT W D + q = 0
pT D1:N
e assim,
T
pT D1:N
W + W D+ + e1 eT1 q = 0.
Como p e q foram tomados arbitrariamente, ou seja, essa igualdade deve ser satisfeita
para quaisquer p e q segue que
T
D1:N
W + W D+ + e1 eT1 = 0,
que implica (1.30).
1.2.5
Formulação Integral
Nesta seção mostra-se que a discretização pseudoespectral da equação de estado,
ou seja, da restrição do problema (1.22), tem uma formulação equivalente através de
integrais.
Por (1.34) tem-se que D1 + D2 + · · · + DN = 0 então, se v é um vetor de componentes unitárias vale que
N
X
D1 = −
Dj = −D2:N v.
(1.36)
j=2
Pela Proposição 1.4 a matriz D2:N é invertı́vel então
−1
D2:N
D1 = −v.
(1.37)
Seja P um polinômio qualquer de grau no máximo N . Por D ser a matriz de
diferenciação dos polinômios de grau N tem-se que Dp = ṗ onde pi = P(τi ) e ṗi = Ṗ(τi )
19
para 1 ≤ i ≤ N . Então,
ṗ = Dp =
N
X
Di pi = D1 p1 + D2:N p2:N ,
i=1
−1
multiplicando por D2:N
tem-se
−1
−1
D2:N
ṗ = D2:N
D1 p1 + p2:N .
Utilizando (1.37), para i = 2, . . . , N vem que
−1
pi = p1 + (D2:N
ṗ)i .
(1.38)
Agora obtém-se uma expressão diferente para p1 − pi baseado na integração da
interpolação da derivada. Seja `+
j , para j = 1, . . . , N o polinômio de Lagrange interpolador
associado aos pontos de colocação:
`+
j
N
Y
τ − τm
.
=
τj − τm
m=1
m6=j
Dado um polinômio P de grau no máximo N , sua derivada Ṗ é um polinômio de
grau no máximo N − 1. Assim Ṗ pode ser interpolado exatamente pelos polinômios de
Lagrange `+
j :
N
X
Ṗ(τ ) =
ṗj `+
j .
j=1
Integrando essa igualdade de −1 a τi tem-se
Z
τi
Ṗ(τ )dτ =
−1
N
X
j=1
Z
τi
ṗj
`+
j (τ )dτ ,
−1
Rτ
pelo teorema fundamental do cálculo e denotando −1i `+
j (τ )dτ = Aij , para i = 2, . . . , N
vem que
N
X
P(τi ) − P(−1) =
ṗj Aij
(1.39)
j=1
ou seja,
pi − p1 = (Aṗ)i .
(1.40)
As relações (1.38) e (1.40) são satisfeitas para qualquer polinômio de grau no
máximo N . Escolha um polinômio P tal que P(1) = 0, ou seja, p1 = 0. Daı́ por (1.38)
20
−1
tem-se que pi = (D2:N
ṗ)i e por (1.40) tem-se pi = (Aṗ)i e assim segue que
−1
D2:N
ṗ = Aṗ.
Tomando ṗ como a i-ésima coluna da matriz identidade na igualdade acima, conclui-se
−1
que, para todo i = 1, . . . , N − 1, a i-ésima coluna de D2:N
é igual a i-ésima coluna da
matriz A, ou seja,
−1
A = D2:N
.
Sabendo isso, multiplicando a equação (1.28) por A, e usando (1.37), para i = 2, . . . , N ,
se obtém
Xi = x0 + Ai F (X, U )
(1.41)
onde Ai é a i-ésima linha de A.
Assim, a forma diferencial da equação de estado DX = F (X, U ) é equivalente a
forma integrada (1.41), onde os elementos de A são integrais do polinômio interpolador
de Lagrange `+
j , enquanto os elementos de D são as derivadas do polinômio de Lagrange
`i .
Para resumir, o que se tem em (1.41) é uma equação que está na forma de um
método de integração global implı́cito, enquanto a aproximação DX = F (X, U ) está na
forma de um método pseudoespectral.
O fato de que a integral ou a forma diferencial poder ser usada, mostra que o
método de colocação Radau pode ser visto como um método de integração global implı́cito
ou um método pseudoespectral. Em particular, usando a forma pseudoespectral dos
pontos de colocação LGR, resulta num sistema de equações que não tem qualquer perda
de informação quando se passa para a forma integral.
1.3
Método de Euler
Esta seção, que tem [2, Sec. 3.1] como principal referência, apresenta o método
de Euler para obtenção de uma solução numérica do problema (1.2). O método de Euler
é baseado no Teorema de Taylor [26].
O intervalo de tempo [t0 , tf ] é discretizado em (N − 1) subintervalos, de modo
que:
t0 ≡ t1 < t2 < · · · < tN ≡ tf .
Definindo as amplitudes de cada subintervalo i = 1, · · · , N −1 por hi = ti+1 −ti , a variável
de estado x(t) ∈ IRn é expandida, segundo Taylor, como
x(ti+1 ) = x(ti + hi ) = x(ti ) + hi
h2 d2 x
dx
(ti ) + i 2 (ςi ),
dt
2 dt
para algum ςi ∈ [ti , ti+1 ]. Assim, para valores suficientemente pequenos de hi , tem-se a
21
seguinte aproximação
x(ti+1 ) − x(ti )
dx
(ti ) ≈
.
dt
hi
Como o estado x satisfaz a equação diferencial do problema (1.2) tem-se que
x(ti+1 ) − x(ti )
= f (x(ti ), u(ti )),
hi
para hi suficientemente pequeno.
Tomando-se amplitude h > 0 constante suficientemente pequena para todos os
subintervalos e denotando x(tk ) por xk e u(tk ) por uk , a condição diferencial acima é
escrita da seguinte forma,
xk+1 − xk
,
(1.42)
f (xk , uk ) =
h
para todo k = 1, · · · , N − 1. Analogamente, segundo [2], a discretização da função custo
do problema (1.2) é dada por
N
−1
X
r(xk , uk )h.
k=0
Assim o problema (1.2) é discretizado, segundo o método de Euler, como
minimizar
N
−1
X
r(xk , uk )h
k=1
sujeito a
f (xk , uk ) =
xk+1 − xk
parak = 1, · · · , N − 1
h
(1.43)
x(t1 ) = x1
x(tN ) = xN .
A resolução deste problema de otimização leva a uma solução numérica do problema
original. No próximo capı́tulo, veremos um exemplo particular.
1.4
Outros métodos
Dois métodos de colocação LGR são apresentados em [14] e [15]. O método de
Kameswaran e Biegler em [15] concentra-se na colocação local usando pontos LGR. O
método de Fahroo e Ross em [14] descreve um método global para resolver problemas
de horizonte infinito. Nesta seção, um breve comentário sobre a forma como o método
apresentado neste trabalho refere-se a estes trabalhos.
1.4.1
Comparação com o método de Kameswaran e Biegler
O método pseudoespectral abordado neste trabalho tem semelhanças com o método
de Kameswaran e Biegler ([15]). A aproximação para a variável de estado usa também
os polinômios de Lagrange. É observado, no entanto, que o método de Kameswaran e
22
Biegler usa colocação local, utilizando vários subintervalos. O grau dos polinômios em
cada subintervalo é fixo e a convergência é conseguida através do aumento do número de
subintervalos. O método aqui tratado é um método de colocação global, em que há um
único intervalo e a convergência é alcançada através do aumento do grau de polinômios,
ou seja, no aumento do N , dos pontos de colocação, como visto pela Seção 1.2.1. O
método de Kameswaran e Biegler é implementado de uma forma semelhante ao método
de Euler tratado na Seção 1.3 (devido ao fato de que o intervalo de tempo é dividido em
subintervalos), enquanto que o método do presente trabalho é implementado na forma
de um método pseudoespectral. Nota-se que ambas as abordagens são válidas, mas a
abordagem atual, segundo [22], é usada com mais frequência na literatura de controle.
1.4.2
Comparação com o método de Fahroo e Ross
Na abordagem pseudoespectral Lobatto como descrito em [21], a variável de estado é aproximada por polinômios de grau N − 1 e a dinâmica do sistema é discretizado
com N pontos de quadratura Lobatto. Para o problema de controle do horizonte infinito
estudado em [14], Fahroo e Ross propõem utilizar uma mudança de variáveis para transformar o intervalo de tempo infinito para o intervalo [−1, +1). Esta mudança de variáveis
leva a uma singularidade na dinâmica no ponto τ = +1. Desta forma, não é possı́vel
utilizar τ = +1 como um ponto de colocação. Para lidar com essa singularidade, Fahroo
e Ross propõem discretizar nos pontos de quadratura Radau para τ = N < 1.
A diferença fundamental entre o método pseudoespectral em [14] e o método previsto neste trabalho é que, em [14], a variável de estado é aproximada por polinômios
de grau N − 1, enquanto que neste trabalho, a variável de estado é aproximada usando
polinômios de grau N . Esta mudança no grau dos polinômios leva a diferenças fundamentais entre os dois esquemas. Por exemplo, uma vez que os polinômios de Lagrange são
de diferentes graus, as matrizes de diferenciação são completamente diferentes. A matriz
utilizada na diferenciação em [14] é singular, enquanto que a matrize D2:N , segundo a Proposição 1.4, é invertı́vel. Se o controle e o estado inicial x0 são dados, então a dinâmica
discretizada do problema [14] é um sistema de N equações e de N − 1 incógnitas, X2:N .
Em contraste, 1.28 é um sistema de N − 1 equações com N − 1 incógnitas, X2:N , onde a
matriz de coeficientes D2:N é invertı́vel.
Na abordagem de [14], XN +1 , a estimativa da variável de estado em τ = 1, é
removido do problema usando polinômios de grau N − 1 em vez de polinômios de grau N .
Na abordagem aqui apresentada, a variável de estado é aproximada em τi , 1 ≤ i ≤ N + 1.
Assim, XN +1 , a estimativa do estado, é uma variável incluı́da no esquema pseudoespectral.
Avaliar o estado em τ = +1 é útil quando a função objetivo depende do estado no
momento final, ou quando há uma restrição de ponto final, como era o caso do problema
abordado neste trabalho.
23
1.5
Problema de Bolza
No próximo capı́tulo resolve-se um problema que é chamado de problema de
Bolza. Para mais detalhes sobre esse tipo de problema consultar [5]. O problema de
Bolza pode ser formulado de diversas maneiras, cada uma das quais tem as suas vantagens
peculiares e desvantagens. Uma das formulações mais úteis pode ser descrita brevemente
como segue:
Determinar o estado x(τ ) ∈ IRn , o controle u(τ ) ∈ IRm , o tempo incial t0 e tempo
final tf que encontre um mı́nimo local do seguinte problema
tf − t0 R 1
minimizar J = Φ(x(−1), t0 , x(1), tf ) +
g(x(τ ), u(τ ), τ )dτ
−1
2
dx
t −t
= f 2 0 f (x(τ ), u(τ ), τ ) ∈ IRn
sujeito a
dτ
φ(x(−1), x(1)) = 0 ∈ IRq
C(x(τ ), u(τ )) ≤ 0 ∈ IRc .
(1.44)
Quando Φ = 0 o problema é o chamado problema de Lagrange e quando g = 0
tem-se o problema geral de Mayer como formulado por Bliss em [5]. Estas três versões,
ou seja, o problema completo, o problema com Φ = 0 e o problema com g = 0, são
equivalentes no sentido de que cada um pode ser transformado em qualquer um dos
outros dois tipos.
Destas três versões, o problema de Bolza formulado acima parece ser o mais
conveniente, pois possui todos os termos de forma explı́cita. Para o presente trabalho
formula-se o problema utilizando uma aproximação pseudoespectral LGR. E assim, o
problema de Bolza toma a seguinte forma:
N
tf − t0 X
wk g(Xk , Uk , τk )
minimizar Φ(X1 , t0 , XN +1 , tf ) +
2 k=1
tf − t0
F (X, U )
sujeito a DX =
2
φ(X1 , XN +1 ) = 0
C(Xk , Uk ) ≤ 0 1 ≤ k ≤ N,
onde os wk0 s são dados por (1.19).
Capı́tulo 2
Exemplos
Neste capı́tulo consideram-se alguns problemas de controle ótimo particulares que
são resolvidos pelo método pseudoespectral utilizando pontos LGR discutido no capı́tulo
anterior. Inicialmente, discute-se um problema de Bolza sem restrições [2, 22] dito problema do regulador linear quadrático, conhecido pela abreviação LQR, do inglês linear
quadratic regulator. Discute-se sua solução exata e soluções numéricas utilizando o método
de Euler visto na Seção 1.3 e o método pseudoespectral visto na Seção 1.2. Em seguida,
são discutidas as soluções numéricas de dois problemas de controle ótimo com restrições
não lineares.
2.1
Exemplo 1
O primeiro exemplo é um problema do regulador linear quadrático, conhecido
pela abreviação LQR, do inglês linear quadratic regulator que consiste em minimizar uma
função custo quadrática com tempos iniciais e finais fixos [2, pág. 126]. O funcional é
dado por
Z
1 tf
1
T
x(t)T Qx(t) + u(t)T Ru(t) dt,
J = x(tf ) Sx(tf ) +
2
2 t0
sujeito a um sistema linear dinâmico
dx
= Ax + Bu,
dt
e as condições
x(t0 ) = x0 ,
x(tf ) = xf .
O número de estados é n, x(t) ∈ IRn , o número de controles é m, u(t) ∈ IRm , tais que
S ∈ IRn×n , Q ∈ IRn×n , R ∈ IRm×m , A ∈ IRn×n e B ∈ IRn×m .
A solução exata do problema [2] pode ser encontrada utilizando o Princı́pio do
Máximo de Pontryagin, que faz recair no seguinte sistema
24
Exemplos
25
ẋ(t)
ṗ(t)
!
=
A −BR−1 B T
−Q
−AT
!
x(t)
p(t)
!
,
onde p é a variável de co-estado.
O controle ótimo é definido por
u(t) = −R−1 B T p(t).
O caso especı́fico considerado aqui tem um único estado e um único controle de
modo que n = m = 1 e S, Q, R, A e B são escalares. Em particular, tome S = 0 e
√
Q = R = A = B = 1. Além disso, considere as condições de contorno: inicial x(t0 ) = 2
e a condição final x(tf ) = 1, com t0 = 0 e tf = 5. Assim, o problema considerado é dado
por
R5
maximizar − 0 (x2 (t) + u2 (t)) dt
sujeito a ẋ(t) = x(t) + u(t)
√
(2.1)
x(0) = 2
x(5) = 1.
Aplicam-se as técnicas discutidas no capı́tulo anterior para obtenção da solução
exata e de soluções aproximadas para este problema.
2.1.1
Solução Exata
A solução exata do problema é obtida através da aplicação do Princı́pio do
Máximo de Pontryagin, como visto no Teorema 1.1.
Identificam-se os elementos do problema (2.1) com os elementos do problema de
controle ótimo dado em (1.2) e com os elementos do Teorema 1.1. Para não carregar a
notação o argumento t é omitido, ou seja, escreve-se, por exemplo, x ao invés de x(t), e
assim para todas as variáveis que dependem de t. Assim, desta identificação, tem-se
f (x, u)
= x + u,
r(x, u)
= −x2 − u2 ,
H(x, p, u) = f (x, u)p + r(x, u).
Desta forma,
ẋ = ∇p H(x, p, u) = f (x, u),
∂r
∂f
= −p + 2x,
ṗ = −∇x H(x, p, u) = − p −
∂y
∂y
∂f
∂r
Hu (x, p, u) = 0 =
p+
= p − 2u.
∂u
∂u
(2.2)
(2.3)
(2.4)
Exemplos
26
Das igualdades acima, tem-se o seguinte sistema
(
ẋ = x + p2
ṗ = 2x − p
que pode ser escrito na forma matricial
ẋ
ṗ
!
!
1 12
=
2 −1
|
{z
}
!
x
p
.
M
A solução deste sistema de equações diferenciais, como discutido na Seção A.2, é
x
p
!
x0
p0
= eM t
!
.
(2.5)
Então precisa-se calcular eM t e encontrar p0 , e assim x e p estarão bem definidos. A
matriz M é uma matriz diagonalizável, ou seja, como visto na Seção A.1.2, existe uma
matriz S tal que M = SDS −1 com D diagonal. Neste caso,
S=
1
−1
√
√
2 2−2 2 2+2
!
√
2
0
√
; S −1 =
0 − 2
!
;D =
√
2+2
√4
2−2
4
1
√
4 2
1
√
4 2
Pela Proposição A.6, eM t = SeDt S −1 , onde
√
e
eDt =
2t
!
0
√
e−
0
.
2t
Desta forma,
eM t =
1
−1
√
√
2 2−2 2 2+2
!
√
e
2t
0
√
0
!
e−
2t
 √
2+2

 √ 4
 2−2
4

1
√
4 2 
.
1 
√
4 2
Fazendo a multiplicação das matrizes tem-se
√
√
 √

√
2 + 2 √2t 2 − 2 −√2t
e 2t − e− 2t
√
e +
e


Mt
4
4

.
4
2 √
√
√
√
e =
2 √2t
2 −√2t
2 − 2 √2t 2 + 2 −√2t 
e −
e
e +
e
2
2
4
4
√
Usando as condições iniciais x0 = x(0) = 2 e x(5) = 1 em (2.5) tem-se que
1
p(5)
!
5M
=e
√ !
2
.
p0
!
.
Exemplos
27
Denotando
e
5M
=
tem-se que
1=
e assim, como B12 6= 0,
B11 B12
B21 B22
√
!
,
2B11 + p0 B12 ,
√
1 − B11 2
p0 =
.
B12
Substituindo os valores de B11 e B12 e fazendo algumas manipulações algébricas conclui-se
que
√
√
√
√
√
4 2 − (2 2 + 4)e5 2 + (2 2 − 4)e−5 2
√
√
p0 = p(0) =
.
(2.6)
e5 2 − e−5 2
√
Voltando em (2.5) e usando a condição inicial x0 = 2, tem-se que
x(t)
p(t)
√
!
Mt
=e
!
2
p(0)
ou seja
x(t) =
e
p(t) =
√
√
2
√
2
!
√
√
2 + 2 √2t 2 − 2 −√2t
e +
e
+
4
4
2
e
2
√
√
2t
−
√
− 2t
2
e
2
√
!
+
√
e
2t
√
− e−
√
4 2
2t
!
p(0)
(2.7)
!
√
√
2 − 2 2t 2 + 2 − 2t
e +
e
p(0),
4
4
√
com p(0) dado em (2.6). Da igualdade (2.4) segue que
u(t) =
p(t)
.
2
Assim a solução do problema (2.1) é

√ √2+2 √2t 2−√2 −√2t e√2t −e−√2t 
√
x(t)
=
2
e + 4 e
+
p(0)

4

4 2
!
!
√
√
√
√
√
√
−5 2
5 2
√
√
(2
2
−
4)e
+
2
2
−
2
−(2
2
+
4)e
+
2
2
+
2
 u(t) =
√
√
√
√
e 2t +
e− 2t


2e5 2 − 2e−5 2
2e5 2 − 2e−5 2
(2.8)
A Figura 2.1 exibe graficamente o controle u e a variável de estado y = x2 .
Exemplos
28
2
y(t)
u(t)
1
Solução
0
−1
−2
−3
−4
0
0.5
1
1.5
2
2.5
t
3
3.5
4
4.5
5
Figura 2.1: Solução exata do problema.
2.1.2
Solução aproximada pelo método pseudoespectral
Nesta seção discute-se a solução numérica pelo método pseudoespectral discutido
na Seção 1.2 do problema (2.1) que escrito na forma de minimização é dado por,
R5
minimizar 21 0 (x2 (t) + u(t)2 ) dt
sujeito a ẋ(t) = x(t) + u(t)
√
x(0) = 2
x(5) = 1.
(2.9)
Inicialmente, considera-se a mudança de variável (1.8) de t ∈ [−1, 1] para τ ∈ [0, 5],
5
t = (τ + 1).
2
Assim,
dτ
2
dx
dx dτ
2 dx
=
e
ẋ =
=
=
dt
5
dt
dτ dt
5 dτ
e a restrição do problema (2.14) se escreve como
2 dx
= x(τ ) + u(τ ).
5 dτ
Sejam N pontos de colocação LGR, −1 = τ1 < τ2 · · · < τN < 1, obtidos como raı́zes
da soma PN −1 (τ ) + PN (τ ) dos polinômios de Legendre, como discutido na Seção ??.
Considere D ∈ IRN ×N a matriz de diferenciação definida em (1.14). Por (1.15), tem-se
dx
que DX ≈
. Assim a restrição se reescreve como
dτ
2
DX = X + U,
5
Exemplos
29
com X, U ∈ IRN . Tendo calculado o vetor de pesos w ∈ IRN associados aos pontos de
colocação por (1.19), o problema (2.14) discretizado é dado por
N
1X 2
minimizar
(x + u2k )wk
2 k=1 k
2
DX =
5
√
sujeito a
(2.10)
X +U
x1 = 2
xN +1 = 1.
Os pontos de colocação e o vetor w ∈ IRn foram calculados utilizando a rotina
pontos lgr w em Matlab descrita no Apêndice B. Este programa consiste numa adaptação
para cálculo dos pontos de colocação LGR [23] do código lglnodes.m escrito por Winckel
[32] que tem como referência [7]. O resultado obtido pelo programa para diferentes valores
de N foi comparado com os valores fornecidos em [13]. A matriz de diferenciação D ∈
IRN ×N foi calculada pela rotina matriz dif.
Tendo o vetor w ∈ IRN de pesos da quadratura associados com os N pontos de
colocação LGR e a matriz D de diferenciação, o problema (2.10) pode ser visto como um
problema de minimização de uma função quadrática com restrições de igualdade lineares
e condição de caixa, na variável (X, U ) ∈ IR2N , com uma variável adicional que deve
satisfazer a condição xN +1 = 1. Os problemas, para diferentes valores de N e soluções
iniciais randômicas, foram resolvidos utilizando-se a rotina quadprog do Matlab. A Figura
2.2 apresenta o gráfico da solução exata e uma solução numérica obtida adotando-se
N = 60 pontos de colocação. As linhas cheias representam a solução exata no intervalo
[−1, 1]. Os sı́mbolos triangulares representam a solução aproximada para a variável de
estado y = x2 e o sı́mbolo asterisco é usado para representar a variável de controle u.
2
1
0
−1
−2
yexato
−3
uexato
yaprox
uaprox
−4
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
τ
Figura 2.2: Solução exata e solução obtida pelo método pseudoespectral.
Exemplos
30
Análise de erros.
Foram consideradas 30 instâncias do problema (2.10) para cada valor de N entre
10 e 100. Cada instância difere na solução inicial que é tomada arbitrária. Para cada
instância foram calculadas a norma da diferença entre a solução exata e a solução numérica
tanto para a variável de estado y = x2 e a variável de controle u, ou seja, foram calculados
os erros:
erro y = kyexata − yaprox k∞
erro u = kuexata − uaprox k∞ ,
onde (yexata , uexata ) representa a solução exata e (yaprox , uaprox ) representa a solução aproximada. Para cada valor de N foi calculada a mediana dos erros calculados para as 30
instâncias. A Figura 2.3 mostra os gráficos da variação deste erro quando varia-se o valor
de N . O gráfico da esquerda mostra o erro na variável de estado, enquanto o gráfico da
direita mostra o gráfico do erro para a variável de controle. O eixo vertical de ambos
os gráficos está na escala logarı́tmica. As curvas em linha contı́nua referem-se às curvas
de regressão linear e quadrática na escala logarı́tmica, cujos parâmetros foram obtidos
através do comando polyfit do Matlab. Note que os erros descrescem mais lentamente na
variável de controle u.
erroy
errou
4.25N−1.44
−1
0.0832N−0.165
−1.2
10
0.0979N0.691 + (−0.292 ln(N))
log(erroy)
log(errou)
10
0.465N−1.14
+ (0.133 ln(N))
−1.3
10
−2
10
−1.4
10
10
20
30
40
50
60
70
80
90
100
10
20
30
40
50
N
60
70
80
90
100
N
Figura 2.3: Variação em função de N do erro na variável de estado (esquerda) e na variável
de controle (direita).
2.1.3
Solução aproximada pelo método de Euler
Nesta seção será aplicado o método de Euler estudado na Seção 1.3 para resolver
o problema (2.1). O intervalo de tempo [0, 5] é inicialmente transformado no intervalo
[−1, 1], utilizando a mudança dada em (1.8) e este é discretizado em N subintervalos de
2
amplitude . Adotando-se t0 = −1 e tN = 1, tem-se que o (k + 1)-ésimo subintervalo
N
é [tk , tk+1 ] para k = 0, . . . , N − 1. Denota-se x(tk ) por xk e u(tk ) por uk e estima-se a
Exemplos
31
xk+1 − xk
derivada ẋ por
em cada intervalo. Assim, a restrição principal do problema
h
(2.1) se reescreve como k restrições da forma:
xk+1 − xk =
5
(xk + uk ),
N
(2.11)
com k = 0, . . . , N − 1.
A função objetivo dada por uma integral é discretizada através do somatório
N −1
1X 2
xk + u2k h,
2 k=0
e o problema (2.1) se reescreve na forma discretizada como
minimizar
1
2
N
−1
X
(x2k + u2k )h
k=0
sujeito a
5
xk+1 − xk = (xk + uk ), k = 0, . . . , N − 1
N
√
x0 = 2
xN = 1.
A condição de contorno no tempo final foi incorporada ao problema como uma
penalização à função objetivo, ou seja, fixando-se um valor M suficientemente grande, o
problema anterior é transformado em
minimizar
1
2
N
−1
X
(x2k + u2k )h + M (xN − 1)2
k=0
sujeito a
5
xk+1 − xk = (xk + uk ),
N
√
x0 = 2.
k = 0, . . . , N − 1
(2.12)
Para as implementações, foi tomado M = 105 .
O lema a seguir, relaciona cada variável de estado xk com a posição inicial x0 e
com as variáveis de controle uj com j = 0, · · · , k − 1.
Lema 2.1 Para todo k = 1, . . . , N , vale a relação
k−1
X
xk = (1 + h) x0 + h
(1 + h)k−j−1 uj .
k
j=0
Demonstração. A prova é feita por indução. Primeiramente verifica-se que vale para k = 1.
Note que por (2.11) tem-se
x1 − x0 = h(x0 + u0 ),
Exemplos
32
ou seja,
x1 = (1 + h)x0 + hu0 ,
mostrando assim que vale para k = 1. Assume-se que a proposição vale para algum k,
com 1 ≤ k ≤ N − 1, ou seja,
k−1
X
xk = (1 + h) x0 + h
(1 + h)k−j−1 uj .
k
j=0
Prova-se então que vale para k + 1. Utilizando novamente (2.11) tem-se que
xk+1 = xk + h(xk + uk ) = (1 + h)xk + huk .
Usando a hipótese de indução, a igualdade acima se torna
"
xk+1 = (1 + h) (1 + h)k x0 + h
k−1
X
#
(1 + h)k−j−1 uj + huk .
j=0
Fazendo as multiplicações e agrupando os termos tem-se
xk+1 = (1 + h)k+1 x0 + h
k−1
X
(1 + h)k−j uj + h(1 + h)0 uk
j=0
= (1 + h)k+1 x0 + h
k−1
X
(1 + h)(k+1)−j−1 uj + h(1 + h)(k+1)−k−1 uk
j=0
k+1
= (1 + h)
x0 + h
k
X
(1 + h)(k+1)−j−1 uj .
j=0
Provando assim que, para qualquer k = 1, . . . , N , vale a relação
k−1
X
xk = (1 + h) x0 + h
(1 + h)k−j−1 uj .
k
(2.13)
j=0
Cabe ressaltar que as restrições do problema (2.12) válida para k = 0, . . . , N − 1
foram usadas fortemente na prova do Lema 2.1. O resultado provado será usado para
escrever a função objetivo do problema (2.12) apenas em função das variáveis de controle
√
uk e de x0 que pela condição inicial é fixado em 2.
Usando (2.13) a função objetivo do problema (2.12) se escreve como
Exemplos
33
N −1
1X 2
J =
(xk + u2k )h + M (xN − 1)2
2 k=0
N −1
1 2
1X 2
2
=
(x + u0 )h +
(x + u2k )h + M (xN − 1)2
2 0
2 k=1 k
=
1 2
(x0 + u20 )h
2
N −1
k−1
X
1X
2k 2
k
+
(1 + h) x0 + 2hx0 (1 + h)
(1 + h)k−j−1 uj +
2 k=1
j=0
!
k−1 X
k−1
X
(1 + h)2k−j−m−2 uj um + u2k h
+h2
j=0 m=0
N
2
N
((1 + h) x0 − 1) + 2h((1 + h) x0 − 1)
+M
N
−1
X
(1 + h)N −j−1 uj +
j=0
+h2
!
N
−1 N
−1
X
X
(1 + h)2N −j−m−2 uj um
,
j=0 m=0
que pode ser reescrita como
N −1
N −1
k
XX
1 2X
J =
hx0
(1 + h)2k + M (x0 (1 + h)N −1 − 1)2 + h2 x0
(1 + h)2k−j−2 uj
2
k=0
k=1 j=0
+ 2M h(x0 (1 + h)N −1 − 1)
N
−2
X
(1 + h)N −j−2 uj +
j=0
2
+ hM
N
−2 N
−2
X
X
2N −j−m−2
(1 + h)
j=0 m=0
k
N −1 k
h3 X X X
(1 + h)2k−j−m−2 uj um
2 k=1 j=0 m=0
N −1
hX 2
uj um +
u ,
2 k=0 k
√
que é uma função quadrática na variável de controle u, visto que x0 = 2.
Assim (2.12) recai no problema de minimização da função quadrática J, sem
restrições, que pode ser resolvido pelo Algoritmo A.1 do método de gradientes conjugados.
Tendo obtido o vetor u das variáveis de controle, obtém-se o vetor x através da expressão
(2.13), o que permite determinar o vetor y das variáveis de estado através da igualdade
y = x2 .
Exemplos
34
A listagem referente à implementação necessária para resolução do problema (2.1)
pelo método de Euler descrito nesta seção é apresentada no Apêndice B.
A Figura 2.4 apresenta a solução obtida adotando-se N = 60
2
1
0
−1
−2
yexato
uexato
yaprox
−3
uaprox
yEuler
uEuler
−4
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
τ
Figura 2.4: Solução exata e soluções numéricas.
Análise de erros. Como para o caso da solução numérica obtida pelo método pseudoespectral, foram consideradas 30 instâncias do problema (2.10) para cada valor de N
entre 10 e 100. Cada instância difere na solução inicial que é tomada arbitrária. Para
cada instância foram calculadas a norma da diferença entre a solução exata e a solução
numérica tanto para a variável de estado y = x2 e a variável de controle u, ou seja, foram
calculados os erros:
erro y = kyexata − yEuler k∞
erro u = kuexata − uEuler k∞ ,
onde (yexata , uexata ) representa a solução exata e (yEuler , uEuler ) representa a solução aproximada obtida pelo método de Euler. Para cada valor de N foi calculada a mediana dos
erros obtidos para as 30 instâncias. A Figura 2.5 mostra os gráficos da variação deste erro
quando varia-se o valor de N . O gráfico da esquerda mostra o erro na variável de estado,
enquanto o gráfico da direita mostra o gráfico do erro para a variável de controle. O eixo
vertical de ambos os gráficos está na escala logarı́tmica. A linha cheia representa a curva
da regressão linear na escala logarı́tmica. Os coeficientes da regressão foram fornecidos
pelo comando polyfit do Matlab.
O erro na variável de estado é da ordem de 10−1 , enquanto para o método pseudoespectral o erro foi da ordem de 10−2 . Os erros para o método de Euler foram maiores
que para o método pseudoespectral.
Exemplos
35
erroy
erro
−0.1
u
10
−0.485
−0.539
0.713N
2.91N
−0.2
log(errou)
log(erroy)
10
−1
10
−0.3
10
−0.4
10
−0.5
10
−0.6
10
10
20
30
40
50
60
70
80
90
100
10
20
30
40
N
50
60
70
80
90
100
N
Figura 2.5: Variação em função de N do erro na variável de estado (esquerda) e na variável
de controle (direita).
2.2
Exemplo 2
Considere o problema de controle ótimo, discutido em [31, pág. 347], dado por:
R1
minimizar 0 (u2 (t) − y(t)3 ) dt
sujeito a
ẏ(t) = y(t)u(t)
y(0) = 1
y(1) = 1
−1 ≤ u(t) ≤ 0,
(2.14)
ˆ 1] e y ∈ C 1 [0, 1], ou seja, u : [0, 1] → IR é uma função contı́nua por partes e
onde u ∈ C[0,
y : [0, 1] → IR é uma função continuamente diferenciável. A solução deste problema é
(
y(t) ≡ 1,
u(t) ≡ 0.
(2.15)
A seguir discute-se a resolução numérica pelo método estudado na Seção 1.2.
2.2.1
Solução aproximada pelo método pseudoespectral
De maneira análoga ao exemplo anterior, se faz a mudança de variável de t ∈ [0, 1]
para τ ∈ [−1, 1]. Por (1.8) tem-se que:
1
1
t= τ+ .
2
2
Assim,
dτ
=2
dt
e
ẏ =
dy
dy dτ
dy
=
=2
dt
dτ dt
dτ
Exemplos
36
e a restrição do problema (2.14) se escreve como
dy
1
= y(τ )u(τ ).
dτ
2
Sejam N pontos de colocação LGR, −1 = τ1 < τ2 < ... < τN < 1, obtidos como raı́zes
da soma dos polinômios de Legendre PN −1 (τ ) + PN (τ ). Considere D ∈ IRN ×N a matriz
dy
e a restrição se
de diferenciação definida em (1.14). Por (1.15) tem-se que DY ≈
dτ
reescreve como
1
DY = Y U,
2
onde Y, U ∈ IRN .
Tendo os pontos de colocação, e sabendo que os pesos wi0 s, com i = 1, . . . , N ,
para a discretização do problema, é dado, segundo [1], por
Z
w(i) =
N
1 Y
−1
j=1
j6=i
τ − τj
dτ,
τi − τj
pode-se discretizar o problema (2.14), que toma a forma
minimizar
N
X
(u2k − yk3 )wk
k=1
sujeito a
2DY = Y U
y1 = 1
yN +1 = 1.
(2.16)
Os procedimentos utilizados para resolver este problema são análogos aos que
foram utilizados para resolver o exemplo anterior. O problema foi resolvido numericamente em Matlab. O vetor w ∈ IRN de pesos da quadratura associados com os N pontos
de colocação LGR foram obtidos pela rotina pontos lgr w. A matriz de diferenciação
D ∈ IRN ×N foi calculada pela rotina matriz dif. O problema 2.16 que consiste na minimização de uma função não linear, não quadrática, sujeita a restrições de igualdade
não lineares e condições de contorno na variável (y, u) ∈ IR2N , foi resolvido pela função
fmincon disponı́vel em Matlab. As rotinas utilizadas estão disponı́veis no Apêndice B.
A Figura 2.6 apresenta uma solução do problema tomando-se N = 60. O sı́mbolo
triangular representa a solução aproximada para a variável de estado y e o sı́mbolo asterisco é usado para representar a variável de controle u associadas com cada um dos 60
pontos de colocação.
Exemplos
37
1.2
1
0.8
0.6
y
u
0.4
0.2
0
−0.2
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
τ
Figura 2.6: Solução obtida pelo método pseudoespectral.
Análise de erros. Adotando-se soluções iniciais arbitrárias, foram resolvidas 30 instâncias
do problema (2.16) para cada valor de N entre 2 e 100. Para cada uma destas instâncias,
foi calculada a norma infinito do vetor diferença entre a solução exata e a solução numérica
para a variável de estado y e para a variável de controle u. Ou seja, foram calculados os
erros dados por
erroy = kyexata − yaprox k∞
e
errou = kuexata − uaprox k∞ .
onde (yexata , uexata ) é dado em (2.15) e (yaprox , uaprox ) é a solução numérica fornecida
pela rotina fmincon. Para cada um dos valores de N considerados, foi tomada a mediana
dos erros obtidos nas 30 instâncias. Os gráficos da Figura 2.7 mostram a variação do erro
na escala logarı́tmica para a solução aproximada do estado e de controle, respectivamente,
em relação ao número de pontos de colocação N entre 2 e 100. Note que os erros são
da ordem de 10−8 e que neste caso, diferentemente do caso anterior, os erros aumentam
com o valor de N . As linhas cheias correspondem à curva de regressão linear na escala
logarı́tmica cujos coeficientes foram fornecidos pelo comando polyfit do Matlab.
2.3
Exemplo 3
O segundo problema consiste em determinar o estado y ∈ Cˆ1 e o controle u ∈ Cˆ
como solução do seguinte problema de Bolza:
R2
minimizar y 2 (2) + 0 y(t)2 dt
sujeito a ẏ(t) = u(t)
y(0) = 1
−1 ≤ u(t) ≤ 1,
(2.17)
Exemplos
38
−8
−5
10
10
erro
u
2.99
−6
1.41e−14N
10
−9
10
−7
10
−8
10
log(errou)
log(erroy)
−10
10
−11
10
−10
10
−11
erroy
−12
10
10
2.24
3.27e−14N
−12
10
−13
10
−9
10
0
−13
20
40
60
80
10
100
0
20
40
N
60
80
100
N
Figura 2.7: Variação do erro das variáveis y e u na escala logarı́tmica em relação a N .
cuja solução exata apresentada em [31, pag 348] é
(
y(t) =
2.3.1
(
1 − t se t ≤ 1,
0
se t > 1,
e
u(t) =
−1 se t ≤ 1,
0 se t > 1.
(2.18)
Solução aproximada pelo método pseudoespectral
Inicialmente considera-se a mudança de variável de t ∈ [0, 2] para τ ∈ [−1, 1], ou
seja,
t = τ + 1.
Assim,
dy
dy dτ
dy
dτ
=1
e
ẏ =
=
=
dt
dt
dτ dt
dτ
e a restrição do problema (2.17) se escreve como
dy
= u(τ ).
dτ
Calculam-se os N pontos de colocação LGR, −1 = τ1 < τ2 < ... < τN < 1, o vetor de
pesos w ∈ IRN e a matriz de diferenciação D ∈ IRN ×N como discutidos nos exemplos
anteriores. Como a função objetivo do problema (2.17) envolve o valor y(2), considera-se,
além das variáveis Y ∈ IRN e U ∈ IRN , uma variável adicional denotada por YN +1 . Assim
o problema (2.17) se escreve na forma discretizada como
minimizar YN2 +1 +
N
X
yk2 wk
k=1
sujeito a
DY = U
y1 = 1
−1 ≤ U ≤ 1.
(2.19)
Exemplos
39
Note que o problema acima consiste na minimização de uma função quadrática com
restrições de igualdade lineares e condições de contorno, na variável (Ȳ , U ) ∈ IR2N +1 ,
onde Ȳ = (Y, YN +1 ) ∈ IRN +1 e U ∈ IRN . Deste modo este problema pode ser resolvido
pela rotina quadprog disponı́vel no Matlab.
A Figura 2.8 apresenta a solução exata e a solução numérica, considerando-se 60
pontos de colocação e solução inicial arbitrária. A solução exata (2.18) que se escreve na
variável τ como
(
(
−τ se τ ≤ 0,
−1 se τ ≤ 0,
y(τ ) =
e
u(τ ) =
0 se τ > 0,
0 se τ > 0.
está representada por linhas cheias. O sı́mbolo triangular representa a solução aproximada
para a variável de estado y e o sı́mbolo asterisco é usado para representar a variável de
controle u.
1
0.8
0.6
0.4
0.2
0
−0.2
−0.4
−0.6
yexato
uexato
yaprox
−0.8
uaprox
−1
−1
−0.8
−0.6
−0.4
−0.2
0
0.2
0.4
0.6
0.8
1
τ
Figura 2.8: Solução do problema 2.17.
Note que a variável de controle u é uma função descontı́nua. A solução aproximada assume erros maiores no ponto de descontinuidade e no extremo direito do intervalo.
No Apêndice B são apresentadas as listagens das rotinas em Matlab utilizadas.
Análise de erros. Adotando-se soluções iniciais arbitrárias, foram resolvidas 30 instâncias
do problema (2.19) para cada valor de N entre 10 e 100. Para cada uma destas instâncias,
foi calculada a norma infinito do vetor diferença entre a solução exata e a solução numérica
para a variável de estado y e para a variável de controle u. Ou seja, foram calculados os
erros dados por
erroy = kyexata − yaprox k∞
e
errou = kuexata − uaprox k∞ .
onde (yexata , uexata ) é dado em (2.18) e (yaprox , uaprox ) é a solução numérica fornecida
Exemplos
40
pela rotina quadprog. Para cada um dos valores de N considerados, foi tomada a mediana
dos erros obtidos nas 30 instâncias. Como já ressaltado, tendo em vista a descontinuidade
da variável de controle u, o erro da solução aproximada na região de descontinuidade
é grande e foi desconsiderado na análise de erro. Os gráficos da Figura 2.9 mostram a
variação do erro, na escala logarı́tmica para a solução aproximada do estado e de controle,
respectivamente, em relação ao número de pontos de colocação N entre 10 e 100. As linhas
cheias representam as curvas de regressão linear na escala logarı́tmica cujos coeficientes
foram fornecidos pelo comando polyfit do Matlab. Enquanto o erro na variável de estado
é da ordem de 10−3 , o erro na variável de controle é da ordem de 10−1 .
erroy
errou
0.048N−0.891
0.472N−0.648
−1
log(erroy)
log(errou)
10
−3
10
−2
10
20
30
40
50
60
N
70
80
90
100
10
10
20
30
40
50
60
70
80
90
100
N
Figura 2.9: Variação do erro das variáveis y e u na escala logarı́tmica em relação a N .
Conclusão
Discutiu-se neste trabalho o método de discretização pseudoespectral com pontos
de colocação LGR. Esta técnica é utilizada para encontrar soluções numéricas de problemas de controle ótimo sem restrições (problema de Bolza tipo LQR), como foi publicado
em [22]. Apresentação da técnica segue a sequência em que o método pseudoespectral
LGR é mostrado em [22], mas as demonstrações são próprias e estão dadas em notação
tensorial. Para medir diretamente a precisão do método pseudoespectral LGR, é necessário ter a solução exata do problema. A solução exata do problema de Bolza LQR
de controle ótimo foi encontrada utilizando o Princı́pio de Máximo de Pontryagin. Para
comparar (positivamente) o desempenho do método pseudoespectral LGR, o problema
LQR de Bolza é resolvido também aplicando uma discretização de Euler da equação de
estado é por uma quadratura tipo Euler do funcional. A discretização da equação de
estado fornece uma forma de exprimir as variáveis de estado em termos das variáveis
de controle. A substituição desta relação na quadratura permite utilizar um método de
otimização quadrática da variável de controle. O método pseudoespectral LGR é também
aplicado bem sucedidamente a problemas de controle ótimo com restrições nas variáveis
de estado e de controle (algo que não é tentado em [22]).
Todos os códigos MATLAB estão incluı́dos no Apêndice desta dissertação e serão
postados no site do Programa de Pós-graduação em Matemática Aplicada da Universidade
Federal do Paraná. Também no Apêndice encontra-se uma revisão de conceitos referentes
a este trabalho.
Apêndice A
Revisão de Conceitos
Neste capı́tulo apresentam-se algumas definições, propriedades e ressaltam-se alguns resultados que podem ser úteis para o entendimento deste trabalho. As principais
referências deste capı́tulo são [9, 10, 11, 12, 18, 25, 26, 27, 29].
A.1
Matriz
Nesta seção, que é baseada principalmente em [27], apresentam-se algumas definições e resultados essenciais de matrizes que foram utilizados no trabalho. Inicialmente
apresenta-se a definição de um tipo de matriz que é muito comum em problemas de
otimização.
Definição A.1 [25, pag. 260] Seja A ∈ IRn×n uma matriz simétrica. Diz-se que A é
definida positiva quando xT Ax > 0, para todo x ∈ IRn \{0}. Tal propriedade é denotada
por A > 0. Se xT Ax ≥ 0, para todo x ∈ IRn , A é dita semidefinida positiva, fato este
denotado por A ≥ 0.
A.1.1
Produto direto de Matrizes
Em várias demonstrações do Capı́tulo 1 usa-se produto direto de matrizes. Nesta
seção apresentam-se a definição de produto direto de matrizes, algumas propriedades deste
produto e um exemplo de como se faz este cálculo.
Definição A.2 Dadas as matrizes A ∈ IRm×n e B ∈ IRp×q define-se o produto direto de
A por B como a matriz C ∈ IRmp×nq de tal forma que

Cmp×nq


=A⊗B =


···
···
...
a1n B
a2n B
..
.
am1 B am2 B · · ·
amn B
a11 B
a21 B
..
.
42
a12 B
a22 B
..
.



.


Apêndice
43
Algumas propriedades interessantes do produto direto de matrizes:
(i) A ⊗ B 6= B ⊗ A;
(ii) Se u e v são vetores, então uT ⊗ v = v ⊗ uT = vuT ;
(iii) Se as dimensões são compatı́veis
(A ⊗ B)(C ⊗ D) = AC ⊗ BD.
Exemplo A.3 Calcule o produto direto de A por B, sendo
A=
1 2
1/2 4
!
1 2 4
6 8 10
eB=
!
.
Pela definição e sendo A ∈ IR2×2 e B ∈ IR2×3 o resultado será uma matriz
C ∈ IR4×6 . Para construı́-la, os seus elementos serão vistos como blocos, ou seja, Cij é o
bloco (i, j) de mesma dimensão de B. Assim,
C11 = a11 B = 1 ∗
C21 = a21 B = 1/2 ∗
1 2 4
6 8 10
1 2 4
6 8 10
!
C12 = a12 B = 2 ∗
,
!
,
C22 = a22 B = 4 ∗
1 2 4
6 8 10
1 2 4
6 8 10
!
,
!
.
E então,



C=


A.1.2
1
6
1/2
3

2 4 2 4 8

8 10 12 16 20 
.
1 2 4 8 16 

4 5 24 32 40
Exponencial de matriz
Considere a ∈ IR. Ao resolver a equação diferencial ordinária (EDO) escalar
ẋ(t) = ax,
obtém-se a seguinte fórmula,[10], para a solução do problema com condição inicial x(0) =
x0 ∈ IR:
x(t) = x0 eat ,
t ∈ IR.
Na próxima seção, será vista a equação análoga quando a é uma matriz n × n com
coeficentes reais e x : IR → IRn . Para isto, precisa-se saber como calcular a exponencial
de uma matriz. As referências sobre o assunto são [10, 11, 29].
Apêndice
44
Considera-se a função f : IR → IR+ tal que f (x) = ex . Essa função é chamada
de exponencial de x e tem a seguinte representação, [29], por séries de Taylor
ex =
∞
X
xk
k=0
k!
.
Desta forma parece ser natural a definição a seguir
Definição A.4 [11, pag.330] Seja A ∈ IRn×n . A matriz definida pela série
∞
X
Ak
k=0
k!
,
sendo
A0 = I
é denominada exponencial da matriz A. Para representá-la usa-se a notação eA ou ainda
exp(A).
Para os problemas estudados neste trabalho, é suficiente saber como calcular uma exponencial de matriz diagonalizável.
Definição A.5 [29, Def.3.1] Uma matriz A ∈ IRn×n é diagonalizável quando existem
uma matriz invertı́vel S, cujas colunas são os autovetores de A e uma matriz diagonal D
formada pelos autovalores de A tal que
D = S −1 AS.
Proposição A.6 [29, Prop. 3.2] Se A é uma matriz diagonalizável, D = S −1 AS, então
−1
eA = eSDS = SeD S −1 .
Demonstração. Multiplicando a igualdade D = S −1 AS pela esquerda por S e depois pela
direita por S −1 tem-se que
A = SDS −1 .
Além disso,
(SDS −1 )k = (SDS −1 )(SDS −1 ) · · · (SDS −1 ) = SDk S −1 .
|
{z
}
k vezes
Logo, para n ∈ IN as somas parciais são dadas por
Sn =
n
X
(SDS −1 )k
k=0
k!
=
n
X
SDk S −1
k!
k=0
=S
n
X
Dk
k=0
!
k!
S −1 .
Portanto,
"
SDS −1
eA = e
= lim Sn = lim S
n→∞
n→∞
n
X
Dk
k=0
k!
!
#
S −1 = S
lim
n→∞
n
X
Dk
k=0
k!
!
S −1 = SeD S −1 .
Apêndice
45
Teorema A.7 [29, Teo. 3.4] Seja D = diag(α1 , α2 , . . . , αn ), uma matriz diagonal n × n.
Então eD = diag(eα1 , eα2 , . . . , eαn ).
Demonstração. Seja D uma matriz diagonal com entradas αi (i = 1, 2, . . . , n). Assim
para todo k ∈ IN,
Dk = diag(α1k , . . . , αnk ).
Logo para cada n ∈ IN as somas parciais são dadas por
Sn =
n
X
Dk
k=0
k!
= diag
Assim
eD = lim Sn = lim
n→∞
A.2
n→∞
n
X
αk
1
k=0
n
X
Dk
k=0
k!
k!
,...,
n
X
αk
n
k=0
k!
!
.
!
= diag (eα1 , . . . , eαn ) .
Solução de um sistema de EDOs
O problema tratado no decorrer do trabalho está sujeito a uma equação diferencial. O objetivo é resolver esse problema, para isso deve-se lembrar como é a solução de
um sistema de EDOs de 1a e de 2a ordem.
Considere Ω ⊂ IRn e f : Ω → IRn uma aplicação contı́nua. Seja I um intervalo
não degenerado da reta, ou seja, um subconjunto conexo de IR não reduzido a um ponto.
Definição A.8 [30, pag 04.] Uma função diferenciável φ : I → IRn chama-se solução da
equação
dx
= f (x)
(A.1)
dt
no intervalo I se:
i) o gráfico de φ em I está contido em Ω e
ii)
dφ
(t) = f (φ(t)) para todo t ∈ I. Se t é um ponto extremo do intervalo, a derivada
dt
é a derivada lateral respectiva.
A equação (A.1) chama-se equação diferencial ordinária de primeira ordem e é
denotada abreviamente por
ẋ = f (x).
Sob hipóteses bem gerais sobre f , por exemplo se f e ∂f
são contı́nuas em Ω, existe uma
∂x
e só uma solução φ de (A.1) num intervalo que contém t0 e tal que φ(t0 ) = x0 . Uma tal φ
é chamada de solução do problema com dados iniciais (t0 , x0 ) para a equação (A.1). Este
Apêndice
46
problema pode ser denotado abreviadamente por
(
ẋ
= f (x)
x(t0 ) = x0 .
Para existência e unicidade de soluções de uma equação diferencial consultar [30, pag. 12]
e [10].
Lembra-se agora soluções de equações especı́ficas, que podem ser verificadas nos
Capı́tulos 3 e 10 de [10].
A solução do sistema de EDOs de primeira ordem
(
ẋ(t) = M x(t)
x(0) =
x0 ,
onde M ∈ IRn×n e x0 é o ponto inicial, é
x(t) = etM x0 .
A solução do sistema de EDOs de segunda ordem
(
ẍ(t) + bẋ(t) + cx(t) = 0
ẋ(tf ) = k1 , x(tf ) = k2
onde b, c ∈ IR e tf é o tempo final, é dada por
x(t) = c1 eλ1 t + c2 eλ2 t
quando a equação caracterı́stica, λ2 + bλ + c = 0, possui raı́zes reais distintas λ1 e λ2 . As
constantes c1 e c2 são encontradas de forma que as condições iniciais sejam satisfeitas.
A.3
Tópicos de otimização contı́nua
Nesta seção são introduzidos alguns tópicos de otimização contı́nua que serão
úteis para o desenvolvimento deste trabalho.
Inicia-se com algumas ideias básicas sobre minimização de uma função. Em
seguida é apresentado o método de gradiente conjugado para minimização de uma função
quadrática. E encerra-se esta seção com um teorema de otimalidade de primeira ordem
para problemas de otimização com restrições, o teorema de Karush-Kuhn-Tucker(KKT).
Para as demonstrações dos teoremas e maiores detalhes, consultar [12].
Pode-se dizer que otimização consiste em encontrar pontos de mı́nimos ou de
máximos de uma função real sobre um conjunto Ω ⊂ IRn . Isto pode ser representado pelo
Apêndice
47
seguinte problema
minimizar f (x)
sujeito a x ∈ Ω,
(A.2)
onde f : IRn → IR é uma função contı́nua dita função objetivo e Ω ⊂ IRn é um conjunto
chamado de conjunto viável. Quando Ω = IRn , o problema é dito irrestrito.
Definição A.9 [12, pag. 25] Considere f : IRn → IR e x∗ ∈ Ω ⊂ IRn . Diz-se que x∗
é um minimizador local de f em Ω quando existe δ > 0 tal que f (x∗ ) ≤ f (x) para todo
x ∈ B(x∗ , δ) ∩ Ω. Caso f (x∗ ) ≤ f (x) para todo x ∈ Ω, x∗ é dito minimizador global de f
em Ω.
Normalmente contenta-se com a obtenção de minimizadores locais do problema, onde esta
discussão será focada.
O teorema a seguir nos dá uma condição necessária para caracterizar um minimizador local de um problema irrestrito. Os pontos que satisfazem tal condição necessária
são ditos estacionários.
Teorema A.10 Seja f : IRn → IR diferenciável no ponto x∗ ∈ IRn . Se x∗ é um minimizador local de f em IRn então
∇f (x∗ ) = 0.
Demonstração. [12, Teo. 2.9].
Em um problema de otimização é difı́cil resolver, de forma direta, o sistema de
n equações e n incógnitas dado por ∇f (x) = 0. Normalmente uma solução é obtida por
meio de um processo iterativo. Considera-se então um algoritmo que a partir de um
ponto inicial x0 , gera uma sequência de pontos (xk ) desejando-se que os seus pontos de
acumulação sejam estacionários.
A.3.1
Método de gradientes conjugados
Apresenta-se nesta seção o método de gradientes conjugados [12, Sec.5.3] para
minimização de funções quadráticas.
Considere a função quadrática f : IRn → IR dada por
1
f (x) = xT Ax + bT x + c,
2
(A.3)
com A ∈ IRn×n definida positiva, b ∈ IRn e c ∈ IR.
Segundo [12], uma função f quadrática com Hessiana definida positiva tem um
único minimizador x∗ , que é global e satisfaz, pelo Teorema A.10, a seguinte condição
∇f (x∗ ) = Ax∗ + b = 0.
Apêndice
48
Para entender o algoritmo são necessários alguns conceitos.
Definição A.11 [12, pag. 64] Seja A ∈ IRn×n uma matriz definida positiva. Os vetores
d0 , d1 , ..., dk ∈ IRn \{0} são ditos A-conjugados se
(di )T Adj = 0,
para todos i, j = 0, 1, ..., k, com i 6= j.
Note que, no caso particular onde A é a matriz identidade, vetores A-conjugados
são ortogonais no sentido usual.
Sabe-se que um método de gradientes conjugados minimiza um função quadrática
em IRn em no máximo n iterações.
Dado um conjunto qualquer de direções A-conjugadas d0 , d1 , ..., dn−1 , define-se
uma sequência finita da seguinte maneira: dado x0 ∈ IRn arbitrário, define-se para
k = 0, 1, ..., n − 1,
xk+1 = xk + tk dk ,
(A.4)
onde tk = argmin{f (xk + tdk )}. O escalar tk é o comprimento do passo na direção dk a
t∈IR
partir do ponto corrente xk .
Como f é quadrática pode-se obter uma fórmula explı́cita para tk . Para isso,
define-se φ : IR → IR por φ(t) = f (xk + tdk ). Como, pela definição, tk é o minimizador
de f (xk + tdk ), tem-se que φ0 (tk ) = 0. Note que φ0 (tk ) = ∇f (xk + tk dk )T dk . Por f ser
quadrática
∇f (xk + tk dk ) = A(xk + tk dk ) + b = (Axk + b) + tk Adk = ∇f (xk ) + tk Adk .
Assim,
φ0 (tk ) = ∇f (xk )T + tk Adk dk = 0,
ou seja,
tk = −
∇f (xk )T dk
.
(dk )T Adk
Agora mostra-se como gerar as direções conjugadas.
Dado x0 ∈ IRn , defina d0 = −∇f (x0 ) e, para k = 0, 1, ..., n − 2,
dk+1 = −∇f (xk+1 ) + βk dk ,
onde xk+1 é dado por (A.4) e βk é tal que dk e dk+1 sejam A-conjugados, ou seja,
(dk )T A(−∇f (xk+1 ) + βk dk ) = (dk )T Adk+1 = 0.
Apêndice
49
Isolando βk da igualdade acima
βk =
(dk )T A∇f (xk+1 )
.
(dk )T Adk+1
Agora com todas as ferramentas necessárias, apresenta-se o algoritmo de gradientes conjugados.
Algoritmo A.1 Gradientes conjugados para funções quadráticas
Dado: x0 ∈ IRn , faça d0 = −∇f (x0 )
k=0
repita enquanto ∇f (xk ) 6= 0
∇f (xk )T dk
tk = − k T k
(d ) Ad
k+1
x
= xk + tk dk
(dk )T A∇f (xk+1 )
βk =
(dk )T Adk
k+1
d
= −∇f (xk+1 ) + βk dk
k =k+1
O algoritmo de gradientes conjugados neste formato é aplicado apenas para
funções quadráticas.
A.3.2
O Teorema de Karush-Kuhn-Tucker
O objetivo desta seção é apresentar as condições de otimalidade ou sejam, as
condições de KKT (Karush-Kuhn-Tucker), para o problema geral de otimização, que
consiste em
minimizar
f (x)
(A.5)
sujeito a g(x) ≤ 0
h(x) = 0,
onde f : IRn → IR, g : IRn → IRp e h : IRn → IRm são funções continuamente diferenciáveis.
O problema (A.5) é o problema (A.2) em que o conjunto viável é dado por
Ω = {x ∈ IRn | g(x) ≤ 0, h(x) = 0}.
Definição A.12 [12, pag. 97] Seja x ∈ Ω. Uma restrição de desigualdade gi é dita ativa
em x, se gi (x) = 0. Caso gi (x) < 0, diz-se que gi é inativa em x.
Denota-se por A(x) o conjunto de ı́ndices das restrições de desigualdade ativas em um
ponto viável x, isto é,
A(x) = {i | gi (x) = 0}.
Apêndice
50
Teorema A.13 (KKT) Seja x∗ ∈ Ω um minimizador local do problema (A.5) e suponha
que o conjunto dos gradientes das restrições de desigualdade ativas e das restrições de
igualdade são linearmente independentes, isto é, {∇gi (x∗ )}i∈A(x∗ ) ∪ {∇hj (x∗ )}j∈{1,...,m} é
LI. Então existem µ∗ ∈ IRp e λ∗ ∈ IRm tais que
∗
−∇f (x ) =
p
X
µ∗i ∇gi (x∗ )
i=1
+
m
X
λ∗j ∇hi (x∗ ),
j=1
µ∗i ≥ 0, i = 1, ..., p,
µ∗i gi (x∗ ) = 0, i = 1, ..., p.
Demonstração. [19, Teo. 12.1]
Os vetores λ∗ e µ∗ são chamados de multiplicadores de Lagrange.
Note que, o resultado do teorema diz que o oposto do gradiente da função objetivo
pode ser expresso pela combinação linear dos gradientes das restrições do problema.
Interpretação geométrica
Para representar geometricamente o que o teorema de KKT afirma, considere o
seguinte problema
minimizar f (x) = (x1 − 2)2 + (x2 − 1)2
sujeito a g1 (x) = x1 + x2 − 2 ≤ 0
g2 (x) = x21 − x2 ≤ 0
x1 ≥ 0
x2 ≥ 0,
onde f : IR2 → IR, g1 : IR2 → IR e g2 : IR2 → IR.
(A.6)
!
1
Primeiramente note que o ponto x∗ =
é solução global do problema.
1
Na figura abaixo, estão representados algumas curvas de nı́vel da função, o conjunto viável e a solução x∗ .
Apêndice
51
Figura A.1: Ilustração do problema (A.6).
1
1
! Na figura abaixo, estão representados os gradientes das restrições ativas no ponto
e o oposto do gradiente da função objetivo.
Figura A.2: Ilustração da relação dos gradientes do problema (A.6).
2
−1
Algebricamente tem-se que ∇f (x∗ ) =
!
−2
0
!
, ∇g1 (x∗ ) =
1
1
!
, ∇g2 (x∗ ) =
. Assim
2
2
−∇f (x∗ ) = ∇g1 (x∗ ) + ∇g2 (x∗ ),
3
3
ou seja, o oposto do gradiente da função objetivo no ponto x∗ é combinação linear, com
coeficientes µ = λ = 32 , dos gradientes das restrições no ponto x∗ .
Apêndice B
Códigos em Matlab
52
Cálculo dos Pontos de Colocação e pesos de Quadratura
function [x,w]=pontos_lgr_w(n)
%========================================================================
% Karla Arsie - 2012
% Calcula os n pontos LGR como raizes de P_{n-1}(x)+P_{n}(x).
% Polinomio de Legendre P_n = P(:,n+1)
%
% Foi baseado no programa disponivel em:
% http://www.mathworks.com/matlabcentral/fileexchange/4775-legende-gausslobatto-nodes-and-weights/content/lglnodes.m.
% conforme descricao abaixo e na referencia
%
F. B. Hildebrand , "Introduction to Numerical Analysis," Section 8.11
%
Dover 1987
%========================================================================
% lglnodes.m
%
% Computes the Legendre-Gauss-Lobatto nodes, weights and the LGL Vandermonde
% matrix. The LGL nodes are the zeros of (1-x^2)*P'_N(x). Useful for numerical
% integration and spectral methods.
%
% Reference on LGL nodes and weights:
%
C. Canuto, M. Y. Hussaini, A. Quarteroni, T. A. Tang, "Spectral Methods
%
in Fluid Dynamics," Section 2.3. Springer-Verlag 1987
%
% Written by Greg von Winckel - 04/17/2004
% Contact: [email protected]
%
% Truncation + 1
% N1=n;
% N=n-1;
N1=n;
N=n-1;
%Ponto inicial para pontos LGR
x=-cos(2*pi*(0:N)/(2*N+1))';
% Matriz de Vandermonde
P=zeros(N1,N1+1);
% Encontra P_(N), utilizando a relação de recorrencia
% Calcula suas derivadas de primeira e segunda ordem
% X: atualização usando o método de Newton-Raphson
xold=2;
free=2:N1;
while max(abs(x-xold))> eps
xold=x;
P(1,:)=(-1).^(0:N1);
P(free,1)=1;
P(free,2)=x(free);
53
Apêndice
54
for k=2:N1
P(free,k+1)=( (2*k-1)*x(free).*P(free,k)-(k-1)*P(free,k-1) )/k;
end
x(free)=xold(free)-((1-xold(free))/N1).*(P(free,N1)+P(free,N1+1))...
./(P(free,N1)-P(free,N1+1));
end
P=P(1:N1,1:N1);
% Calculo dos pesos
w=zeros(N1,1);
w(1)=2/N1^2;
w(free)=(1-x(free))./(N1*P(free,N1)).^2;
Apêndice
55
Matriz de Diferenciação
function D=matriz_dif(n,x)
%============================================================
% Karla, Miguel, Elizabeth
% 2012
% Fornece a matriz de diferenciacao
% Adaptacao do programa legsrddiff escrito por Wang Li-Lian disponivel em:
% http://www1.spms.ntu.edu.sg/~lilian/bookcodes/legen/legsrddiff.m
%=============================================================
% D=legsrddiff(n,x) returns the first-order differentiation matrix of size
% n by n, associated with the Legendre-Gauss-Radau points x, which may be
%computed by
% x=legsrd(n). Note: x(1)=-1.
% See Page 110 of the book: J. Shen, T. Tang and L. Wang, Spectral Methods:
% Algorithms, Analysis and Applications, Springer Series in Compuational
% Mathematics, 41, Springer, 2011.
% Use the function: lepoly()
% Last modified on August 31, 2011
%=============================================================
if n==0, D=[]; return; end;
xx=x; nx=size(x);
% Encontra L_{n-1}+L_n e sua derivada de primeira ordem
[dy1,y1]=lepoly(n-1,xx); [dy2,y2]=lepoly(n,xx); dy=dy1+dy2; y=y1+y2;
if nx(2)>nx(1), y=y'; dy=dy'; xx=x'; end; %% y é o vetor coluna de L_{n-1}(x_k)
D=(xx./dy)*dy'-(1./dy)*(xx.*dy)'; %% encontra dy(x_j) (x_k-x_j)/dy(x_k);
% 1/d_{kj} for k not= j (see (3.204))
D=D+eye(n);
% add a matriz identidade para que 1./D pode ser
% operada
D=1./D;
D=D-eye(n); xx=xx(2:end);
D=D+diag([-(n+1)*(n-1)/4; xx./(1-xx.^2)+ n*y1(2:end)./((1-xx.^2).*dy(2:end))]);
%atualiza as diagonais
return;
Apêndice
56
function [varargout]=lepoly(n,x)
% lepoly Legendre polynomial of degree n
% y=lepoly(n,x) is the Legendre polynomial
% The degree should be a nonnegative integer
% The argument x should be on the closed interval [-1,1];
% [dy,y]=lepoly(n,x) also returns the values of 1st-order
% derivative of the Legendre polynomial stored in dy
% Last modified on August 30, 2011
% Verified with the chart in http://keisan.casio.com/has10/SpecExec.cgi
if nargout==1,
if n==0, varargout{1}=ones(size(x)); return; end;
if n==1, varargout{1}=x; return; end;
polylst=ones(size(x)); poly=x;
% L_0(x)=1, L_1(x)=x
for k=2:n,
% Three-term recurrence relation:
polyn=((2*k-1)*x.*poly-(k-1)*polylst)/k;
% kL_k(x)=(2k-1)xL_{k-1}(x)-(k-1)L_{k-2}(x)
polylst=poly; poly=polyn;
end;
varargout{1}=polyn;
end;
if nargout==2,
if n==0, varargout{2}=ones(size(x)); varargout{1}=zeros(size(x));
return;
end;
if n==1, varargout{2}=x; varargout{1}=ones(size(x));
return;
end;
polylst=ones(size(x)); pderlst=zeros(size(x));poly=x; pder=ones(size(x));
% L_0=1, L_0'=0, L_1=x, L_1'=1
for k=2:n,
% Three-term recurrence relation:
polyn=((2*k-1)*x.*poly-(k-1)*polylst)/k;
% kL_k(x)=(2k-1)xL_{k-1}(x)-(k-1)L_{k-2}(x)
pdern=pderlst+(2*k-1)*poly; % L_k'(x)=L_{k-2}'(x)+(2k-1)L_{k-1}(x)
polylst=poly; poly=polyn;
pderlst=pder; pder=pdern;
end;
varargout{2}=polyn; varargout{1}=pdern;
end;
return
Apêndice
57
Solução Exata e pelo método Pseudoespectral do Problema do Exemplo 1
go_ex1
%=====================================================
% Dissertacao de Mestrado de Karla Arsie
% 17/08/2012
% Problema: maximizar -int_{0}^{5}(x^2(t)+u^2(t)) dt
%
sujeito dx/dt=x+u
%
x(0)=sqrt{2},x(5)=1
% Primeiro Exemplo do Capitulo 2 da dissertacao
%=====================================================
clear all
N=60; % Numero de pontos de colocacao
X1=sqrt(2); Xend=1; % Condicoes de contorno
% Solucao aproximada
[tau,VETORW]=pontos_lgr_w(N); % retorna os pontos de colocacao e os pesos da
discretizacao.
MATRIZD=matriz_dif(N,tau); %retorna matriz de diferenciacao
%ponto inicial
x0=X1*rand(N,1);
x0(1)=X1;
u0=rand(N,1);
xu0 = [x0;u0];
% Dados do problema para ser resolvido pelo quadprog nas variaveis
%(x1,..xN,u1,..uN)
xu0 = [x0;u0];
H=diag([VETORW;VETORW]);
f=zeros(2*N,1);
id=eye(N,N);
Aeq = [(2*MATRIZD/5-id) -id];
Beq =zeros(N,1);
% Limites apos varios testes ----------------LB = [X1;zeros(N-2,1);1;-inf*ones(N,1)];
UB = [X1;inf*ones(N-2,1);1;inf*ones(N,1)];
[xu,fval,EXITFLAG] = quadprog(H,f,[],[],Aeq,Beq,LB,UB,xu0);
x = [X1;xu(2:N);Xend];
u = xu(N+1:2*N);
Apêndice
58
% --------------------------------------------------------% Solucao exata
s=X1;
x0=s;
p0=(4*s-exp(5*s)*(2*s+4)-exp(-5*s)*(4-2*s))/(exp(5*s)-exp(-5*s));
x_exata=(exp(s*((5/2)*tau+5/2))*((1-exp(-5*s))/(exp(5*s)-exp(-5*s)))+ exp(s*((5/2)*tau+5/2))*(s-(1-exp(-5*s))/(exp(5*s)-exp(-5*s))))'; %no intervalo [-1,1]
y_exata=x_exata.^2;
p=(((s/2)*exp(s*((5/2)*tau+5/2))-(s/2)*exp(-s*((5/2)*tau+5/2)))*x0+(((2s)/(4))*exp(s*((5/2)*tau+5/2))+((2+s)/(4))*exp(-s*((5/2)*tau+5/2)))*p0)';
%no intervalo [-1,1]
u_exata=p/2;
% Graficos
%----------------------------------------------------------figure(1)
clf
axis([-1 5 -4 2])
%solucao exata
plot(tau,y_exata,'b-',tau,u_exata,'r-')
hold on
xlabel('\tau','fontsize',20)
% Solucao aproximada --------------------------------------plot([tau;1],x.*x,'^b')
plot(tau(1:N-1),u(1:N-1),'*r')
legend('y_{exato}','u_{exato}','y_{aprox}','u_{aprox}','Location','SouthEast')
%----------------------------------------------------------figure(2)
clf
axis([-1 5 -4 2])
%solucao exata
plot(tau,y_exata,'b-',tau,u_exata,'r-')
hold on
xlabel('\tau','fontsize',20)
% Solucao aproximada --------------------------------------plot([tau;1],x.*x,'^b')
plot(tau(1:N-1),u(1:N-1),'*r')
euler_ex1
legend('y_{exato}','u_{exato}','y_{aprox}','u_{aprox}','y_{Euler}',
'u_{Euler}','Location','SouthEast')
%-----------------------------------------------------------
% Erro na restricao
%ndifEx=norm(MATRIZD*y_exata-u_exata);
ndifAp=norm(2*MATRIZD/5*x(1:N)-x(1:N)-u);
fprintf(' %4d |
%7.3f | %2d \n',N,ndifAp,EXITFLAG)
Apêndice
59
Solução pelo método de Euler do Problema do Exemplo 1 - euler_ex1
%=======================================================
% Dissertacao de Mestrado de Karla Arsie
% 25/05/2012
% Problema: maximizar -int_{0}^{5}(x^2(t)+u^2(t)) dt
%
sujeito dx/dt=x+u
%
x(0)=sqrt{2},x(5)=1
% Primeiro Exemplo do Capitulo 2 da dissertacao
%resolvido pelo método de Euler
%=====================================================
n=N;
M=10^3;
h=5/(n-1);
[Q b c]=gra(n,X1);
% gera a quadratica a ser minimizada
% somando o termo M*(Xend-1)^2
beta=X1*(1+h)^(n-1)-Xend;
c=c+M*beta^2;
for i=1:n-1
b(i)=b(i)+2*M*beta*h*(1+h)^(n-i-1);
for j=1:n-1
Q(i,j)=Q(i,j)+2*M*h^2*(1+h)^(2*n-j-i-2);
end
end
u0=rand(n-1,1);
% Solucao aproximada Euler ---------------u_euler=GC(c,b,Q,u0); % usa Gradiente Conjugado para minimizacao
x_euler=zeros(n,1);
x_euler(1)=X1;
for k=2:n
x_euler(k)=(1+h)^(k-1)*X1;
for j=1:k-1
x_euler(k)=x_euler(k)+h*(1+h)^(k-j-1)*u_euler(j);
end
end
y_euler=x_euler.^2; % plotado y=x^2
t=-1:2/(N-1):1;t=t';
plot(t,y_euler,'og','linewidth',2)
plot(t(1:N-1),u_euler,'dk','linewidth',2)
Apêndice
Funções Auxiliares
function [Q b c]=gra(n,x1)
%Gera c,b e Q da função J=1/2sum(xk^2+uk^2)=c+b^Tu+u^TQu/2;
v=zeros(n,n-1);
for i=1:n-1
for j=i+1:n
v(j,i)=1;
end
end
%encontrar c
c=zeros(n-1,1);
h=1/(n-1);
h=5*h;
s=0;
x1=sqrt(2);
for k=1:n-1
s=s+(1+h)^(2*k-2)*x1^2;
end
c=h/2*s;
%encontrar b
z=zeros(n-1,n);
for k=2:n-1
for i=1:k-1
z(i,k)=h^2*(1+h)^(2*k-i-2)*x1;
end
end
for i=1:n-1
s=0;
for k=1:n
s=s+z(i,k)*v(k,i);
end
b(i)=s;
end
b=b';
%encontrar Q
w=zeros(n-1,n-1,n);
for k=2:n-1
for i=1:k-1
for j=1:k-1
w(i,j,k)=h^3*(1+h)^(2*k-i-j-2);
end
end
end
60
Apêndice
61
for i=1:n-1
for j=1:n-1
s=0;
if i==j
for k=1:n
s=s+w(i,i,k)*v(k,i);
end
s=s+h;
elseif i>j
for k=1:n
s=s+w(i,j,k)*v(k,i);
end
else
for k=1:n
s=s+w(i,j,k)*v(k,j);
end
end
Q(i,j)=s;
end
end
end
Apêndice
62
% Gradiente Conjugado
% função quadratica f(x)=c+bx+x'Qx/2
function x=GC(c,b,Q,x0);
x=x0;
n=length(x0)+1; % dimensao do problema.
gradfx=b+Q*x;
fx=c+b'*x+x'*Q*x/2;
d=-gradfx; % direcao d0
ngradf=norm(gradfx); % norma do grad
k=1;
kmax=3*n; %n;
epsilon=1e-6;
while (ngradf>=epsilon) & (k<=kmax)
Qd=Q*d;
dQd=d'*Qd;
alfa=-(d'*gradfx)/dQd;
x=x+alfa*d;
gradfx=b+Q*x;
ngradf=norm(gradfx);
fx=c+b'*x+x'*Q*x/2;
beta=(d'*Q*gradfx)/dQd;
d=-gradfx+beta*d;
if k>n
d=-gradfx;
end
k=k+1;
end
if ngradf>epsilon | k>=kmax
disp('GC - Nao resolveu')
fprintf('norma do gradiente:
pause(0.1)
end
%12f
\n',ngradf)
Apêndice
63
Solução pelo método Pseudoespectral do Problema do Exemplo 2 - go_ex2
%===========================================================
% Dissertacao de Mestrado de Karla Arsie
% 10/03/2013
% Problema: minimizar int_{0}^{1}(u^2(t)-y^3(t)) dt
%
sujeito dy/dt=yu
%
y(0)=1,y(1)=1
%
-1=<u(t)=<0
% Primeiro Exemplo Nao linear do Capitulo 2 da dissertacao
%==========================================================
clear all
global VETORW MATRIZD Y1 Yend
N=60; % numero de pontos de colocacao
Y1=1; Yend=1; % Condicoes de contorno
% Solucao aproximada
[tau,VETORW]=pontos_lgr_w(N); % pontos de colocacao e pesos da discretizacao
MATRIZD=matriz_dif(N,tau)/2; %retorna matriz de diferenciacao
%ponto inicial
y0=Y1*rand(N,1);
y0(1)=Y1;
u0=rand(N,1);
yu0 = [y0;u0];
% Dados do problema para ser resolvido pelo fmincon
A = [];
B = [];
Aeq = [];
Beq = [];
LB = [ones(N,1);-ones(N,1)];
UB = [Inf*ones(N,1);zeros(N,1)];
% Resolucao pelo fmincon
OPTIONS = OPTIMSET('Display','iter','GradObj','on');
[yu,fval,EXITFLAG] = FMINCON(@(yu0) funcao_ex2(yu0),yu0,A,B,Aeq,Beq,LB,UB,@(yu0)
nonlin_ex2(yu0),OPTIONS);
y = [Y1;yu(2:N);Yend];
u = yu(N+1:2*N);
%plota graficos da solucao aproximada
figure(3)
hold on
plot([tau;1],y,'^b')
plot(tau,u,'*r')
legend('y','u',4)
xlabel('\tau','fontsize',16)
Apêndice
64
function [J,grad_J]=my_functional_J(YU0)
%gera a funcao a ser minimziada
global VETORW MATRIZD Y1 Yend
n0 = (length(YU0))/2; % assumed to be n
Y0 = YU0(1:n0); % size n
U0 = YU0(n0+1:2*n0); % size n
J=VETORW'*(Y0.^3+U0.^2);
grad_J =[3*(Y0.^2).*VETORW;2*U0.*VETORW];
end
function [c,ceq]=nonlin(YU0) %gera as restricoes do problema
global VETORW MATRIZD Y1 Yend
% YU0 is [y(2:n-1),u]
c=[];
n0 = length(YU0)/2; % assumed to be n
Y0 = max(0,YU0(1:n0));
%evitar Y <0 % size n
%SY0 = diag(sqrt(Y0)); % size n x n
U0 = YU0(n0+1:2*n0); % size n
ceq = MATRIZD*Y0 - Y0.* U0; % size n
end
Apêndice
65
Solução pelo método Pseudoespectral do Problema do Exemplo 3 - go_ex3
%==========================================================================
% go_ex3
% Segundo Exemplo - Problema nao linear
% Referencia: J. L. Troutman. Variational Calculus and Optimal Control:
% Optimization with Elementary Convexity. Springer-Verlag, New York, 1996.
% Solucao exata com t in [0,2]: y(t) =1-t se t<=1, 0 c.c.
%
u(t)=1 se t<=1, 0 c.c.
% Solucao exata com tau in [-1,1]: y(tau) = -tau se tau <= 0, 0 c.c.
%
u(tau) = 1 se tau <= 0, 0 c.c.
% Dissertacao de Mestrado - Karla Arsie
% Marco/2013
%==========================================================================
clear all
N=60; % Numero de pontos de colocacao
Y1=1; Yend=0;% Condicoes de contorno
% Solucao aproximada
[tau,VETORW]=pontos_lgr_w(N); % retorna os pontos de colocacao
%e os pesos da discretizacao
MATRIZD=matriz_dif(N,tau); % retorna a matriz de diferenciacao
%ponto inicial
y0=[Y1*rand(N,1);Yend];
y0(1)=Y1;
u0=rand(N,1);
% Dados do problema para ser resolvido pelo quadprog nas variaveis
(y1,..yN,y{N+1},u1,..uN)
yu0 = [y0;u0];
H=2*diag([VETORW;1;zeros(N,1)]);
f=zeros(2*N+1,1);
Aeq = [MATRIZD zeros(N,1) -eye(N,N)];
Beq =zeros(N,1);
LB = [1;-inf*ones(N,1);-ones(N,1)];
UB = [1;inf*ones(N,1);ones(N,1)];
% Resolucao pelo quadprog
OPTIONS = OPTIMSET('Algorithm','interior-point-convex',
'Display','iter','GradObj','on');
yu = quadprog(H,f,[],[],Aeq,Beq,LB,UB,yu0,OPTIONS);
y = [Y1;yu(2:N);Yend];
u = yu(N+2:end);
Apêndice
%plota graficos para comparar solucao exata e solucao aproximada
figure(1);
clf
% Solucao Exata
plot([-1 0 1],[1 0 0],'b-','linewidth',2)
hold on
plot([-1 0],[-1 -1],'r-','linewidth',2)
plot([tau;1],y,'^b')
plot(tau,u,'*r')
axis([-1 1 -1 1])
xlabel('\tau','fontsize',24)
grid on
legend('y_{exato}','u_{exato}','y_{aprox}','u_{aprox}',4)
plot([0 1],[0 0],'r-')
plot([tau;1],y,'^b')
% Solucao exata nos pontos de colocacao para analise do erro
y_exata=-tau.*(tau<=0);
u_exata=-(tau<=0);
66
Referências Bibliográficas
[1] D. N. Arnold. A concise introduction to numerical analysis. School of Mathematics,
University of Minnesota, 1991.
[2] D. Benson. A gauss pseudospectral transcription for optimal control. Technical
report, Massachusetts Institute of Technology, 2005.
[3] J. T. Betts. Survey of numerical methods for trajectory optimization. Technical
report, Journal of Guidance, Control and Dynamics, Washington, Março-Abril 1998.
[4] J. T. Betts. Practical Methods for Optimal Control and Estimation Using Nonlinear
Programming. Society for Industrial & Applied Mathematics; 2nd edition, Washington, 2009.
[5] G.A. Bliss. The problem of Bolza in the calculus of variations. Annals of Mathematics(2), 33:261–274, 1932.
[6] M. L. Boas. Mathematical Methods in the Physical Sciences. John Wiley and Sons,
New York, 1983.
[7] C. Canuto, M. Y. Hussaini, A. Quarteroni, and T. A. Tang. Spectral Methods in
Fluid Dynamics. Springer-Verlag, 1987.
[8] D. Garg e A.V. Rao C.L. Darby. Costate estimation using multiple-interval pseudospectral methods. Journal of spacecraft and rockets, 48(5), 2011.
[9] P. J. Davis and P. Rabinowitz. Methods of Numerical Integration. Dover Publications,
INC, New York, 2a edition, 1984.
[10] C. I. Doering and A. O. Lopes. Equações Diferenciais Ordinárias. IMPA, Rio de
Janeiro, RJ, 2005.
[11] J. Baumeister e A. Leitão. Introdução à teoria de controle e programação dinâmica.
Instituto de Matemática Pura e Aplicada, Rio de Janeiro, Brasil, 1nd edition, 2008.
[12] A. A. Ribeiro e E. W. Karas. Um curso de Otimização. Cengage Learning, 2013. A
aparecer.
67
Referências Bibliográficas
68
[13] S. Islam e G. Saha. Applications of gauss-radau and gauss-lobatto numerical integrations over a four node quadrilateral finite element. Bangladesh J. Sci. Ind. Res.,
43(3):377–386, 2008.
[14] F. Fahroo e I. M. Ross. Pseudospectral methods for infinite-horizon nonlinear optimal
control problems. Journal of Guidance, Control, and Dynamics,, 31:927–936, 2008.
[15] S. Kameswaran e I. T. Biegler. Convergence rates for direct transcription of optimal
control problems using collocation at radau points. Computational Optimization and
Applications, 41:81–126, 2008.
[16] B. A. Finlayson e L. E. Scriven. The method of weighted residuals - a review. Applied
Mechanics Reviews, 19(9):735–748, 1966.
[17] O. Stryk e R. Bulirsch. Direct and indirect methods for trajectory optimization.
Annals of Operations Research, 37:357–373, 1992.
[18] N. Barron e R. Jensen. The pontryagin maximum principle from dynamic programming and viscosity solutions to first-order partial differential equations. Trans. Amer.
Math. Soc., 298:635–641, 1986.
[19] J. Nocedal e S. J. Wright. Numerical Optimization. Springer-Verlag, Springer Series
in Operations Research, USA, 2nd edition, 2006.
[20] F. Lewis e V. Syrmos. Optimal Control. John Wiley & Sons, INC, 3nd, New Jersey,
USA, 1995.
[21] M. Kazemi e M. Razzaghi G. Elnagar. The pseudospectral legendre method for
discretizing optimal control problems. IEEE Transactions on Automatic Control,
40:1793–1796, 1995.
[22] D. Garg, M. A. Patterson, C. Francolin, C. L. Darby, G. T. Huntington, W. W. Hager,
and A. V. Rao. Direct trajectory optimization and costate estimation of finite-horizon
and infinite-horizon optimal control problems using a Radau pseudospectral method.
Comput. Optim. Appl., 49:335–358, 2011.
[23] F. B. Hildebrand. Introduction to Numerical Analysis. Dover Publications, Dover,
2a edition, 1987.
[24] D. Kraft. On converting optimal control problems into nonlinear programming codes.
NATO ASI Series, Computational Mathematical Programming, ed. K. Schittkowski,
Springer, F15:261–280, 1985.
[25] S. J. Leon. Álgebra linear com Aplicações. Editora S.A., Rio de Janeiro, Brasil, 4nd
edition, 1998.
Referências Bibliográficas
69
[26] E. L. Lima. Curso de Análise volume 2. Instituto de Matemática Pura e Aplicada,
Rio de Janeiro, Brasil, 1981.
[27] A. Quarteroni, R. Sacco, and F. Saleri. Numerical Mathematics. Springer, New York,
2000.
[28] J. Stoer e K. H. Well (eds.) R. Bulirsch, A. Miele. Optimal control - calculus of
variations, optimal control theory and numerical methods. International Series of
Numerical Mathematics, 111:129–143, 1993.
[29] F. A. Silva. Sistemas de equações diferenciais e exponencial de matrizes. Cadernos
PET - Matemática, 1:169–195, 2007.
[30] J. Sotomayor. Lições de Equações Diferenciais. Projeto Euclides, IMPA, Rio de
Janeiro, Brasil, 1979.
[31] J. L. Troutman. Variational Calculus and Optimal Control: Optimization with Elementary Convexity. Springer-Verlag, New York, 1996.
[32] G.
V.
Winckel.
Código
em
Matlab.
Disponı́vel
http://www.mathworks.com/matlabcentral/fileexchange/4775-legende-gausslobatto-nodes-and-weights/content/lglnodes.m, consultado em junho de 2012.
em