UNIVERSIDADE FEDERAL DO PARÁ

DEPARTAMENTO DE ENGENHARIA ELÉTRICA E DE COMPUTAÇÃO

MINI-CURSO DE PROGRAMAÇÃO NÃO-LINEAR

Prof. Carolina de Mattos Affonso

Belém, setembro de 2005

2

Tópicos abordados 1. Introdução

2. Análise Convexa

3. Problemas de Otimização

4. Otimização Irrestrita – Métodos de Busca

4.1. Busca Unidimensional 4.2. Busca Multidimensional

5. Otimização Irrestrita - Condições de Otimalidade

5.1 Condições de Otimalidade 5.2 Busca Unidimensional 5.3 Busca Multidimensional 5.4 Aplicações

6. Otimização Restrita

6.1 Restrições de desigualdade 6.2 Restrições mistas 6.3 Formulação Convexa 7. Função Lagrangeana e Dualidade

7.1 Dualidade 7.2 Ponto de Sela 7.3 Dualidade Fraca 7.4 Dualidade Forte 7.5 Decomposição Dual

Bibliografia:

• Stephen Boyd and Lieven Vandenberghe, ‘Convex Optimization’. Cambridge University Press, 2004.

• M. S. Bazaraa, H. D. Sherali, and C. M. Shetty. ‘Nonlinear Programming. Theory and Algorithms’. John Wiley & Sons, second edition, 1993.

• D. G. Luenberger. ‘Linear and Nonlinear Programming’. Addison-Wesley, second edition, 1984.

• S. S. Rao. ‘Optimization: theory and applications’. Wiley, 1996.

3

1. Introdução A otimização é o processo pelo qual determina-se a melhor solução para problemas de tomada de decisão a partir de modelos matemáticos. A otimização possui aplicação nas mais diversas áreas. Exemplos:

- Processamento de sinais;

- Sistemas de potência (Fluxo de Potência Ótimo: minimização de perdas, minimização dos custos de geração, Planejamento Energético...);

- Identificação de parâmetros (Problema de mínimos quadrados);

- Otimização da produção, problema de transportes e etc (modelos de programação linear).

As técnicas de solução de problemas de otimização podem ser agrupadas em várias subáreas:

• Programação Linear;

• Programação Não-Linear;

• Programação Inteira;

• Programação Dinâmica.

Neste curso, serão vistos os principais tópicos relacionados a problemas de programação não-linear.

4

2. Análise Convexa a) Combinação Convexa: Seja x1, x2, ... xp elementos de S ⊂ ℜn. Elementos da forma:

pp

p

i

ii xxxxx λλλλ +++== ∑

=...2

21

11

com λ ≥ 0 e ∑λi = 1 são combinações convexas dos elementos x1, x2, ... xp ∈ S. b) Conjunto Convexo: Um conjunto S ⊂ ℜn é dito convexo se para todo x1 e x2 ∈ S, então para todo λ ∈ [0,1] o ponto:

21 )1( xx λλ −+ ∈ S Em outras palavras, um conjunto S ⊂ ℜn é dito convexo se o segmento de linha conectando dois pontos quaisquer do conjunto também pertence ao conjunto S. A Figura 2.1 ilustra a noção de conjunto convexo. Note que na Figura 2.1 b) o segmento de linha que une x1 e x2 não está completamente contido em S.

Figura 2.1 – Conjunto convexo e não-convexo

c) Função Convexa: Seja S ⊂ ℜn um conjunto convexo. Diz-se que f(x) é uma função convexa se para todos x1, x2 ∈ S e todo λ ∈ [0,1]:

[ ] )()()1()1( 2121 xfxfxxf λλλλ +−≤−+

Ou seja, a equação da reta ligando os pontos x1 e x2 ∈ Ω deve estar ‘por cima’ da função, como mostra a Figura 2.2. Se a desigualdade for estrita (<) para todos x1 ≠ x2 e α ∈ [0,1] então f(x) é estritamente convexa. Dizemos que f(x) é uma função côncava se – f(x) for convexa.

x1

x2

a) Convexo b) Não-Convexo

equação da reta função

5

Figura 2.2 – Gráfico de uma função convexa

Figura 2.3 – Função convexa, côncava e nem côncava e nem convexa

d) Mínimo Global / Máximo Global: Considere o problema de minimizar f(x) sujeito a x ∈ S. Um ponto x* ∈ S é chamado de mínimo global de f(x) se e somente se f(x*) ≤ f(x), para todo x ∈ S. Se para todo x ≠ x* f(x*) < f(x), então mínimo global é único.

-2 -1.5 -1 -0.5 0 0.5 1 1.5 20

0.5

1

1.5

2

2.5

3

3.5

4

mínimo global e único

-4 -3 -2 -1 0 1 2 3 40

0.5

1

1.5

2

2.5

3

3.5

4

x

f ( x )

mínimo global mínimo global

Figura 2.4 – Mínimo global

Analogamente tem-se a definição de máximo global: Considere o problema de maximizar f(x) sujeito a x ∈ S. Um ponto x* ∈ S é chamado de máximo global de f(x) se e somente se f(x*) ≥ f(x), para todo x ∈ S.

x1

f(x1)

f(x2)

x x2

S

6

Observação: • Algumas funções apresentam mínimos e máximos globais em conjuntos

ilimitados. Exemplo: f(x) = sin(x) • Outras funções podem apresentar apenas mínimos ou máximos. Exemplo: A

função f(x) = 1/x possui máximo global em (1,1) para x ∈[1,∞), mas não possui mínimo.

0 1 2 3 4 50

1

2

3

4

5

máximo

Figura 2.5 – Exemplo

e) Mínimo Relativo ou Local/ Máximo Relativo ou Local: Se a definição de mínimo global só for válida na vizinhança de x*, então x* é um mínimo local de f(x). A definição de máximo local é análoga.

Figura 2.6 – Mínimo global e mínimo local

Na prática pode-se garantir apenas que o ponto seja de mínimo/máximo local. Para garantia de mínimo/máximo global, há a necessidade de propriedades de convexidade. Assim: Seja S um conjunto convexo, considere o problema de minimizar f(x) sujeito a x ∈ S. Suponha ainda que xl é uma solução ótima local do problema.

