# Découvrir Scilab/Optimisation d'une fonction

Table des matières — Index
Optimisation d'une fonction
Soit une fonction ƒ de $\mathbb {R} ^{n}\to \mathbb {R}$. 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 optim :
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 forme function [f, g, ind] = costf(x, ind) où 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 x$_{inf}$ et x$_{sup}$ :
La fonction optim est une méthode de quasi-Newton utilisant les critères de Wolfe.
Par exemple :
Si l'on ne connaît pas de forme analytique de la fonction dérivée, on peut utiliser la fonction numderivative :

## Optimisation linéaire

La fonction ƒ est une application linéaire ; elle peut donc s'écrire :
    $f(\mathbf {x} )=\mathbf {c} ^{\mathrm {t} }\mathbf {x}$
où c est un vecteur de $\mathbb {R} ^{n}$ et c$^t$ est sa transposée. On peut par ailleurs restreindre le domaine de recherche à un polyèdre convexe décrit par m inéquations :
    $\mathrm {A} \mathbf {x} \leqslant \mathbf {b}$
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 :
résout
    ${\begin{cases}\inf _{\mathbf {x} }\mathbf {c} ^{\mathrm {t} }\mathbf {x} \\\mathrm {A_{e}} \mathbf {x} =\mathbf {b_{e}} \end{cases}}$
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 :
    ${\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}}$
    ${\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}}$
La solution s'obtient donc par
et le résultat est :
On peut y ajouter un système d'inéquations :
résout
    ${\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}}$
et si l'on n'a que des inéquations :
résout
    ${\begin{cases}\inf _{\mathbf {x} }\mathbf {c} ^{\mathrm {t} }\mathbf {x} \\\mathrm {A_{i}} \mathbf {x} \leqslant \mathbf {b_{i}} \\\end{cases}}$
On peut indiquer un vecteur de départ x$_0$ :
et l'on peut demander de calculer la valeur de ƒ(x$_{opt}$) :

### Voir aussi

* (en) Michael Baudin et coll., « Linear Programming Examples in Scilab », sur wiki.scilab.org (consulté le 13 février 2017)

## Optimisation quadratique

Soit ƒ une fonction quadratique de n variables (x$_i$)$_{1≤i≤n}$, c'est-à-dire une combinaison linéaire de x$_i$x$_j$. 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$_1$ ; x$_2$ ; … ; x$_n$]
    ƒ(x$_1$, …, x$_n$) = ½$^t$xQx + $^t$px
    où $^t$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$_e$ conditions d'égalité
    ∑$_{1≤j≤n}$C$_{ij}$x$_j$ = b$_i$, 1 ≤ i ≤ m$_e$
et m - m$_e$ conditions d'inégalité
    ∑$_{1≤j≤n}$D$_{ij}$x$_j$ ≤ d$_i$, 1 ≤ i ≤ m - m$_e$
soit sous forme matricielle
    C$_1$x = b$_1$
    C$_2$x ≤ b$_2$
où
* C$_1$ est une matrice m$_e$×n ;
* b$_1$ est une matrice colonne de dimension m$_e$ ;
* C$_2$ est une matrice (m - m$_e$)×n ;
* b$_2$ est une matrice colonne de dimension (m - m$_e$).
On rassemble les matrices :
* C = [C$_1$ ; C$_2$] ;
* b = [b$_1$ ; b$_2$].
Pour résoudre un tel système, Scilab propose deux commandes.
La commande qpsolve, sous la forme :
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 c$_i$ et c$_s$ sont des vecteurs colonne de dimension n contenant les limites inférieures et supérieures aux valeurs des x$_i$
    c$_i$ ≤ x ≤ c$_s$.
Si l'on n'impose pas de limite, on utilise des matrices vides.
La commande qld, sous la forme :
utilise la méthode de Powell modifiée par Schittkowski.
La variable lagr est un vecteur de multiplicateurs lagrangiens.

## Notes

* ↑ les cinq paramètres vides sont des paramètres que nous ne présentons pas ici à l'exception du premier, x$_0$ 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