Algorithmes de descente de gradient avec recherche linéaire de Wolfe

Bonjour,

Je cherche à utiliser un algorithme d'optimisation de descente de gradient avec recherche linéaire de Wolfe.

Pour ce faire, j'utilise un programme de recheche linéaire de Wolfe que j'ai trouvé dans la bibliothèque d'échange de mathworks.

Mon programme est réalisé de trois programmes imbriquées (1 script et 2 fonctions imbriquées):

Le premier est celui où je définis la fonction objectif appelée optimisation:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
% define the objective function:
f = @(x) 1/2*x.^2;
 
% plot the objective function for visualization:
X = -2:0.01:2;
Y = f(X);
figure(1); clf; plot(X,Y); axis equal; hold on
 
% define the gradient of the objective
gradF = @(x) x;
 
% Point de départ
x0 = 2;
 
% Optimisation avec un algorithme de descente de gradient avec recherche
% linéaire de Wolfe
 
grad_pas_wolfe(f,gradF,x0)

Le deuxième est celui permettant de déterminer le minimum de la fonction à l'aide d'un algorithme de descente de gradient avec une recherche linéaire de Wolfe appelé grad_pas_wolfe:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
function [xopt,fopt,niter,gnorm,dx] = grad_pas_wolfe(f,gradF,x0)
% grad_descent.m demonstrates how the gradient descent method can be used
% to solve a simple unconstrained optimization problem. Taking large step
% sizes can lead to algorithm instability. The variable alpha below
% specifies the fixed step size. Increasing alpha above 0.32 results in
% instability of the algorithm. An alternative approach would involve a
% variable step size determined through line search.
%
% This example was used originally for an optimization demonstration in ME
% 149, Engineering System Design Optimization, a graduate course taught at
% Tufts University in the Mechanical Engineering Department. A
% corresponding video is available at:
% 
% http://www.youtube.com/watch?v=cY1YGQQbrpQ
%
% Author: James T. Allison, Assistant Professor, University of Illinois at
% Urbana-Champaign
% Date: 3/4/12
 
 
% termination tolerance on the gradient
tol = 1e-6;
 
% maximum number of allowed iterations
maxiter = 1000;
 
% minimum allowed perturbation
dxmin = 1e-6;
 
% initialize gradient norm, optimization vector, iteration counter, perturbation
x = x0;
niter = 0;
gnorm = inf;   
dx = inf;
 
 
% redefine objective function syntax for use with optimization:
% f2 = @(x) f(x(1),x(2));
 
% gradient descent algorithm:
 
while and(gnorm>=tol, and(niter <= maxiter, dx >= dxmin))
    % calculate gradient:
    g = gradF(x);
    gnorm = norm(g);
 
    % Linesearch
 
    dir=-g;
    slope0=gradF(0)'*gradF(0);
    of=f(0);
    alpha = mb_nocLineSearch(f,gradF,x,dir,slope0,of)
 
    % take step:
    xnew = x - alpha*g;
 
    % check step
    if ~isfinite(xnew)
        display(['Number of iterations: ' num2str(niter)])
        error('x is inf or NaN')
    end
 
    % plot current point
    plot(xnew,f(xnew),'ko-')
    refresh
 
    % update termination metrics
    niter = niter + 1;
    dx = norm(xnew-x);
    x = xnew;
 
end
xopt = x
fopt = f(xopt)
niter = niter - 1

Le 3ème programme est la fonction permettant de rechercher le pas alpha par une recherche linéaire qui vérifie les critères de Wolfe.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
function alpha = mb_nocLineSearch(f,gradF,x,dir,slope0,of)
 
% implementation of strong wolfe line search
% 
% original c++ code by m.siggel@dkfz.de
% import to matlab by m.bangert@dkfz.de
% reference: nocedal: numerical optimization 3.4 line search methods
%
% f       - function handle of objective function
% gradF   - function handle of gradient
% x       - current iterate
% dir     - search direction
% slope0  - gradient of function at x in direction dir
% alphaLo - alpha at lower objective function value for zoom
% alphaHi - alpha at higher objectvie function value for zoom
% of_0
% oflo
 
% parameter for sufficient decrease condition
c1 = 0.001;
% parameter for curvature condition
c2 = 0.1;
 
if c1 > c2
    error('c1 > c2\n');
end
 
alphaMax = 100;
alpha    = 1;
 
alpha_0  = 0;
alpha_1  = alpha;
 
of_x = of;
of_0 = of;
iter = 0;
 
while 1
 
    xc     = x+alpha_1*dir;
    of     = f(xc);
    slopec = gradF(xc)'*dir;
 
    % check if current iterate violates sufficient decrease
    if  (of > of_0 + slope0*c1*alpha_1) || ((of >= of_x ) && (iter > 0))
        % there has to be an acceptable point between alpha_0 and alpha_1
        % (because c1 > c2)
        alpha = nocZoom(f,gradF,x,dir,slope0, alpha_0, alpha_1,of_0,of_x ,c1,c2);
        break;
    end
    % current iterate has sufficient decrease, but are we too close?
    if(abs(slopec) <= -c2*slope0)
        % strong wolfe fullfilled, quit
        alpha = alpha_1;
        break;
    end
    % are we behind the minimum?
    if (slopec >= 0)
        % there has to be an acceptable point between alpha_0 and alpha_1
        alpha = nocZoom(f,gradF,x,dir,slope0,alpha_1 , alpha_0,of_0,  of,c1,c2);
        break;
    end
 
    alpha_0 = alpha_1;
    alpha_1 = min(alphaMax, alpha_1*3);
    of_x = of;
 
    iter = iter + 1;
end
 
end
 
function alpha = nocZoom(f,gradF,x,dir,slope0,alphaLo,alphaHi,of_0,ofLo,c1,c2)
% this function is only called by mb_nocLineSearch - everything else does
% not make sense!
 
while 1
 
    alpha = (alphaLo+alphaHi)/2;
    xc    = x + alpha*dir;
    of    = f(xc);
 
    if of > of_0 + c1*alpha*slope0 || of >= ofLo
        % if we do not observe sufficient decrease in point alpha, we set
        % the maximum of the feasible interval to alpha
        alphaHi = alpha;       
    else
        slopec = gradF(xc)'*dir;
        % strong wolfe fullfilled?
        if abs(slopec) <= -c2*slope0
            return;
        end
        if slopec*(alphaHi-alphaLo) >= 0 % if slope positive and alphaHi > alphaLo  
            alphaHi = alphaLo;
            alphaLo = alpha;
            ofLo    = of;
        end
    end
 
end
 
end

Normalement, ce troisième est bon mais mon soucis est d'arriver à m'en servir.

PROBLEME :

Lorsque j'essaye de compiler mon code (mis à disposition ci-dessus), j'obtiens le message d'erreur suivant :

Citation:

Undefined function 'mb_nocLineSearch' for input arguments of type
'function_handle'.

Error in grad_pas_wolfe (line 52)
alpha = mb_nocLineSearch(f,gradF,x,dir,slope0,of)

Error in optimisation_gradient (line 24)
grad_pas_wolfe(f,gradF,x0)

Auriez-vous des idées pour me débloquer ?

Il me semble pourtant que mon f et gradF sont bien définis avec des handle de fonctions.

Merci d'avance pour votre aide.