Découvrir Scilab/Optimisation d'une fonction

Optimisation d'une fonction
Soit une fonction ƒ de formula_1. L'optimisation consiste à trouver le vecteur x (vecteur à "n" composantes) donnant la valeur minimale de ƒ.
Optimisation non linéaire.
L'optimisation non linéaire est le cas général. On utilise pour cela la fonction codice_1 :
[fopt, xopt] = optim(costf, x0)
où
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 codice_12 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 codice_13 :
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.
La fonction ƒ est une application linéaire ; elle peut donc s'écrire :
où c est un vecteur de formula_3 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ù
Scilab dispose de la commande codice_14 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 ƒ("x"1, "x"2, "x"3) = –"x"1 – "x"2 avec pour contraintes "x"1 – "x"2 = 0 et "x"1 + "x"2 + "x"2 = 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 :
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(…)
Optimisation quadratique.
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" :
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 : "m"e conditions d'égalité
et "m" - "m"e conditions d'inégalité
soit sous forme matricielle
où
On rassemble les matrices :
Pour résoudre un tel système, Scilab propose deux commandes.
La commande codice_15, sous la forme :
[x] = qpsolve(Q, p, C, b, ci, cs, me)
utilise la fonction Fortran codice_16 (également appelée codice_17), developpée par Berwin A. Turlach selon l'algorithme de Goldfarb/Idnani.
Les paramètres "c"i et "c"s sont des vecteurs colonne de dimension "n" contenant les limites inférieures et supérieures aux valeurs des "xi"
Si l'on n'impose pas de limite, on utilise des matrices vides codice_18. 
La commande codice_19, 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.
"Résolution d'équations" < ↑ > "Matrices creuses"