I.

introduction :

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à

résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou
maximiser une fonction sur un ensemble.

L’optimisation joue un rôle important en recherche opérationnelle (domaine à la frontière entre

l'informatique, les mathématiques et l'économie), dans les mathématiques appliquées
(fondamentales pour l'industrie et l'ingénierie), en analyse et en analyse numérique, en statistique
pour l’estimation du maximum de vraisemblance d’une distribution, pour la recherche de
stratégies dans le cadre de la théorie des jeux, ou encore en théorie du contrôle et de la
commande.

Beaucoup de systèmes susceptibles d’être décrits par un modèle mathématique sont optimisés. La
qualité des résultats et des prédictions dépend de la pertinence du modèle, du bon choix des
variables que l'on cherche à optimiser, de l’efficacité de l’algorithme et des moyens pour le
traitement numérique.

1. La modalisation:

Pour décrire (et éventuellement résoudre) un problème d’optimisation nous utilisons

lamodélisation mathématique. Modéliser un problème consiste à identifier : les variables
intrinsèques (inconnues), les différentes contraintes auxquelles sont soumises ces variables,
l’objectif visé (optimisation).

2. Lien minimum/maximum :
soit f une fonction f : S →R dont on veut trouver le maximum. Le problème maxx∈S f(x) renvoit
(x0,v) alors que le problème minx∈S f(x) renvoit (x0, − v). D’où ce lien. Ainsi la recherche d’un
maximum peut toujours se ramener à la recherche d’un minimum.
1. Problématique :
Étant donnée une fonction f : S →R, un problème d’optimisation consiste à trouver :
1- son minimum v (respectivement. son maximum) dans S
2- un point x0 ∈ S qui réalise ce minimum (respectivement. maximum) i.e. f(x0) = v.
3. Appellations:
– f est la fonction objectif
– v est la valeur optimale
– x0 est la solution optimale
– S = {solutions réalisables du problème}
– écriture du problème : minx∈S f(x) resp. maxx∈S f(x)

4. Programmation linéaire:
C’est un outil générique qui peut résoudre un grand nombre de problèmes. Dans un problème de
programmation linéaire (PL) les contraintes et l’objectif sont des fonctions linéaires des
variables. On parle alors de programme linéaire. En effet, une fois un problème modélisé sous la
forme d’équations linéaires, des méthodes assurent la résolution du problème de manière exacte.
On distingue dans la programmation linéaire, la programmation linéaire en nombres réels, pour
laquelle les variables des équations sont dans IR+ et la programmation en nombres entiers, pour
laquelle les variables sont dans IN. Bien entendu, il est possible d’avoir les deux en même temps.
Cependant, la résolution d’un problème avec des variables entières est nettement plus compliquée
qu’un problème en nombres réels.

- Les problèmes d'optimisation peuvent être classés en deux grandes catégories :

Les problèmes d'optimisation continue: dans lesquels les variables peuvent
prendre des vleurs continues. Par exemple, on peut chercher à minimiser la
distance entre deux points, ou à maximiser le rendement d'une machine.
Les problèmes d'optimisation discrète: dans lesquels les variables ne
peuvent prendre que des valeurs discrètes. Par exemple, on peut chercher à
minimiser le nombre d'ingrédients nécessaires pour préparer un plat, ou à
maximiser le nombre de personnes pouvant être transportées par un véhicule. - Les méthodes
d'optimisation peuvent être classées en deux grandes catégories :
Mathworks ‘matlab’
Pour déterminent la position d’un minimum d’une fonction objectif non linéaire. Vous pouvez
rechercher un minimum d’une fonction à une seule variable dans un intervalle borné avec
fminbnd: ou un minimum d’une fonction à plusieurs variables dans un domaine non borné
avec fminsearch:. Pour maximiser une fonction, minimisez son opposée.
Pour trouver une solution non négative à un problème de moindres carrés linéaires, utilisez
lsqnonneg.
Le solveur d’équations fzero recherche un zéro réel d’une fonction scalaire non linéaire.
Contrôlez le résultat ou d’autres aspects de votre optimisation en définissant les options avec
optimset.
Résolvez des problèmes et définissez les options à l’aide d’une interface visuelle avec la tâche
Optimize du Live Editor.
Fonctions développer tout Optimiseurs
fminbnd : Find minimum of single-variable function on fixed interval
fminsearch : Find minimum of unconstrained multivariable function using derivative-free
method
Lsqnonneg : Solve nonnegative linear least-squares problem

5. Les méthodes d'optimisation linéaire:

A. La méthode de dichotomie
est une méthode d'optimisation linéaire utilisée pour trouver pour trouver le maximum local ou le
minimum local est la méthode de recherche de [Link] solution approchée à une équation
f(x) = 0. Elle fonctionne en répétant des partages d'un intervalle en deux parties, puis en
sélectionnant le sous-intervalle dans lequel existe un zéro de la fonction. Supposons que nous
voulions résoudre l'équation f(x) = 0. D'après le théorème des valeurs intermédiaires, f a au moins
un zéro dans l'intervalle [a, b].
La méthode de dichotomie consiste à diviser l'intervalle en deux en calculant
m =(a+b)/2.

