Otimização Não-Condicionada

Este documento tem como objetivo contribuir para o entendimento de como resolver problemas de otimização não-condicionada no R. Para tanto, vamos aprender os seguintes pontos:

• Como usar a abordagem da derivadas parciais para solucionar problemas com apenas uma variável de escolha
  • Encontrar as condições de primeira e segunda ordem;
  • Obter os valores máximos e mínimos da função objetivo;
  • Gerar gráficos com os resultados.
• Como usar a abordagem de diferencial total para solucionar problemas com \(N\) variáveis
  • Encontrar a solução do problema usando a função optim
  • Testar se esta função encontra resultados semelhantes aos obtidos por meio dos determinantes dos menores principais líderes da matriz hessiana avaliada nos pontos críticos.

ABORDAGEM DAS DERIVADAS PARCIAIS

Como estudamos em sala de aula, uma alternativa para encontrar os valores críticos (candidatos à máximo e/ou mínimo) de uma função é fazer uso das derivadas parciais. Neste sentido, entendemos que igualar a derivada parcial de primeira ordem nos permite encontrar os valores críticos (chamamos tal procedimento de condição necessária de primeira ordem, CPO). Por outro lado, avaliar o sinal da derivada parcial de segunda ordem nos pontos críticos nos fornece a conclusão se o valor crítico é ponto de máximo, mínimo e/ou inflexão.

No decorrer desta seção, vamos entender como usar o pacote rootSolve para resolver problemas de otimização não-condicionada com 1 variável de escolha por meio da abordagem das derivadas parciais. Para tanto, vamos usar como exemplo a função \(y = x^{3} + 3x^{2} - 6x -8\). Observe o formato da função para o domínio \(-5<x<4\) no gráfico abaixo.

• CONDIÇÃO DE PRIMEIRA ORDEM (CPO)

