 # Rosenbrock Function Minimization

0

## Introduction

In this article, we present different approaches on minimizing the Rosenbrock function, namely thru Newton, Damped Newton and Steepest Descent.

## The Rosenbrock Function

Rosenbrock’s function is given as

(1) where in this article we consider the following example:

(2) Since all the methods we will use are gradient-aware and/or Hessian-aware, then we will spend some time in computing a closed form formula of the gradient and Hessian. Let us now start with the gradient of , that is

(3) and let

(4) Also let’s compute the Hessian matrix

(5) Therefore, we can compute the four double derivatives gives

(6) ## Minimization with Numerical Methods

#### Steepest Descent

Steepest descent works as follows

(7) where is a given parameter, called \textit{step-size}. So, the iteration works as follows where are the values of at iteration .

#### Newton Method

Newton is a modified steepest descent working on Hessian’s instead as follows

(8) #### Damped Newton Method

In contrast to Newton, Damped Newton method adds a damping factor as

(9) ## MATLAB implementation

We will implement the three methods above as

function[x] =  steepdescent(f,df,x0,alpha,Niter)
x(:,1) = x0;

for n = 2:Niter
x1 = x(1,n-1);
x2 = x(2,n-1);
x(:,n) = x(:,n-1) -  alpha*df(x1,x2);
end
function[x] =  newtonmethod(f,df,H,x0,Niter)
x(:,1) = x0;

for n = 2:Niter
x1 = x(1,n-1);
x2 = x(2,n-1);
x(:,n) = x(:,n-1) -  inv(H(x1,x2))*df(x1,x2);
end
function[x] =  dampednewtonmethod(f,df,H,x0,alpha,Niter)
x(:,1) = x0;

for n = 2:Niter
x1 = x(1,n-1);
x2 = x(2,n-1);
x(:,n) = x(:,n-1) -  alpha*inv(H(x1,x2))*df(x1,x2);
end

Furthermore, we implement our main function with three different initializers to test their sensitivity to the final solution as

Niter = 3000;
f = @(x1,x2)100*(x2 - x1^2)^2 + (1-x1)^2;
df = @(x1,x2) [-400*x1*(x2 - x1^2) - 2*(1-x1); 200*(x2 - x1^2)];
H = @(x1,x2) [-400*(x2-x1^2) + 800*x1^2 + 2, -400*x1; -400*x1, 200];

% Initials
x0_1 = [-1;1];
x0_2 = [0;1];
x0_3 = [2;1];
%Steepest Descent
[x_steepest_1] =  steepdescent(f,df,x0_1,1e-3,Niter);
[x_steepest_2] =  steepdescent(f,df,x0_2,1e-3,Niter);
[x_steepest_3] =  steepdescent(f,df,x0_3,1e-3,Niter);
% Newton
[x_newton_1] =  newtonmethod(f,df,H,x0_1,Niter);
[x_newton_2] =  newtonmethod(f,df,H,x0_2,Niter);
[x_newton_3] =  newtonmethod(f,df,H,x0_3,Niter);
%Damped Newton
[x_dampednewton_1] =  dampednewtonmethod(f,df,H,x0_1,1e-2,Niter);
[x_dampednewton_2] =  dampednewtonmethod(f,df,H,x0_2,1e-2,Niter);
[x_dampednewton_3] =  dampednewtonmethod(f,df,H,x0_3,1e-2,Niter);

%plot
figure
subplot(3,1,1)
plot(x_steepest_1(1,:),'r','Linewidth',2)
hold on
plot(x_steepest_2(1,:),'g','Linewidth',2)
plot(x_steepest_3(1,:),'b','Linewidth',2)

plot(x_steepest_1(2,:),'--r','Linewidth',2)
plot(x_steepest_2(2,:),'--g','Linewidth',2)
plot(x_steepest_3(2,:),'--b','Linewidth',2)

xlabel('Iteration number n')
ylabel('x')
legend('x1 path initializing x0 = [-1 1]','x1 path initializing x0 = [0 1]','x1 path initializing x0 = [2 1]','x2 path initializing x0 = [-1 1]','x2 path initializing x0 = [0 1]','x2 path initializing x0 = [2 1]')
title('Steepest descent with step size 10^{-3}')
grid on
grid minor

subplot(3,1,2)
plot(x_newton_1(1,:),'r','Linewidth',2)
hold on
plot(x_newton_2(1,:),'g','Linewidth',2)
plot(x_newton_3(1,:),'b','Linewidth',2)

plot(x_newton_1(2,:),'--r','Linewidth',2)
plot(x_newton_2(2,:),'--g','Linewidth',2)
plot(x_newton_3(2,:),'--b','Linewidth',2)

xlabel('Iteration number n')
ylabel('x')
legend('x1 path initializing x0 = [-1 1]','x1 path initializing x0 = [0 1]','x1 path initializing x0 = [2 1]','x2 path initializing x0 = [-1 1]','x2 path initializing x0 = [0 1]','x2 path initializing x0 = [2 1]')
title('Newton method')
grid on
grid minor

subplot(3,1,3)
plot(x_dampednewton_1(1,:),'r','Linewidth',2)
hold on
plot(x_dampednewton_2(1,:),'g','Linewidth',2)
plot(x_dampednewton_3(1,:),'b','Linewidth',2)

plot(x_dampednewton_1(2,:),'--r','Linewidth',2)
plot(x_dampednewton_2(2,:),'--g','Linewidth',2)
plot(x_dampednewton_3(2,:),'--b','Linewidth',2)

xlabel('Iteration number n')
ylabel('x')
legend('x1 path initializing x0 = [-1 1]','x1 path initializing x0 = [0 1]','x1 path initializing x0 = [2 1]','x2 path initializing x0 = [-1 1]','x2 path initializing x0 = [0 1]','x2 path initializing x0 = [2 1]')
title('Newton method with damping factor 10^{-2} ')
grid on
grid minor

which gives us the plot below