Optimisation avec MATLAB

Présentation générale

Plusieurs fonctions spécifiques existent dans MATLAB pour résoudre des problèmes d'optimisation. Certaines fonctions sont disponibles dans la version de base du logiciel (polyfit/polyval, fminsearch et fminbnd) alors que les autres ne sont accessibles que par l'intermédiaire de l'optimization toobox.

Dans une grande majorité des cas, la fonction objectif du problème matlab doit être exprimée dans une fonction MATLAB externe ou anonyme. Selon la nature du problème d'optimisation à traiter, il est nécessaire de choisir la bonne fonction MATLAB apte à résoudre un tel problème. Dans le tableau suivant, sont regroupées les principales fonctions selon la nature des problèmes qu'elles peuvent résoudre.

Tableau récapitulatif des fonctions MATLAB pour l'optimisation selon le problème à traiter et la méthode numérique programmée. La dernière colonne indique les fonctions accessibles via l'optimization toolbox.

Problème monodimensionnel

sans contrainte

Méthode de la recherche dorée

fminbnd

Problème multidimensionnel

sans contrainte

Méthode de Nedler et Mead

fminsearch

Problème multidimensionnel

sans contrainte

Méthode de quasi-Newton

fminunc

Problème multidimensionnel

sans contrainte - identification paramétrique

Méthode de Gauss-Newton

lsqnonlin

Identification paramétrique - cas d'un polynôme

Méthode des moindres carrés

polyfit / polyval

Problème linéaire multidimensionnel

avec contraintes

Méthode du Simplex (cf. cours de Recherche Opérationnelle)

linprog

Problème non-linéaire multidimensionnel

avec contraintes

Méthode Sequential Quadratic Programming

fmincon

Fonction fminsearch (matlab)

La fonction fminsearch code la méthode de Nedler et Mead et permet de résoudre un problème multidimensionnel sans contrainte. C'est un méthode d'ordre 0, qui n'utilise aucune information concernant les gradients de la fonction objectif. La syntaxe générale de cette fonction peut faire appel à une fonction externe (premier cas) ou à une fonction anonyme (second cas):

1
[x,fval,exitflag,output] = fminsearch('fun',x0,options)

ou

1
[x,fval,exitflag,output] = fminsearch(@(x) fun(x),x0,options)

Arguments d'entrée :

  • fun : dans le premier cas, fun est une fonction externe où est exprimée la fonction objectif qu'on cherche à minimiser. Dans le second cas, fun est une fonction anonyme où est exprimée la fonction objectif qu'on cherche à minimiser.  

    Entête de la fonctionexterne fun : function f = fun(x)  ;

  • x0 :  vecteur des valeurs initiales pour démarrer la méthode. La dimension de x0 est égale au nombre de variables du problème ;

  • options (pas obligatoire) ; voir ci-dessous.

Arguments de sortie :

  • x : valeur finale des variables, ce sont les solutions si la méthode a convergé ;

  • fval : valeur finale de la fonction à minimiser ;

  • exitflag (pas obligatoire) : indicateur de fin d'exécution : 1 arrêt car solution trouvée, 0 car nombre d'itérations maximal atteint ;

  • output (pas obligatoire) : nombres d'itérations et d'évaluations de fonction réalisés.

Fonction fminbnd (matlab)

La fonction fminbnd code une méthode partiellement basée sur la méthode de la recherche dorée (optimisation monodimensionnelle sans contrainte). La syntaxe générale de cette fonction peut faire appel à une fonction externe (premier cas) ou à une fonction anonyme (second cas):

