Newton Search Direction (Unconstrained Optimization)

Unconstrained Optimization

Newton Search Direction

좀더 좋은 search direction 을 얻기 위해서, \(B_k\)는 어떤 symmetric positive definite 행렬, search direction

\[ p_k := -B_k^{-1} \nabla f(x_k) \]

는 descent direction 이다.

왜냐하면, \(B_k\) 는 positive defined 이기 때문에 \(B_k^{-T}\) 이므로

\[ p_k^{T} \nabla f(x_k) = -(\nabla f(x_k))^T B_k^{-T} \nabla f(x_k) < 0 \]

이다. 이 search direction 함수 \(f\)의 \(x_k\) 근방에서의 quadratic approximation 을 고려하는, quadratic problem

\[ g(x_k+p):=f(x_k)+p^T \nabla f(x_k)+\cfrac{1}{2} p^T B_k p \]

의 고정점과 연결된다. 특히, 만약 \(B_k=H(x_k)\) 이면, \(x_k\)에서의 \(f\) 의 Hessian, \(g\) 는 \(f\)의 2차 Taylor approximation 이다. 이경우 search direction \(p_k := -H(x_k)^{-1} \nabla f(x_k)\) 을 Newton direction 이라 한다.

Theorem Let \(f: \mathbb{R}^n \rightarrow \mathbb{R}\) be continuously differentiable and \(\nabla f\) be Lipschitz in \(\mathbb{R}^n\). Suppose the generic minimization algorithm with the back tracking Armijo line search is used with descent direction \(p_k = −B_k \nabla f(x_k)\), where the \(B_k\) are symmetric positive definite matrices with \(\lambda_{\max} (B_k) \leq \lambda_{\max} < \infty\) and \(\lambda_{\min} (B_k) \geq \lambda_{\min} > 0\) for all \(k\). Then the iterates \(x_k\) satisfy one of the following statements:

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

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

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

Proof

아래는 Armijo backtracking line search using the Newton search direction 의 MATLAB 코드이다.

function [x,xk]=Newton(f,fp,fpp,x0,tol,maxiter,tau,be,alinit)
% NEWTON Minimization with Newton descent and Armijo line search
% [x,xk]=Newton(f,fp,fpp,x0,tol,maxiter,tau,be,alinit) finds an
% approximate minimum of the function f with gradient fp and Hessian
% fpp, 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<9, alinit=1; end;
if nargin<8, be=0.1; end;
if nargin<7, tau=0.5; end;
if nargin<6, maxiter=100; end;
if nargin<5, tol=1e-6; end;

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

while norm(feval(fp,x))>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(fpp,x)\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)];
>> fpp=@(x) [80*x(1)^2-40*(x(2)-x(1)^2)+2, -40*x(1); -40*x(1), 20];
>> [x,xk]=Newton(f,fp,fpp,[-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
>> axis([-1.5 1 -0.5 1.5])
>> quiver(X,Y,Fp1(X,Y),Fp2(X,Y),5)
>> plot(xk(1,:),xk(2,:),'-o')
>> hold off