• Se a função f(x) é convexa, então xl é ótimo global. • Se a função f(x) é estritamente convexa, então xl é ótimo global único.

mínimo local

mínimo global

S

7

f) Função Quasi-Convexa: Quasi-convexidade pode ser considerada como uma generalização da convexidade. Seja S ⊂ ℜn um conjunto convexo. Diz-se que f(x) é uma função quasi-convexa se para todos x1, x2 ∈ S e todo λ ∈ [0,1]:

[ ] )(),(max)1( 2121 xfxfxxf ≤−+ λλ

Figura 2.7 – Função quasi-convexa

Uma função contínua f é quasi-convexa se e somente se uma das seguintes condições se aplica:

• f é não-decrescente; • f é não-crescente; • existe um ponto c tal que para t ≤ c → f é não-crescente, e para t ≥ c → f é não-

decrescente. O ponto c pode ser escolhido como qualquer ponto, o qual é mínimo global de f.

Figura 2.8 – Função quasi-convexa

h) Função Unimodal: É uma função do tipo estritamente quasi-convexa, ou seja, tem apenas um mínimo relativo.

[ ] )(),(max)1( 2121 xfxfxxf <−+ λλ

x1 x2

8

Não é unimodal É unimodal

Figura 2.9 – Função Unimodal.

Este tipo de função é de especial importância na programação não-linear, pois garante que um mínimo local (máximo local) de um conjunto convexo seja um mínimo global (máximo global).

9

3. Problemas de Otimização a) Construção do modelo matemático de otimização:

Um modelo matemático é uma representação simplificada de uma situação da vida real, formalizado com símbolos e expressões matemáticas.

A modelagem matemática de um problema possibilita uma melhor compreensão da essência do mesmo

Etapas:

1º) Função Objetivo que desejamos maximizar ou minimizar. Por exemplo, em um processo industrial, desejamos maximizar o lucro ou minimizar o custo de produção.

2º) Um conjunto de variáveis que afetam o valor da função objetivo. No caso do processo industrial, as variáveis podem incluir a soma de diversas fontes de faturamentos ou o tempo gasto em cada atividade.

3º) Um conjunto de restrições que permite que as variáveis recebam certos valores, excluindo, no entanto, outros valores. No caso do processo industrial, não faz sentido gastar uma quantidade negativa de tempo em nenhuma atividade. Assim, pode-se restringir todas as variáveis de tempo a serem positivas (não negativas).

O problema de otimização é então:

Encontrar os valores apropriados das variáveis, que minimize/maximizem a função objetivo, satisfazendo as restrições.

a) Problema de Otimização: Forma Padrão

Minimizar f(x) Sujeito a: gj(x) ≤ 0, j = 1...p (3.1) hi(x) = 0, i = 1...m

O problema é irrestrito se não existem restrições, ou seja, m = p = 0.

Denomina-se:

x é a variável de otimização; f(x) é a função objetivo ou função custo; gj(x) ≤ 0 são as restrições de desigualdade; hi(x) = 0 são as restrições de igualdade; Factibilidade:

• x é factível se satisfaz as restrições; • o conjunto factível S é o conjunto que contém todos os pontos factíveis; • o problema é factível se existem soluções factíveis;

Otimalidade:

• o valor ótimo da função é f*(x) = inf x∈S f(x) • solução ótima: x* ∈ S s.a. f(x*) = f*(x)

10

Exemplo:

Minimizar x1 + x2 Sujeito a: - x1 ≤ 0 - x2 ≤ 0 1 - x1 x2 ≤ 0

-5 -4 -3 -2 -1 0 1 2 3 4 5-5

-4

-3

-2

-1

0

1

2

3

4

5 Valor ótimo de x: x* = (1,1) Valor ótimo de f(x): f*(x) = 2

Figura 3.1 – Plano x1 ,x2 das restrições do exemplo

0 1 2 3 4 5 0

1

2

3

4

5

f(x) = 5

f(x) = 4

f(x) = 3

f(x) = 2

Figura 3.2 – Gráfico do exemplo

b) Problema de Factibilidade Encontrar x tal que:

gj(x) ≤ 0, j = 1...p hi(x) = 0, i = 1...m (3.2) x ∈ S

ou determinar que C = ∅

S

S

11

Este problema é equivalente ao problema (3.1) considerando que f(x) = 0. Assim:

∅=∞+∅≠

=)(convenção C se ,

C se ,0)(* xf

c) Expressando o Problema de Otimização na Forma Padrão

Restrições de desigualdade: No problema de otimização na forma padrão adota-se por convenção que o segundo membro (lado direito) da restrição de igualdade e desigualdade é igual a zero. Isto pode ser sempre obtido fazendo com que a restrição de igualdade )(~)( xpxp ii = seja expressa por:

)(~)()(0)( xpxpxhxh iiii −=⇒= De modo similar, a restrição de desigualdade gj ≥ 0 pode ser expressa por:

00)( ≤−⇒≥ jj gxg Função objetivo: Problemas de maximização também podem ser resolvidos como problemas de minimização:

Minimizar f(x) Sujeito a: gj(x) ≤ 0, j = 1...p

hi(x) = 0, i = 1...m

Maximizar - f(x) Sujeito a: gj(x) ≤ 0, j = 1...p

hi(x) = 0, i = 1...m

Uso de Variáveis de Folga: O uso de variáveis de folga baseia-se na simples observação de que gj(x) ≤ 0 se e somente se existe sj ≥ 0 que satisfaz gj(x) + sj = 0. De modo similar gj(x) ≥ 0 se e somente se existe sj ≥ 0 que satisfaz gj(x) - sj = 0. Estas variáveis sj são chamadas de variáveis de folga, estando associadas a cada restrição j. Estas variáveis podem ser utilizadas para substituir uma restrição de desigualdade por uma restrição de igualdade e uma restrição de não negatividade. Para (x1=0, x2=1, x3=12, F1=32): Restrição: 6x1 + 4x2 + x3 ≤ 48 (0+4+12) ≤ 48 (16) ≤ 48 Nova restrição: 6x1 + 4x2 + x3 + s1 = 48 (0+4+12+32) = 48 (48) = 48

12

Definições Importantes

a) Vetor Gradiente: É obtido a partir das derivadas parciais da função em relação as variáveis x1...xn de f(x).

