aula 2 - instituto tecnológico de aeronáuticakawakami/ee253/ee253_2020_aula2.pdfrevis~ao de...

Aula 2

10 Mar 2020

EE-253 (Controle Ótimo de Sistemas) Aula 2 10 Mar 2020 1 / 20

Revisão de Otimização sem Restrições


Mini-Tutorial: Matrizes Positivo/Negativo-Definidas

Uma matriz Q ∈ Rn×n simétrica é dita positivo-definida (PD) se esomente se (s.s.s)

xTQx > 0,∀x ∈ Rn, x 6= 0

Notações comumente empregadas: Q = QT > 0, Q = QT � 0.

Termo alternativo: Definida positiva


Relação com os autovalores de Q

Sejam λ1, λ2, . . . , λn os autovalores de uma matriz Q = QT ∈ Rn×n.

Tem-se que Q > 0⇐⇒ λi > 0, i = 1, 2, . . . , n.


Observações:

Uma matriz PD pode ter elementos negativos.

Por exemplo, a matriz

Q =

[2 −1−1 3

]tem autovalores λ1 = 1,4 e λ2 = 3,6.

Uma matriz com todos os elementos positivos não é necessariamentePD.

Por exemplo, a matriz

Q =

[2 44 3

]tem autovalores λ1 = −1,5 e λ2 = 6,5.


Definições adicionais

Seja Q = QT ∈ Rn×n. Diz-se que:

Q > 0 (Positivo-Definida) se xTQx > 0,∀x 6= 0.Q ≥ 0 (Positivo-Semidefinida) se xTQx ≥ 0, ∀x .Q < 0 (Negativo-Definida) se xTQx < 0, ∀x 6= 0.Q ≤ 0 (Negativo-Semidefinida) se xTQx ≤ 0,∀x .Q é Indefinida nos demais casos.

Condições sobre os autovalores:

Q > 0⇔ λi > 0, i = 1, 2, . . . , nQ ≥ 0⇔ λi ≥ 0, i = 1, 2, . . . , nQ < 0⇔ λi < 0, i = 1, 2, . . . , nQ ≤ 0⇔ λi ≤ 0, i = 1, 2, . . . , nQ indefinida ⇔ λi > 0 e λj < 0 para algum i e j .


Ponto de ḿınimo de uma função

Seja uma função F : Rn → R. Um ponto x∗ ∈ Rn é dito ser um ḿınimolocal se F (x∗) ≤ F (x) para todo x em uma vizinhança de x∗.

Se F (x∗) ≤ F (x) para todo x ∈ Rn, diz-se que x∗ é um ḿınimo global.

Notações comumente empregadas:

x∗ = arg minx∈Rn

F (x)

F (x∗) = minx∈Rn

F (x)

O problema de otimização é expresso como

minx∈Rn

F (x)


Teorema de Taylor

Seja uma função F : Rn → R de classe C 2 (isto é, com derivadascont́ınuas de até 2a ordem).

Dados x ∈ Rn e ∆x ∈ Rn, existe θ ∈ [0,1] tal que

F (x + ∆x) = F (x) + FTx (x)∆x +1

2∆xTFxx(x + θ∆x)∆x

Referência: GILL, P.E.; MURRAY, W.; WRIGHT, M.H. Practical Optimization,Academic Press, 1981.


Vetor gradiente: Fx =∂F

∂x=

∂F

∂x1∂F

∂x2...∂F

∂xn

Matriz Hessiana: Fxx =∂2F

∂x2=

∂2F

∂x21

∂2F

∂x1∂x2· · · ∂

2F

∂x1∂xn∂2F

∂x2∂x1

∂2F

∂x22· · · ∂

2F

∂x2∂xn...

.... . .

...∂2F

∂xn∂x1

∂2F

∂xn∂x2· · · ∂

2F

∂x2n


Observação sobre a matriz Hessiana

Fxx =

∂2F

∂x21

∂2F

∂x1∂x2· · · ∂

2F

∂x1∂xn∂2F

∂x2∂x1

∂2F

∂x22· · · ∂

2F

∂x2∂xn...

.... . .

...∂2F

∂xn∂x1

∂2F

∂xn∂x2· · · ∂

2F

∂x2n

Se a função for de classe C 2, tem-se que

∂2F

∂xi∂xj=

∂2F

∂xj∂xi

Portanto, a matriz Hessiana Fxx será simétrica.


Condições necessárias para otimalidade

