Module : Optimisation Année 2020-2021

Solution de la série de TD 3

Exercice 1 Soit la fonction objectif suivante

f (x, y) = x3 + y 3 + 3x2 − 3y 2 − 8

Sous MATLAB,
1. Introduire la fonction f (x, y) dans un chier function nommé 'f'.
2. Sur un chier script, calculer les dérivées partielles de f , en utilisant la commande
diff.
∂f (x, y)


 =0

 ∂x
3. Dans le même chier, résoudre le système en utilisant la com-

 ∂f (x, y)

 =0
∂y
mande solve et donner les points stationnaires.
4. Visualiser la fonction ainsi que les résultats, en utisant les commandes meshc,
surfc, contour.
5. Déterminer la natures des points stationnaires de la fonction f à partir de la ques-
tion précédente.

Solution.
1. Introduction de la fonction f (x, y)

function [z] = exsupp(x)

z = x3 + y 3 + 3 ∗ x2 − 3 ∗ y 2 − 8 ;
end

2. Calcul des dérivées partielles

syms x y ;
fx=di (f(x,y),x)
fy=di (f(x,y),y)

f x = 3 ∗ x2 + 6 ∗ x
f y = 3 ∗ y2 − 6 ∗ y
3. Résolution du système

1
 S=solve(fx,fy)
[S.x, S.y]

S = x : [4 × 1 sym]
y : [4 × 1 sym]
ans =
[0, 0]
[0, 2]
[−2, 0]
[−2, 2]
4. Visualisation de la fonction f (x, y)

[x,y]=meshgrid(-3 :0.1 :3) ;

gure(1)
mesh(x,y,f(x,y))
xlabel('x')
ylabel('y')
zlabel('z=f(x,y)')

gure(2)
surfc(x,y,f(x,y))
xlabel('x')
ylabel('y')
zlabel('z=f(x,y)')

gure(3)
contour(x,y,f(x,y),20)

On observe bien les points critiques (-2,0) et (0,2). On peut aussi dessiner les
courbes à diérentes hauteurs avec :

2
 gure(4)
[c, h]=contour(x,y,f(x,y),-10 :0) ;
clabel(c,h)

A partir de ces contours, on observe :

(a) Peu importe la direction d'approche du point (-2,0) les courbes de niveau aug-
mentent. Par conséquent, on trouve un maximum local en ce point.
(b) Peu importe la direction d'approche du point (0,2) les courbes de niveau dimi-
nuent. Par conséquent, on trouve un minimum local en ce point.
(c) Pour les points (0,0) et (-2,2), on observe une croissance et décroissance des
courbes de niveau selon des direction opposées. On peut dire qu'il y a deux
points selles.
Exercice 2 Le polynôme suivant
f (x) = −5x5 + 4x4 − x3 + 11x2 − 2x + 1

est une fonction unimodale sur l'intervalle I = [−0.5, 0.5].

1. Utiliser la méthode de dichotomie pour trouver le minimum de f (x) sur I avec une
incertitude inférieure à 10−5 .
2. Résoudre la question (1) en utilisant la méthode de Fibonacci.
3. Résoudre la question (1) en utilisant la méthode de la section d'or.
4. Résoudre la question (1) en utilisant l'interpolation parabolique.
Solution

function f = ex2(x)
f = −5 ∗ x5 + 4 ∗ x4 − x3 + 11 ∗ x2 − 2 ∗ x + 1 ;
end

3
1. La méthode de dichotomie
function [xs,fs,k] = dichotomous(fname,xL1,xU1,rou)
disp(' ')
disp('Program dichotomous.m')
k = 0;
xL = xL1 ;
xU = xU1 ;
I = xU - xL ;
% Perform dichotomous search
while I > rou,
x1 = 0.5*(xL + xU) ;
epsi = 0.005*I ;
xa = x1 - epsi ;
xb = x1 + epsi ;
fxa = feval(fname,xa) ;
fxb = feval(fname,xb) ;
if fxa < fxb,
xU = xb ;
elseif fxa > fxb,
xL = xa ;
else
xL = xa ;
xU = xb ;
end
I = xU - xL ;
k = k + 1;
end
xs = 0.5*(xL + xU) ;
fs = feval(fname,xs) ;
% Display results
disp('Minimum point :')
format long
xs
disp('Minimum of objective function :')
fs
format short
disp('Number of iterations :')
k