T

nxf

xf

xfxf ),......,,()(

21 ∂∂

∂∂

∂∂

=∇

Considere a função: f(x1,x2) = 2x1+3x2, cujo gradiente é:

=∇

32

)(xf

a) b)

Figura 3.3 – a) Gráfico de f(x) b) projeção das retas de nível

O gradiente da função indica a direção e sentido de maior variação da função f(x1,x2) no ponto onde está aplicado. Essa direção é perpendicular às retas de nível. b) Direções Factíveis: Uma direção d é factível quando qualquer movimento ao longo desta direção não viola nenhuma restrição do problema:

∃ ε > 0 tal que para 0 ≤ α ≤ ε : x + αd ∈ S

Figura 3.4 – Direções factíveis

d factível d não factível região factível

x1

x2

S

função f(x) gradiente

f(x)

13

4. Otimização Irrestrita – Métodos de Busca

4.1. Busca Unidimensional: Considere o problema: minimizar )(xf sujeito bxa ≤≤ . Como não se conhece o ponto exato de mínimo, chama-se este intervalo [ak, bk] de intervalo de incerteza. A idéia do método de busca unidimensional é excluir a cada iteração partes do intervalo de incerteza que não contém o mínimo da função, reduzindo, o intervalo de incerteza até que o intervalo seja tão pequeno quanto desejado

ε≤− )( kk ab , sendoε especificado como uma tolerância. O método baseia-se no fato da função f(x) ser unimodal/estritamente quasi-convexa (existe um x* ∈ (ak, bk) tal que f(x) é estritamente decrescente em [ak, x*), e estritamente crescente em (x*,bk]. Teorema: Seja f(x) uma função convexa no intervalo [a, b]. Seja λ e µ ∈[a, b], tal que λ < µ . Se f(λ) > f(µ), então f(z) ≥ f(µ) para todo z ∈[a, λ). Se f(λ) ≤ f(µ), então f(z) ≥ f(λ) para todo z ∈(µ, b]. De uma maneira geral, os métodos de busca que não utilizam derivadas (tais como Dicotômica, Fibonacci, Segmento Áureo ... ) baseiam-se neste princípio. Estes métodos também são chamados de busca seqüencial.

Figura 4.1 –Métodos de busca seqüencial

Busca Dicotômica Este método de busca realiza a redução do intervalo com duas avaliações da função objetivo. A partir do centro do intervalo de incerteza, a função objetivo é avaliada em dois pontos:

εµελ −+

=++

=22

kkk

kkk

baba

f(µ)

novo intervalo

f(λ)

λ µ ba λ µ b a

f(µ)

novo intervalo

f(λ)

14

• Quando f(λk) > f(µk), sabes-se que o ponto de mínimo não se encontra no intervalo [ak, λk]. Assim, o novo intervalo de incerteza será [λk, bk].

• Se f(λk) < f(µk), sabes-se que o ponto de mínimo não se encontra no intervalo

[µk, bk]. Assim o novo intervalo de incerteza será [ak, µk]. Algoritmo:

Método da Biseção

Este método utiliza informação da derivada para achar o ótimo.

• 1º caso: Se f ’(λk) = 0 ⇒ λk é o ponto mínimo • 2º caso: Se f ’(λk) > 0 ⇒ a função é crescente em λk e o mínimo está a

esquerda de λk • 3º caso: Se f ’(λk) < 0 ⇒ a função é decrescente em λk e o mínimo está a

direita de λk

Algoritmo:

Seja [a1, b1] o intervalo de incerteza inicial, e l o intervalo de incerteza final permitido. Seja n o menor inteiro positivo tal que (½)n ≤ l/(b1- a1). Faça k = 1. 1. Faça λk = ½(ak + bk) e calcule f’(λk). Se f’(λk) = 0, pare. A solução ótima é λk . Senão, se f’(λk) > 0 vá para o passo 2, e se f’(λk) < 0 vá para o passo 3. 2. Faça ak+1 = ak e bk+1 = λk. Vá para o passo 4. 3. Faça ak+1 = λk e bk+1 = bk. Vá para o passo 4. 4. Se k = n, pare. O mínimo está no intervalo [an+1, bn+1] e pode ser calculado como sendo λ = (an+1 + bn+1)/2 (ponto médio). Senão, faça k = k+1 e volte para o passo 1.

Escolha 2ε > 0, l > 0. Faça k = 1. 1. Se (bk - ak) < l, pare. O mínimo da função está no intervalo [ak, bk]. Senão, considere: λ = [ (ak + bk)/2 - ε ] e µ = [ (ak + bk)/2 + ε ] Vá para o passo 2. 2. Se f(λ) < f(µ), faça: ak+1 = ak e bk+1 = µk Senão, faça: ak+1 = λk e bk+1 = bk 3. Atualize: k = k + 1. Vá para o passo 1.

15

Exemplo: f(x) = x2 + 2x s.a. -3 ≤ x ≤ 6 Vamos supor que desejamos reduzir o intervalo de incerteza inicial para um intervalo de incerteza final cujo tamanho l seja menor ou igual a 0.2. Assim, o valor de n que satisfaz:

(½)n ≤ l/(b1- a1) 0.2/9 = 0.0222

Como: (½)5 = 0.0313 (½)6 = 0.0156 ⇒ n = 6 (½)7 = 0.0078

RESULTADOS DO METODO DE BUSCA DA BISECAO ==================================================== k | a | b | lamb | derivada | ==================================================== 1.0 -3.0000 6.0000 1.5000 5.0000 2.0 -3.0000 1.5000 -0.7500 0.5000 3.0 -3.0000 -0.7500 -1.8750 -1.7500 4.0 -1.8750 -0.7500 -1.3125 -0.6250 5.0 -1.3125 -0.7500 -1.0313 -0.0625 6.0 -1.0313 -0.7500 -0.8906 0.2188 7.0 -1.0313 -0.8906 ------------------------------------------------ FIM DA BUSCA!!! O INTERVALO DE INCERTEZA É: -1.0313 -0.8906 O MINIMO ESTIMADO É: -0.9609 O VALOR DA FUNCAO NO MINIMO É: -0.9985 Valor de "n" utilizado é: 6.0 Observe que o tamanho do intervalo de incerteza final é 0.1407, que é menor que 0.2.

Busca Exaustiva

Este método consiste em avaliar a função objetivo em um número de pontos pré-determinados e igualmente espaçados entre si dentro do intervalo de incerteza [a, b]. Suponha que uma função definida dentro de um intervalo de incerteza [a, b] seja avaliada em 6 pontos distintos igualmente espaçados entre si. Considerando que o valor da função nestes pontos seja conforme a Figura x, o ponto ótimo deve estar dentro do intervalo [x3, x5], de acordo com o conceito de função unimodal.

Figura 4.2 –Ilustração do método de busca exaustiva

x1 x2 x3 x4 x5 x6

16

Como a função é avaliada em todos os n pontos simultaneamente, este método pode ser chamado de busca simultânea. Este método é relativamente ineficiente quando comparado com os métodos de busca seqüencial (Dicotômica, Biseção, Fibonacci ...), nos quais a informação adquirida a partir da avaliação inicial é utilizada nas avaliações seguintes. 4.2. Busca Multidimensional

Método do Gradiente (Steepest Descent)

Problema:

)(min xfx

Neste método caminha-se na direção contraria a do gradiente da função, ou seja, na direção em que a função decresce:

)(xfd −∇=

Figura 4.3 –Método do gradiente

Algoritmo:

Seja ε > 0, escolha um ponto de partida x1, e faça k = 1. Repita 1. Determine descent direction: dk := −∇f(xk) 2. Determinar λk que minimize f(xk + αk dk), sendo αk ≥ 0. )(minarg

0 kkk dxf ααα

+=≥

3. Atualizar xk+1 = x k + αk d k k = k + 1 até critério de parada: ||∇f(xk)||<ε (solução é ótima!)

17

Neste método d é a direção de busca e α é o tamanho do passo a ser dado na direção d. Note que o passo 2 refere-se a um subproblema de busca unidimensional, tendo como variável apenas αk , pois sabe-se os valores de xk e dk. Exemplo: Min. f(x) = (x1-2)4 + (x1-2x2)2

+

=

+

2

1

2

1

1

2

1

dd

xx

xx

k

kk

α

f(x) = [(x1

k+αkd1k) – 2]4 + [ (x1

k+αkd1k) – 2(x2

k+αkd2k) ]2

Assim, a cada iteração, para um novo valor de xk e dk , calcula-se um αk ótimo através de uma busca unidimensional. O método do gradiente geralmente possui um bom desempenho nas primeiras iterações do processo de otimização. No entanto, à medida que se aproxima do ponto estacionário, o método apresenta um desempenho pobre, tomando pequenos passos, fazendo zig zag. O método do gradiente é um algoritmo simples, porém de convergência lenta, por isto é pouco usado na prática.

Figura 4.4 –Ilustração do método do gradiente – zig zag

Outros algoritmos de busca: Gradiente Conjugado, Newton ...

18

5. Otimização Irrestrita - Condições de Otimalidade

Este tipo de problema pode ser definido por:

Minimizar f(x) Sujeito a: x ∈ ℜn

5.1. Condições necessárias de primeira ordem: Seja Ω ⊂ ℜn e f possui todas as derivadas de primeira ordem. Se x* é um mínimo local de f em Ω, então para qualquer direção factível d em x*:

∇xf(x*)T d ≥ 0 (5.1) Se ∇xf(x*)T d < 0 para algum d ∈ ℜn factível, então a derivada direcional é negativa e f decresce na direção d. Ilustração:

Figura 5.1 – Condições necessárias de primeira ordem Produto Escalar:

Para o caso irrestrito, x* é interior a Ω, ou seja, todas as direções são factíveis. Logo:

∇xf(x*)T = 0 (5.2)

xT. y > 0 (ângulo entre x e y < 90º) xT. y < 0 (ângulo entre x e y > 90º)

xT. y = 0 (x e y são ortogonais)

19

5.2. Condições necessárias de segunda ordem: Seja Ω ⊂ ℜn e f possui todas as derivada de segunda ordem. Se x* é um mínimo local de f em Ω, então para qualquer direção factível d em x*:

1. ∇xf(x*)T d ≥ 0 (5.3) 2. Se ∇xf(x*)T d = 0 então dT ∇2

xf(x*) d ≥ 0 A primeira condição de 5.3 equivale a condição necessária de primeira ordem apresentada anteriormente. A segunda condição de 5.3 aplica-se somente se o ponto for interior a Ω, ou seja, se o problema for irrestrito. Assim, tem-se para o caso irrestrito que se x* é um mínimo local, então:

∇xf(x*)T = 0 (5.4) dT ∇2

xf(x*) d ≥ 0 onde ∇2

xf(x*) é a matriz Hessiana da função, também utilizada com a notação H(x). A equação 5.4 equivale a dizer que H(x) é semi-definida positiva (H ≥ 0). A matriz Hessiana é determinada por:

∂∂

∂∂∂

∂∂∂

∂∂∂

∂∂

∂∂∂

∂∂∂

∂∂∂

∂∂

=∇=Η

2

2

2

2

1

2

2

2

22

2

12

21

2

21

2

21

2

2

)()()(

)()()(

)()()(

)()(

nnn

n

n

xxf

xxxf

xxxf

xxxf

xxf

xxxf

xxxf

xxxf

xxf

xfx

L

MOMM

L

L

Vale lembrar que esta é uma condição necessária, e não suficiente! 5.3. Condições suficientes de segunda ordem: Seja Ω ⊂ ℜn e f possui todas as derivada de segunda ordem onde x* é um ponto interior a Ω. Suponha ainda que:

1. ∇xf(x*)T = 0 (5.4) 2. H(x) > 0 (H é positiva definida)

Então x* é mínimo local estrito de f(x).

20

Como identificar se H é definida positiva? Uma matriz A é definida positiva se e somente se todos os seus autovalores forem positivos, ou seja, todos os valores de λ que satisfazem a equação (A - λI) = 0 devem ser positivos. Do mesmo modo, uma matriz A é: • seimi-definida positiva sse: todos seus autovalores forem não-negativos • definida negativa sse: todos seus autovalores forem negativos • semi-definida negativa sse: todos seus autovalores forem não-positivos • indefinida sse: possui ao mesmo tempo autovalores positivos e

negativos (não é nem definida-positiva e nem definida-negativa).

Pode-se ainda verificar se uma matriz é definida positiva ou negativa através do cálculo de seus determinantes (menores principais líderes). Considere a matriz:

=

nnnn

n

n

aaa

aaaaaa

A

L

MOMM

L

L

21

22221

11211

Sejam ∆k para k = 1...n os menores principais líderes de A, então A > 0 (definida positiva) se e somente se ∆k > 0 para todo k = 1...n, e A < 0 (definida negativa) se e somente se (-1)k ∆k > 0 para todo k = 1...n (ou se o sinal de ∆k for (-1)k).

=∆

=∆=∆

nnnn

n

n

n

aaa

aaaaaa

aaaa

a

L

MOMM

L

L

K

21

22221

11211

2221

1211

2111 ,,,

Soluções de x* onde ∇f(x*) = 0 são chamadas de pontos estacionários de f(x) e em relação a natureza do ponto x* pode-se verificar que:

pt. de mínimo local H definida positiva

pt. de máximo local H definida negativa

pt. de sela H indefinida

nada podemos concluir (pode ser pt.de sela ou extremo local)

H é semi-definida positiva

Pelas condições previamente apresentadas só podemos garantir que um ponto x* seja mínimo local de f(x). Introduzindo conceitos de convexidade podemos dizer:

21

Teorema: Seja f(x) ∈ C2 e S um conjunto convexo. Então f(x) é convexa em S se e somente se a matriz H(x) for semi-definida positiva para todos os x ∈ S. Teorema: Seja S um conjunto convexo e f(x) uma função em S com f(x) ∈ C2. Se a matriz H(x) for definida positiva para todos os x ∈ S então f(x) é estritamente convexa. No entanto, se f(x) é estritamente convexa então a H(x) é semi-definida positiva para todos os x ∈ S. Teorema: Seja S um conjunto convexo e considere o problema de minimizar f(x) em S. Suponha que x* é um mínimo local do problema. Então: 1. Se f(x) é uma função convexa, então x* é mínimo global do problema. 2. Se f(x) é uma função estritamente convexa, então x* é mínimo global estrito (único) do problema. Teorema: Seja f(x) ∈ C2 uma função convexa, então as condições de 1ª ordem são necessárias e suficientes para que x* seja um ponto de mínimo global. Exemplos:

Exemplo 1) Minimizar 1)( 2 −= xxf Condição necessária de 1a ordem:

002)( =⇒==′ xxxf Condição de suficiência:

2)( =′′ xf Como 0)( >′′ xf , x = 0 é mínimo local e global único da função.

-5 -4 -3 -2 -1 0 1 2 3 4 5-5

0

5

10

15

20

25

x

y

Figura 5.2 – Gráfico da função

22

Exemplo 3) Minimizar f(x1,x2) = x1

