MATLAB: Steepest descent method algorithm

algorithmhomeworkmathematicsMATLAB and Simulink Student Suiteoptimization

For practice purpose, I want to find minima of -humps() function.

I have written the following code but it's not giving correct answer

clear; clc;
%function
f = @(x) -humps(x);
dx = 0.1; %step length
x_current = 1; %starting guess
delta = 1e-4; %threshold value
alpha = 0.1; %finding optimal step length
g = inf; %starting gradient
while norm(g) > delta
    
    %gradient by finite difference
    f1 = f(x_current + dx/2); 
    f2 = f(x_current - dx/2);
    g = (f1-f2)/dx;
    
    x_next = x_current-alpha*g; %new solution
    
    x_current = x_next; 
    
    fprintf('%d %d\n',x_current,x_next);
    
    x_current = x_next;
end

It give 5.543798e+01 as solution while the solution should either be 0.9 or 0.3 (local and global minimas, respectivily).

Whate am I missing here? can anyone help?

Best Answer

alpha is too big. Try alpha=0.001.

Related Solutions

MATLAB: Solving problem for gradient descent

Hi,

Following code Illustrates the working of Gradient Descent for 3 variables.

To eliminate error changes were made to:

Initial value
Maxiter value
Alpha value

function [xopt,fopt,niter,gnorm,dx] = grad_descent(varargin)
 
 
if nargin==0
    % define starting point
    x0 = [3 3 3]';  
elseif nargin==1
    % if a single input argument is provided, it is a user-defined starting
    % point.
    x0 = varargin{1};
else
    error('Incorrect number of input arguments.')
end
 
% termination tolerance
tol = 1e-6;
 
% maximum number of allowed iterations
maxiter = 100000;
 
% minimum allowed perturbation
dxmin = 1e-6;
 
% step size ( 0.33 causes instability, 0.2 quite accurate)
alpha = 0.000001;
 
% initialize gradient norm, optimization vector, iteration counter, perturbation
gnorm = inf; x = x0; niter = 0; dx = inf;
 
% define the objective function:
f = @(x1,x2,x3) 4*(x1.^2 + x2-x3).^2 +10;  
 
 
% plot objective function contours for visualization:
%figure(1); clf; contour3(f,[-5 5 -5 5 -5 5]); axis equal; hold on
 
% redefine objective function syntax for use with optimization:
f2 = @(x) f(x(1),x(2),x(3));               
 
% gradient descent algorithm:
while and(gnorm>=tol, and(niter <= maxiter, dx >= dxmin))
    % calculate gradient:
    g = grad(x);
    gnorm = norm(g);
    % 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([x(1) xnew(1)],[x(2) xnew(2)],'ko-')
    refresh
    % update termination metrics
    niter = niter + 1;
    dx = norm(xnew-x);
    x = xnew;
    
end
xopt = x;
fopt = f2(xopt);
niter = niter - 1;
 
%define the gradient of the objective
% function g = grad(x)
% g = [2*x(1) + x(2)
%     x(1) + 6*x(2)];
function g = grad(x)                   
g = 4*(x(1).^2 + x(2)-x(3)).^2 +10;

ans =

0.3667

Alternately make use of the following code for accurate result

fun = @(x) 4*(x(1).^2 + x(2)-x(3)).^2 +10;
x0 = [3,3,3];
x = fminsearch(fun,x0);

MATLAB: Function functions of fixed-point iteration

Hi,

You were almost there and just overlooked at one point with: g=diff(fun); that requires symbolic differentiaion w.r.t the variable x. Another very minor point is output variable name t that was assigned but not given any output value within F.m. I have chosen phi_of_x_at_x_current that can be changed to any output calc's from F.m

Here is the corrected codes. Note that I have done some name changes not to get confused with fun and g which are substitute with FF and G. I like upper cases for the sake of visibility.

function phi_of_x_at_x_current = F(FF, x0, n)
%   Detailed explanation goes here
syms x
G=diff(FF, x);
epsilon = 5*10^-(n+1);
i=1;
rng(0,'twister');
alpha = -2/vpa(subs(G,x,x0));
x_current = x0;
while i~=200
    phi_of_x_at_x_current= x_current + (alpha*vpa(subs(FF,x,x_current)));
    err=abs(phi_of_x_at_x_current-x_current);
    if  abs(1+alpha*vpa(subs(G,x,x_current)))>=1
        alpha = -1*(2/vpa(subs(G,x,x0))*rand);
        i=1;
    elseif err<epsilon
        break
    end
    x_current =  phi_of_x_at_x_current;
    i=i+1;
end
phi_of_x_at_x_current = phi_of_x_at_x_current - rem(phi_of_x_at_x_current,10^-n);
fprintf('Answer: %f \n',phi_of_x_at_x_current);
end

clc;
close all;
clear variables
syms x
FF=@(x)-0.0641*x^3+1.0889*x^2-3.8260*x+0.6364;
n=input('Enter the number of decimal places:   ');
x0 = input('Enter the intial approximation:    ');
OUT = F(FF, x0, n);

>> Enter the number of decimal places:   3
>> Enter the intial approximation:    55
Answer: 12.188000

Good luck.

Best Answer

Related Solutions

MATLAB: Solving problem for gradient descent

MATLAB: Function functions of fixed-point iteration

Related Question