Résultat :
 [xs,fs,k] = dichotomous('ex2',-0.5,0.5,1e-5) ;
Program dichotomous.m
Minimum point :
xs = 0.091577214805933
Minimum of objective function :
fs = 0.908576939574782
Number of iterations :
k = 17

4
2. La méthode de Fibonacci

function [xs,fs,k] = bonacci(fname,xL1,xU1,n)

disp(' ')
disp('Program bonacci.m')
% Generate a Fibonacci sequence
f(1) = 1 ;
f(2) = 1 ;
for i = 1 :n-1 ;
f(i+2) = f(i) + f(i+1) ;
end
F = f(2 :n+1) ;
% Generate xa1, xb1, f(xa1), and f(xb1)
k = 1;
I1 = xU1-xL1 ;
I2 = (F(n-1)/F(n))*I1 ;
xak = xU1 - I2 ;
xbk = xL1 + I2 ;
fak = feval(fname,xak) ;
fbk = feval(fname,xbk) ;
Ik1 = I2 ;
xLk = xL1 ;
xUk = xU1 ;
% Perform Fibonacci search
while k < n-2 & xak <= xbk,
Ik2 = (F(n-k-1)/F(n-k))*Ik1 ;
if fak >= fbk,
xLk1 = xak ;
xUk1 = xUk ;
xak1 = xbk ;
xbk1 = xLk1 + Ik2 ;
fak1 = fbk ;
fbk1 = feval(fname,xbk1) ;
xw = 0.5*(xak1 + xUk1) ;
else
xLk1 = xLk ;
xUk1 = xbk ;
xak1 = xUk1 - Ik2 ;
xbk1 = xak ;
fbk1 = fak ;
fak1 = feval(fname,xak1) ;
xw = 0.5*(xLk1 + xbk1) ;
end
xLk = xLk1 ;
xUk = xUk1 ;
xak = xak1 ;
xbk = xbk1 ;
fak = fak1 ;
fbk = fbk1 ;

5
 Ik1 = Ik2 ;
k = k + 1;
end
xs = 0.5*(xLk + xUk) ;
fs = feval(fname,xs) ;
% Display results
format long
disp('Minimum point :')
xs
disp('Minimum value of objective function :')
fs
format short
disp('Number of iterations performed :')
k

Résultat :
 [xs,fs,k] = bonacci('ex2',-0.5,0.5,30) ;
Program bonacci.m
Minimum point :
xs = 0.091573823656342
Minimum of objective function :
fs = 0.908576939464953
Number of iterations :
k = 28
3. La méthode de la section d'or
function [xs,fs,k] = golden_sect(fname,xL1,xU1,rou)
disp(' ')
disp('Program golden.sect.m')
% Generate xa1, xb1, f(xa1), and f(xb1)
K = 0.5*(1+sqrt(5)) ;
k = 1;
I1 = xU1 - xL1 ;
I2 = I1/K ;
xak = xU1 - I2 ;
xbk = xL1 + I2 ;
fak = feval(fname,xak) ;
fbk = feval(fname,xbk) ;
Ik1 = I2 ;
xLk = xL1 ;
xUk = xU1 ;
% Perform Golden-Section search
while Ik1 >= rou & xak <= xbk,
Ik2 = Ik1/K ;
if fak >= fbk,
xLk1 = xak ;
xUk1 = xUk ;
xak1 = xbk ;

6
 xbk1 = xLk1 + Ik2 ;
fak1 = fbk ;
fbk1 = feval(fname,xbk1) ;
xw = 0.5*(xak1 + xUk1) ;
else
xLk1 = xLk ;
xUk1 = xbk ;
xak1 = xUk1 - Ik2 ;
xbk1 = xak ;
fbk1 = fak ;
fak1 = feval(fname,xak1) ;
xw = 0.5*(xLk1 + xbk1) ;
end
xLk = xLk1 ;
xUk = xUk1 ;
xak = xak1 ;
xbk = xbk1 ;
fak = fak1 ;
fbk = fbk1 ;
Ik1 = Ik2 ;
k = k + 1;
end
% Display results
format long
disp('Minimum point :')
xs = xw
disp('Minimum value of objective function :')
fs = feval(fname,xw)
format short
disp('Number of iterations performed :')
k

