# Something is wrong in my line search gradient descent code. It gets stuck!

6 views (last 30 days)
Cantor Set on 29 Dec 2018
Answered: John D'Errico on 30 Dec 2018
x0=[10 5]';
x0=[10 5]';
tol=1e-6;
syms x y
f= (1/2)*(x^2)+(9/2)*(y^2);
g0=subs(g, x, x0(1,1));
g0=subs(g, y, x0(2,1));
while norm(g0)>tol
s0=-g0;
%perform a linesearch to find an acceptable step size
alpha=1/2;
L0=1;
f0=subs(f,x, x0(1,1));
f0=subs(f0,y,x0(2,1));
v=f0;
xnew=x0+L0*s0;
f1=subs(f,x, xnew(1,1));
f1=subs(f,y,xnew(2,1));
u=f1;
w=alpha*L0*g0'*s0;
while u > v+w
L0=L0/2;
end
L0;
x0=x0+L0*s0;
end
double(x0)
When I try to run the script it gets stuck I guess, it returns the output

John D'Errico on 30 Dec 2018
The immediate answer is to learn to use the debugger!
For example, I ran your code. When I stepped down therough the code, I noticed that you write:
g0=subs(g, x, x0(1,1));
g0=subs(g, y, x0(2,1));
So, what is g0?
g0
g0 =
x
45
So you differentiated wrt x, then substituted in x0(1,1), but then did not save that result. So g0 is still a function of x. You would have done better to be more careful. For example:
g0=subs(g, x, x0(1,1));
g0=subs(g0, y, x0(2,1));
g0
g0 =
10
45
You made a similar mistake further down in your code with f1. Regardless, those are minor problems in context. Even if I fix them, you still have major problems.
The real problem however, is this while loop:
while u > v+w
L0=L0/2;
end
What does it do? It compares u to v+w.
u
u =
7200
>> v + w
ans =
-900
I have no real idea what those variables are (not without getting a massive headache, trying to decipher your code) but here we see that u > v+w.
So then it decreases the value of L0, continuously dividing it by 2. But it NEVER changes u or v or w in that loop!!!!!!
So your while loop runs forever.