DAS-6651:
Otimização e Suas Subáreas
DAS-6651 - MSPO
Eduardo Camponogara
1
0. Agenda










2
Conceitos
Programação Linear
Programação Linear Inteira
Programação Quadrática
Mínimos Quadrados Não-Linear
Equações Não-Lineares
Otimização Não-Linear Irrestrita
Otimização Não-Linear com Limites Sup/Inf
Otimização Não-Linear Restrita
Programação Semi-Definida
1. Conceitos

Otimização:
–
3
Área da matemática aplicada que se preocupa em
calcular e computar valores ótimos para variáveis
de decisão que induzam o desempenho ótimo, ao
mesmo tempo que satisfazem restrições, de um
modelo matemático.
1. Elementos de um Problema de
Otimização

Variáveis de Decisão:
–
–
4
parâmetros cujos valores definem uma solução para o
problema.
Em um sistema de produção, esses parâmetros podem definir
as quantidades produzidas e os recursos utilizados.
1. Elementos de um Problema de
Otimização

Variáveis de Decisão:
–
–

Função Objetivo:
–
–
5
parâmetros cujos valores definem uma solução para o
problema.
Em um sistema de produção, esses parâmetros podem definir
as quantidades produzidas e os recursos utilizados.
uma função das variáveis de decisão a ser minimizada ou
maximizada.
No sistema de manufatura, podemos estar interessados em
minimizar custos.
1. Elementos de um Problema de
Otimização

Variáveis de Decisão:
–

Função Objetivo:
–

uma função das variáveis de decisão a ser minimizada ou
maximizada. No sistema de manufatura, podemos estar
interessados em minimizar custos.
Restrições:
–
6
parâmetros cujos valores definem uma solução para o
problema. Em um sistema de produção, esses parâmetros
podem definir as quantidades produzidas e os recursos
utilizados.
conjunto de funções que definem o espaço factível de
soluções. No sistema de manufatura, as restrições
estabelecem os limites nos recursos utilizados.
1. Elementos de um Problema de
Otimização


Minimize f(x)
Sujeito a:
g(x)  0
h(x) = 0
x  Rn
Onde f: Rn  R,
g: Rn  Rp
h: Rn  Rq
7
1. Duas Exceções

Problemas sem objetivos
–

O usuário deseja apenas encontrar um conjunto de
decisões que sejam viáveis.
Encontre x  Rn, tal que:
g(x)  0
h(x) = 0
8
1. Duas Exceções

Problemas com múltiplos objetivos
–
–

9
Em problemas reais, não é incomum procurar otimizar mais do
que um objetivo. No problema de manufatura, o usuário pode
estar interessado em maximizar lucro, maximizar qualidade e
minimizar tempo de produção.
Usualmente, estes problemas são reduzidos a problemas
envolvendo apenas um objetivo (combinando -se múltiplos
objetivos em apenas um ou, alternativamente, escolhendo-se
um objetivo e introduzindo restrições).
Exemplo:
Minimize f1(x)
Maximize f2(x)
2. Programação Linear

Problema:
–
–

Dados:
–
–
–
–
–
10
Um atleta deseja definir uma dieta, ou seja, tipos e quantidades de
alimentos que atendam as suas necessidades mínimas.
Os alimentos devem ser escolhidos de forma a minimizar o preço
total
N alimentos, tais como arroz, feijão, alface, etc.
M tipos de substâncias alimentares, como proteínas, lipídios, etc.
cn o preço unitário do alimento n
amn a quantidade de substância m em cada unidade de alimento n
bm a quantidade mínima de substância m a ser ingerida pelo atleta
2. Programação Linear

11
Exercício: modele o problema em
programação matemática.
2. Programação Linear

Variáveis:
xn quantidade de alimento n a ser comprada e ingerida, n=1,…,N

Restrições:
a11x1 + a12x2 + … + a1NxN  b1
a21x1 + a22x2 + … + a2NxN  b2
…
aM1x1 + aM2x2 + … + aMNxN  bM
x1, x2, …, xN  0
12
2. Programação Linear

Função objetivo:
f = c1x1 + c2x2 + … + cNxN

Formulação compacta:
PL: Minimize cTx
Sujeito a:
Ax  b
x0
x  RN
13
3. Programação Linear Inteira

Em algumas aplicações, as variáveis de decisão são
inteiras. (Número de pessoas contratadas, número de
peças produzidas, etc.)

O mundo da programação linear inteira engloba os
seguintes problemas
Minimize cTx
Sujeito à:
Ax  b
Cx = d
x0
x  Zn
14
3. Programação Linear Inteira

Dados do Problema
–
–
–
–
–
–
15
Há um número m de possíveis locais para instalação de
depósitos.
Há um número n de clientes.
A demanda de aço do cliente i é di e esta deve ser suprida por
precisamente um depósito.
A capacidade de um possível depósito no local j é de uj.
O custo de transporte do depósito j para o cliente i é e cij.
O custo de instalação do depósito j é de fj.
3. Programação Linear Inteira