Résultat :
 [xs,fs,k] =golden_sect('ex2',-0.5,0.5,1e-5) ;
Program golden.sect.m
Minimum point :
xs = 0.091570111659837
Minimum of objective function :
fs = 0.908576939631818
Number of iterations :
k = 24
4. La méthode de l'interpolation parabolique (quadratique)
function [xs,fs,k] = quad_inter(fname,x1,x3,epsi)
disp(' ')
disp('Program quad_inter.m')
x0bar = 1e99 ;
% Perform the rst iteration

7
x2 = 0.5*(x1 + x3) ;
f1 = feval(fname,x1) ;
f2 = feval(fname,x2) ;
f3 = feval(fname,x3) ;
z1 = (x2 - x3)*f1 ;
z2 = (x3 - x1)*f2 ;
z3 = (x1 - x2)*f3 ;
z4 = (x2 + x3)*z1+(x3 + x1)*z2+(x1 + x2)*z3 ;
xbar = z4/(2*(z1 + z2 + z3)) ;
fbar = feval(fname,xbar) ;
d = abs(x0bar - xbar) ;
k = 1;
% Perform quadratic interpolation based search
while d >= epsi,
if x1 < xbar & xbar < x2,
if fbar <= f2,
x3 = x2 ;
f3 = f2 ;
x2 = xbar ;
f2 = fbar ;
else
x1 = xbar ;
f1 = fbar ;
end
elseif x2 < xbar & xbar < x3,
if fbar <= f2,
x1 = x2 ;
f1 = f2 ;
x2 = xbar ;
f2 = fbar ;
else
x3 = xbar ;
f3 = fbar ;
end
end
x0bar=xbar ;
z1 = (x2 - x3)*f1 ;
z2 = (x3 - x1)*f2 ;
z3 = (x1 - x2)*f3 ;
z4 = (x2 + x3)*z1 + (x3 + x1)*z2 + (x1 + x2)*z3 ;
xbar = z4/(2*(z1 + z2 + z3)) ;
fbar = feval(fname,xbar) ;
d = abs(x0bar - xbar) ;
k = k+1 ;
end
% Display results
format long
disp('Minimum point :')
xs = xbar

8
 disp('Minimum value of objective function :')
fs = feval(fname,xbar)
format short
disp('Number of iterations performed :')
k

Résultat :
 [xs,fs,k] =quad_inter('ex2',-0.5,0.5,1e-5) ;
Program quad_inter.m
Minimum point :
xs = 0.091574134072784
Minimum of objective function :
fs = 0.908576939464594
Number of iterations :
k=4
5. Vérication avec la commande fmnibnd
clear all, close all, clc
x=-0.5 :.001 :0.5 ;
min=fminbnd('ex2',-0.5,0.5,optimset('Display','iter'))
gure(1)
plot(x,ex2(x))
hold on
plot(min,ex2(min),'r*') ;
grid on

Résultat.
Optimization terminated : the current x satises the termination criteria using
OPTIONS.TolX of 1.000000e-04
min = 0.0916

9
 Func-count x f(x) Procedure
1 -0.118034 1.39186 initial
2 0.118034 0.916202 golden
3 0.263932 1.23302 golden
4 0.0919197 0.908578 parabolic
5 0.0916188 0.908577 parabolic
6 0.0915741 0.908577 parabolic
7 0.0915407 0.908577 parabolic

Méthode min f(min) Nbre d'itérations

Dichotomie 0.0915772 0.908576 17
Fibonacci 0.0915738 0.908576 28
Section d'or 0.0915701 0.908576 24
Interpolation quadratique 0.0915741 0.908576 4
fminbnd 0.0915407 0.908577 7
Table 1  Tableau récapitulatif
Exercice 3 Le polynôme suivant
f (x) = [ln(x − 2)]2 + [ln(10 − x)]2 − x0.2
est une fonction unimodale sur l'intervalle I = [6, 9.9]. Répéter les questions de l'exercice
2.
Solution