2 – x1x2 + x22 – 3x2

Condição necessária 1a de ordem:

=

−+−

−=∇

00

322

21

21

xxxx

f ⇒ x1 = 1 e x2 = 2

Condição de suficiência:

0314022112

21 >=−=∆>=∆⇒

−

−= eH

Logo, o ponto x1 = 1 e x2 = 2 é mínimo global de f(x1,x2).

-5

0

5

-5

0

5-20

0

20

40

60

80

100

x1x2

f(x1,

x2)

-5 -4 -3 -2 -1 0 1 2 3 4 5-5

-4

-3

-2

-1

0

1

2

3

4

5

x1

x2

Figura 5.3 – Gráficos da função

ponto ótimo ponto ótimo

23

6. Otimização Restrita Este tipo de problema pode ser definido por:

Minimizar f(x) Sujeito a: gj(x) ≤ 0, j = 1...p (6.1) hi(x) = 0, i = 1...m

A seguir serão apresentadas as condições de otimalidade de KKT (Karush-Kuhn-Tucker). 6.1 Restrições de desigualdade Consideraremos apenas as restrições de desigualdade:

Minimizar f(x) Sujeito a: gj(x) ≤ 0, j = 1...p (6.2)

Definições Importantes: • Restrições Ativas e Inativas: Uma restrição g(x) ≤ 0 está ativa em um ponto factível

