Controle ótimo e programação dinâmica

Prévia do material em texto

Controle ótimo e programação dinâmica:
do discreto ao contínuo
e de volta outra vez
Bernardo Freitas Paulo da Costa
Sextas Matemáticas – 18 de Junho 2021
Bernardo Controle ótimo Sextas Matemáticas 1 / 18
Controle ótimo e programação dinâmica:
do discreto ao contínuo
e de volta outra vez
Bernardo Freitas Paulo da Costa
Sextas Matemáticas – 18 de Junho 2021
Bernardo Controle ótimo Sextas Matemáticas 1 / 18
Controle ótimo
Ideia fundamental: tomar decisões ao longo do tempo.
Modelo simples:
Estado: xt;
Controle: ut;
Dinâmica: xt`1 “ fpxt, utq;
Custo: cpxt, utq a cada instante, mais gpxT q final.
Problema: escolher ut para minimizar o custo total.
Bernardo Controle ótimo Sextas Matemáticas 2 / 18
Controle ótimo
Ideia fundamental: tomar decisões ao longo do tempo.
Modelo simples:
Estado: xt;
Controle: ut;
Dinâmica: xt`1 “ fpxt, utq;
Custo: cpxt, utq a cada instante, mais gpxT q final.
Problema: escolher ut para minimizar o custo total.
Bernardo Controle ótimo Sextas Matemáticas 2 / 18
Controle ótimo
Ideia fundamental: tomar decisões ao longo do tempo.
Modelo simples:
Estado: xt;
Controle: ut;
Dinâmica: xt`1 “ fpxt, utq;
Custo: cpxt, utq a cada instante, mais gpxT q final.
Problema: escolher ut para minimizar o custo total.
Bernardo Controle ótimo Sextas Matemáticas 2 / 18
Controle ótimo
Ideia fundamental: tomar decisões ao longo do tempo.
Modelo simples:
Estado: xt;
Controle: ut;
Dinâmica: xt`1 “ fpxt, utq;
Custo: cpxt, utq a cada instante, mais gpxT q final.
Problema: escolher ut para minimizar o custo total.
Bernardo Controle ótimo Sextas Matemáticas 2 / 18
Alguns exemplos
Clássicos:
Controlador linear quadrático: custo quadrático, dinâmica linear;
Alocação de pessoal: custos lineares, controle discreto;
Planejamento de operações: custos lineares, controle limitado;
Gestão de portfólio: custos aleatórios.
E contemporâneos:
Frota de carros elétricos: uso alternativo das baterias;
Serviço de entregas: cálculo de rotas e posições;
Bernardo Controle ótimo Sextas Matemáticas 3 / 18
Alguns exemplos
Clássicos:
Controlador linear quadrático: custo quadrático, dinâmica linear;
Alocação de pessoal: custos lineares, controle discreto;
Planejamento de operações: custos lineares, controle limitado;
Gestão de portfólio: custos aleatórios.
E contemporâneos:
Frota de carros elétricos: uso alternativo das baterias;
Serviço de entregas: cálculo de rotas e posições;
Bernardo Controle ótimo Sextas Matemáticas 3 / 18
Roteiro
1. Algoritmos diretos
2. Recorrência e função de custo futuro
3. Algoritmos “discretos”
4. Algoritmos “contínuos”
5. Um método universal
Bernardo Controle ótimo Sextas Matemáticas 4 / 18
Algoritmos diretos
OpT q variáveis de decisão: todas as xt e ut.
Custo por iteração:
Gradiente descendente: OpT q
Newton genérico: OpT 3q
Newton tridiagonal: OpT q
d “ dimpxtq ` dimputq
Bernardo Controle ótimo Sextas Matemáticas 5 / 18
Algoritmos diretos
OpT q variáveis de decisão: todas as xt e ut.
Custo por iteração:
Gradiente descendente: OpT q
Newton genérico: OpT 3q
Newton tridiagonal: OpT q
d “ dimpxtq ` dimputq
Bernardo Controle ótimo Sextas Matemáticas 5 / 18
Algoritmos diretos
OpT q variáveis de decisão: todas as xt e ut.
Custo por iteração:
Gradiente descendente: OpT q
Newton genérico: OpT 3q
Newton tridiagonal: OpT q
d “ dimpxtq ` dimputq
Bernardo Controle ótimo Sextas Matemáticas 5 / 18
Algoritmos diretos
OpT q variáveis de decisão: todas as xt e ut.
Custo por iteração:
Gradiente descendente: OpT q
Newton genérico: OpT 3q
Newton tridiagonal: OpT q
d “ dimpxtq ` dimputq
Bernardo Controle ótimo Sextas Matemáticas 5 / 18
Algoritmos diretos
OpT q variáveis de decisão: todas as xt e ut.
Custo por iteração:
Gradiente descendente: OpTdq
Newton genérico: OpT 3d3q
Newton tridiagonal: OpTd3q
d “ dimpxtq ` dimputq
Bernardo Controle ótimo Sextas Matemáticas 5 / 18
Recorrência
Caso T “ 1:
Qpx0q “
minu0,x1 cpx0, u0q ` gpx1q
s.a x1 “ fpx0, u0q
u0 P U , x1 P X.
Função de custo de um passo: Qpx0q.
Dado x0, é fácil calcular Qpx0q.
Bernardo Controle ótimo Sextas Matemáticas 6 / 18
Recorrência
Caso T “ 1:
Qpx0q “ minu0,x1 cpx0, u0q ` gpx1q
s.a x1 “ fpx0, u0q
u0 P U , x1 P X.
Função de custo de um passo: Qpx0q.
Dado x0, é fácil calcular Qpx0q.
Bernardo Controle ótimo Sextas Matemáticas 6 / 18
Recorrência
Caso T “ 1:
Qpx0q “ minu0,x1 cpx0, u0q ` gpx1q
s.a x1 “ fpx0, u0q
u0 P U , x1 P X.
Função de custo de um passo: Qpx0q.
Dado x0, é fácil calcular Qpx0q.
Bernardo Controle ótimo Sextas Matemáticas 6 / 18
O controlador linear-quadrático
Sem restrições em u e x, apenas com custos quadráticos:
Qpx0q “ minu0,x1 cpx0, u0q ` gpx1q
s.a x1 “ Ax0 `Bu0.
Proposição
O controle ótimo é linear em x0.
O custo Q é uma função quadrática de x0.
Ideia: condições de otimalidade lineares.
Bernardo Controle ótimo Sextas Matemáticas 7 / 18
O controlador linear-quadrático
Sem restrições em u e x, apenas com custos quadráticos:
Qpx0q “ minu0,x1 cpx0, u0q ` gpx1q
s.a x1 “ Ax0 `Bu0.
Proposição
O controle ótimo é linear em x0.
O custo Q é uma função quadrática de x0.
Ideia: condições de otimalidade lineares.
Bernardo Controle ótimo Sextas Matemáticas 7 / 18
O controlador linear-quadrático
Sem restrições em u e x, apenas com custos quadráticos:
Qpx0q “ minu0,x1 cpx0, u0q ` gpx1q
s.a x1 “ Ax0 `Bu0.
Proposição
O controle ótimo é linear em x0.
O custo Q é uma função quadrática de x0.
Ideia: condições de otimalidade lineares.
Bernardo Controle ótimo Sextas Matemáticas 7 / 18
Programação dinâmica I
Definimos
1. QT pxT q “ gpxT q;
2. Qtpxtq “ minut,xt`1 ctpxt, utq `Qt`1pxt`1q
s.a xt`1 “ Axt `Btut
;
3. Recorrência para calcular a forma quadrática Qt;
4. Complexidade: OpTd3q.
Ganhamos o controle ótimo partindo de qualquer x0.
Também é conhecido como “controle ótimo por feedback linear”.
Bernardo Controle ótimo Sextas Matemáticas 8 / 18
Programação dinâmica I
Definimos
1. QT pxT q “ gpxT q;
2. Qtpxtq “ minut,xt`1 ctpxt, utq `Qt`1pxt`1q
s.a xt`1 “ Axt `Btut
;
3. Recorrência para calcular a forma quadrática Qt;
4. Complexidade: OpTd3q.
Ganhamos o controle ótimo partindo de qualquer x0.
Também é conhecido como “controle ótimo por feedback linear”.
Bernardo Controle ótimo Sextas Matemáticas 8 / 18
Programação dinâmica I
Definimos
1. QT pxT q “ gpxT q;
2. Qtpxtq “ minut,xt`1 ctpxt, utq `Qt`1pxt`1q
s.a xt`1 “ Axt `Btut
;
3. Recorrência para calcular a forma quadrática Qt;
4. Complexidade: OpTd3q.
Ganhamos o controle ótimo partindo de qualquer x0.
Também é conhecido como “controle ótimo por feedback linear”.
Bernardo Controle ótimo Sextas Matemáticas 8 / 18
Programação dinâmica I
Definimos
1. QT pxT q “ gpxT q;
2. Qtpxtq “ minut,xt`1 ctpxt, utq `Qt`1pxt`1q
s.a xt`1 “ Axt `Btut
;
3. Recorrência para calcular a forma quadrática Qt;
4. Complexidade: OpTd3q.
Ganhamos o controle ótimo partindo de qualquer x0.
Também é conhecido como “controle ótimo por feedback linear”.
Bernardo Controle ótimo Sextas Matemáticas 8 / 18
Programação dinâmica I
Definimos
1. QT pxT q “ gpxT q;
2. Qtpxtq “ minut,xt`1 ctpxt, utq `Qt`1pxt`1q
s.a xt`1 “ Axt `Btut
;
3. Recorrência para calcular a forma quadrática Qt;
4. Complexidade: OpTd3q.
Ganhamos o controle ótimo partindo de qualquer x0.
Também é conhecido como “controle ótimo por feedback linear”.
Bernardo Controle ótimo Sextas Matemáticas 8 / 18
Programação dinâmica I
Definimos
1. QT pxT q “ gpxT q;
2. Qtpxtq “ minut,xt`1 ctpxt, utq `Qt`1pxt`1q
s.a xt`1 “ Axt `Btut
;
3. Recorrência para calcular a forma quadrática Qt;
4. Complexidade: OpTd3q.
Ganhamos o controle ótimo partindo de qualquer x0.
Também é conhecido como “controle ótimo por feedback linear”.
Bernardo Controle ótimo Sextas Matemáticas 8 / 18
Programação dinâmica II
Caso geral: discretizar Qt.
Complexidade: T ˆO
`
d3 ¨ p1{εqn
˘
.
d “ dimpxtq ` dimputq
n “ dimpxtq
p1{εqn é conhecido como a “maldição da dimensão”.
Bernardo Controle ótimo Sextas Matemáticas 9 / 18
Programaçãodinâmica II
Caso geral: discretizar Qt.
Complexidade: T ˆO
`
d3 ¨ p1{εqn
˘
.
d “ dimpxtq ` dimputq
n “ dimpxtq
p1{εqn é conhecido como a “maldição da dimensão”.
Bernardo Controle ótimo Sextas Matemáticas 9 / 18
Programação dinâmica II
Caso geral: discretizar Qt.
Complexidade: T ˆO
`
d3 ¨ p1{εqn
˘
.
d “ dimpxtq ` dimputq
n “ dimpxtq
p1{εqn é conhecido como a “maldição da dimensão”.
Bernardo Controle ótimo Sextas Matemáticas 9 / 18
O caso estocástico
Variáveis aleatórias ξt: influenciam custo e dinâmica.
ctpxt, ut, ξtq
xt`1 “ ftpxt, ut, ξtq
Variáveis de decisão: utpξrtsq e xt`1pξrtsq.
Outro crescimento exponencial:
dimpxt, utq “ OpN tq
com N amostras a cada estágio.
Bernardo Controle ótimo Sextas Matemáticas 10 / 18
O caso estocástico
Variáveis aleatórias ξt: influenciam custo e dinâmica.
ctpxt, ut, ξtq
xt`1 “ ftpxt, ut, ξtq
Variáveis de decisão: utpξrtsq e xt`1pξrtsq.
Outro crescimento exponencial:
dimpxt, utq “ OpN tq
com N amostras a cada estágio.
Bernardo Controle ótimo Sextas Matemáticas 10 / 18
O caso estocástico
Variáveis aleatórias ξt: influenciam custo e dinâmica.
ctpxt, ut, ξtq
xt`1 “ ftpxt, ut, ξtq
Variáveis de decisão: utpξrtsq e xt`1pξrtsq.
Outro crescimento exponencial:
dimpxt, utq “ OpN tq
com N amostras a cada estágio.
Bernardo Controle ótimo Sextas Matemáticas 10 / 18
Recorrência estocástica
Qtpxtq “ minut,xt`1 E rctpxt, ut, ξtq `Qt`1pxt`1qs
s.a xt`1 “ ftpxt, ut, ξtq
Complexidade de um passo: N ˆO
`
d3 ¨ p1{εqn
˘
. Não é exponencial em T .
Bernardo Controle ótimo Sextas Matemáticas 11 / 18
Recorrência estocástica
Qtpxtq “ minut,xt`1 E rctpxt, ut, ξtq `Qt`1pxt`1qs
s.a xt`1 “ ftpxt, ut, ξtq
Complexidade de um passo: N ˆO
`
d3 ¨ p1{εqn
˘
.
Não é exponencial em T .
Bernardo Controle ótimo Sextas Matemáticas 11 / 18
Recorrência estocástica
Qtpxtq “ minut,xt`1 E rctpxt, ut, ξtq `Qt`1pxt`1qs
s.a xt`1 “ ftpxt, ut, ξtq
Complexidade de um passo: N ˆO
`
d3 ¨ p1{εqn
˘
. Não é exponencial em T .
Bernardo Controle ótimo Sextas Matemáticas 11 / 18
Programação dinâmica & convexidade
Suponha
ct e gt convexas
U e X convexos
ft linear
Então cada Qt é convexa.
Bernardo Controle ótimo Sextas Matemáticas 12 / 18
Programação dinâmica & convexidade
Suponha
ct e gt convexas
U e X convexos
ft linear
Então cada Qt é convexa.
Bernardo Controle ótimo Sextas Matemáticas 12 / 18
Programação dinâmica & convexidade
Suponha
ct e gt convexas
U e X convexos
ft linear
Então cada Qt é convexa.
Bernardo Controle ótimo Sextas Matemáticas 12 / 18
Programação dinâmica & convexidade
Suponha
ct e gt convexas
U e X convexos
ft linear
Então cada Qt é convexa.
Bernardo Controle ótimo Sextas Matemáticas 12 / 18
Programação dinâmica & convexidade
Amostrar Qt em alguns pontos:
Qt
t
Complexidade de aproximação de Qt.
Bernardo Controle ótimo Sextas Matemáticas 13 / 18
Programação dinâmica & convexidade
Aproximar as funções Qt por tangentes:
Qt
t
Complexidade de aproximação de Qt.
Bernardo Controle ótimo Sextas Matemáticas 13 / 18
Programação dinâmica & convexidade
Aproximar as funções Qt por tangentes:
Qt
t
Complexidade de aproximação de Qt.
Bernardo Controle ótimo Sextas Matemáticas 13 / 18
Complexidade no caso estocástico
Dimensões:
T estágios;
n variáveis de estado (xt);
d variáveis de decisão (xt e ut);
N amostras de ξt.
Newton tridiagonal em blocos: OpNT ˆ Td3q
Programação dinâmica: OpTNqOpd3qO
`
p1{εqOpnq
˘
Bernardo Controle ótimo Sextas Matemáticas 14 / 18
Complexidade no caso estocástico
Dimensões:
T estágios;
n variáveis de estado (xt);
d variáveis de decisão (xt e ut);
N amostras de ξt.
Newton tridiagonal em blocos: OpNT ˆ Td3q
Programação dinâmica: OpTNqOpd3qO
`
p1{εqOpnq
˘
Bernardo Controle ótimo Sextas Matemáticas 14 / 18
Complexidade no caso estocástico
Dimensões:
T estágios;
n variáveis de estado (xt);
d variáveis de decisão (xt e ut);
N amostras de ξt.
Newton tridiagonal em blocos: OpNT ˆ Td3q
Programação dinâmica: OpTNqOpd3qO
`
p1{εqOpnq
˘
Bernardo Controle ótimo Sextas Matemáticas 14 / 18
Demo
Dimensões:
T “ 12 estágios;
n “ 2 variáveis de estado;
d “ 16 variáveis de decisão;
N “ 10 amostras por estágio.
0 50 100 150 200 250 300
0
1
2
3
4
1e9
Cota inferior
Cota superior
50 100 150 200 250 300
4.90
4.95
5.00
5.05
5.10
5.15
5.20
1e8
Cota inferior
Cota superior
Convergência do Algoritmo
Bernardo Controle ótimo Sextas Matemáticas 15 / 18
Demo
Dimensões:
T “ 12 estágios;
n “ 2 variáveis de estado;
d “ 16 variáveis de decisão;
N “ 10 amostras por estágio.
0 50 100 150 200 250 300
0
1
2
3
4
1e9
Cota inferior
Cota superior
50 100 150 200 250 300
4.90
4.95
5.00
5.05
5.10
5.15
5.20
1e8
Cota inferior
Cota superior
Convergência do Algoritmo
Bernardo Controle ótimo Sextas Matemáticas 15 / 18
Demo
Dimensões:
T “ 12 estágios;
n “ 2 variáveis de estado;
d “ 16 variáveis de decisão;
N “ 10 amostras por estágio.
0 50 100 150 200 250 300
10 2
10 1
100
101
102
103 Gap
50 100 150 200 250 300
0.004
0.006
0.008
0.010Gap
Erro relativo da solução
Bernardo Controle ótimo Sextas Matemáticas 15 / 18
Casos não-convexos
Variáveis de decisão inteiras;
Dinâmicas não-lineares;
Restrições não-convexas em geral.
1. Discretizar o problema (programação dinâmica “clássica”);
2. Aproximar o problema (envoltória convexa, . . . ) [Thomé 2013];
3. Problemas especiais (Q monótona) [MIDAS 2016];
4. Aumentar a dimensão para convexificar [SDDiP 2018];
5. Usar aproximadores não-convexos [SLDP 2020].
Bernardo Controle ótimo Sextas Matemáticas 16 / 18
Casos não-convexos
Variáveis de decisão inteiras;
Dinâmicas não-lineares;
Restrições não-convexas em geral.
1. Discretizar o problema (programação dinâmica “clássica”);
2. Aproximar o problema (envoltória convexa, . . . ) [Thomé 2013];
3. Problemas especiais (Q monótona) [MIDAS 2016];
4. Aumentar a dimensão para convexificar [SDDiP 2018];
5. Usar aproximadores não-convexos [SLDP 2020].
Bernardo Controle ótimo Sextas Matemáticas 16 / 18
Casos não-convexos
Variáveis de decisão inteiras;
Dinâmicas não-lineares;
Restrições não-convexas em geral.
1. Discretizar o problema (programação dinâmica “clássica”);
2. Aproximar o problema (envoltória convexa, . . . ) [Thomé 2013];
3. Problemas especiais (Q monótona) [MIDAS 2016];
4. Aumentar a dimensão para convexificar [SDDiP 2018];
5. Usar aproximadores não-convexos [SLDP 2020].
Bernardo Controle ótimo Sextas Matemáticas 16 / 18
Casos não-convexos
Variáveis de decisão inteiras;
Dinâmicas não-lineares;
Restrições não-convexas em geral.
1. Discretizar o problema (programação dinâmica “clássica”);
2. Aproximar o problema (envoltória convexa, . . . ) [Thomé 2013];
3. Problemas especiais (Q monótona) [MIDAS 2016];
4. Aumentar a dimensão para convexificar [SDDiP 2018];
5. Usar aproximadores não-convexos [SLDP 2020].
Bernardo Controle ótimo Sextas Matemáticas 16 / 18
Casos não-convexos
Variáveis de decisão inteiras;
Dinâmicas não-lineares;
Restrições não-convexas em geral.
1. Discretizar o problema (programação dinâmica “clássica”);
2. Aproximar o problema (envoltória convexa, . . . ) [Thomé 2013];
3. Problemas especiais (Q monótona) [MIDAS 2016];
4. Aumentar a dimensão para convexificar [SDDiP 2018];
5. Usar aproximadores não-convexos [SLDP 2020].
Bernardo Controle ótimo Sextas Matemáticas 16 / 18
Casos não-convexos
Variáveis de decisão inteiras;
Dinâmicas não-lineares;
Restrições não-convexas em geral.
1. Discretizar o problema (programação dinâmica “clássica”);
2. Aproximar o problema (envoltória convexa, . . . ) [Thomé 2013];
3. Problemas especiais (Q monótona) [MIDAS 2016];
4. Aumentar a dimensão para convexificar [SDDiP 2018];
5. Usar aproximadores não-convexos [SLDP 2020].
Bernardo Controle ótimo Sextas Matemáticas 16 / 18
A dificuldade do caso não-convexo
SB SDDiP SLDP
LB 1.167 2.370 3.031
UB 3.453 3.490 3.380
tempo (s) 12 3317 23
Tabela: T “ 8, n “ 1
SB SDDiP SLDP SLDP
# iters 100 50 100 250
LB 4.605 4.577 7.113 7.883
tempo (s) 10 2500 21 194
Tabela:T “ 8, n “ 4
Bernardo Controle ótimo Sextas Matemáticas 17 / 18
A dificuldade do caso não-convexo
SB SDDiP SLDP
LB 1.167 2.370 3.031
UB 3.453 3.490 3.380
tempo (s) 12 3317 23
Tabela: T “ 8, n “ 1
SB SDDiP SLDP SLDP
# iters 100 50 100 250
LB 4.605 4.577 7.113 7.883
tempo (s) 10 2500 21 194
Tabela: T “ 8, n “ 4
Bernardo Controle ótimo Sextas Matemáticas 17 / 18
Temas de pesquisa
Algoritmos mistos entre diretos e recorrentes;
Análise dos sistemas dinâmicos de controle com T Ñ8;
Constantes de Lipschitz, curvatura, e qualidade de aproximação;
Propriedades estruturais adicionais;
Aversão a risco.
Bernardo Controle ótimo Sextas Matemáticas 18 / 18
Temas de pesquisa
Algoritmos mistos entre diretos e recorrentes;
Análise dos sistemas dinâmicos de controle com T Ñ8;
Constantes de Lipschitz, curvatura, e qualidade de aproximação;
Propriedades estruturais adicionais;
Aversão a risco.
Bernardo Controle ótimo Sextas Matemáticas 18 / 18
Temas de pesquisa
Algoritmos mistos entre diretos e recorrentes;
Análise dos sistemas dinâmicos de controle com T Ñ8;
Constantes de Lipschitz, curvatura, e qualidade de aproximação;
Propriedades estruturais adicionais;
Aversão a risco.
Bernardo Controle ótimo Sextas Matemáticas 18 / 18
Temas de pesquisa
Algoritmos mistos entre diretos e recorrentes;
Análise dos sistemas dinâmicos de controle com T Ñ8;
Constantes de Lipschitz, curvatura, e qualidade de aproximação;
Propriedades estruturais adicionais;
Aversão a risco.
Bernardo Controle ótimo Sextas Matemáticas 18 / 18
Temas de pesquisa
Algoritmos mistos entre diretos e recorrentes;
Análise dos sistemas dinâmicos de controle com T Ñ8;
Constantes de Lipschitz, curvatura, e qualidade de aproximação;
Propriedades estruturais adicionais;
Aversão a risco.
Bernardo Controle ótimo Sextas Matemáticas 18 / 18
	Introdução
	Algoritmos