function f = ex3(x)
f = [ln(x − 2)]2 + [ln(10 − x)]2 − x0.2 ;
end

1. La méthode de dichotomie
Résultat :
 [xs,fs,k] = dichotomous('ex3',6,9.9,1e-5) ;
Program dichotomous.m
Minimum point :
xs = 8.501585880271733
Minimum of objective function :
fs = 2.133838341661793
Number of iterations :
k = 19
2. La méthode de Fibonacci
Résultat :
 [xs,fs,k] = bonacci('ex3',6,9.9,30) ;
Program bonacci.m
Minimum point :
xs = 8.501589095492802
Minimum of objective function :
fs = 2.133838341663351
Number of iterations :
k = 28

10
3. La méthode de la section d'or
Résultat :
 [xs,fs,k] =golden_sect('ex3',6,9.9,1e-5) ;
Program golden.sect.m
Minimum point :
xs = 8.501589098477894
Minimum of objective function :
fs = 2.133838341663354
Number of iterations :
k = 27
4. La méthode de l'interpolation parabolique (quadratique)
Résultat :
 [xs,fs,k] =quad_inter('ex3',6,9.9,1e-5) ;
Program quad_inter.m
Minimum point :
xs = 8.501422361780906
Minimum of objective function :
fs = 2.133838348297733
Number of iterations :
k = 147
5. Vérication avec la commande fmnibnd
clear all, close all, clc
x=-0.5 :.001 :0.5 ;
min=fminbnd('ex3',6,9.9,optimset('Display','iter'))
gure(1)
plot(x,ex3(x))
hold on
plot(min,ex3(min),'r*') ;
grid on

11
 Func-count x f(x) Procedure
1 7.48967 2.25106 initial
2 8.41033 2.13573 golden
3 8.97933 2.22435 golden
4 8.28201 2.1437 parabolic
5 8.44552 2.13458 parabolic
6 8.64942 2.14 golden
7 8.49402 2.13385 parabolic
8 8.50446 2.13384 parabolic
9 8.50169 2.13384 parabolic
10 8.50158 2.13384 parabolic
11 8.50161 2.13384 parabolic
12 8.50154 2.13384 parabolic

Résultat.
Optimization terminated : the current x satises the termination criteria using
OPTIONS.TolX of 1.000000e-04
min = 8.5016

Méthode min f(min) Nbre d'itérations

Dichotomie 8.50158 2.13383 19
Fibonacci 8.50158 2.13383 28
Section d'or 8.50158 2.13383 27
Interpolation quadratique 8.50142 2.13383 147
fminbnd 8.50154 2.13384 12
Table 2  Tableau récapitulatif
Exercice 4 Le polynôme suivant
f (x) = −3x sin(0.75x) + e−2x
est une fonction unimodale sur l'intervalle I = [0, 2π]. Répéter les questions de l'exercice
2.
Solution

function f = ex3(x)
f = −3 ∗ x sin(0.75 ∗ x) + exp(−2 ∗ x) ;
end

1. La méthode de dichotomie
Résultat :
 [xs,fs,k] = dichotomous('ex4',0,2*pi,1e-5) ;
Program dichotomous.m
Minimum point :
xs = 2.706477229782301
Minimum of objective function :
fs = -7.274357970065606
Number of iterations :
k = 20

12
2. La méthode de Fibonacci
Résultat :
 [xs,fs,k] = bonacci('ex4',0,2*pi,30) ;
Program bonacci.m
Minimum point :
xs = 2.706473335404749
Minimum of objective function :
fs = -7.274357970058500
Number of iterations :
k = 28
3. La méthode de la section d'or
Résultat :
 [xs,fs,k] =golden_sect('ex4',0,2*pi,1e-5) ;
