MATLAB code not working (gradient descent algorithm)

Question

I am trying gradient descent, I wrote following however not getting any answer,

n=0;            %initialize iteration counter 
eps=1;          %initialize error 
a=0.8;         %set iteration parameter 
x=[1;1];        %set starting value
f=6*x(1)^2+8*x(2)^2-3*x(1)*x(2);
%Computation loop 
while eps>1e-12||n<100 
   gradf=[12*x(1)-3*x(2); 16*x(2)-3*x(1)];  %gradf(x) 
   eps=(norm(gradf)/(1+abs(f)));                                %error 
   y=x-a*gradf;                                                 %iterate 
   x=y;                                                         %update x 
   n=n+1;                                                       %counter+1 
end 
n;x;eps;        %display end values

When I add this file to path and type x it shows NaN, NaN. what is wrong?

It seems to me gradient method doesn't always converge for constant 'a'. Try using another. Also, if you watch your 'eps' when debuggin you'll note it increasing to NaN. — Rail Suleymanov
– Rail Suleymanov, Commented Oct 27, 2012 at 17:16

Acorbe · Accepted Answer · 2012-10-27 22:32:22Z

5

There are several errors in your code. Consider this (I put comments where corrections were needed)

 n=0;            
 eps=1;         
 a=0.1;                    %You need a way smaller parameter to converge!
 x=[1;1];       

 A = [6 -3/2 ; -3/2 8];     %You have a bilinear positive definite form,
                            %you may use matrix form for convenience


while eps>1e-12 && n<100    %You had wrong termination conditions!!
    gradf=2*A*x;            %(gradf in terms of matrix)
    f=x'*A*x;               %you need to update f every iteration!!
    eps=(norm(gradf)/(1+abs(f)))                              
    disp(eps > 1e-12)
    x=x-a*gradf;                                               

       %Now you can see the orbit  towards minimum                                     
    plot(x(1),x(2),'o'); hold on        
    n=n+1;                                                        
end 
n
x
eps

for instance with the current value a=.1 I get

n = 100
eps = 1.2308e-011

x = 
  1.0e-012 *

  -0.2509
  0.4688

That is I had to perform 100 iteration because my epsilon is still above the threshold. If I allow 200 iterations I get

n =  110
eps = 
   7.9705e-013

x = 
1.0e-013 *
  -0.1625
   0.3036

I.e. 110 iterations are sufficient.

Points get dense around the solution <code>(0,0)</code>

Case of a general f (i.e. not a quadratic form).

You can use, for instance, function handles, i.e. you define (before the while)

foo = @(x) 6*x(1)^2+8*x(2)^2-3*x(1)*x(2);
foo_x = @(x) 12*x(1)-3*x(2); 
foo_y = @(x) 16*x(2)-3*x(1);

then, in the while you substitute

gradf = [foo_x(x);foo_y(x)];
f = foo(x);

P.S. for what concerns the while cycle, please keep in mind that you keep on iterating while you are not satisfied with your precision (eps>1e-12) AND your total number of iteration is below a given threshold (n<100).

Consider also that you are working in finite precision: a numerical algorithm can never reach the analytic solution (i.e. what you have with infinite precision and infinite iterations), therefore, you always have to set a threshold (eps, which should be above the machine precision \approx1e-16) and that is your 0.

edited Oct 27, 2012 at 22:32

answered Oct 27, 2012 at 17:46

Acorbe

8,4115 gold badges43 silver badges68 bronze badges

Sign up to request clarification or add additional context in comments.

11 Comments

Nick_R Over a year ago

Thanks for your help. Regarding "a", starting with 1, I am planning to update its value for every iteration by a factor 0.8.

Acorbe Over a year ago

Well, I don't see convergence with a bigger than .1. You can look at the orbit. Btw you may consider to accept the answer.

Acorbe Over a year ago

Well, the issue with too large as is that your solution starts bouncing among large gradient zones and can't really converge. You should notice that your error estimator fails in those zone of big f .

Acorbe Over a year ago

what's wrong with the answer, now? why did you change your mind?

Nick_R Over a year ago

Sorry for the trouble. But if we inspect the function the min answer should be 0 which is not obtained. and the termination conditions are "OR" not "AND"

|

Collectives™ on Stack Overflow

MATLAB code not working (gradient descent algorithm)

1 Answer 1

11 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

11 Comments

Your Answer

Sign up or log in

Post as a guest

Related