of 38 /38
Teoria de Otimização com Restrições EEL 5102-47: Métodos Numéricos de Otimização I Laboratório de Planejamento de Sistemas de Energia Elétrica Centro Tecnológico – Departamento de Engenharia Elétrica Tel. +55 (48) 3721.9731/9933 – Fax +55 (48) 3721.7538 Homepage: htto://www.labplan.ufsc.br Prof.: Erlon Cristian Finardi, D. Eng. [email protected]

Teoria de Otimizacao Com Restricoes

Embed Size (px)

DESCRIPTION

Aulas do Professor Erlon

Citation preview

  • Teoria de Otimizaocom Restries

    EEL 5102-47: Mtodos Numricos de Otimizao I

    Laboratrio de Planejamento de Sistemas de Energia EltricaCentro Tecnolgico Departamento de Engenharia Eltrica

    Tel. +55 (48) 3721.9731/9933 Fax +55 (48) 3721.7538Homepage: htto://www.labplan.ufsc.br

    Prof.: Erlon Cristian Finardi, D. [email protected]

  • 2Formulao Geral

    min ( )

    ( ) 0, sujeito a:

    ( ) 0,

    nx

    i

    i

    f x

    c x i

    c x i I

    f e ci so funes suaves definidas em um subconjunto que pertence ao n

    f a funo objetivo, enquanto ci, i so as restries de igualdade e ci, i I so as restries de desigualdade

    Abaixo definido um conjunto vivel que contm todos os pontos x que atendem as restries

    { | ( ) 0, ; ( ) 0, } i ix c x i c x i I

    Deste modo possvel escrever o problema acima na forma compacta

    min ( ) x

    f x

  • 3Caracterizando as Solues

    Encontrar o mnimo global uma tarefa rdua em

    problemas irrestritos

    Adio das restries pode excluir muitos mnimos locais

    e facilitar a busca pelo global

    Contudo, as restries tambm podem tornar essa tarefa

    mais complicada

    As restries podem produzir um grande nmero de

    solues que no formam um conjunto fechado

    Embora, no caso geral, as restries alterem a soluo,

    em alguns casos elas no tem efeito na determinao de

    um mnimo

  • 4Vrios Mnimos Locais

    2

    2

    2

    2

    2

    min ( )

    sujeito a: 1

    xf x x

    x

    Sem a restrio um problema quadrtico estritamente convexo com um nico minimizador em x = 0

    Com a restrio, xtal ||x||2 = 1 resolve o problema existindo, portanto, infinitos mnimos globaisRegio Vivel contornos

    de f(x)

    infinitas solues

  • 5Vrios Mnimos Locais

    Sem a restrio o nico minimizador em x = (0,-100)

    Com a restrio, vetor (x1,x2)=(k,-1) tal que k=1, 3, 5,... resolve o problema

    2

    2 22 1

    2 1

    min ( ) ( 100) 0,01

    sujeito a: cos 0

    xf x x x

    x x

    Regio Vivel

    contornos de f(x)

    vrios mnimos locais

  • 6nico Minimizador

    Se a primeira restrio for ignorada, o ponto timo (1,5 1,5)T e f(x) = 0

    2

    2 21 2

    1 2

    1

    2

    min ( ) ( 1,5) ( 1,5)

    2 0

    sujeito a: 0

    0

    xf x x x

    x x

    x

    x

    Regio Vivel

    contornos de f(x)

    mnimo globalrestrito

    mnimo global

    irrestrito

    O ponto timo restrito (1,1)T e f(x) = 0,5

  • 7Restries No Interferem na Soluo do Problema

    2

    2 21 2

    1 2

    1

    2

    min ( ) ( 0,5) ( 0,5)

    2 0

    sujeito a: 0

    0

    xf x x x

    x x

    x

    x

    Regio Vivel

    contornos de f(x)

    mnimo globalrestrito

    mnimo global

    irrestrito

    O ponto timo deste problema pode ser obtido ignorando-se todas as restries do problema

    x=(0,5;0,5)T e f(x) =0

  • 8Definindo Solues Locais

    Simples extenses do caso irrestrito, exceto que agora

    deve-se levar em considerao os pontos viveis na

    vizinhana de x

    Um vetor x uma soluo local se x e existe uma

    vizinhana V de x tal que f(x) f(x) para x V

    Um vetor x uma soluo local estrita (soluo local forte)

    se x e existe uma vizinhana V de x tal que f(x) > f(x)

    para todo x V com x x

  • Problemas Somente com Restries de Igualdade

  • 10

    Consideraes Iniciais

    Introduzir os princpios bsicos que caracterizam as

    solues dos problemas com restries de igualdade

    Formulao

    min ( )

    sujeito a: ( ) 0

    nx

    i

    f x

    c x

    i e I =

    Uma restrio no linear

    Uma restrio linear

  • 11

    Uma Restrio No Linear

    = {1} e I = 1 22 21 2

    min

    s.a: 2 0

    x x

    x x

    T* ( 1, 1)x

    ( *)f x

    1( *)c x

    1( )ac x

    ( )af x

    ( )bf x

    ( )cf x

    1( )dc x

    De qualquer ponto em ,

    tal que x x, possvel

    realizar um movimento

    vivel enquanto f

    decrementada

    Em x os gradientes da

    restrio e da funo

    objetivo so paralelos

    Existe um escalar tal

    que

    * * *1( ) ( )f x c x

  • 12

    Caracterizao da Soluo1) Para manter a viabilidade deve-se respeitar c1(x+d)=0:

    1 1 1 10 ( ) ( ) ( ) ( )T Tc x d c x c x d c x d

    2) De forma anloga, para uma direo de descida produzir

    um decrscimo em f ento: 0 ( ) ( ) ( )Tf x d f x f x d

    Se existe um d que satisfaz 1) e 2) ento possvel ter melhorias

    Em consequncia, a condio necessria de otimalidade que no

    exista nenhuma direo d que satisfaa 1) e 2) simultaneamente

    Com base no exemplo, tem-se que tal direo no pode existir

    se f(x) e c1(x) forem paralelos

    A condio f(x)=c1(x) no suficiente para encontrar a

    soluo tima. No exemplo, essa condio atendida para o

    ponto x=(1,1)T ponto de mximo, em que =0,5

  • 13

    Uma Restrio Linear

    Condio necessria

    atendida para um nico

    valor de = 3,46

    Em problemas com

    restries de igualdade no

    possvel colocar como

    condio adicional que

    > 0!

    2 21 2

    1 2

    min 3 4

    s.a: 3,5 4 14 0

    x x

    x x

    T* (2,02 1,73)x 1( *)c x

    ( *)f x

    O ponto encontrado um

    (nico) mnimo global

  • 14

    Funo Lagrangiana

    1( , ) ( ) ( )L x f x c x

    Problema restrito analisado sob ponto de vista de um

    problema irrestrito

    Sendo a funo Lagrangeana definida por:

    O ponto estacionrio calculado da seguinte maneira:

    1( , ) 0 ( ) ( )x x xL x f x c x 1( , ) 0 ( )L x c x

    possvel buscar a soluo de um problema com restries de

    igualdade calculando os pontos estacionrios da funo

    Lagrangiana

  • Problemas com Restries de Desigualdade Somente

  • 16

    Consideraes Iniciais

    Em um ponto vivel x a isima restrio de desigualdade, tal que i I, dita estar ativa se

    ci(x) = 0 e inativa se ci(x) > 0

    Introduzir os princpios bsicos que caracterizam as

    solues dos problemas com restries de desigualdade

    Formulao

    min ( )

    sujeito a: ( ) 0

    nx

    i

    f x

    c x

    i I

  • 17

    Uma Restrio No Linear

    O vetor gradiente da

    restrio, nos pontos onde

    a mesma est ativa,

    sempre aponta para o

    interior da regio vivel

    1 2

    2 21 2

    min

    s.a: 2 0

    x x

    x x

    Regio Invivel

    T* ( 1, 1)x

    1( *)c x

    ( *)f x

    ( )bf x

    ( )cf x

    1( )dc x

    1( )ac x

    ( )af x

    A condio f(x)=c1(x)

    atendida nos pontos

    x = (1,1)T com = 0,5

    x =(1,1)T com = 0,5

    Porm, o sinal de um

    importante parmetro

    para encontrar uma

    soluo

  • 18

    Caracterizao da Soluo1) Para manter a viabilidade deve-se respeitar:

    1 1 1 1 10 ( ) ( ) ( ) ( ) ( ) 0T Tc x d c x c x d c x c x d

    2) Direo de descida: ( ) 0Tf x d

    Para encontrar d que satisfaz 1) e 2) simultaneamente

    necessrio analisar dois casos:

    x um ponto tal que c1(x) > 0. Neste caso d atende 1), dado que

    seja suficientemente pequeno. A nica situao onde no possvel

    atender 1) e 2) com f(x)=0

    x um ponto tal que c1(x) = 0. Assim 1) e 2) tornam-se f(x)Td < 0

    e c1(x)Td 0. A nica situao onde essas duas regies no tem

    nenhum ponto em comum quando f(x) e c1(x) apontam na

    mesma direo, isto , quando:

    1( ) ( ), com 0.f x c x

  • 19

    Duas Restries

    ci(x*)Td 0, i =1,2,

    so satisfeitas com d no

    quadrante definido por

    c1(x*) e c2(x*)

    1 2

    2 21 2

    2

    min

    s.a: 2 0

    0

    x x

    x x

    x

    Regio Invivel

    2( *)c x

    1( *)c x

    ( *)f x

    T* ( 2 ,0)x

    2( )ac x

    1( )ac x

    ( )af x

    Vetores neste quadrante

    atendem a f(x*)Td 0

    1 2

    1 02 2( *) , ( *) , ( *)

    1 10f x c x c x

    1

    * 2 2

    1

  • 20

    No Linearidade Acentuada

    1 2

    2 21 2

    min

    s.a: 2 0

    x x

    x x

    1 2

    2 2 21 2

    min

    s.a: ( 2) 0

    x x

    x x

    Os dois problemas possuem o ponto timo em x= (1,1)T

    Em (2) tem-se que c1(x) = 0 para todos pontos viveis e

    f(x)=c1(x) no pode ser assegurado

    (1) (2)

    Definio: Dado um ponto x* e um conjunto A(x*), diz-se

    que as restries esto qualificadas se {ci(x), i A(x*)} so

    linearmente independentes

    Se a condio acima for verificada, nenhum dos elementos de

    {ci(x), i A(x*)} nulo. Ainda, permite expressar as

    condies de otimalidade para um problema de programao

    no linear qualquer

  • Condies de Otimalidade de Primeira Ordem

  • 22

    Condies Necessrias de Primeira Ordem

    Seja x* um mnimo local e que as restries ativas

    em x* esto qualificadas. Assim, existe um vetor *,

    i I , tal que as seguintes condies so

    satisfeitas em (x*, *)

    xL(x*, *) = 0

    ci(x*) = 0 i

    ci(x*) 0 i I

    *i 0 i I

    *i ci(x*) = 0 i I

    Condies de Karush-Kuhn-Tucker (KKT)

  • 23

    Condies de KKT - Ilustrao

    2 4

    1 2

    1 1 2

    2 1 2

    3 1 2

    4 1 2

    3 1min ( )=

    2 8

    ( ) : 1 0

    ( ) : 1 0s.a:

    ( ) : 1 0

    ( ) : 1 0

    f x x x

    c x x x

    c x x x

    c x x x

    c x x x

    1( )c x

    2( )c x

    3( )c x

    4( )c x

    Regio Vivel

    1 2

    11 1

    * (1,0) ( *) , ( *) , ( *)11 1

    2

    x f x c x c x

    T3 1

    * 0 04 4

  • Condies de Otimalidade de Segunda Ordem

  • 25

    Introduo... (1)

    Condies de KKT indicam como as derivadas primeiras

    de f(x) e das restries ativas esto relacionadas em x*

    Quando as condies de KKT so verificadas, um

    movimento de qualquer vetor w F1 faz com que

    wTf(x*)>0 ou wTf(x*)=0, onde

    1

    ( *) 0,| 0,

    ( *) 0, ( *)

    Ti

    Ti

    d c x iF d

    d c x i A x I

    Para direes w F1 tal que wTf(x*)=0, no possvel

    determinar da informao de primeira ordem se um

    movimento nesta direo ir incrementar ou diminuir a

    funo objetivo

  • 26

    Dado F1 e algum multiplicador de Lagrange * que satisfaz

    as condies de KKT, define-se um subconjunto F2(*) de

    F1 por

    Introduo... (2)

    T

    T *2

    T *

    ( *) 0, ,

    ( *) ( *) 0, ( *) com 0,

    ( *) 0, ( *) com 0.

    i

    i i

    i i

    c x w i

    w F c x w i A x I

    c x w i A x I

    Portanto, F2(*) contm direes de F1 que no informam,

    com base nas derivadas primeira, se f(x*) ir aumentar ou

    diminuir

  • 27

    Teorema: Seja x* uma soluo local e que os

    gradientes das restries ativas sejam linearmente

    independentes. Seja * um vetor de multiplicadores de

    Lagrange tal que as condies de KKT so verificadas

    e seja F2(*) conforme definido anteriormente. Ento,

    Condies Necessrias

    Envolvem as derivadas de segunda ordem: se x* uma

    soluo local, ento a curvatura da funo Lagrangiana

    nas direes de F2(*) devem ser no negativas

    T2( *, *) 0, para ( *).xxw L x w w F

  • 28

    Teorema: Suponha que para x* vivel n existe um

    vetor *, i I , tal que as condies de KKT so

    satisfeitas. Suponha tambm que

    Ento x* um mnimo local

    Condies Suficientes

    So condies em f e ci que asseguram que x* uma

    soluo local em oposio s condies necessrias que

    assumem que x* uma soluo e deduzem propriedades

    em f e ci

    T2( *, *) 0, para ( *), 0.xxw L x w w F w

  • 29

    Exemplo 12 2

    1 2 1 1 2min ( ) s.a: ( ) 2 0f x x x c x x x 2 2

    1 2 1 2( , ) (2 )L x x x x x

    fcil verificar que as condies de KKT so satisfeitas

    em x* =(1,1)T com *=1/2. A hessiana de L(x*,*)

    ** * 1

    1 *1

    1 02 0( , )

    0 10 2xxL x

    Essa matriz Definida Positiva para qualquer w 0, e

    portanto, certamente satisfaz as condies do teorema

    mostrado no slide anterior

    Assim x* uma soluo estrita do PNL de fato, uma soluo global dado que o PNL convexo

  • 30

    Exemplo 2

    Condies de KKT so satisfeitas em xa =(1,1)T com

    a*= 1/2 e em xb =(1,1)

    T com b*=1/2. As hessianas so

    1 0 1 0( , ) e ( , )

    0 1 0 1xx a a xx b bL x L x

    xa uma soluo estrita do PNL De fato, uma soluo

    global, pois xb no atende as condies de segunda ordem

    e no existem outros pontos que atendem as condies de

    primeira ordem

    Adicionalmente, a regio vivel limitada

    2 21 2 1 1 2min ( ) s.a: ( ) 2 0f x x x c x x x

    2 21 2 1 2( , ) ( 2)L x x x x x

  • 31

    Regio Vivel

    2 21 2

    2 21 2

    min 0,1( 4)

    s.a: 1 0

    x x

    x x

    1 1

    2 2

    0,2( 4) 2( , )

    2 2

    0,2 2 0( , )

    0 2 2

    x

    xx

    x xL x

    x x

    L x

    x* = (1,0)T atende KKT em *

    = 0,3

    Note que c(x*)=(2,0)T, ento:

    2 2

    22

    ( *, *)

    0 0,8 0 0

    0 1,4

    1,4 0

    Txx

    T

    w L x w

    w w

    w

    x* = (1,0)T um mnimo local

    Exemplo 3... (1)

  • 32

    x* = (1,0)T um mnimo global? Uma vez que o problema no

    convexo deve-se verificar se existem outros pontos que atendem as

    condies de 1 e 2 ordem

    Exemplo 3... (2)

    1 1 2 21 2

    2 2

    0,2( 4) 2 0, 1 0

    2 2 0x

    x xL L x x

    x x

    Condies de KKT

    De xL=0 (segunda equao) tem-se que =1 ou x2=0. Com x2=0

    chega-se ao ponto testado no slide anterior. Com =1 obtm-se da

    primeira equao de xL que x1=0,3636 e, aplicando-se na equao

    yL tem-se x2 = 0,9315

    Portanto dois pontos adicionais atendem as condies de KKT

    xa=(0,3636 0,9315)T com =1

    xb=(0,3636 -0,9315)T com =1

  • 33

    Exemplo 3... (3) Considerando xa=(0,3636 0,9315)

    T com =1, tem-se

    T1 2

    0,7273( ) ( ) 0 2,5617

    1,8631a ac x c x w w w

    T

    T

    2 2 22

    2 2

    ( , )

    2,5617 2,2 0 2,561714,4371 0

    0 0

    xx aw L x w

    w ww

    w w

    Portanto, xa no um ponto de mnimo, pois a funo

    Lagrangiana tem curvatura negativa

    Uma vez que neste problema a curvatura no depende do valor das

    variveis primais, ento xb tambm no representa uma soluo local

    Embora x* = (1,0)T seja um mnimo local, a f(x) no limitada

    inferiormente na regio vivel e, portanto, no existe soluo global

  • 34

    2

    2 21 2

    3max ( ) ( 1) 2

    4xf x x x

    21 1 2s.a : ( ) : 2 4 0c x x x

    2 1( ) : 5c x x

    Exemplo 4... (1)2

    2 21 2

    3min ( ) ( 1) 2

    4xf x x x

    21 1 2s.a : ( ) : 2 4 0c x x x

    2 1( ) : 5 0c x x

    2( )c x

    1( )c x

  • 35

    Somente c1(x) ativa

    De (2) tem-se x2 = 0 ou = 1.

    Com x2 = 0, pode-se obter por (3) x1 = 4. Note que c2(x) > 0. De (1) tem-se que = 4,5. Assim, x = (4,0)T atende KKT

    Considerando x = (4,0)T e = 4,5 as condies de segunda ordem so

    1

    2 2

    1,5( 1) 10

    4 4x

    xL

    x x

    1

    2 2

    21 2

    1,5 1,5 0

    4 4 0

    2 4 0

    x

    x x

    x x

    (1)

    (2)

    (3)

    Exemplo 4... (2)

    1 22 2

    2 2

    1,5 0 01 4 0 0, 0 0, 14 0

    0 14

    ww w

    w w

    Assim, x = (4,0)T um ponto de mnimo local estrito

  • 36

    ...continuando...

    Com = 1, pode-se obter por (1) que x1 = 5/3. Note que c2(x) > 0. De (3) tem-se que x2 = 1,0801.

    Considerando x = (5/3 1,0801)T e = 1 as condies de segunda ordem so

    1

    2 2

    1,5( 1) 10

    4 4x

    xL

    x x

    1

    2 2

    21 2

    1,5 1,5 0

    4 4 0

    2 4 0

    x

    x x

    x x

    (1)

    (2)

    (3)

    Exemplo 4... (3)

    1 2 22 2 2

    2 2

    1,5 0 4,321 4,32 0, 4,32 0, 28 0

    0 0

    w ww w w

    w w

    Assim, x = (5/3 1,0801)T no um ponto de mnimo local estrito

  • 37

    Considerando x = (5/3 1,0801)T e = 1

    Exemplo 4... (4)

    1 2 22 2 2

    2 2

    1,5 0 4,321 4,32 0, 4,32 0, 28 0

    0 0

    w ww w w

    w w

    Assim, x = (5/3 1,0801)T no um ponto de mnimo local estrito

    x* = (4,0)T um mnimo global?

    Embora seja o nico ponto de KKT que atende a segunda ordem, deve-

    se verificar se o valor de f(x) na regio vivel limitada inferiormente

    Note que f(x*) = 6,75. Pode-se fixar x1 = 4 em c1(x). Assim x2 = 2 e

    f(4,2) = 14,75 < f(x*)

    Portanto, x* no um mnimo global

  • OBRIGADO!

    Prof. Erlon Cristian Finardi [email protected]