Program golden.sect.m
Minimum point :
xs = 2.706475914806454
Minimum of objective function :
fs = -7.274357970073561
Number of iterations :
k = 28
4. La méthode de l'interpolation parabolique (quadratique)
Résultat :
 [xs,fs,k] =quad_inter('ex4',0,2*pi,1e-5) ;
Program quad_inter.m
Minimum point :
xs = 2.706475106584253
Minimum of objective function :
fs = -7.274357970073213
Number of iterations :
k=9
5. Vérication avec la commande fmnibnd
clear all, close all, clc
x=0 :.001 :2*pi ;
min=fminbnd('ex4',0,2*pi,optimset('Display','iter'))
gure(1)
plot(x,ex4(x))
hold on
plot(min,ex4(min),'r*') ;
grid on

Résultat.
Optimization terminated : the current x satises the termination criteria using
OPTIONS.TolX of 1.000000e-04
min = 2.7065

13
 Func-count x f(x) Procedure
1 2.39996 -7.00341 initial
2 3.88322 -2.64609 golden
3 1.48326 -3.939 golden
4 2.58031 -7.22681 parabolic
5 2.81305 -7.2391 parabolic
6 3.22182 -6.40957 golden
7 2.70588 -7.27436 parabolic
8 2.70537 -7.27435 parabolic
9 2.70646 -7.27436 parabolic
10 2.7065 -7.27436 parabolic
11 2.70643 -7.27436 parabolic

Méthode min f(min) Nbre d'itérations

Dichotomie 2.70647 -7.27435 20
Fibonacci 2.70647 -7.27435 28
Section d'or 2.70647 -7.27435 28
Interpolation quadratique 2.70647 -7.27435 9
fminbnd 2.70643 -7.27436 11
Table 3  Tableau récapitulatif

Exercice 5 Les valeurs d'une fonction f (x) au points x = x1 et x = x2 sont f1 et f2

respectivement, et la dérivée de f (x) au point x1 est f10 . Montrer que

f10 (x2 − x1 )2
x̄ = x1 +
2 [f1 − f2 + f10 (x2 − x1 )]

est une estimée du minimiseur de f (x).

Application. Trouver sous matlab l'estimé du minimun de la fonction f (x) = e −x
x 3

sur l'intervalle [−1, 0].

14
 Solution
Nous avons, f (x1 ) = f1 , f (x2 ) = f2 et f 0 (x1 ) = f10 .
Tout d'abord, on approxime f (x) par un polynôme du second ordre P (x) = a0 + a1 x +
a2 x . Et nous avons :
2


 a0 + a1 x1 + a2 x21 = f1 · · · (1)
a0 + a1 x2 + a2 x22 = f2 · · · (2)
a1 + 2a2 x1 = f10 ··· (3)


On va soustraire l'équation (2) de l'équation (1), on obtient :

f1 − f2 = a1 (x1 − x2 ) + a2 (x21 − x22 ) · · · (4)

de (3), on a :
a1 = f10 − 2a2 x1 · · · (5)
On remplace l'expression de a1 dans l'équation (4) :

f1 − f2 = (f10 − 2a2 x1 )(x1 − x2 ) + a2 (x21 − x22 ) = f10 (x1 − x2 ) − a2 (x1 − x2 )2

Ainsi
f10 (x1 − x2 ) − (f1 − f2 )
a2 =
(x1 − x2 )2
En remplaçant l'expression de a2 dans l'équation (5), on trouve :
−f10 (x21 − x22 ) + 2(f1 − f2 )x1
a1 =
(x1 − x2 )2

On a P 0 (x) = a1 + 2a2 x, et si P 0 (x) = 0 et a2 6= 0 alors le minimiseur de P (x) peut

s'écrire comme suit : a1
x̄ = −
2a2
En remplaçant les expressions de a1 et a2 dans x̄, on obtient :

f10 (x2 − x1 )2
x̄ = x1 +
2 [f1 − f2 + f10 (x2 − x1 )]
Application.
x1 = −1 ;
x2 = 0;
xbar = x1 + ((f (x1) ∗ (x2 − x1)2 )/(2 ∗ (f (x1) − f (x2) + f (x1) ∗ (x2 − x1))))

Résultat
xbar = −0.4188
ybar = 0.7313

15