Tarefa
–
16
Formule o problema de definir quais depósitos devem ser
instalados de maneira a suprir a demanda e, ao mesmo
tempo, minimizar o custo total de instalação e transporte.
3. Programação Linear Inteira

Variáveis
xij = 1 se o cliente i é
atendido pelo depósito j
xij = 0 caso contrário

Formulação
n
m
m
Minimize S S cijxij + S fjyj
i=1 j =1
j =1
Sujeito a:
n
yj = 1 se o depósito j é
instalado
yj = 0 caso contrário
S dixij  ujyj
i=1
m
S xij = 1
j=1
xij  {0, 1} " i, j
yj  {0, 1} " j
17
para j =1, ..., m
para i =1, ..., n
4. Programação Quadrática

Representação
Minimize xTQx + cTx
Sujeito a:
Ax  b
Cx = d
onde Q é uma matriz simétrica.

Aplicações
–
18
Várias aplicações em identificação de parâmetros para
modelos de processos, modelos estruturais e sistemas de
controle, e em algoritmos como SQP.
4. Programação Quadrática


19
A dificuldade de se resolver tais problemas
depende da natureza da matriz Q.
Quais características de Q tornam o problema
difícil?
4. Programação Quadrática

20
A dificuldade de se resolver tais problemas
depende da natureza da matriz Q.
–
Se Q  0 (positiva semi-definida) ou Q > 0 (positiva
definida) o problema é relativamente fácil de se
resolver (ou seja, encontrar a solução ótima global).
–
Se Q é indefinida (ou negativa semi-definida,
definida) então o problema é muito difícil.
5. Mínimos Quadrados Não-Linear

O problema dos mínimos quadrados não-linear
consiste de um problema da seguinte forma:
P: Minimize 1/2||f(x)||2
x  Rn
Onde a) |||| corresponde à norma Euclidiana e
b) f(x) : Rn  Rm é uma função qualquer, contínua e diferenciável.

21
Tais problemas têm aplicações no casamento de
modelos com dados experimentais, tipicamente
encontrados em estudos econômicos, aprendizagem
automática e engenharia.
5. Mínimos Quadrados (Linear)
22

Seja w(h) um modelo que descreve a relação entre a
altura e o peso médio das pessoas do sexo feminino.

Suponha que o modelo escolhido é da forma
w(h) = x3h3 + x2h2 + x1h + x0,
um polinômio de ordem 3 representando o peso como
uma função da altura.
5. Mínimos Quadrados (Linear)

23
Os seguintes dados amostrais são fornecidos.
Exemplo (i)
Altura (hi) Peso (wi)
------------------------------------------------------------1
1.5
55
2
1.54
53
3
1.58
56
4
1.60
52
5
1.65
58
6
1.67
54
7
1.70
64
8
1.72
70
9
1.72
71
10
1.75
75
11
1.80
82
12 (n)
1.81
81
---------------------------------------------------------------
5. Mínimos Quadrados (Linear)

Problema
–
Encontre os parâmetros x3, x2, x1 e x0 que
minimizam a função, consistindo da soma dos
quadrados dos erros de predição.
n
Minimize
x1,x2,x3,x4
24
1/2 S || w(hi) - wi ||2
i=1
5. Mínimos Quadrados (Linear)

Solução Ótima
x1 = 100.0000
x2 = -33.1098
x3 = -62.9920
x4 = 41.7403
w (peso, kg)
predição
25
h (altura, m)
6. Equações Não-Lineares
26

Aplicações: sistemas de equações não-lineares aparecem em
problemas de otimização, mas também em equações diferenciais
e suas formas discretizadas, jogos dinâmicos e processos
iterativos.

Equações Não-Lineares
– Seja f(x) : Rn  Rm uma função contínua e diferenciável
– Problema: encontre x* tal que f(x*) = 0

Observação: alguns algoritmos, transformam este problema em
um problema de otimização irrestrita:
Minimize ||f(x)||
x  Rn
para alguma norma ||||.
6. Equações Não-Lineares

Aplicação em sistemas de controle: dado um sistema de
equações diferenciais, encontre um ponto de equilíbrio.

Exemplo
dx1/dt = - x1 - 1
dx2/dt = 2x1x2 - 2sqrt(2)x1 + 2x2 - 2sqrt(2) + sin(x2 - sqrt(2))
dx3/dt = 2x2 - 2sqrt(2)
x = [x1, x2, x3]
dx/dt = f(x) = 0
x* = [-1, sqrt(2), x3]
27
7. Otimização Não-Linear Irrestrita
28

Otimização irrestrita constitui um bloco fundamental no
desenvolvimento de software. Algoritmos para solução de
problemas de otimização restrita fazem uso de otimização
irrestrita.

Problema de Otimização Irrestrita
Minimize f(x)
x  Rn

Tipicamente procura-se um ótimo local x*, ou seja, x* tal que
f(x*)  f(x) para todo x B(x*, d) = {x : ||x - x*||  d} e d > 0.
Otimização global se preocupa em encontrar um vetor x*
cujo valor f(x*)  f(x) para todo x.
7. Otimização Não-Linear Irrestrita