Seja uma função F : Rn → R pertencente à classe C 2. Se x∗ ∈ Rn é umḿınimo local de F , então as seguintes condições devem ser satisfeitas:

Fx(x∗) = 0

Fxx(x∗) ≥ 0

Observação: Se Fx(x∗) = 0, diz-se que x∗ é um “ponto estacionário” de F .


Condições suficientes para otimalidade

Seja uma função F : Rn → R pertencente à classe C 2. Se as seguintescondições forem satisfeitas:

Fx(x∗) = 0

Fxx(x∗) > 0

então x∗ ∈ Rn é um ḿınimo local de F .


Observação: Suponha que F ∈ C 2 e Fx(x∗) = 0. Tem-se então que:

Fxx(x∗) > 0⇒ x∗ é ḿınimo local.

Fxx(x∗) < 0⇒ x∗ é máximo local.

Fxx(x∗) indefinida ⇒ x∗ é ponto de sela.


Algumas expressões para cálculo de gradientes

Sejam x ∈ Rn, y ∈ Rn,Q ∈ Rn×n. Então:

∂(yT x)

∂x=∂(xT y)

∂x= y

∂(yTQx)

∂x=∂(xTQT y)

∂x= QT y

∂(xTQx)

∂x= Qx + QT x

∂[(x − y)TQ(x − y)

]∂x

= (Q + QT )(x − y)

Se Q for simétrica, as expressões se simplificam, pois Q + QT = 2Q.


Sejam duas funções F ,G : Rn → Rn dadas por

F (x) =

F1(x)F2(x)

...Fn(x)

, G (x) =

G1(x)G2(x)

...Gn(x)


Tem-se então:

∂[FT (x)G (x)

]∂x

= FTx (x)G (x) + GTx (x)F (x)

em que Fx é a matriz Jacobiana definida como

Fx =

∂F1∂x1

∂F1∂x2

· · · ∂F1∂xn

∂F2∂x1

∂F2∂x2

· · · ∂F2∂xn

......

. . ....

∂Fn∂x1

∂Fn∂x2

· · · ∂Fn∂xn

(e de forma similar para Gx).


Algumas expressões para cálculo de Hessianas

Sejam x ∈ Rn, y ∈ Rn,Q ∈ Rn×n. Então:

∂2(xTQx)

∂x2= Q + QT

∂2[(x − y)TQ(x − y)

]∂x2

= Q + QT

Se Q for simétrica, as expressões se simplificam, pois Q + QT = 2Q.


Ex: Funções Quadráticas

F (x) =1

2xTHx + cT x + cte

Neste caso, tem-se

Fx(x) =

Hx + c

Portanto, x∗ deve satisfazer Hx∗ + c = 0, isto é

x∗ = −H−1c

desde que H seja não singular.

Adicionalmente, a matriz Hessiana em x∗ é dada por

Fxx(x∗) = H



F (x) =1

2xTHx + cT x + cte

Neste caso, tem-se

Fx(x) = Hx + c


x∗ = −H−1c



Fxx(x∗) = H



F (x) =1

2xTHx + cT x + cte

Neste caso, tem-se

Fx(x) = Hx + c

Portanto, x∗ deve satisfazer Hx∗ + c = 0

, isto é

x∗ = −H−1c



Fxx(x∗) = H



F (x) =1

2xTHx + cT x + cte

Neste caso, tem-se

Fx(x) = Hx + c


x∗ = −H−1c



Fxx(x∗) = H



F (x) =1

2xTHx + cT x + cte

Neste caso, tem-se

Fx(x) = Hx + c


x∗ = −H−1c



Fxx(x∗) =

H



F (x) =1

2xTHx + cT x + cte

Neste caso, tem-se

Fx(x) = Hx + c


x∗ = −H−1c



Fxx(x∗) = H


Exemplo 1

x∗ = −H−1c, Fxx(x∗) = H

H =[

1 00 2

], c =

[00

]

−1

−0.5

0

0.5

1

−1

−0.5

0

0.5

10

0.5

1

1.5

x1x2

J(x)


Exemplo 2

x∗ = −H−1c, Fxx(x∗) = H

H =[

1 00 −2

], c =

[00

]

−1

−0.5

0

0.5

1

−1

−0.5

0

0.5

1−1

−0.5

0

0.5

x1x2

J(x)


aula 2 - instituto tecnológico de aeronáuticakawakami/ee253/ee253_2020_aula2.pdfrevis~ao de...

Documents