Steepest Descent (Unconstrained Optimization)

Unconstrained Optimization

Steepest Descent

기본적인 방법은 gradient 를 이용하는 steepest descent 방법이다. 즉, \(p_k := -\nabla f(x_k)\) 이다.

Corollary Let \(f:\mathbb{R}^n \rightarrow \mathbb{R}\) be continuously differentiable, and let \(\nabla f\) be locally Lipschitz at \(x_k\) with Lipschitz constant \(L(x_k)\). Then the generic minimization algorithm with backtracking Armijo line search and steepest descent search direction leads to one of the following results:

1. \(\nabla f(x_k) = 0\) for some \(k\geq 0\).

2. \(\lim_{k\rightarrow 0} f(x_k) = −\infty\).

3. \(\lim_{k \rightarrow \infty} \nabla f(x_k) = 0\).

Proof

아래는 Armijo line search and steepest descent direction 알고리즘 의 MATLAB 코드이다.

function [x,xk]=SteepestDescent(f,fp,x0,tol,maxiter,tau,be,alinit)
% STEEPESTDESCENT steepest descent min. search with Armijo line search
% [x,xk]=SteepestDescent(f,fp,x0,tol,maxiter,tau,be,alinit) finds an
% approximate minimum of the function f with gradient fp, starting
% at the initial guess x0. The remaining parameters are optional and
% default values are used if they are omited. xk contains all the
% iterates of the method.

if nargin<8, alinit=1; end;
if nargin<7, be=0.1; end;
if nargin<6, tau=0.5; end;
if nargin<5, maxiter=100; end; if nargin<4, tol=1e-6; end;

x=x0;
xk=x0;
p=-feval(fp,x);
k=0;

while norm(p)>tol & k<maxiter
al=alinit;
  while feval(f,x+al*p)>feval(f,x)-al*be*p’*p
    al=tau*al;
  end;
x=x+al*p
p=-feval(fp,x);
k=k+1;
xk(:,k+1)=x;
end;

Example \(f(x, y) = 10(y − x^2)^2 + (1 − x)^2\)의 최소값을 위의 MATLAB 코드를 이용하여 구해보자.

>> f=@(x) 10*(x(2)-x(1)^2)^2+(x(1)-1)^2;
>> fp=@(x) [-40*(x(2)-x(1)^2)*x(1)+2*(x(1)-1); 20*(x(2)-x(1)^2)];
>> [x,xk]=SteepestDescent(f,fp,[-1.2;1])
>> F=@(x,y) 10*(y-x.^2).^2+(x-1).^2;
>> Fp1=@(x,y) -40*(y-x.^2).*x+2*(x-1);
>> Fp2=@(x,y) 20*(y-x.^2);
>> [X,Y]=meshgrid(-1.5:0.1:1,-0.5:0.1:1.5);
>> contour(X,Y,F(X,Y),50)
>> hold on
>> quiver(X,Y,Fp1(X,Y),Fp2(X,Y),5)
>> plot(xk(1,:),xk(2,:),'-o')
>> hold off

실행화면

via GIPHY