Optimización univariada: Método de búsqueda exhaustiva en R

Se implementa el método de búsqueda exhaustiva siguiendo el algoritmo presentado en "Optimization for Engineering Design" de Kalyanmoy Deb. Es un método de optimización univariada, en donde se hace el supuesto de que la función a optimizar cumple los requerimientos de concavidad/convexidad, unimodal y continua. Se trata del método más simple entre el resto de los métodos de optimización univariada, por lo que es un buen punto de partida.

En el método de búsqueda exhaustiva, el óptimo de la función es encerrado al calcular los valores de la función de puntos igualmente espaciados (vea figura). Usualmente, la búsqueda comienza desde un límite inferior de la variable y tres valores de la función consecutivos son comparados al mismo tiempo basado en el supuesto de unimodalidad de la función. Basado en el resultado de la comparación, la búsqueda se termina o continúa reemplazando uno de los tres puntos por un  nuevo punto. La búsqueda continua hasta que el mínimo es encerrado.

Fig. Método de búsqueda exhaustiva usa tres puntos igualmente espaciados

Implementación del algoritmo

exhaustiva <- function(a, b, n=10, evalua = function(x){x^2 + 54/x}){
  ## Parámetros
  # a: Límite inferior del intervalo.
  # b: Límite superior del intervalo.
  # n: Número de intervalos (default 10).
  # evalua: Función objetivo (default x² + 54/x).

  # Almacenar solución
  solucion <- c()
  # Contador
  iter <- 1

  # Paso 1
  x1 = a
  delta_x <- (b-a)/n
  x2 = x1 + delta_x
  x3 = x2 + delta_x

  # Paso 3a 
  while(x3 <= b  & length(solucion) == 0){
    fx1 = evalua(x1)
    fx2 = evalua(x2)
    fx3 = evalua(x3)
    # Paso 2
    if( fx1  >= fx2  & fx2 <= fx3 ){
      cat("\nFinalizado en ",iter,"Iteraciones\n")
      solucion <- c(x1,x3)
      return(list(Solucion=solucion))
    }else{
      cat("Iteración:",iter,"\t  x1:",x1,"\t  x2:",x2,"\t  x3:",x3,"\n")
      iter <- iter + 1

      # Actualiza valores
      x1 = x2
      x2 = x3
      x3 = x2 + delta_x
    } # Fin paso 2
  } # Fin paso 3a
  # Paso 3b
  cat("\nFinalizado en ",iter,"Iteraciones: Sin solución\n")
  return(list(Rango =  c(a,b)))
}

# Ejemplo
exhaustiva(0,5,500,  function(x){x^2 + 54/x})

> exhaustiva(0,5,25,  function(x){x^2 + 54/x})
Iteración: 1       x1: 0.0       x2: 0.2       x3: 0.4
Iteración: 2       x1: 0.2       x2: 0.4       x3: 0.6
Iteración: 3       x1: 0.4       x2: 0.6       x3: 0.8
Iteración: 4       x1: 0.6       x2: 0.8       x3: 1.0
Iteración: 5       x1: 0.8       x2: 1.0       x3: 1.2
Iteración: 6       x1: 1.0       x2: 1.2       x3: 1.4
Iteración: 7       x1: 1.2       x2: 1.4       x3: 1.6
Iteración: 8       x1: 1.4       x2: 1.6       x3: 1.8
Iteración: 9       x1: 1.6       x2: 1.8       x3: 2.0
Iteración: 10       x1: 1.8       x2: 2.0       x3: 2.2
Iteración: 11       x1: 2.0       x2: 2.2       x3: 2.4
Iteración: 12       x1: 2.2       x2: 2.4       x3: 2.6
Iteración: 13       x1: 2.4       x2: 2.6       x3: 2.8
Iteración: 14       x1: 2.6       x2: 2.8       x3: 3.0

Finalizado en  15 Iteraciones
$Solucion
[1] 2.8 3.2

>