Gradientenverfahren zur nicht-linearen Optimierung, mit nloptr in R

In diesem Beitrag wird die Optimierung mittels Gradientenverfahren in R mithilfe des nloptr-Pakets vorgestellt.

Zur Lösung von Transportproblemen oder Netzwerkmodellierungsproblemen reicht oftmals eine lineare Programmierung aus.

Abhängig vom jeweiligen Thema kann jedoch eine nicht-lineare Optimierung relevant werden, wenn zusätzliche Einschränkungen oder Ziele berücksichtigt werden, die nicht linear sind.

R bietet ein Paket zur Lösung nichtlinearer Probleme an: nloptr.

In diesem Beitrag werde ich das nloptr-Paket anwenden um das folgende nicht-lineare Optimierungsproblem unter Anwendung der Gradientenabstiegsmethode (Gradientenverfahren) zu lösen. Gradientenabstiegsalgorithmen suchen nach der Richtung der steilsten Änderung, d.h. der Richtung der maximalen oder minimalen ersten Ableitung. Die Logik ist, dass ich mich schnell meinem Optimum nähern werde, wenn ich mich weiter in Richtung des steilsten Abstiegs (Minimierung) oder der steilsten Steigung (Maximierung) bewege.

Das Problem:

Wichtiger Hinweis: Wenn Sie mit nloptr nichtlineare Probleme modellieren müssen Sie das Problem als Minimierungsproblem angeben und alle Ungleichheitsbeschränkungen müssen vom Typ <= 0 (kleiner als) sein. Die Funktion kann Gleichheitsbeschränkungen verarbeiten, sodass Sie sie nicht durch überlappende Gleichheitsbeschränkungen ersetzen müssen. Variablen dürfen auf Boxen beschränkt sein und dies kann vom nloptr-Solver berücksichtigt werden.

Für die Durchführung des Gradientenverfahrens muss dem Algorithmus ein Startpunkt zur Verfügung gestellt werden. Dieser Startpunkt muss also definiert sein.

Ich modelliere und löse das obige Problem über das Gradientenverfahren mit dem nloptr-Paket in R.

# Paket laden
library(nloptr)

# zu optimierende Funktion definieren
eval_f <- function(x){
  return(
    list(
      "objective"=x[1]^2+x[2]^2,
      "gradient"=c(2*x[1],
                   2*x[2])
       )
  )
}

# Funktion zur Darstellung der Ungleich-NB definieren ("<=0")
eval_g_ineq <- function(x){
  return(
    list(
      "constraints"=x[1]+x[2]-100,
      "jacobian"=c(1,
                   1)
    )
  )
}

# Startpunkt definieren
x_0 <- c(10,10)

# zusätzliche Einstellunge; auch in nloptr Dokumentationsdatei empfohlen
# diese Einstellungen definieren den anzuwendenden Optimierungsalgorithmus
local_opts <- list( "algorithm" = "NLOPT_LD_MMA",
                    "xtol_rel"  = 1.0e-7 )

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

# problem modellieren und lösen
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)

Das Optimierungsergebnis kann nun angezeigt werden:

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

Die Optimierung mittels Gradientenverfahren ist auch hier dokumentiert: https://en.wikipedia.org/wiki/Gradient_descent