x* se g(x*) = 0, e inativa se g(x*) < 0. A figura abaixo apresenta três restrições de desigualdade: g1(x) ≤ 0, g2(x) ≤ 0 e g3(x) ≤ 0. A região pontilhada representa o conjunto factível formado pelas restrições. Na fig. a), o ponto x* está no interior do conjunto. Assim, nenhuma restrição está ativa, portanto g1(x*) < 0, g2(x*) < 0, g3(x*) < 0. Na fig. b), as restrições g1 e g3 estão ativas em x*, portanto g1(x*) = g3(x*) = 0.

Figura 6.1 – Restrições Ativas e Inativas

• Ponto Regular: Seja x* um ponto que satisfaz a restrição g(x*) ≤ 0, e seja J o

conjunto dos índices das restrições ativas gj(x*) ≤ 0, j ∈ J. Diz-se que x* é um ponto regular das restrições ativas se os vetores gradiente ∇gj(x*), com j∈J, são linearmente independente.

∇g1(x*) , ∇g2(x*) , ... , ∇gn(x*)

g1(x)

g2(x)

g3(x)

• x*

g1(x)

g2(x)

g3(x)

• x*

∇f (x*)

∇g1 (x*) ∇g3 (x*)

Fig. a) Fig. b)

24

Interpretação Geométrica: Dado o problema: Min. f(x,y) = (x-2)2 + (y-1)2 s.a. g1(x,y) = -y + x2 ≤ 0 g2(x,y) = x + y -2 ≤ 0 Obtém-se como solução ótima restrita x* = (1,1), sendo a solução ótima irrestrita x = (2,1). O gradiente da função no ponto x* é: ∇f(x,y) = [-2 0]T. O gradiente das restrições no ponto x* são: ∇g1(x,y) = [2 -1]T e ∇g2(x,y) = [1 1]T. Através da figura abaixo nota-se que -∇f está dentro do cone gerado pelos gradientes das restrições limitantes do problema.