Problema Exemplo:
–
–
–
29
Seja z = (x, y) a coordenada onde será instalada
uma central telefônica.
Suponha que as chamadas são recebidas de um
conjunto S = {z1=(x1,y1), ..., zm= (xm,ym)} de
localidades com probabilidade uniforme.
Seja Z a variável randômica associada com o local
das chamadas.
7. Otimização Não-Linear Irrestrita

Tarefa
–
30
Qual deve ser a localização z da central telefônica para que
E[(Z - z)2] seja minimizado? (E[f(Z)] é o valor esperado da
função f(Z) da variável randômica Z.)
7. Otimização Não-Linear Irrestrita

Solução
m
E[(Z - z)2] = S (zk - z)2.Probabilidade{Z = zk}
k=1
m
= S [(xk,yk) - (x,y)]2 / m
k=1
31
8. Otimização Não-Linear com
Limites Sup/Inf

Formulação: problemas da seguinte classe:
Minimize f(x)
lxu
x  Rn
f é uma função contínua, diferenciável
32

Aplicações: estes modelos têm aplicações em engenharia e na
identificação de modelos físicos, onde as grandezas (parâmetros)
são sujeitos a limites.

Algoritmos: alguns algoritmos de otimização restrita resolvem
sequências de problemas com limites superiores e inferiores.
9. Otimização Não-Linear Restrita

Modelo: os problemas de otimização não-linear restrita consistem
em minimizar uma função não-linear (contínua e diferenciável)
sujeita a restrições não-lineares (contínuas e diferenciáveis).
Minimize f(x)
Sujeito à:
g(x)  0
h(x) = 0
Onde f(x) : Rn  Rm, g(x) : Rn  Rp e h(x) : Rn  Rq são
funções contínuas e diferenciáveis

33
Observação: modelos de otimização não-linear restritos são os
mais gerais no domínio da otimização contínua.
9. Otimização Não-Linear Restrita

Problema Exemplo
–
–

Desejamos instalar uma estação de bombeiros de forma que a
mesma esteja dentro de um raio r (km) de um conjunto S =
{(x1,y1), ..., (xp,yp)} de prédios nas proximidades.
Além disso, desejamos localizá-la o mais afastado possível de
outras estações de bombeiros T = {(x1,y1), ..., (xq,yq)}.
Tarefa
Formule este problema em linguagem de otimização.
34
9. Otimização Não-Linear Restrita

Tarefa
Formule este problema em linguagem de otimização.
35
9. Otimização Não-Linear Restrita

Formulação
Maximize d
Sujeito a:

||(x,y) - (xj,yj)||  r
para j = 1, ..., p
||(x,y) - (xj,yj)||  d
para j = 1, ..., q
Observações
d  Min{ ||(x,y) - (xj,yj)|| : j = 1, ..., q }
r  Max{ ||(x,y) - (xj,yj)|| : j = 1, ..., p }
36
10. Programação Semi-Definida

Caracterização
Problemas com função objetivo linear.
Restrições envolvendo matrizes e suas propriedades
(tais como, positiva definida e semi-definida).

Definições
Fi(x) = Fi,0 + Fi,1x1 + ... + Fi,nxn
onde Fi,j = Fi,jT é uma matriz simétrica
37
10. Programação Semi-Definida

Classe de Problemas
Minimize cTx
Sujeito a: Fi(x)  0
para i = 1, ..., m
(a matriz Fi(x) deve ser positiva semi-definida,
linear matrix inequality).
38
10. Programação Semi-Definida

Exemplo:
–
Considere o seguinte sistema dinâmico
dx/dt = Ax
–
Uma condição suficiente para que o sistema convirja para x* = 0,
para qualquer estado inicial x(0), quanto t   é a existência de um
função V(x) com as seguintes propriedades:
–
–

39
V(x) é positiva definida, ou seja, para todo x  0 tem-se V(x) > 0 e
V(0) = 0
dV(x)/dt < 0 para x  0.
Problema: como encontrar tal função?
10. Programação Semi-Definida

Seja V(x) = xTPx para P > 0. Neste caso V(x) satisfaz a condição
de ser positiva definida.

Como fazer para satisfazer a segunda condição?
dV/dt = d(xTPx)/dt =
= (dx/dt)TPx + xTP(dx/dt) =
= (xTAT)Px + xTP(Ax) =
= xT( ATP + PA)x
Então a condição dV/dt < 0 é equivalente a ATP + PA < 0.
40
10. Programação Semi-Definida

Formulação do problema
Minimize cTx
Sujeito a:
P(x) > 0
ATP(x) + P(x)A < 0,
onde P(x) gera o espaço de matrizes simétricas
41
11. Referências

Optimization Tree
–

OR Notes
–
42
http://www-fp.mcs.anl.gov/otc/Guide/OptWeb/
http://www.ms.ic.ac.uk/jeb/or/contents.html
12. FIM

43
Obrigado!!!