Cálculo da Direção de Caminhada:
Gradiente de f(x)
• O gradiente de uma função f(x1, x2, ..., xn), denotado por f(x1, x2, ..., xn),
é um vetor de derivadas parciais da função f(.) :
• f(x1, x2, ..., xn) = (f/x1, f/x2, ... , f/xn )
• Dado um ponto xk , a direção dada pelo vetor gradiente f(xk) é a direção
de maior crescimento em torno deste ponto.
• xk+1 = xk + α .f(xk)
• O vetor gradiente é perpendicular às curvas de nível da função
5-13
Cálculo da Direção de Caminhada:
Direção de crescimento e de decrescimento
Curva de nível
xk
f(x)
θ
x
Qualquer direção x é uma direção de crescimento sempre que o
seu ângulo (θ) em relação ao vetor gradiente é menor do que 90°.
Se θ > 90° então x é uma direção de decrescimento.
A direção -f(x) é a direção de máximo decrescimento neste
ponto.
5-14
Cálculo da Direção de Caminhada:
Teste sobre a Direção de Caminhada
• Seja uma função objetivo f(x) e seja xk uma solução.
Então uma nova solução dada por xk+1 = xk + x causa uma variação
na função objetivo de aproximadamente:
 f  j(f/xj)(λ  xj)  λ ( f(x). x ) (Produto escalar)
• Se f(x). x > 0, então x é uma direção de crescimento.
• Caso contrário x é uma direção de decrescimento.
• É possível mostrar que :
f(x). x = f(x) . x .cos θ
(1)
onde f(x) é a norma do gradiente.
Supondo f(x) e x normalizados, então f(x) = x = 1.
Portanto, (1) fica f(x). x =cos θ, que tem o valor máximo
para θ = 0 °. Ou seja, o máximo crescimento é quando
x = f(x)
5-15
Busca Unidimensional
Quanto Caminhar na direção x?
Nova solução : xk+1 = xk + α x
α?
• Como a busca é sobre uma única direção, então diz-se que esta
é uma busca unidimensional.
• O valor de α é tal que o valor da função objetivo seja o melhor
possível nesta direção.
5-16
Busca Unidimensional
• A busca unidimensional é equivalente a um problema de
uma única variável :
– Seja o problema :
• minimizar f(x) =( x1)2 + 2 (x2 )2 + x1 x2 - 6x1 -10x2, a partir do
ponto xk =( 1, 2)T e na direção d k = ( 1, 2)T.
• Então teremos : xk+1= xk + α d k = (1, 2 )T + α (1, 2 )T
= (1+ α , 2+ 2)T
(I)
• Substituindo (I) em f(x), teremos :
• f(α)= 11(α)2 - 4α - 15
• f(x) agora é função só de α
• Busca Unidimensional :
– Determinar o valor α* que minimiza f(α).
5-17
Busca Unidimensional
Mínimo de f(α)
f(α)/α = 0
22 α - 4 = 0
α *= 4/22
f(α)
α
α*=4/22
5-18
Observação 1 : Função Unimodal
• Uma função objetivo f(x) é unimodal se, para quaisquer dois pontos x1
e x2 tais que f(x1) < f(x2), x=(x1 - x2) é uma direção de crescimento.
• Uma função objetivo linear é sempre unimodal.
• Se a função objetivo de um problema de otimização é unimodal, então
todo ótimo local irrestrito é também um ótimo global.
5-19
Observação 2 : Função Unimodal, Conjunto Convexo e Ótimo Global
• Um CSF é dito convexo se para quaisquer duas soluções
factíveis x1 e x2 o segmento de reta que une estes dois pontos
também pertence ao CSF.
• O segmento de reta que une os pontos x1 e x2 é dado por x =
x1 +λ(x1- x2), 0  λ 1.
• Se todas as restrições de um problema de otimização são
lineares, então o CSF é um conjunto convexo.
• Se a função objetivo de um problema de otimização é
unimodal e o CSF é um conjunto convexo, então todo
ótimo local é também ótimo global
5-20
Obs.3 : Direção de Caminhada em problemas com restrições:
Restrições Ativas e Folgadas
• Em problemas com restrições uma direção de melhoria
pode ser infactível.
• Restrições ativas e restrições folgadas: Supondo que as
restrições de um dado problema são constituídas somente
das restrições de desigualdade, então, se para uma dada
solução factível todas as restrições são satisfeitas na
desigualdade, então todas as restrições são ditas folgadas.
• Caso contrário, se alguma restrição for satisfeita na
igualdade, então diz-se que esta restrições é ativa.
5-21
Obs.3 : Direção de Caminhada em problemas com restrições:
Restrições Ativas e Folgadas
A figura a seguir mostra alguns pontos sobre a região factível do problema da
RECAP. No ponto x(1) uma restrição está ativa; no ponto x(2) todas estão folgadas; e
nos pontos x(3) e x(4) há duas restrições ativas.
5-22
Direção de Caminhada em problemas com restrições
A direção x é uma direção factível em problemas com restrições
restrições lineares se satisfaz as seguintes condições:
i) Para restrições do tipo j aj xj b deve-se ter
j aj xj  0.
ii) Para restrições do tipo j aj xj  b deve-se ter
j aj xj  0.
iii) Para restrições do tipo j aj xj = b deve-se ter
j aj xj = 0.
5-23