Um dos passos iniciais em qualquer problema de otimização é encontrar condições necessárias e suficientes para o problema em questão. Ou seja, encontrar as raízes responsáveis por atender a condição \(f'(x=x_{0}) = 0\), também conhecida como condição de primeira ordem (CPO).

No código abaixo, mostramos como fazer uso do R para encontrar os valores críticos, ou seja, valor de \(x_{0}\) que torna a primeira derivada igual a zero.

######
### PACOTES NECESSÁRIOS
######

# Instalar pacotes (executar apenas uma vez)
# install.packages("rootSolve")

# Carregar os pacotes no ambiente
suppressMessages(require(rootSolve))               


######
### FUNÇÃO OBJETIVO 
######

# A função que analisaremos
y = function(x) (x^3 + 3*x^2 - 6*x - 8)

######
### CONDIÇÃO DE PRIMEIRA ORDEM 
######

# função vazia que receberá o resultado da primeira derivada 
derivada1 = function(x){}

# resultado da derivação usando as funções body e D. body permite acessar uma função
# seja para gravar o resultado ou para pegar a função. D aplica a derivação
body(derivada1) = D(body(y), 'x')

# Encontrar as raizes que tornam a primeira derivada igual a zero para o intervalo -5<x<4
roots = rootSolve::uniroot.all(derivada1, c(-5, 4))

Como resultado encontramos que os valores críticos são -2.73 e 0.73. Agora, precisamos avaliar se eles são pontos de mínimo, máximo ou sela.

• CONDIÇÃO DE SEGUNDA ORDEM (CSO)

Assim, precisamos verificar a condição de segunda ordem que verifica se a segunda derivada avaliada nas raízes da condição necessária (\(f"(x=x_{0})\)) é positiva, negativa ou igual a zero. Abaixo, exemplo de como encontrar as condições de primeira e segunda ordem

# Função que armazenará o resultado da derivada de segunda ordem
derivada2 = function(x){}
# Obtendo a derivada segunda
body(derivada2) = D(body(derivada1), "x")
# Encontrar o valor da derivada segunda para os valores críticos. Como
# estudamos, valores críticos que geram f"(x)<0 são pontos de máximo e
# valores críticos que geram f"(x)>0 são ponto de mínimo. Assim, pelos
# resultados esperamos que a primeira raiz seja um máximo e a segunda um
# mínimo.
derivada2(roots)

[1] -10.39229  10.39228

# Avaliar a função nas raízes da condição necessária (f'(x)=0).
# Aqui, usamos y() porque definimos a função como y. Observe que 
# confirmamos que a primeira raíz gera um máximo e a segunda um mínimo
y(roots)

[1]  10.3923 -10.3923

• GRÁFICO COM OS VALORES DE MÁXIMO E/OU MÍNIMO RELATIVOS

Uma vez que testamos as condições de primeira e segunda ordem e temos os valores críticos da condição necessária, \(f'(x=x_{0}) = 0\), avaliados na condição suficiente, \(f"(x=x_{0})\), podemos definir o máximo e/ou mínimo. O código abaixo mostra como criar um gráfico que nos mostra tais avlores.

# Usamos a função curve que desenha a função. Seus parâmetros são:
# - expr: a função a ser plotada
# - from: valor inferior do intervalo
# - to: valor superior do intervalo
# - type: tipo de gráfico (l: em linha)
# - ylab: nome do eixo vertical
# - xlab: nome do eixo horizontal
curve(expr = y, from = -5, to = 4, type = "l", ylab = "y=f(x)", xlab = "")
# Após isso, adicionamos as raízes para a função no intervalo. Usamos
# a função points que tem os seguintes parâmetros:
# - x: a variável do eixo verticial
# - y: a variável do eixo horizontal
# Observe que a função colocará um ponto nas coordenadas (x,y)
points(y(roots) ~ roots)

ABORDAGEM DE DIFERENCIAL TOTAL

Como estudamos em sala de aula, resolver problemas de otimização não-condicionada com \(N\) variáveis de escolha por meio da abordagem de derivadas parciais pode ser trabalhoso. Assim, nesta seção mostramos como usar a abordagem de diferencial total para resolver problemas de otimização não-condicionada com mais de uma variável de escolha no R. Para tanto, vamos aprender os seguintes pontos:

• EXEMPLO 1: ENCONTRAR MÁXIMO

Suponha que temos a função \(f(x,y,z) = -5x^2+10x+xz-2y^2+4y+2yz-4z^2\) e queremos encontrar os valores de \(x\), \(y\) e \(z\) que maximizam \(f(x,y,z)\). O códigoa abaixo, mostra como formular tal problema no R e como fazer uso do função optim para encontrar a solução.

######
### FUNÇÃO OBJETIVO 
######
f = function(x) -5*x[1]^2+10*x[1]+x[1]*x[3]-2*x[2]^2+4*x[2]+2*x[2]*x[3]-4*x[3]^2
#####
### CPO E CSO AO MESMO TEMPO
#####
# Aqui, usamos a função optim que permite resolver diversos problemas 
# de otimização. Seus parâmetros são:
# - par: valores iniciais para as variáveis de escolha
# - fn: a função objetivo que será minimizada (ou maximizada)
# - gr: uma função com a derivada parcial (gradiente) da função objetivo
# - method: o método a ser usado pelo algoritmo (use o help da função para entender melhor)
# - lower: limite inferior para as variáveis de escolha (restringir o domínio)
# - upper: limite superior para as variáveis de escolha (restringir o domínio)
# - hessian: valor lógico (retornar (TRUE) ou não retornar (FALSE) a matriz hessiana)
# - control = define se o problema é de máximo (fnscale=-1) ou mínimo (defaul)
# Otimizacao (repare o uso de control = list(fnscale=1) dado que queremos o máximo)
otimizacao1 = optim(par = c(0,0,0), fn = f, method = "L-BFGS-B", control = list(fnscale =-1), lower = c(0,0,0), hessian = TRUE)
# Valores críticos (CPO)
valores_criticos = otimizacao1$par
# Matriz Hessiana (CSO)
h1 = det(matrix(otimizacao1$hessian[1,1]))                                     # primeiro menor principal líder
h2 = det(matrix(otimizacao1$hessian[c(1,2),c(1,2)], ncol = 2, byrow = TRUE))   # segundo menor principal líder
h3 = det(matrix(otimizacao1$hessian, ncol = 3, byrow = TRUE))                  # terceiro menor principal líder
#####
### REGRA PARA AVALIAÇÃO DOS VALORES CRÍTICOS
#####
# Como estudamos em sala de aula, a regra que deve ser usada para definir se o valor
# crítico gera máximo ou mínimo é:
# - Máximo: H1<0, H2>0, H3<0, ..., (-1)^nHn>0
# - Mínimo: H1>0, H2>0, ..., Hn>0

Como resultado temos que o valor de máximo é 7.652 e que os valores de \(x\), \(y\) e \(z\) que geram este valor são 1.04, 1.22 e 0.43, respectivamente. Além disso, se fizemos o cálculo dos determinantes dos menores principais líderes da matriz hessiana resultante, obtemos que o primeiro menor princial tem valor igual a -10 (negativo) enquanto o segundo tem o valor 40 (positivo) e o terceiro tem o valor -276 (negativo) . Isso confirma que os resultados obtidos são para um máximo, conforme estudamos em sala de aula.

• EXEMPLO 2: ENCONTRAR MÍNIMO

Suponha agora que temos a função \(z(x_{1},x_{2},x_{3}) = 2*(x_{1})^2 + x_{1}*x_{2} + 4*(x_{2})^2 + x_{1}*x_{3} + (x_{3})^2 + 2\) e queremos encontrar os valores de \(x_{1}\), \(x_{2}\) e \(x_{3}\) que minimizam \(z(x_{1},x_{2},x_{3})\). Este exemplo foi resolvido em sala de aula e usaremos o R para cofirmar a resposta encontrada.

f = function(x){
  x1 = x[1]
  x2 = x[2]
  x3 = x[3]
  2*(x1)^2 + x1*x2 + 4*(x2)^2 + x1*x3 + (x3)^2 + 2
}

optim(c(-1,-1,-1), f, method = "BFGS", hessian = TRUE)

Como resultado temos que os valores de \(x_{1}\), \(x_{2}\) e \(x_{3}\) que minimizam \(z(x_{1},x_{2},x_{3})\) são bem próximos de \(0\), conforme encontramos em sala de aula. Ainda, o valor mínimo de \(z(x_{1},x_{2},x_{3})\) é \(2\) e a matriz hessiana é bem próxima da encontrada em sala de aula.

REFERÊNCIAS

Chiang, Alpha C., and Kevin Wainwright. 2006. Matemática Para Economistas. Elsevier.

Soetaert, Karline, and Peter MJ Herman. 2008. A Practical Guide to Ecological Modelling Using R as a Simulation Platform. Springer Science & Business Media.