Introduction à l'optimisation non linéaire (I)

1. Résumé

Cette fois, j'ai résumé les grandes lignes de la méthode Newton, qui est la méthode d'optimisation non linéaire la plus connue et la plus couramment utilisée, et j'ai fourni un exemple d'implémentation en R et Python. Je l'ai utilisé (prévu) pour l'estimation des paramètres d'une méthode d'analyse avec analyse multivariée, donc je l'ai implémenté pour l'étude également.

2. Optimisation non linéaire

2.1 Qu'est-ce que c'est?

En l'état, c'est l'optimisation (= minimisation / maximisation) des fonctions non linéaires. Des exemples de fonctions non linéaires incluent $ y = x ^ 2 $ et $ y = x \ log_e x $. Par exemple, en prenant $ y = x \ log_e x $ comme exemple, si vous voulez obtenir un point qui donne la valeur minimale de cette fonction, (en supposant que vous savez que $ 0 <x $ est convexe vers le bas) ) Différencier par rapport à $ x $ $\frac{d}{dx}y = \log_e x + 1$ Tout ce que vous avez à faire est de calculer la valeur de la fonction au point où ce dégradé est de 0 . En d'autres termes $\log x_e + 1 = 0$$ Tout ce que vous avez à faire est de trouver la racine de. Au fait, $ \ hat {x} = 1 / e $. De cette façon, si l'équation peut être résolue simplement comme une étendue (si elle peut être résolue analytiquement), c'est bien, mais dans de nombreux cas, la solution ne peut pas être exprimée explicitement. Les méthodes d'optimisation non linéaires sont utiles dans de tels cas.

2.2 Méthode Newton-Raphson

Parmi les optimisations non linéaires, la méthode Newton (méthode Newton-Raphson, wiki est la méthode la plus connue, la plus simple et la plus largement utilisée. Il y a Newton% 27s_method)). Pour des détails mathématiques, voir Ici (Qu'est-ce que la méthode Newton ?? Solution approximative de l'équation résolue par la méthode Newton). Si vous êtes poliment illustré et que vous comprenez doucement les mathématiques du secondaire, je pense que vous pouvez vous faire une idée générale. Pour mettre en œuvre cela

• Différenciation numérique pour le calcul du gradient
• Itération de la formule de mise à jour de la méthode Newton

Deux sont nécessaires. Concernant le premier, pour le moment,

Implémentons. En R,

numerical.differentiate = function(f.name, x, h = 1e-6){
  return((f.name(x+h) - f.name(x))/h)
}

Donc, en python,

def numerical_diff(func, x, h = 1e-6):
    return (func(x + h)-func(x))/h

C'est comme ça? En utilisant ceux-ci et le calcul séquentiel par la méthode de Newton,

Résolvons. Un exemple d'exécution dans R est

newton.raphson(f.5, 100, alpha = 1e-3) # 0.3678798

Un exemple d'exécution en python est

newton_m(f_1, 100, alpha = 1e-3) # 0.36787980890600075

Vous pouvez voir que les deux sont proches de la solution de l'équation ci-dessus $ 1 / e \ Fallingdotseq1 / 2.718 = 0.3679176 $.

3. Exemple de code

C'est un code divers ...

{r, newton_raphson.R}

numerical.differentiate = function(f.name, x, h = 1e-6){
  return((f.name(x+h) - f.name(x))/h)
}

newton.raphson = function(equa, ini.val, alpha = 1, tol = 1e-6){
  x = ini.val
  while(abs(equa(x)) > tol){
    #print(x)
    grad = numerical.differentiate(equa, x)
    x = x - alpha * equa(x)/grad
  }
  return(x)
}

f.5 = function(x)return(log(x) + 1)
newton.raphson(f.5, 100, alpha = 1e-3)

{python, newton_raphson.py}

import math
def numerical_diff(func, x, h = 1e-6):
    return (func(x + h)-func(x))/h

def newton_m(func, ini, alpha = 1, tol = 1e-6):
    x = ini
    while abs(func(x)) > tol:
        grad = numerical_diff(func, x)
        x = x - alpha * func(x)/grad
    return x

def f_1(x):
    return math.log(x) + 1

print(newton_m(f_1, 100, alpha = 1e-3))

Pour que la méthode de Newton converge vers une solution optimale globale, la fonction à optimiser doit avoir une solution optimale globale dans l'intervalle d'optimisation $ [a, b] $ et être convexe dans cet intervalle. Faisons attention. Le programme que j'écrivais n'était pas facile à comprendre car il s'agissait d'un cas de variables multiples, mais il est simple et facile à comprendre dans le cas d'une variable. La précision du calcul dépend du paramètre tol et du paramètre h.