Se x* é um mínimo local e se 0*)( <∇ dxf T (d é uma direção que minimiza f), então d não é uma direção factível. Em outras palavras, Se x* é mínimo local, então toda direção que minimiza f não é factível (já está no mínimo), portanto:

factívelpara,0*)( ddxf T ≥∇

Na figura, note que em x* não há direção factível tal que ∇f(x)Td < 0.

0 0.5 1 1.5 2 2.5 30

0.5

1

1.5

2

2.5

3

x

y

Figura 6.2 – Exemplo

(2,1)x*=(1,1)

∇f (x*)

∇g1(x*)

∇g2(x*)

-∇f (x*)

25

a) Condições necessárias de 1ª ordem de KKT Considere o problema (6.2) com f e g diferenciáveis. Assuma que x* é ponto regular. Seja x* um mínimo local do problema, então existe escalares µj ≥ 0 (j∈J) tal que:

∑∈

≥∇=∇−Jj

jjj uxguxf 0,*)(*)(

Esta condição necessária equivale a dizer que o negativo do gradiente da função é uma combinação convexa do gradiente das restrições limitantes, ou seja, -∇f(x*) deve estar dentro do cone gerado pelos gradientes das restrições limitantes do problema.

Generalizando, para incluir todas as restrições (ativas e inativas), pode-se escrever:

se µj = 0 então gj(x*) < 0 ⇒ restrição inativa µj > 0 apenas se gj(x*) = 0 ⇒ restrição ativa

Sendo o produto µj gj = 0 para todo j. Esta igualdade é chamada de condição de folga complementar.

Portanto, as condições necessárias de KKT são:

0,0

0*)(*)(1

=≥

=∇+∇ ∑=

jjj

p

jjj

guu

xguxf (6.3)

onde µj são os multiplicadores de Lagrange. Notação Vetorial:

0,00*)(*)(

=≥

=∇+∇

j

T

j guuuxgxf

Tendo-se p restrições e n variáveis, ∇g(x*) é uma matriz n x p cuja coluna é ∇gj(x*), e u é um vetor p x 1 contendo os multiplicadores de Lagrange. NOTA: Para que o ponto seja candidato a ótimo local, ∇gj(x)Td ≤ 0, como pode ser observado na figura. Exemplos: Exemplo 1) Min - x1 g1(x) = - x2 ≤ 0 g2(x) = - (1 - x1)3 + x2 ≤ 0 Considere x* = (1,0) e a direção d = (1,0) Sendo: ∇g1(x*)T = [ 0 -1 ]

∇g2(x*)T = [ -3(1 - x1)2 1 ] = [0 1] Verificar: ∇gj(x*)Td ≤ 0

26

[ ]

[ ] 001

10

001

10

=

=

−

⇒ Atende a condição !!

A direção d atende a condição ∇gj(x*)Td ≤ 0 mesmo apontando para fora da região factível. Porém, esta condição só é válida quando os vetores gradiente das restrições ativas são LI, o que não acontece neste caso.

0 0.5 1 1.5-0.5

0

0.5

1

x1

x2

Figura 6.3 – Gráfico do exemplo 1

Exemplo 2) A partir do gráfico abaixo, podemos observar que o ponto x1 satisfaz as condições de necessárias de KKT, pois -∇f(x1) está dentro do cone gerado pelos gradientes das restrições limitantes em x1 (∇g1(x1) e ∇g2(x1)). Por outro lado, -∇f(x2) está fora do cone gerado pelos gradientes das restrições limitantes em x2 (∇g2(x2) e ∇g3(x2)). Logo, o ponto x2 não atende as condições necessárias de KKT.

Figura 6.4 – Gráfico do exemplo 2

NOTA: Se o ponto está no interior do conjunto factível, as condições necessárias e suficientes são as obtidas para um problema sem restrições.

x2

x1

∇g3

∇g2 -∇f

-∇f ∇g1 ∇g2

g2=0

g1=0

g3=0

∇g2

∇g1

d

27

b) Condições necessárias de 2ª ordem de KKT Considere o problema (6.2). Seja f e g com derivadas de segunda ordem e x* ponto regular das restrições. Se x* é mínimo local do problema, então existem escalares uj tal que:

MLguu

xguxf

jjj

p

jjj

em positiva definida-semi é0,0

0*)(*)(1

=≥

=∇+∇ ∑=

As matrizes F e G são matrizes de derivadas parciais de segunda ordem em relação a x, e a matriz Hessiana L(x*) é dada por: L(x*) = F(x*) + ∑µjGj(x*) M é o plano tangente às restrições ativas do problema dado por: M=d: ∇gj(x*)Td=0, para j ∈ J onde: J = j: gj(x*) = 0, uj > 0 Assim, para que L(x*) seja semi-definida positiva em M : para todo d ∈ M ⇒ dTL(x*)d ≥ 0

c) Condições suficientes de KKT Considere o problema (6.2). Seja f e g com derivadas de segunda ordem. A condição suficiente para que x* seja mínimo local do problema é que existam escalares uj tal que:

MLguu

xguxf

jjj

p

jjj

em positiva definida é0,0

0*)(*)(1

=≥

=∇+∇ ∑=

Ou seja, para todo d ∈ M ⇒ dTL(x*)d > 0 6.2. Restrições de Mistas: Considere o problema com restrições de igualdade e desigualdade:

Minimizar f(x) Sujeito a: gj(x) ≤ 0, j = 1...p (6.4) hi(x) = 0, i = 1...m

28

a) Condições necessárias de 1ª ordem de KKT

