|
175. 325. 700.
</source>
== Optimisation d'une fonction ==
Soit une fonction ƒ de <math>\mathbb{R}^n \to \mathbb{R}</math>. L'optimisation consiste à trouver le vecteur '''x''' (vecteur à ''n'' composantes) donnant la valeur minimale de ƒ.
=== Optimisation linéaire ===
La fonction ƒ est une application linéaire ; elle peut donc s'écrire :
: <math>f(\mathbf{x}) = \mathbf{c}^\mathrm{t} \mathbf{x}</math>
où '''c''' est un vecteur de <math>\mathbb{R}^n</math> et '''c'''<sup>t</sup> est sa transposée. On peut par ailleurs restreindre le domaine de recherche à un polyèdre convexe décrit par ''m'' inéquations :
: <math>\mathrm{A} \mathbf{x} \leqslant \mathbf{b}</math>
où
* A est une matrice ''m''×''n'' ;
* '''b''' est un vecteur de ''m'' dimensions.
Scilab dispose de la commande <code>karmarkar()</code> 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 :
<source lang="scilab">
xopt = karmarkar(Ae, be, c)
</source>
résout
: <math>\begin{cases}
\inf_\mathbf{x} \mathbf{c}^\mathrm{t} \mathbf{x} \\
\mathrm{A_e} \mathbf{x} = \mathbf{b_e}
\end{cases}</math>
'''Exemple'''
Si l'on veut minimiser la fonction ƒ(''x''<sub>1</sub>, ''x''<sub>2</sub>, ''x''<sub>3</sub>) = –''x''<sub>1</sub> – ''x''<sub>2</sub> avec pour contraintes ''x''<sub>1</sub> – ''x''<sub>2</sub> = 0 et ''x''<sub>1</sub> + ''x''<sub>2</sub> + ''x''<sub>2</sub> = 2, on a :
: <math>\begin{pmatrix} -1 & -1 & 0 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = 0 \Longrightarrow \mathbf{c} = \begin{pmatrix} -1 \\ -1 \\ 0 \end{pmatrix}</math>
: <math>\begin{pmatrix} 1 & -1 & 0 \\ 1 & 1 & 1 \end{pmatrix} \cdot \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 0 \\ 2 \end{pmatrix} \Longrightarrow \mathrm{A_e} = \begin{pmatrix} 1 & -1 & 0 \\ 1 & 1 & 1 \end{pmatrix} \text{ ; } \mathbf{b_e} = \begin{pmatrix} 0 \\ 2 \end{pmatrix} </math>
La solution s'obtient donc par
<source lang="scilab">
Aeq = [1, -1, 0 ; 1, 1,1];
beq = [0 ; 2];
c = [-1 ; -1 ; 0];
xopt = karmarkar(Aeq, beq, c)
</source>
et le résultat est :
<source lang="scilab">
xopt =
0.9999949
0.9999949
0.0000102
</source>
On peut y ajouter un système d'inéquations<ref>les cinq paramètres vides <code>[]</code> sont des paramètres que nous ne présentons pas ici à l'exception du premier, '''x<sub>0</sub>''' ci-dessous. Ils sont décrits dans la page d'aide : {{lien web | url = https://help.scilab.org/docs/6.0.0/fr_FR/karmarkar.html | titre = karmarkar: Solves a linear optimization problem. | langue = en | site = help.scilab.org | consulté le = 2017-02-13}}</ref> :
<source lang="scilab">
xopt = karmarkar(Ae, be, c, [], [], [], [], [], Ai, bi)
</source>
résout
: <math>\begin{cases}
\inf_\mathbf{x} \mathbf{c}^\mathrm{t} \mathbf{x} \\
\mathrm{A_e} \mathbf{x} = \mathbf{b_e} \\
\mathrm{A_i} \mathbf{x} \leqslant \mathbf{b_i} \\
\end{cases}</math>
et si l'on n'a que des inéquations :
<source lang="scilab">
xopt = karmarkar([], [], c, [], [], [], [], [], Ai, bi)
</source>
résout
: <math>\begin{cases}
\inf_\mathbf{x} \mathbf{c}^\mathrm{t} \mathbf{x} \\
\mathrm{A_i} \mathbf{x} \leqslant \mathbf{b_i} \\
\end{cases}</math>
On peut indiquer un vecteur de départ '''x<sub>0</sub>''' :
<source lang="scilab">
xopt = karmarkar(A, b, c, x0)
xopt = karmarkar(A, b, c, x0, [], [], [], [], Ai, bi)
xopt = karmarkar([], [], c, x0, [], [], [], [], Ai, bi)
</source>
et l'on peut demander de calculer la valeur de ƒ('''x<sub>opt</sub>''') :
<source lang="scilab">
[xopt,fopt] = karmarkar(…)
</source>
; Voir aussi
* {{lien web | url = https://wiki.scilab.org/Linear%20Programming%20Examples%20in%20Scilab | titre = Linear Programming Examples in Scilab | langue = en | site = wiki.scilab.org | consulté le = 2017-02-13 | auteur = Michael Baudin et coll.}}
=== Optimisation non linéaire ===
Ici, la fonction ƒ de <math>\mathbb{R}^n \to \mathbb{R}</math> est non linéaire. On utilise pour cela la fonction <code>optim</code> :
<source lang="scilab">
[fopt, xopt] = optim(costf, x0)
</source>
où
* <code>costf</code> 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<br /><code>function [f, g, ind] = costf(x, ind)</code><br />où <code>f</code> désigne ƒ('''x'''), <code>g</code> est le gradient et <code>ind</code> est un index, un entier permettant de modifier le comportement de <code>costf</code> ;
* <code>x0</code> est une estimation de la solution ;
* <code>xopt</code> est le vecteur trouvé ;
* <code>fopt</code> = ƒ(<code>xopt</code>), valeur estimée du minimum.
On peut indiquer des bornes inférieures et supérieure de '''x''', sous al forme de vecteurs '''x'''<sub>inf</sub> et '''x'''<sub>sup</sub> :
<source lang="scilab">
[fopt, xopt] = optim(f, x0, "b", xinf, xsup)
</source>
La fonction <code>optim()</code> est une [[w:fr:Méthode de quasi-Newton|méthode de quasi-Newton]] utilisant les [[w:fr:Critères de Wolfe|critères de Wolfe]].
=== Optimisation quadratique ===
Soit ƒ une fonction quadratique de ''n'' variables (''x<sub>i</sub>'')<sub>1 ≤ ''i'' ≤ ''n''</sub>, c'est-à-dire une combinaison linéaire de ''x<sub>i</sub>x<sub>j</sub>''. 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 [''x''<sub>1</sub> ; ''x''<sub>2</sub> ; … ; ''x''<sub>''n''</sub>]
: ƒ(''x''<sub>1</sub>, …, ''x''<sub>''n''</sub>) = ½<sup>t</sup>'''x'''Q'''x''' + <sup>t</sup>''p''<nowiki></nowiki>'''x'''
: où <sup>t</sup>M 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 : ''m''<sub>e</sub> conditions d'égalité
: ∑<sub>1 ≤ ''j'' ≤ ''n''</sub>C<sub>''ij''</sub>''x<sub>j</sub>'' = ''b<sub>i</sub>'', 1 ≤ ''i'' ≤ ''m''<sub>e</sub>
et ''m'' - ''m''<sub>e</sub> conditions d'inégalité
: ∑<sub>1 ≤ ''j'' ≤ ''n''</sub>D<sub>''ij''</sub>''x<sub>j</sub>'' ≤ ''d<sub>i</sub>'', 1 ≤ ''i'' ≤ ''m'' - ''m''<sub>e</sub>
soit sous forme matricielle
: C<sub>1</sub>'''x''' = ''b''<sub>1</sub>
: C<sub>2</sub>'''x''' ≤ ''b''<sub>2</sub>
où
* C<sub>1</sub> est une matrice ''m''<sub>e</sub>×''n'' ;
* ''b''<sub>1</sub> est une matrice colonne de dimension ''m''<sub>e</sub> ;
* C<sub>2</sub> est une matrice (''m'' - ''m''<sub>e</sub>)×''n'' ;
* ''b''<sub>2</sub> est une matrice colonne de dimension (''m'' - ''m''<sub>e</sub>).
On rassemble les matrices :
* C = [C<sub>1</sub> ; C<sub>2</sub>] ;
* ''b'' = [''b''<sub>1</sub> ; ''b''<sub>2</sub>].
Pour résoudre un tel système, Scilab propose deux commandes.
La commande <code>qpsolve</code>, sous la forme :
<source lang="scilab">
[x] = qpsolve(Q, p, C, b, ci, cs, me)
</source>
utilise la fonction Fortran <code>qpgen1.f</code> (également appelée <code>QP.solve.f</code>), developpée par Berwin A. Turlach selon l'algorithme de Goldfarb/Idnani.
Les paramètres ''c''<sub>i</sub> et ''c''<sub>s</sub> sont des vecteurs colonne de dimension ''n'' contenant les limites inférieures et supérieures aux valeurs des ''x<sub>i</sub>''
: ''c''<sub>i</sub> ≤ '''x''' ≤ ''c''<sub>s</sub>.
Si l'on n'impose pas de limite, on utilise des matrices vides <code>[]</code>.
La commande <code>qld</code>, sous la forme :
<source lang="scilab">
[x, lagr] = qld(Q, p, C, b, ci, cs, me)
</source>
utilise la méthode de Powell modifiée par Schittkowski.
La variable ''lagr'' est un vecteur de multiplicateurs lagrangiens.
== Le problème de la précision et de l'exactitude ==
== Notes ==
{{références}}
<references />
----
''[[Découvrir Scilab/Calculs élémentaires|Calculs élémentaires]]'' < [[Découvrir Scilab|↑]] > ''[[Découvrir Scilab/GraphiquesOptimisation etd'une sonsfonction|GraphiquesOptimisation etd'une sonsfonction]]''
[[Catégorie:Découvrir Scilab (livre)|Calcul numérique]]
| 