Line search methods (Unconstrained Optimization)

Unconstrained Optimization

Line Search Methods

Line search method는 다음식에 의해 수열 \(x_k\)를 생성한다.

\[ x_{k+1} = x_k + \alpha_k p_k \]

여기서, \(p_k\)는 search direction, 스칼라 \(\alpha_k\)는 step length 이다.

일반적으로 \(p_k^{T} \nabla f(x_k)<0\)가 descent direction을 보장한다.

Step length 결정을 위한 첫번째 아이디어는,

\[ \frac{d}{d\alpha}f(x_k+\alpha p_k)=p_k^{T} \nabla f(x_k+\alpha p_k)=0\]

Example \(f(x)=x^2\)의 최소값을 시작점 \(x_0=2\)에서 구해보자. 만약 descent direction \(p_k=(-1)^{k+1}\), step length \(\alpha_k=2+\cfrac{3}{2^{k+1}}\) 로 MATLAB을 이용하여 아래 코드로 계산해 본다. 계산 결과는 아래 그림과 같다.

x(1)=2;
for k=1:10
    x(k+1)=x(k)+(2+3/(2^k))*(-1)^k;
end
xx=-2.2:0.1:2.2;
plot(xx,xx.^2,'-',x,x.^2,'-o');
xlabel('x');
legend('iterates','sqr(x)');

via GIPHY

Step length가 너무 크기 때문에, 두점을 순환하는 결과를 보여주고 있다.

Example \(f(x)=x^2\)의 최소값을 시작점 \(x_0=2\)에서 구해보자. 만약 descent direction \(p_k=-1\), step length \(\alpha_k=\cfrac{1}{2^{k+1}}\) 로 MATLAB을 이용하여 아래 코드로 계산해 본다. 계산 결과는 아래 그림과 같다.

x(1)=2;
for k=1:10
    x(k+1)=x(k)-1/(2^k);
end
xx=-2.2:0.1:2.2;
plot(xx,xx.^2,'-',x,x.^2,'-o');
xlabel('x');
legend('iterates','sqr(x)');

via GIPHY

이번에는 Stpe length가 너무 작기 때문에 실패하였다.