B.
Gradient
Multidimensionnel :
Le gradient multidimensionnel utilise une méthode itérative pour trouver le minimum
ou le maximum d’une fonction. À chaque étape de l’itération, le gradient de la
fonction est calculé. Le gradient est un vecteur qui indique la direction de la plus forte
augmentation de la fonction. Pour trouver le minimum, le vecteur gradient est
inversé. La méthode utilise ensuite une descente de gradient, qui suit la direction du
vecteur gradient pour trouver le minimum de la fonction.
En termes simples, le gradient multidimensionnel est une méthode qui permet detrouver le
minimum ou le maximum d’une fonction à plusieurs variables. Dans l
contexte de l’apprentissage automatique, cela correspond généralement à la
recherche du minimum d’une fonction de coût qui mesure l’écart entre les sorties
prédites d’un modèle et les sorties attendues.
Par exemple pour une fonction f (x, y) :
 Le gradient est calculé comme suit :

Matrice Hessienne :

La matrice Hessienne est une matrice carrée de secondes dérivées partielles d'une
fonction de plusieurs variables. Elle est utilisée pour décrire la courbure de la fonction
en chaque point de l’espace des variables. Plus précisément, la matrice Hessienne
est une matrice symétrique qui contient les dérivées partielles croisées de la fonction.
La i-ème ligne et la j-ème colonne de la matrice Hessienne représentent la dérivée
partielle seconde de la fonction par rapport à la i-ème et j-ème variable.
La matrice Hessienne est importante dans l’optimisation car elle permet d’obtenir des
informations sur la géométrie de la fonction. En particulier, elle permet de déterminer
si la fonction est convexe ou concave, ce qui peut être utile pour trouver les minima
ou maxima globaux de la fonction. Si la matrice Hessienne est définie positive, alors
la fonction est convexe et a un minimum global. Si elle est définie négative, alors la
fonction est concave et a un maximum global. Si la matrice Hessienne n’est pas
définie positive ou négative, alors la fonction peut avoir des minima locaux et des
maxima locaux.

C. La méthode de
Newton-
Raphson :
La méthode Newton-
Raphson est un algorithme de recherche de zéro d’une fonction
réelle par approximations linéaires successives.
Introduction :
En analyse numérique, la méthode de Newton ou méthode
de Newton-Raphson est, dans son application la plus
simple, un algorithme efficace pour trouver numériquement
une approximation précise d’un zéro (ou racine)
D’une fonction réelle d’une variable réelle. Cette méthode
doit son nom aux mathématiciens anglais Isaac
Newton (1643-1727) et Joseph Raphson (peut-être 1648-
1715), qui furent les premiers à la décrire pour la recherche
des solutions d’une équation polynomiale. Thomas
Simpson (1710-1761) élargit considérablement le domaine
D’application de l’algorithme en montrant, grâce à la notion
de dérivée, comment on pouvait l’utiliser pour calculer une
solution d’une équation non linéaire, pouvant ne pas être un
polynôme, et d’un système formé de telles équations.

L’algorithme de cette méthode :

On va donc chercher à construire une bonne approximation d’un zéro de la fonction
D’une variable réelle f(x) en considérant son développement de Taylor au premier
ordre. Pour cela, partant d’un point x 0 que l’on choisit de préférence proche du zéro à
trouver (en faisant des estimations grossières par exemple), on approche la fonction
au premier ordre, autrement dit, on la considère asymptotiquement égale à
sa tangente en ce point :
Partant de là, pour trouver un zéro de cette fonction d’approximation, il suffit de
calculer l’intersection de la droite tangente avec l’axe des abscisses, c’est-à-dire
résoudre l’équation affine :

On obtient alors un point x 1 qui en général a de bonnes chances d’être plus proche
du vrai zéro de f que le point x 0 précédent. Par cette opération, on peut donc espérer
améliorer l’approximation par itérations successives: on approche à nouveau la
fonction par sa tangente en x 2 pour obtenir un nouveau point x 2 , etc .
Cette méthode requiert que la fonction possède une tangente en chacun des points
de la suite que l’on construit par itération, par exemple il suffit que f soit dérivable.
Formellement, on part d’un point x 0 appartenant à l’ensemble de définition de la
fonction et on construit par récurrence la suite où f’ désigne la dérivée de la fonction f. Le point x
k+1 est bien la solution de l’équation affine.

Il se peut que la récurrence doive se terminer, si à l’étape k, x (k) n’appartient pas au domaine de
définition ou si la dérivée f ‘x( k ) est nulle ; dans ces cas, la méthode
échoue.

Si le zéro inconnu α est isolé, alors il existe

