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

x0=[10 5]';

x0=[10 5]';
tol=1e-6;
syms x y
f= (1/2)*(x^2)+(9/2)*(y^2);
g=gradient(f, [x, y]);
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

Answer 1

[John D'Errico]

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:

g=gradient(f, [x, y]);
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:

g=gradient(f, [x, y]);
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.