1
x,fval,exitflag,output] = fminbnd(‘fun',x1,x2,options)

ou

1
[x,fval,exitflag,output] = fminbnd(@(x) fun(x),x1,x2,options)

Arguments d'entrée :

  • fun : dans le premier cas, fun est une fonction externe où est exprimée la fonction objectif qu'on cherche à minimiser. Dans le second cas, fun est une fonction anonyme où est exprimée la fonction objectif qu'on cherche à minimiser. Entête de la fonction fun : function f = fun(x)

  • x1 et x2 :  bornes inférieure et supérieure du domaine dans lequel la solution est recherchée.

  • options (pas obligatoire) ; voir ci-dessous.

Arguments de sortie : voir les arguments de sortie de fminsearch.

Fonction fminunc (optimization toolbox)

La fonction fminunc code une méthode de type quasi-Newton pour l'optimisation multidimensionnelle sans contrainte. C'est une méthode d'ordre 2, la matrice hessienne est évaluée. La syntaxe générale de cette fonction peut faire appel à une fonction externe (premier cas) ou à une fonction anonyme (second cas):

1
[x,fval,exitflag,output] = fminunc('fun',x0,options)

ou

1
[x,fval,exitflag,output] = fminunc(@(x) fun(x),x0,options)

Arguments d'entrée et de sortie : voir fminsearch

Fonction lsqnonlin (optimization toolbox)

La fonction lsqnonlin code la méthode de Gauss-Newton pour l'optimisation multidimensionnelle sans contrainte. lsqnonlin est dédiée aux problèmes d'identification paramétrique puisque la fonction objectif doit s'exprimer sous la forme de termes élevés au carré ; chaque terme représentant la différence entre une valeur donnée et une valeur calculée par un modèle. La syntaxe générale de cette fonction peut faire appel à une fonction externe (premier cas) ou à une fonction anonyme (second cas):

1
[x,resnorm,residual,exitflag,output] = lsqnonlin(‘fun',x0,lb,ub,options)

ou

1
[x,resnorm,residual,exitflag,output] = lsqnonlin(@(x) fun(x),x0,lb,ub,options)

Arguments d'entrée :

  • fun : dans le premier cas, fun est une fonction externe où sont exprimés les termes intervenant dans la fonction objectif qu'on cherche à minimiser. Dans le second cas, fun est une fonction anonyme où sont exprimés les termes intervenant dans la fonction objectif qu'on cherche à minimiser. L'entête de la fonction fun est ainsi : function F = fun(x) ; F est un vecteur contenant l'ensemble des termes formant la fonction objectif (égale à la somme des termes de F élevés au carré) ;

  • x0 :  vecteur des valeurs initiales pour démarrer la méthode. La dimension de x0 est égale au nombre de variables du problème ;

  • lb et ub :  bornes inférieure et supérieure des éléments de x : domaine dans lequel la solution est recherchée. lb et ub ont la même dimension que x ;

  • options (pas obligatoire) ; voir ci-dessous.

Arguments de sortie :

  • x : valeur finale des variables, ce sont les solutions si la méthode a convergé ;

  • resnorm : valeur finale de la fonction à minimiser ;

  • residual : vecteur des résidus, c'est à dire le vecteur sortie de fun pour la valeur finale de x

  • exitflag (pas obligatoire) : indicateur de fin d'exécution : 1 arrêt car solution trouvée, 0 car nombre d'itérations maximal atteint ;

  • output (pas obligatoire) : nombres d'itérations et d'évaluations de fonction réalisés.

Fonction fmincon (optimization toolbox)

La fonction fmincon code des plusieurs méthodes (dont SQP) de résolution de problème d'optimisation multidimensionnelle avec contraintes. L'utilisateur avisé peut choisir la méthode numérique ou sinon laisser la fonction fmincon choisir automatiquement la méthode la plus adaptée. La syntaxe générale de cette fonction peut faire appel à une fonction externe (premier cas) ou à une fonction anonyme (second cas) :

1
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(‘fun',x0,A,B,Aeq,Beq,lb,ub,'nonlcon',option)

ou

1
[x,fval,exitflag,output,lambda,grad,hessian] = fmincon(@(x) fun(x),x0,A,B,Aeq,Beq,lb,ub,'nonlcon',option)

Arguments d'entrée :

  • fun : dans le premier cas, fun est une fonction externe où est exprimée la fonction objectif qu'on cherche à minimiser. Dans le second cas, fun est une fonction anonyme où est exprimée la fonction objectif qu'on cherche à minimiser.  Entête de la fonction fun : function f = fun(x)  ;

  • x0 :  vecteur des valeurs initiales pour démarrer la méthode. La dimension de x0 est égale au nombre de variables du problème ;

  • A et B : respectivement une matrice et un vecteur qui permettent d'exprimer les contraintes linéaires de type inégalité sous la forme : A*x <= B.

    A et B ont autant de lignes que de contraintes inégalité linéaires ; A a autant de colonnes que le nombre de variables de contrôle ;

  • Aeq et Beq : respectivement une matrice et un vecteur qui permettent d'exprimer les contraintes linéaires de type égalité sous la forme : Aeq*x = Beq.

    Aeq et Beq ont autant de lignes que de contraintes égalité linéaires ; Aeq a autant de colonnes que le nombre de variables de contrôle ;

  • lb et ub :  bornes inférieure et supérieure des éléments de x. lb et ub ont la même dimension que x ;

  • ‘nonlcon' : nom de la fonction externe MATLAB dans laquelle sont définies les éventuelles contraintes non-linéaires égalité et inégalité. L'entête de nonlcon.m est : function [c,ceq] = nonlcon(x)

    c est un vecteur qui contient les résidus des contraintes inégalité (toutes les composantes de c doivent être négatives à la solution).

    ceq est un vecteur qui contient les résidus des contraintes égalité (toutes les composantes de ceq doivent être nulles à la solution).

    nonlcon peut être également définie comme une fonction anonyme ;

  • options (pas obligatoire) ; voir ci-dessous.

Arguments de sortie :

  • x : valeur finale des variables, ce sont les solutions si la méthode a convergé ;

  • fval : valeur finale de la fonction à minimiser ;

  • exitflag (pas obligatoire) : indicateur de fin d'exécution : 1 arrêt car solution trouvée, 0 car nombre d'itérations maximal atteint ; il existe d'autres valeurs possible.

  • output (pas obligatoire) : nombres d'itérations et d'évaluations de fonction réalisés.

  • lambda : structure qui contient la valeur des multiplicateurs de Lagrange à la valeur finale de x

  • grad : vecteur gradient à la valeur finale de x

  • hessian : matrice hessienne à la valeur finale de x

Options

Les options par défaut peuvent être modifiées par l'intermédiaire de la fonction optimset qui est utilisée ainsi (par exemple avec fminbnd) :

1
options = optimset(‘propriete1',valeur1, ‘propriete2',valeur2, etc ...)
2
[x,fval,exitflag,output] = fminbnd('fun',x1,x2,options)

Les principales options modifiables sont entre autres :

  • 'display' : on choisira la valeur ‘iter' pour la propriété ‘display' afin d'avoir des informations sur le processus de convergence affichées à l'écran à chaque itération. Par défaut, les affichages ne sont proposés qu'en fin d'exécution.

  • 'MaxIter' : si le nombre d'itérations n'est pas suffisant, il peut être modifié en choisissant une valeur entière plus grande.

  • 'MaxFunEvals' : si le nombre d'évaluations de la fonction objectif n'est pas suffisant, il peut être modifié en choisissant une valeur entière plus grande.

  • 'tolX' : si on veut changer le critère d'arrêt basé les variations des variables de contrôle, il peut être modifié en choisissant une valeur réelle (plus cette valeur est petite, plus les tolérances sont serrées).

  • 'Diagnostics' : on choisira la valeur ‘on' pour avoir un diagnostic du problème traité avant le début des calculs itératifs.

ExempleExemple d'utilisation : fmincon

On cherche à résoudre le problème suivant :

\(Min \quad -x_1x_2\)

\(h_1(x_1,x_2)=20*x_1+15*x_2-30=0\)

\(g_1(x_1,x_2)=(x_1/2)^2+x_2^2-1≤0\)

\(0≤x_1\) et \(0≤x_2\)

C'est un problème avec une contrainte linéaire égalité, une contrainte non-linéaire inégalité et des bornes sur les variables de contrôle.

1
x0=[0.5 0.8] ;             % valeurs initiales pour x1 et x2 prises respectivement égales à 0.5 et 0.8
2
lb=[0 0] ;                 % definition des bornes inférieures
3
ub=[ ] ;                   % pas de bornes supérieures
4
Aeq=[20 15] ; Beq=[30] ;   % définition des coefficients de la première contrainte linéaire égalité
5
A=[ ] ; B=[ ] ;            % pas contrainte linéaire inégalité
6
fun=@(x) -x(1)*x(2) ;      % definition de la fonction objectif (intermédiaire d'une fonction anonyme)
7
[x,fval,exitflag,output] = fmincon(@(x) fun(x),x0,A,B,Aeq,Beq,lb,ub,'nonlcon')

Dans une fonction externe nonlcon.m, va être définie la contrainte non linéaire inégalité :

1
function [c,ceq]=nonlcon(x)
2
   ceq = [] ;                % pas de contrainte non linéaire égalité
3
   c(1)=(x(1)/2)^2+x(2)-1 ;  % definition de la contrainte non lineaire égalité sous la fome c(x) <=0
4
end