un voisinage de α tel que pour toutes les valeurs de
départ x 0 dans ce voisinage ,
la suite x( k ) va converger vers α . De plus,
si f ‘(α) est non nul, alors la convergence est (au
moins) quadratique, ce qui signifie intuitivement
que le nombre de chiffres corrects est
approximativement doublé à chaque étape.
Bien que la méthode soit très efficace,
certains aspects pratiques doivent être pris en
compte. Avant tout, la méthode de
Newton nécessite que la dérivée soit effectivement calculée. Dans les cas où la
dérivée est seulement estimée en prenant la pente entre deux points de la fonction,
la méthode prend le nom de méthode de la sécante, moins efficace (d’ordre 1,618
qui est le nombre d’or) et inférieure à d’autres algorithmes. Par ailleurs, si la valeur
de départ est trop éloignée du vrai zéro, la méthode de Newton peut entrer en boucle
infinie sans produire d’approximation améliorée. À cause de cela, toute mise en
œuvre de la méthode de Newton doit inclure un code de contrôle du nombre
D’itérations.

D. La méthode du nombre d'or

 est une méthode d'optimisation linéaire utilisée
pour trouver une solution approchée à une équation f(x) = 0. Elle est une variante de la méthode
de dichotomie qui utilise le nombre d'or, un nombre irrationnel approximativement égal à 1,618.
La méthode du nombre d'or fonctionne de la même manière que la méthode de dichotomie, mais
elle utilise le nombre d'or pour déterminer la taille des deux parties de l'intervalle.
On calcule f (x1) et f (x2)
si f (x1) ≥ f (x2) alors le nouveau intervalle est:
Xl = X2
X2 =X1
X1 =Xl+N (Xu-Xl)
Sinon f (x2) ≥ f (x1)
Xu=X1
X1=X2
X2=Xu-N (Xu-Xl)
Xu -Xl <

 Le probleme:
Ecrire un script matlab de l’algorithme pour les quatre methode si la fonction:

Programmation en matlab :

[Link] dichotomie:
clear all;
close all;
f=@(x)cos(2*x)+sqrt(x.^2+1)
grid on
a=-4;
b=-3;
eps=0.004;
fplot(f,[a b])
i=1;
while (abs(b-a))>=eps
a=((a+b)/2)-(eps/2);
if f((a+b)/2+eps)/2>f((a+b)/2-eps/2)
x=a;
 else
b=(a+b)/2+eps/2;
x=b;
end
end
sol=x
max=[f(x)]
nmb=[i]

Solution:
sol = -3.3320
max = 4.4072
nmbriteration =28

2. Le nombre d’or:
clc;
clear all;
close all;
f=@(x)cos(2*x)+sqrt(x.^2+1);
fplot(f,[-4 -1.5])
a=-4;
b=-1.5;
eps=0.001;
i=1;
N=0.61;
while (abs(b-a))>=eps, d=N*(b-a);
x1=a+d;
x2=b-d;
if f(x1)>f(x2)
a=x2;
x2=x1;
x1=a+d;
else
b=x1;
x1=x2;
x2=a-d;
end
i=i+1
end
sol=(a+b)/2
max=f((a+b)/2)

Solution
sol = -3.3916
max = 4.4135
Nmbr iteration =17

3. Methode de newton:
clc;
clear all;
close all;
f=@(x)cos(2*x)+sqrt(x.^2+1);
fplot(f,[0 -4]);
ff=@(x)-2*sin(2*x)+x/sqrt(x.^2+1);
fff=@(x)-4*cos(2*x)+(1/sqrt(x.^2+1))-(x.^2)*((x.^2+1).^(- 3/2));
eps=0.004;
x=-3;
n=1;
for i=1:40
x1=x-(ff(x)/fff(x));
if abs (x1-x)<eps
break
end
x=x1
fprintf(' ');x1
n=n+1
end
sol=[x1]
max=[f(x)]
nombreiterqtion=[n]
Solution
Sol=-3.3917
max=4.4135
nombre iteration=3

4. La methode de gradient:
clc;
clear all;
close all;
f=@(x)cos(2*x)+sqrt(x.^2+1);
fplot(f,[-4 0]);
ff=@(x)-2*sin(2*x)+x/sqrt(x.^2+1);
C=0.01;
x=-3.4;
for i=1/20
x1=x-C*ff(x);
if abs (x1 -x)<eps
break
end
x=x1
end
sol=[x]
max=[f(x)]

Solution
sol = -3.4003
max = 4.4134
nombre iteration=1
Conclusion:

objectif de ces séances du TP passe au cours de ce semestre était de voir les différent
méthodes ;optimisation ainsi de les écrire en programme en langage Fortran .

Donc pour résumé objectif de optimisation est de trouver la solution qui satisfait toutes les contraintes et
minimise ou maximise la fonction objective. Cette solution est appelée la solution optimale. Les
applications de loptimisation sont très diverses, allant de lingénierie, la finance, la gestion de production,
la logistique, la planification des réseaux, à lapprentissage automatique et l’intelligence artificielle.