Descida de gradiente em R, para otimização não linear (pacote nloptr)

Este post apresenta a otimização de gradiente descendente em R, usando o pacote nloptr.

Para resolver problemas de transporte ou problemas de modelagem de rede, a programação linear será suficiente.

No entanto, dependendo do tópico em questão, a programação não linear pode se tornar relevante ao considerar restrições adicionais ou objetivos não lineares.

R fornece um pacote para resolver problemas não lineares: nloptr

Neste post vou aplicar o pacote nloptr para resolver o problema de otimização não linear abaixo, aplicando a metodologia gradiente descendente. Os algoritmos de descida de gradiente procuram a direção da mudança mais acentuada, ou seja, a direção da primeira derivada máxima ou mínima. A lógica é que, se eu continuar me movendo na direção da descida mais íngreme, irei rapidamente para o meu ponto ótimo.

O problema em questão:

Nota importante: Ao usar nloptr para modelar problemas não lineares, deve-se definir o problema como um problema de minimização e todas as restrições de desigualdade devem ser do tipo <= 0 (menor que). A função pode lidar com restrições de igualdade, portanto, você não precisa substituí-las pela sobreposição de restrições de igualdade. As variáveis ​​podem ser restritas por caixa, e isso pode ser considerado pelo solucionador nloptr. No entanto, um ponto de partida deve ser escolhido.

Eu modelo e resolvo este problema com gradiente descendente, usando o pacote nloptr em R (com a função nloptr!):

# load package
library(nloptr)

# define function to be optimized
eval_f <- function(x){
  return(
    list(
      "objective"=x[1]^2+x[2]^2,
      "gradient"=c(2*x[1],
                   2*x[2])
       )
  )
}

# define function representing in-equality constraints "<= 0"
eval_g_ineq <- function(x){
  return(
    list(
      "constraints"=x[1]+x[2]-100,
      "jacobian"=c(1,
                   1)
    )
  )
}

# define starting point
x_0 <- c(10,10)

# additional settings suggested by nloptr documentation file
# these settings e.g. define the exact optimization algorithm
local_opts <- list( "algorithm" = "NLOPT_LD_MMA",
                    "xtol_rel"  = 1.0e-7 )

opts <- list( "algorithm" = "NLOPT_LD_AUGLAG",
              "xtol_rel"  = 1.0e-7,
              "maxeval"   = 1000,
              "local_opts" = local_opts )

# model and solve problem
solution <- nloptr(x0=x_0,
                   eval_f=eval_f,
                   lb=NULL,
                   ub=NULL,
                   eval_g_ineq = eval_g_ineq,
                   eval_g_eq = NULL,
                   opts=opts)

Vamos agora revisar o resultado da otimização:

print(solution)
## 
## Call:
## 
## nloptr(x0 = x_0, eval_f = eval_f, lb = NULL, ub = NULL, eval_g_ineq = eval_g_ineq, 
##     eval_g_eq = NULL, opts = opts)
## 
## 
## Minimization using NLopt version 2.4.2 
## 
## NLopt solver status: 3 ( NLOPT_FTOL_REACHED: Optimization stopped because 
## ftol_rel or ftol_abs (above) was reached. )
## 
## Number of Iterations....: 102 
## Termination conditions:  xtol_rel: 1e-07 maxeval: 1000 
## Number of inequality constraints:  1 
## Number of equality constraints:    0 
## Optimal value of objective function:  1.09462903864043e-94 
## Optimal value of controls: -7.398071e-48 -7.398071e-48

Você pode encontrar mais detalhes sobre otimização de gradiente descendente na Wikipedia: https://en.wikipedia.org/wiki/Gradient_descent

You May Also Like

Leave a Reply

Leave a Reply

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *

Esse site utiliza o Akismet para reduzir spam. Aprenda como seus dados de comentários são processados.