0 qualquer,,0

0*)(*)(*)(11

=≥

=∇+∇+∇ ∑∑==

jjij

m

iii

p

jjj

guu

xhxguxf

λ

λ (6.5)

b) Condições necessárias de 2ª ordem de KKT

MLguu

xhxguxf

jjij

m

iii

p

jjj

em positiva definida-semi é0 qualquer,,0

0*)(*)(*)(11

=≥

=∇+∇+∇ ∑∑==

λ

λ (6.6)

As matrizes F, G e H são matrizes de derivadas parciais de segunda ordem em relação a x, e a matriz Hessiana L(x*) é dada por: L(x*) = F(x*) + ∑µjGj(x*) + ∑λiHi(x*) M é o plano tangente às restrições ativas do problema dado por: M=d: ∇hi(x*)Td = 0, i=1...m, e ∇gj(x*)Td=0, para j ∈ J onde: J = j: gj(x*) = 0, uj > 0 Assim, para que L(x*) seja semi-definida positiva em M : para todo d ∈ M ⇒ dTL(x*)d ≥ 0

c) Condições suficientes de KKT

MLguu

xhxguxf

jjij

m

iii

p

jjj

em positiva definida é0 qualquer,,0

0*)(*)(*)(11

=≥

=∇+∇+∇ ∑∑==

λ

λ (6.7)

Ou seja, para todo d ∈ M ⇒ dTL(x*)d > 0 6.3. Formulação Convexa: As condições de KKT são necessárias e suficientes para formulações convexas.

Minimizar f(x) Sujeito a: gj(x) ≤ 0, j = 1...p hi(x) = 0, i = 1...m

29

Formulação convexa:

f(x) convexa gj(x) , j = 1 ... p convexas hi(x) , i = 1 ... p lineares

onde a região factível do problema é um conjunto convexo. KKT necessária para mínimo local ⇒ KKT suficiente para min. global Exemplos: Min. f(x1,x2) = 2x1

2 + 2x1x2 + x22 – 10x1 – 10x2

s.a. g1(x1,x2) = x12 + x2

2 – 5 ≤ 0 g2(x1,x2) = 3x1 + x2 – 6 ≤ 0 Condições Necessárias de 1ª ordem: 4x1 + 2x2 – 10 + µ1(2x1) + µ2(3) = 0 2x2 + 2x1 – 10 + µ1(2x2) + µ2 = 0

µ1(x12 + x2

2 – 5) = 0 µ2(3x1 + x2 – 6) = 0 µ1 ≥ 0 , µ2 ≥ 0

Para obter-se a solução é necessário definir várias combinações de restrições ativas e testar o sinal dos multiplicadores de Lagrange. Hipótese 1: Ambas as restrições relaxadas (inativas)

µ1 = µ2 = 0 ⇒ 4x1 + 2x2 – 10 = 0 ⇒ x1 = 0 2x2 + 2x1 – 10 = 0 x2 = 5

g1: 0 + 25 – 5 = 20 ≤ 0 (FALSO) g2: 0 + 5 – 6 = -1 ≤ 0 (VERDADEIRO)

Hipótese 2: g1 ativa e g2 inativa µ1 > 0, µ2 = 0 ⇒ 4x1 + 2x2 – 10 + µ1(2x1) = 0 ⇒ x1 = 1

2x2 + 2x1 – 10 + µ1(2x2) = 0 x2 = 2 x1

2 + x22 – 5 = 0 µ1 = 1

g1: 5 – 5 = 0 ≤ 0 (VERDADEIRO) g2: 3 + 2 – 6 = -1 ≤ 0 (VERDADEIRO)

OBS: g2 é atendida com folga!

- Condições de Suficiência: L(x*) = F(x*) + ∑µjGj(x*), j ∈ J

=⇒

−+−+

=∇2224

)(10221024

)(21

21 xFxxxx

xf

30

=⇒

=∇

2002

)(22

)( 1

2

1

1 xGxx

xg

=

+

+=

4226

222224

*)(1

1

µµ

xL

Plano tangente: M’ = d : ∇gj(x*)Td = 0

∇g1(x*) = [2x1 2x2] = [2 4] ∇g1(x*)d = [2 4][d1 ; d2] = 2d1 + 4d2 = 0 ⇒ d2 = -d1/2 dTL(x*)d = 6d1

2 + 4d22 + 4d1d2

= 6d12 + 4(-d1/2)2 + 4d1(-d1/2)

= 5d12 > 0

Portanto, L(x*) é definida positiva no plano tangente às restrições ativas e o ponto obtido pela aplicação das condições de 1ª ordem é um mínimo local.

31

7. Função Lagrangeana Seja o problema:

Minimizar f(x) Sujeito a: gj(x) ≤ 0, j = 1...p (7.1) hi(x) = 0, i = 1...m

A função Lagrangeana £ associada ao problema é dada por:

£(x,λ,µ) = f(x) + ∑µjgj(x) + ∑λihi(x)

onde µj e λi são os multiplicadores de Lagrange. Utilizando esta definição, é possível escrever as condições necessárias de KKT de forma mais compacta:

mixhxpjxgx

xhxgxfx

i

j

iijjx

...1,0)(0),,(£...1,0)(0),,(£

0)()()(0),,(£

==→=∇

=≤→≤∇

=∇+∇+∇→=∇ ∑∑

λµλµ

λµλµ

λ

µ

0 qualquer,,0 =≥ jjij guu λ

7.1. Dualidade

Primeiramente vamos considerar, por simplificação, que o problema em questão possui apenas restrições de desigualdade, uma vez que h(x) = 0 pode ser substituído por h(x) ≤ 0 e -h(x) ≤ 0.

Problema Primal (P) Minimizar x f(x) Sujeito a: gj(x) ≤ 0, j = 1...p (7.2) x ∈ S Problema Dual (D) Maximizar µ θ(µ) (7.3) Sujeito a: µ ≥ 0

Sendo a função dual (Lagrangian dual function) dada por:

θ(µ) = min. £(x,µ) = min. f(x) + ∑µjgj(x) Como o problema Dual consiste em maximizar o mínimo do Lagrangeano, este problema é muitas vezes referido como problema max-min. Teorema: A função dual θ(µ) é sempre côncava, mesmo que f(x) não seja convexa.

32

A função Lagrangeana incorpora as restrições do problema Primal. O problema com restrições (7.1) pode ser resolvido pelo problema equivalente dado pela equação 7.4, o qual é irrestrito:

θ(µ) = min. £(x,µ) = min. f(x) + ∑µjgj(x) + ∑λihi(x) (7.4)

Onde os valores de λ e µ devem atender as condições de KKT:

• Primal: gj(x) ≤ 0, j = 1...p, hi(x) = 0, i = 1...m (7.5) • Restrições do Dual: µ ≥ 0 • Folga complementar: µjgj(x) = 0, j = 1...p

Para problemas convexos, a minimização em (7.4) é equivalente a:

0)()()( =∇+∇+∇ ∑∑ xhxgxf iijj λµ (7.6)

As equações 7.4, 7.5 e 7.6 são referidas como condições de KKT. 7.2. Ponto de Sela:

Um ponto (xo, µo) com µo ≥ 0 e xo ∈ S é ponto de sela de £(x, µ) se: • £(xo, µo) ≤ £(x, µo) para todo x ∈ S (minimiza) • £(xo, µo) ≥ £(xo, µ) para todo µ ≥ 0 (maximiza)

Assim, o ponto de sela é simultaneamente um mínimo na direção x e um máximo na direção µ de £(x, µ).

Figura 7.1 – Ponto sela-nó

O conceito de £(x,µ) pode ser estendido para casos de maior dimensão (n-restrições).

7.3. Dualidade Fraca: Seja xo e µo soluções factíveis quaisquer do problema primal e dual. Então:

f(xo) ≥ θ(µo) Isto significa que para um certo (xo,µo) a função primal será sempre maior ou igual do que a função dual. Esta propriedade de dualidade fraca é sempre assegurada tanto para problemas convexos como para problemas não convexos. Portanto, θ(µo) pode fornecer

µ

£(x, µ)

x

33

um limite inferior para o valor ótimo de f(x). Esta propriedade é utilizada em problemas não convexos de difícil solução.

Figura 7.2 – Dualidade Fraca

7.4. Dualidade Forte: Seja xo e µo soluções factíveis do problema primal e dual tal que θ(µo) = f(xo), dizemos que a dualidade é forte (gap=0). O caso de dualidade forte não é assegurado para todos os problemas.

Figura 7.3 – Dualidade Forte

Teorema: Suponha f(x) e g(x) funções convexas e diferenciáveis (problema convexo). Suponha que existe (xo,µo) que satisfaz KKT. Então (xo,µo) são soluções ótimas do (P) e (D) com gap de dualidade nulo. Teorema: Um ponto (xo,µo) é ponto de sela de £(x,µ) se e somente se xo resolve (P), µo resolve (D) para µ ≥ 0 e θ(µo) = f(xo) (gap nulo). EXEMPLO: Minimizar f(x) = x1

2 + x22

Sujeito a: – x1 – x2 + 4 ≤ 0 x1 , x2 ≥ 0

Solução ótima: x1 = 2, x2 = 2

Resolvendo o dual: Max θ(µ) s.a. µ ≥ 0

θ(µ) = min £(x,µ) = x12 + x2

2 + µ(–x1 –x2 + 4)

• Min. £(x,µ) = x12 + x2

2 + µ(–x1 –x2 + 4) Para um dado µ, fixar µ e minimizar em x:

=

−−

00

22

2

1

µµ

xx (como o problema é convexo, a condição necessária é suficiente)

x1 = x2 = µ/2

minimiza f(x)

maximiza θ(µ)

GAP DE DUALIDADE = 0

minimiza f(x)

maximiza θ(µ)

GAP DE DUALIDADE ≠ 0

34

• Max. θ(µ) = µ2/4 + µ2/4 + µ(–µ/2 – µ/2 + 4) = -µ2/2 + 4µ

8)(22/4

404

21

====

=→=+−=∂∂

xfxx

µµµθ

NOTA 1: A função θ(µ) é côncava 7.5. Decomposição Dual: Alguns tipos de problemas são separáveis.

∑

∑

∑

=

=

=

=

≤q

kkk

q

kkk

q

kkk

xh

xgas

xf

1

1

1

0)(

0)(..

)(Minimizar (7.7)

Nesta formulação, o vetor x é dividido em q grupos distintos. Ambas as restrições e função objetivo são decompostas em somatórios dos grupos individuais. Este tipo de problema é muito atrativo para aplicação de métodos duais, pois a minimização irrestrita min £(x,λµ) pode ser decomposta em subproblemas menores. Este método é chamado de decomposição dual. Aplicando o método no problema 7.3 obtém-se:

[ ]∑=

++=q

kkk

Tkk

Tkk xgxhxf

1)()()(),£(x, µλµλ

∑=

=q

k 1k ),(x,£),£(x, µλµλ

onde £k(x,λµ) depende apenas de xk: )()()(),(x,£k kk

Tkk

Tkk xgxhxf µλµλ ++=

Assim, o problema primal (7.7) é equivalente a:

),£(x,min),( x µλµλθ = O qual pode ser decomposto em:

∑=

q

1kk...x ),(x,£min

1µλ

qx

µ

θ(µ)

4

35

E cada subproblema k pode ser resolvido separadamente: ),(x,£min k...x1

µλqx

A solução destes subproblemas pode ser usualmente obtida de modo eficiente, uma vez que os subproblemas são de dimensão menor do que o problema original.

Figura 7.4 – Decomposição Dual

NOTAS FINAIS !!!

“The great watershed in optimization isn’t between linearity and nonlinearity, but convexity and nonconvexity”

R. Rockafellar, SIAM Review 1993.

min £(x,λµ)

min £1 min £2 min £q