Descenso de gradiente en R, para optimización no lineal (paquete nloptr)

Esta publicación presenta la optimización del descenso de gradientes en R, utilizando el paquete nloptr.

Para resolver problemas de transporte o problemas de modelado de redes, será suficiente la programación lineal.

Sin embargo, dependiendo del tema en cuestión, la programación no lineal puede resultar relevante al considerar limitaciones u objetivos adicionales que no son lineales.

R proporciona un paquete para resolver problemas no lineales: nloptr

En esta publicación, aplicaré el paquete optimx para resolver el siguiente problema de optimización no lineal, aplicando la metodología de descenso de gradiente. Los algoritmos de descenso de gradientes buscan la dirección del cambio más pronunciado, es decir, la dirección de la primera derivada máxima o mínima. La lógica es que si sigo moviéndome en la dirección de descenso más pronunciado, me moveré rápidamente hacia mi óptimo.

El problema que nos ocupa:

Nota importante: cuando se usa nloptr para modelar problemas no lineales, se debe establecer el problema como un problema de minimización y todas las restricciones de igualdad deben ser de tipo <= 0 (menor que). La función puede manejar restricciones de igualdad, por lo que no tiene que reemplazarlas superponiendo restricciones de igualdad. Las variables pueden estar restringidas por recuadros, y esto puede ser considerado por el solucionador nloptr. Sin embargo, debe elegirse un punto de partida.

Modelo y resuelvo este problema con el descenso de gradiente, usando el paquete nloptr en R (¡con la función 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)

Repasemos ahora el resultado de la optimización:

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

Puede encontrar más detalles sobre la optimización del descenso de gradientes en Wikipedia: https://en.wikipedia.org/wiki/Gradient_descent