Découvrir Scilab/Optimisation d'une fonction
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 | modifier le wikicode]L'optimisation non linéaire est le cas général. On utilise pour cela la fonction optim
:
[fopt, xopt] = optim(costf, x0)
où
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 formefunction [f, g, ind] = costf(x, ind)
oùf
désigne ƒ(x),g
est le gradient etind
est un index, un entier permettant de modifier le comportement decostf
;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 :
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 | modifier le wikicode]La fonction ƒ est une application linéaire ; elle peut donc s'écrire :
où 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 :
où
- 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) = –x1 – x2 avec pour contraintes x1 – x2 = 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
- (en) Michael Baudin et coll., « Linear Programming Examples in Scilab », sur wiki.scilab.org (consulté le 13 février 2017)
Optimisation quadratique
[modifier | modifier le wikicode]Soit ƒ une fonction quadratique de n variables (xi)1 ≤ i ≤ n, 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
- où 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 ≤ j ≤ nCijxj = bi, 1 ≤ i ≤ me
et m - me conditions d'inégalité
- ∑1 ≤ j ≤ nDijxj ≤ di, 1 ≤ i ≤ m - me
soit sous forme matricielle
- C1x = b1
- C2x ≤ b2
où
- C1 est une matrice me×n ;
- b1 est une matrice colonne de dimension me ;
- C2 est une matrice (m - me)×n ;
- 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
- ci ≤ x ≤ cs.
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.
Notes
[modifier | modifier le wikicode]- ↑ 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)