Découvrir Scilab/Optimisation d'une fonction

Table des matièresIndex



Optimisation d'une fonction


Soit une fonction ƒ de . L'optimisation consiste à trouver le vecteur x (vecteur à n composantes) donnant la valeur minimale de ƒ.

Optimisation non linéaire

modifier

L'optimisation non linéaire est le cas général. On utilise pour cela la fonction optim :

[fopt, xopt] = optim(costf, x0)

  • costf est la « fonction de coût » de ƒ ; c'est une fonction qui renvoit la valeur de la fonction ƒ en x et le gradient de ƒ en x, défini sous la forme
    function [f, g, ind] = costf(x, ind)
    f désigne ƒ(x), g est le gradient et ind est un index, un entier permettant de modifier le comportement de costf ;
  • x0 est une estimation de la solution ;
  • xopt est le vecteur trouvé ;
  • fopt = ƒ(xopt), valeur estimée du minimum.

On peut indiquer des bornes inférieures et supérieure de x, sous al forme de vecteurs xinf et xsup :

[fopt, xopt] = optim(f, x0, "b", xinf, xsup)

La fonction optim() est une méthode de quasi-Newton utilisant les critères de Wolfe.

Par exemple :

 
Minimum de la fonction pseudo-convexe différentiable   avec scilab.
function [f, g, ind] = cout(x, ind)
    f = x.*x + 5*sin(x);
    g = 2*x + 5*cos(x);
endfunction

n = 40;
x = linspace(-2*%pi, 2*%pi, n);
y = cout(x);

x0 = 0;

[fopt, xopt] = optim(cout, x0);

plot(x, y);
plot(xopt, fopt, "k+");

Si l'on ne connaît pas de forme analytique de la fonction dérivée, on peut utiliser la fonction numderivative() :

function [y] = fonction(x)
    y = x.*x + 5*sin(x);
endfunction


function [f, g, ind] = cout(x, ind)
    f = fonction(x);
    g = numderivative(fonction, x);
endfunction

n = 40;
x = linspace(-2*%pi, 2*%pi, n);
y = cout(x);

x0 = 0;

[fopt, xopt] = optim(cout, x0);

plot(x, y);
plot(xopt, fopt, "k+");

Optimisation linéaire

modifier

La fonction ƒ est une application linéaire ; elle peut donc s'écrire :

 

c est un vecteur de   et ct est sa transposée. On peut par ailleurs restreindre le domaine de recherche à un polyèdre convexe décrit par m inéquations :

 

  • A est une matrice m×n ;
  • b est un vecteur de m dimensions.

Scilab dispose de la commande karmarkar() qui permet de résoudre le problème avec l'algorithme de Karmarkar.

La syntaxe la plus simple permet de résoudre le problème sur la frontière du polyèdre, donc avec des égalités partout :

xopt = karmarkar(Ae, be, c)

résout

 

Exemple

Si l'on veut minimiser la fonction ƒ(x1, x2, x3) = –x1x2 avec pour contraintes x1x2 = 0 et x1 + x2 + x2 = 2, on a :

 
 

La solution s'obtient donc par

Aeq = [1, -1, 0 ; 1, 1,1];
beq = [0 ; 2];
c = [-1 ; -1 ; 0];
xopt = karmarkar(Aeq, beq, c)

et le résultat est :

xopt  = 

   0.9999949
   0.9999949
   0.0000102

On peut y ajouter un système d'inéquations[1] :

xopt = karmarkar(Ae, be, c, [], [], [], [], [], Ai, bi)

résout

 

et si l'on n'a que des inéquations :

xopt = karmarkar([], [], c, [], [], [], [], [], Ai, bi)

résout

 

On peut indiquer un vecteur de départ x0 :

xopt = karmarkar(A, b, c, x0)
xopt = karmarkar(A, b, c, x0, [], [], [], [], Ai, bi)
xopt = karmarkar([], [], c, x0, [], [], [], [], Ai, bi)

et l'on peut demander de calculer la valeur de ƒ(xopt) :

[xopt,fopt] = karmarkar()
Voir aussi

Optimisation quadratique

modifier

Soit ƒ une fonction quadratique de n variables (xi)1 ≤ in, c'est-à-dire une combinaison linéaire de xixj. Cette fonction peut se décrire par deux matrices, Q, définie positive de dimension n×n, et p, matrice colonne de dimension n :

si l'on appelle x la matrice colonne [x1 ; x2 ; … ; xn]
ƒ(x1, …, xn) = ½txQx + tpx
tM est la transposée de la matrice M.

L'optimisation quadratique consiste à trouver le vecteur x donnant la valeur minimum de ƒ, en imposant de plus que la solution se trouve dans un espace convexe, ce qui se traduit par m contraintes linéaires : me conditions d'égalité

1 ≤ jnCijxj = bi, 1 ≤ ime

et m - me conditions d'inégalité

1 ≤ jnDijxjdi, 1 ≤ im - me

soit sous forme matricielle

C1x = b1
C2xb2

  • C1 est une matrice me×n ;
  • b1 est une matrice colonne de dimension me ;
  • C2 est une matrice (m - men ;
  • b2 est une matrice colonne de dimension (m - me).

On rassemble les matrices :

  • C = [C1 ; C2] ;
  • b = [b1 ; b2].

Pour résoudre un tel système, Scilab propose deux commandes.

La commande qpsolve, sous la forme :

[x] = qpsolve(Q, p, C, b, ci, cs, me)

utilise la fonction Fortran qpgen1.f (également appelée QP.solve.f), developpée par Berwin A. Turlach selon l'algorithme de Goldfarb/Idnani.

Les paramètres ci et cs sont des vecteurs colonne de dimension n contenant les limites inférieures et supérieures aux valeurs des xi

cixcs.

Si l'on n'impose pas de limite, on utilise des matrices vides [].

La commande qld, sous la forme :

[x, lagr] = qld(Q, p, C, b, ci, cs, me)

utilise la méthode de Powell modifiée par Schittkowski.

La variable lagr est un vecteur de multiplicateurs lagrangiens.

  1. les cinq paramètres vides [] sont des paramètres que nous ne présentons pas ici à l'exception du premier, x0 ci-dessous. Ils sont décrits dans la page d'aide : (en) « karmarkar: Solves a linear optimization problem. », sur help.scilab.org (consulté le 13 février 2017)

Résolution d'équations < > Matrices creuses