[수학적 최적화] 경사 하강법Gradient Descent(혹은 Steepest Descent) 알아 보기 : (1) 기본 개념

지난 포스팅에서는 수학적 최적화의 한 방법인 시뮬레이션 담금질simulated anealling에 대해서 알아 보았습니다. 그리고 시뮬레이션 담금질을 활용하여 조합 최적화combinatorial optimization 문제의 대표적인 예인 외판원 문제travelling salesman problem(TSP)를 풀어 보았습니다. 

 

생각해 보니, 수학적 최적화를 공부하고 활용할 때, 거의 처음 접하면서 가장 기본적인 방법인 경사 하강법gradient descept 방법에 대해서 다루지 않았습니다. 시뮬레이션 담금질을 설명하면서, 국소 최소점, 전역 최소점 같은 명확한 설명 없이 사용하였는데 이에 대한 명확한 정의와 국소 최소점을 피하려고 하는 이유 등에 대해서 설명을 하려면 경사 하강법에 대한 이해가 필요합니다. 따라서 이번 포스팅에서는 경사 하강법에 대해서 알아 보도록 하겠습니다. 앞서 말한대로 경사 하강법은 가장 기본적인 수학적 최적화의 방법이라 구글이나 네이버 검색을 하면 수 없이 많은 글들을 확인할 수 있습니다. 영어에 익숙한 분이라면 영문 위키피디아 정도로 쉽게 찾을 수 있는 문서를 통해서도 경사 하강법을 공부할 수 있습니다. 이런 와중에도 또 하나의 경사 하강법에 대한 글을 쓰는 이유 다음과 같습니다.

 

(1) 경사 하강법이 아닌 다른 수학적 최적화 방법은 대부분 경사 하강법의 단점을 보완하기 위해 나왔습니다. 따라서 경사 하강법의 장단점과 한계를 명확히 알고 있어야 하는데, 이 포스팅을 통해서 이를 설명하기 위함이며, 또 앞에서 먼저 언급 한 것 처럼 다른 형태의 수학적 최적화를 설명하기 위해서는 경사 하강법에서 사용한 개념 활용해야 하는데, 이를 위함 입니다. 

 

(2) 구글 검색을 통해서 찾을 수 있는 한국어로 된 경사 하강법 설명 페이지는 주로 머신러닝의 활용을 기반으로 쓰여진 글이었습니다. 사실 경사 하강법은 머신러닝과는 아무런 상관이 없는 방법론 입니다. 이를 명확하게 하기 위함 입니다. 물론 최근에 머신러닝에 대한 연구와 활용이 많아 지면서 경사 하강법이 머신러닝에서 많이 활용되고는 있습니다. 머신러닝 없이도 수학적 최적화는 존재할 수 있지만, 수학적 최적화 없이는 머신러닝이 존재할 수 없습니다. 

 

수학적 최적화의 정의 다시

 

수학적 최적화의 정의는 다음과 같습니다.

정의역을 $A$로 하는 함수 $f:A\to \mathbb{R}$ 가 주어졌을 때, 임의의 $x\in A$에서 $f(x_{min})\le f(x)$를 만족하는 $x_{min}$를 찾는 방법

정의역 $A$는 별다른 제한이 없는데, 실공간 ${\mathbb{R}}^n$ 일수도 있고, 외판원 문제에서와 같이 유한한 갯수의 일반적인 집합일 수 도 있씁니다. 목적함수 $f$의 성질에도 특별한 제한이 없는데, 거의 마음대로 미적분이 가능한 해석함수analytic function  일수도 있고, 그렇지 않을 수 도 있습니다. 

 

현재까지 알려진 최소값 보다 더 작은 값을 얻는 확실한 방법

 

대부분의 (거의 모든?) 수학적 최적화 방법은 반복적인 계산iterative calcultion을 수행합니다. 이미 알아본 시뮬레이션 담금질에서도 수 차례의 반복 계산을 수행합니다. 반복 계산의 단계에서 서로 다른 N개의 $x_i,i=1,2,3,...,N$에 대한 목적 함수 $f(x_i)$를 계산하여 이에 대한 정보를 갖고 있다고 할 때, 목적함수를 몇 번 더 계산하여 지금까지 알려진 목적함수의 최소값 $\underset{i}{min}f(x_i)$ 보다 더 작은 목적함수를 얻을 수 있는 방법이 있을 까요? 물론 앞 문장에서 쓴 "몇 번" 은 더 적으면 적을 수록 좋습니다. 설명의 편의를 위해서 집합 $X,F$, 정의역 $A$의 한 원소 $x_{min,N}$, 이에 대응되는 목적함수 값 $f_{min,N}$ 를 아래와 같이 정의하도록 하겠습니다.

$$X_N=\{x_1,x_2,..,.x_N\}$$

$$F_N=\{f(x_1),f(x_2),...,f(x_N)\}$$

$$x_{min,N}=min{X}_N,f_{min,N}=min{F}_N=f(x_{min,N})$$

그 방법은 $x=x_{min,N}$에서 목적함수 $f$의 미분값, $\frac{df}{dx}(x_{min,N})=f^{\prime }(x_{min,N})$을 이용하는 것 입니다. 타이핑의 편의상 미분은 ${}^{\prime }$ 기호를 사용하여 표현하겠습니다. 앞 문장에서 별다른 설명 없이 미분값을 사용한다고 하였는데, 여기에는 사실 몇 가지 가정이 들어가 있습니다. 가장 먼저 목적함수 $f$가 미분이 된다는 것이고, 따라서 자연스럽게 정의역의 집합은 실공간으로 생각할 수 있습니다. 경사 하강법은 목적함수가 미분이 가능할 때 사용될 수 있습니다. 또한 정의역의 집합이 2차원 이상인 경우에는 미분이 아닌 편미분이나 그레이디언트를 사용해야 하는데 그냥 단순히 $x$에 대한 미분을 활용하였습니다. 이는 설명의 편의를 위한 것입니다. 만일 정의역의 차원이 늘어난다면 단순히 한 변수에 대한 미분이 아닌 그레이디언트를 사용해야 합니다. 특별한 언급이 없다면, (최소한 개념을 설명하는 부분에서는) 설명의 편의를 위해서 정의역 $A$를 실수 집합 $\mathbb{R}$로 정의하고, 목적함수가 정의역의 전 공간에서 미분가능하다고 가정하겠습니다. 

 

$x_{min,N}$에서의 미분값을 $f^{\prime }(x_{min,N})$라고 하고 $x_{min,N}$ 근처에서 $f(x)$의 테일러 전개를 하면,

$$f(x_{min,N}+\mathrm{\Delta }x)\approx f(x_{min,N})+\mathrm{\Delta }x{f}^{\prime }(x_{min,N})$$

가 됩니다. 만일 $f^{\prime }(x_{min,N})$가 양수이고, $\mathrm{\Delta }x$가 음수라면, $x_{new}=x_{min,N}+\mathrm{\Delta }x$ 라고 정의하면,

$$f(x_{new})\approx f(x_{min,N})-|\mathrm{\Delta }x||f^{\prime }(x_{min,N})|$$

로 부터, $x_{new}$에서의 목적함수 값이 지금까지의 목적함수의 최소값이였던 $x_{min,N}$에서의 목적함수 값 보다 $|\mathrm{\Delta }x||f^{\prime }(x_{min,N})|$ 만큼 작게 됩니다! 만일 $f^{\prime }(x_{min,N})$가 음수라면, $\mathrm{\Delta }x$를 양수로 선택하면 됩니다. 위 테일러 전개 근사는 $\mathrm{\Delta }x$의 1차식까지만 고려한 것 입니다. 따라서 $\mathrm{\Delta }x$가 작은 경우에 성립합니다. 

 

위 결과는 어느 정도 당연하다고 볼 수 있는데, 극대 혹은 극소점에서는 목적함수의 미분값이 0이 됩니다. 그 외의 점에서는 목적함수의 미분값은 0이 아닌 값이 됩니다. 정의로 부터 미분값이 0이 아닌 지점에서는 미분값의 반대 방향으로 $x$를 이동하면 목적함수의 값은 작아지게 됩니다. 다소 당연하지만, 목적함수를 더 낮출 수 있는 100% 명확한 방법입니다. 위와 같이 특정한 점에서 미분값을 계산하고, 미분값의 반대방향으로 $x$를 조금씩 이동시킨다면, 궁극적으로는 목적함수의 극소값에 도달할 수 있게 됩니다. 

 

경사 하강법

 

위에서 설명한 방식을 수식으로 쓰면 아래와 같습니다. 임의의 점 $x_0$에서 반복 계산을 실행한다고 할때, 

$$x_{n+1}=x_n-{\gamma }_n{f}^{\prime }(x_n)$$

와 같이  수열 $x_n$을 정의하고, ${\gamma }_n$을 적당히 설정한다면, 목적함수 $f$에 대해서 감소하는 수열

$$f(x_0)>f(x_1)>...>f(x_n)$$

을 얻게 됩니다. 목적함수의 정의역이 실수 공간이 아니라 임의의 $n$차원 유클리드 공간이라면 미분 대신에 그레이디언트가 돼야 해서,

$${\overrightarrow{x}}_{n+1}={\overrightarrow{x}}_n-{\gamma }_n\mathrm{\nabla }f({\overrightarrow{x}}_n)$$

이 됩니다. 물론 여기서 ${\gamma }_n$을 잘 잡아야 하는데, 이에 대해서는 아래에서 추가적으로 설명을 하도록 하겠습니다. 이를 계속 반복하면 얻어지는 값

$$\underset{n\to \mathrm{\infty }}{lim}f(x_n)$$

는 목적함수 $f$의 최소값이 될 가능성이 높습니다. 위 방법에 따라 목적함수의 최소값을 찾는 알고리듬을 경사 하강법이라고 합니다. 말 그대로 경사, 즉 gradient, 의 방향으로 목적함수를 "하강" 한다는 뜻 입니다. 경사 하강법은 가파른 하강법steepest descent라는 이름으로 불리기도 하는데, 그레이디언트의 방향은 함수 값을 가장 빠르게 증가 시키는 방법이기 때문입니다. 

 

"가능성이 높다"라고 한 것은 위 계산에서는 정의역 전체 집합 $A$에서의 목적함수 값을 계산한 것이 아니고, 위에서 정의한 수열 $x_n$에서의 함수값만 계산했기 때문입니다. 물론, 앞에서 설명한대로 미분의 성질에 따라서 $\underset{n\to \mathrm{\infty }}{lim}f(x_n)$ 값은 $x_n$들의 "주변"에 있는 정의역의 부분 집합의 목적함수 값 보다는 작겠지만, 정의역 전체 집합에서 구한 목적함수의 최소값 보다는 작다는 보증이 없습니다.

 

국소 최저점

 

경사 하강법에서는 미분값을 사용합니다. 특정한 점, $x_n$, 에서 미분값은 (목적)함수의 $x_n$ 근방에서의 정보만을 갖고 있습니다, 즉, $x_n$보다 조금 큰 값 $x_n+h$와 $x_n$ 보다 조금 작은 값 $x_n-h$에서의 함수값의 차이 정보를 갖고 있습니다. 또한, $x_n$은 $x_{n-1}$ 의 근방의 점이 되고, $x_{n-1}$은 역시 $x_{n-2}$의 근방이 됩니다. 즉, $x_n$은 경사 하강법을 시작한 점 $x_0$의 근방이 되기 때문에, 한 마디로 요약하면 경사 하강법은 특정한 점, $x_0$, 을 기준으로 근방에 있는 정의역의 부분집합에서 최소값을 구하는 샘이 됩니다. 물론, $x_n$으로 부터 $x_{n+1}$을 구하는 과정에서 ${\gamma }_n$의 값을 크게 사용하거나 혹은 $f^{\prime }(x_n)$값이 크다면, $x_{n+1}$은 $x_n$의 근방이 아닐 수 있습니다. 그러나, ${\gamma }_n$이 크거나 $f^{\prime }(x_n)$이 큰 경우에는 경사 하강법으로 부터 구한 해가 수렴하지 않는 문제가 있기 때문에, 현실적으로는 ${\gamma }_n$과 $f^{\prime }(x_n)$이 작은 값이라서, 모든 $n$에 대해서 $x_n$은 $x_0$의 근방의 점이 됩니다. 물론 여기서 "근방"에 대해서는 명확하게 정의(혹은 설명)하지 않았으나, $x_n$이 정의역의 모든 영역에 골고루 퍼져 있지는 못 합니다. 

 

요약하자면, 경사 하강법으로 부터 구한 최저값은 시작점 $x_0$의 값(위치)에 크게 의존하게 되고, 이 최저값은 $x_0$ "부근"에서 얻을 수 있는 "국소" 최저점이 됩니다. 정의역 전체에 걸쳐서 목적함수가 어떻게 생겼는지를 확인(계산)해 보는 것이 아니라, $x_n$ 주변의 정보만을 확인합니다. 경사 하강법의 가장 큰 특징은 이처럼 국소화된 정보만을 이용한다는 것 입니다. 

 

백문이 불여일견 : 실제 코드 구현을 통한 경사 하강법의 예시

우선은 매우 간단한 형태의 목적함수에 대해서 경사 하강법을 통한 계산이 어떻게 되는지 보겠습니다. 위 그래프는 목적함수가 

$$y=f(x)=x^2$$

으로 주어진 경우, 경사 하강법을 이용하여 $x_n,f(x_n)$을 구하는 과정을 그림으로 나타낸 것 입니다. 이 계산에서

$$x_0=2.0,N=20,{\gamma }_n=0.1$$

을 사용하였습니다. 위 그래프에서 $x=0$ 부근을 확대한 것이 아래 그래프 입니다. 이해의 편의를 위해서 $n$이 증가 함에 따라서 그래프상에서 $(x_n,f(x_n))$ 점의 색깔을 무지개색으로 표현하였습니다. 계산으로 부터 얻어진 $x_n$은

$$2,1.6,1.28,1.024,0.819,0.655,0.524,0.419,0.336,0.268,0.215,0.172,0.137,0.11,0.088,0.07,0.056,0.045,0.036,0.029,0.023$$

입니다. $x_{2}0=0.023$으로 해석적인 해 $x_{min}=0$과는 일치하지는 않지만 비슷한 값입니다. $N=20$까지 밖에 계산하지 않았기 때문에, 아직은 0으로 수렴하지 않았지만, $N$의 값을 크게 한다면 이 값은 0으로 수렴하게 됩니다. $n$이 증가하여 $x_n$값이 0에 가까워질 수록, 목적함수의 값과 목적함수의 미분값이 작아집니다. 따라서, $x_{n+1}-xn$이 작아지게 되고, $x_n$이 $x_{min}$에 수렴하기는 하지만 다소 천천히 수렴함을 볼 수 있습니다. 

위 그래프는 목적함수가

$$y=f(x)=x^4-4x^2+x$$

으로 주어진 경우, 경사 하강법을 이용하여 $x_n,f(x_n)$을 구하는 과정을 그림으로 나타낸 것 입니다. 이 계산에서

$$x_0=2.0,N=20,{\gamma }_n=0.01$$

을 사용하였습니다. 계산으로 부터 얻어진 $x_n$ 값은

$$x_n=2,1.83,1.721,1.645,1.589,1.545,1.511,1.484,1.462,1.444,1.429,1.417,1.406,1.398,1.39,1.384,1.379,1.374,1.37,1.367,1.364$$

입니다. 이 값은 위 목적함수의 극소값인 $x_{local}=1.347$, 목적함수가 다항함수이기 때문에 미분을 이용하여 극대, 극소 값을 구할 수 있습니다,  로 수렴하는 값 입니다. $x=1.364$는 이 목적함수의 최소값에 대응되는 $x$값이 아닙니다! 이 함수의 최소값에 대응되는 $x$를 해석적으로 구하면 $-1.473$ 입니다. 경사 하강법을 통해 구한 값이 실제 목적함수의 전역 최소값이 아닌 경우 입니다. 

위 그래프는 바로 위 계산과 모든 것이 같고, 다만 $x_0=-2$로 계사한 경우의 결과 입니다. 이 계산으로 얻어진 $x_n$의 값은

$$x_n=-2,-1.85,-1.755,-1.689,-1.641,-1.606,-1.579,-1.558,-1.541,-1.528,-1.517,-1.509,-1.502,-1.497,-1.492,-1.489,-1.486,-1.484,-1.482,-1.48,-1.479$$

으로, 해석적으로 부터 구할 수 있는 최소값에 대응되는 $x$의 값, $-1.473$, 으로 수렴합니다. 경사 하강법의 계산의 시작을 $x=2$에서 한다면 국소 최소값을 얻게 되고, $x=-2$에서 시작한다면 전역 최소값을 찾게 됩니다. 이게 바로 국소 최저점 단락에서 설명한 개념의 구체적인 예시 입니다. 

 

파라미터 ${\gamma }_n$ 값에 따른 $x_n$의 변화

 

경사 하강법에서는 하나의 파라미터 ${\gamma }_n$ 값이 사용되는데, 앞의 예시에서는 각각 $0.1,0.01$의 값을 사용하였고, $n$에 대해서 변화하지 않는 상수 ${\gamma }_n=\gamma$를 사용하였습니다. 이번에는 $\gamma$ 값의 변화에 따라서 $x_n$이 어떻게 달라지는지 확인해 보도록 하겠습니다. 개념의 설명을 위해서 목적함수는 간단한 $y=f(x)=x^2$를 사용하도록 하겠습니다. "지나치게 간단한 형태의 목적함수를 예시로 활용한다" 라고 하실 수 있지만, 목적함수의 극소값 근처에서는 대체로 목적함수 값을 $x$의 2차함수의 형태로 근사할 수 있습니다. 

위 그래프는  ${\gamma }_n=\gamma =0.1$을 사용한 경우 입니다. 앞에서 이미 본 바 있는데, $x_{20}\approx x_{min}$임을 확인할 수 있습니다. 

${\gamma }_n=\gamma =0.01$ 로 계산한 경우 입니다. $x_n$은 매우 느리게 $x_{min}$으로 수렴하는 패턴을 보입니다. $x$가 변화 하는 정도, $x_{n+1}-x_n$, 는 ${\gamma }_n{f}^{\prime }(x_n)$으로 ${\gamma }_n$에 비례하게 되는데, $0.01$이라는 작은 값을 쓰다 보니 $x_n$이 변화하는 정도가 매우 작습니다. 따라서 $x_{min}=0$을 얻기 위해서는 $N$이 매우 커야 합니다. 

${\gamma }_n$ 값이 작으면 해를 얻는 과정이 오래 걸리니 $gamm{a}_n$을 무작정 크게 하면 좋을까요? 그렇지 않습니다. 위 그래프는 ${\gamma }_n=\gamma =0.95$를 사용한 경우 입니다. $x_n$이 $x_{min}=0$을 중심으로 진동하는 패턴을 보입니다. $|x_n|$은 $0$으로 수렴하긴 하지만 그 속도는 매우 느립니다. ${\gamma }_n$ 값이 커서 한 번에 변화되는 $x$의 값이 크다 보니, $x$의 값을 업데이트 하면서 ($n$이 커지면서), $x_{min}$ 값을 "지나쳤"습니다.  

$\gamma$값이 더 커진다면 어떻게 될까요? ${\gamma }_n=\gamma =1.1$를 사용한 예시 입니다. 이 경우에는 $x_n$은 진동하면서 발산하게 됩니다. 

${\gamma }_n=\gamma =0.3$ 를 사용한 예시 입니다. $x_5$ 정도에서 이미 $x_{min}=0$과 값이 비슷해 집니다. 지나치게 크지도 않고, 지나치게 작지도 않은 ${\gamma }_n$ 값을 잘 설정하여 매우 효율적으로 최소값을 구할 수 있었습니다. 

 

$\gamma$ 값을 작게 한다면 해를 찾을 수는 있지만 계산의 반복 횟수가 커집니다. 반대로 $\gamma$ 값을 크게 한다면, 해를 빠르게 찾을 수 있지만 경우에 따라서는 수열 $x_n$이 발산하여 해를 찾을 수 없게 될 수 도 있습니다. 그렇다면, 최적의 ${\gamma }_n$ 값은 무엇일까요? 이는 목적함수에 따라서 달라지는 값이니, 임의의 목적함수에 대해서 통용되는 ${\gamma }_n$ 값을 제시할 수는 없습니다. 그러나 "적당히 좋은" 혹은 "수렴성을 보장하는" ${\gamma }_n$을 제안할 수는 있습니다. 그러나 이에 대한 설명을 하는 것은 이번 포스팅의 능력을 벗어나니, 다음 포스팅에서 차차 알아가도록 하겠습니다. 

 

끌림 영역basin of attraction

 

목적함수가 $y=f(x)=x^4-4x^2+x$로 주어진 경우, $x_0$값에 따라서 경사 하강법을 통해서 얻을 수 있는 값은 전역 최소값일 수 도 있고, 국소 최소값일 수 도 있다는 것을 확인하였습니다. 일반화 하면 (${\gamma }_n$ 값을 매우 작게 하여 $\mathrm{\Delta }x=x_{n+1}-x_n$을 매우 작게 한 파라미터 세팅의 경사 하강법에서) 

$$x_0<0.126$$

인 경우, $x_n$은 전역 최소값(에 대응되는 $x$점) $x_{min}=-1.473$에 수렴하게 되고,

$$x_0>0.126$$

인 경우, $x_n$은 국소 최소값(에 대응되는 $x$점) $x_{local}=1.347$에 수렴하게 됩니다. 만일

$$x_0=0.126$$

인 경우, $x_n=x_0=0.126$ 으로 $x$ 값은 변화하지 않습니다. $x_{saddle}=0.126$에 수렴했다고 볼 수 있습니다. 요약하면, 경사 하강법에 따라 구한 수열 $x_n$은 $x_0$이 놓인 위치에 따라서 $-1.473,1.347,0.126$ 세 값 중 하나의 값으로 수렴을 하게 되는데, 이 세 점을 끌개attractor라고 합니다. 끌개라는 용어와 개념은 동역학계dynamical system에서 온 것 인데, 경사 하강법을 통해 $x$값이 업데이트 되는 것을 동역학계의 개념을 통해서도 설명할 수 있습니다. 경사 하강법에서 나오게 되는 끌개는 목적함수의 미분값을 0으로 만들어 주는 값, 극대 혹은 극소, 입니다. 각 끌개로 수렴하게 되는 $x_0$의 영역을 끌림 영역basin of attration이라고 합니다. $x=-1.473$에 대응되는 끌림영역은 $x<0.126$, $x=1.347$에 대응되는 끌림영역은 $x>0.126$ 입니다. 

위 설명을 그래프로 나타내면 위와 같습니다. 전역 최소값에 대응되는 끌림 영역은 붉은색으로 표시하였고, 국소 최소값에 대응되는 끌림 영역은 파란색으로 표시하였습니다. 사실 끌림 영역은 정의역의 집합을 의미하는 것이라서 위에서 처럼 그래프를 서로 다른 색으로 그리면 약간은 오해의 소지가 있긴 합니다. 

 

경사 하강법을 통해서 전역 최소값을 얻기 위해서는 $x_0$이 전역 최소값에 대응되는 끌림영역에 속해 있어야 합니다. 그렇지 않은 경우, 경사 하강법은 항상 국소 최소값을 최종 결과로 내 놓게 됩니다. 

 

$x_0$이 전역 최소값에 대응되는 끌림영역에 속하도록 하기

 

만일 $x_0$이 전역 최소값에 대응되는 끌림영역에 속한다면, 경사 하강법은 시뮬레이션 담금질이나 유전 알고리듬과 같이 그레이디언트를 사용하지 않는 gradient-free 전역 최소값을 구하는 수학적 최적화 방법에 비해서 월등히 효율적인 알고리듬이 됩니다. 적은 수의 목적함수 계산을 통해서 전역 최소값을 찾을 수 있는 것 입니다. 그러나, 안타깞게도 그리고 당연히도 목적함수를 여러 번 계산해 보기 전까지는 전역 최소값에 대응되는 끌림영역이 어떻게 되는지를 알 수 없습니다. 따라서, 서로 다른 여러개의 $x_0$에 대해서 경사 하강법을 병렬로 실행해 보고, 각 실행에서 얻어지는 값 중 최소값을 선택하는 수 밖에 없습니다. 

 

시뮬레이션 담금질과의 비교

 

이전에 설명한 수학적 최적화의 방법인 시뮬레이션 담금질과 비교를 한다면, 경사 하강법의 성질을 조금 더 잘 알 수 있습니다. 시뮬레이션 담금질도 역시나 $x_0$에서 시작하여 특정한 방식으로 정의역 공간에서의 수열 $x_n$을 얻는 과정이라고 할 수 있습니다. 시뮬레이션 담금질에서는 $x_n$으로 부터 $x_{n+1}$의 후보 $x_c$ 하나 만들어 내고, $f(x_n)$와 $f(x_c)$ 값의 비교를 통해서 $x_n$을 업데이트 할지 아닐지를 결정합니다. $x_n$이 업데이트가 되면, $x_{n+1}=x_c$가 되고, 업데이트가 되지 않으면, $x_{n+1}=x_n$이 됩니다. 시뮬레이션 담금질에서는 무작위성이 도입되지만, 경사 하강법에서는 무작위성의 여지가 없습니다. $x_0$ 값이 같다면, 항상 같은 결과를 줍니다. 시뮬레이션 담금질에서는 $f(x_c)>f(x_n)$이라고 하더라도, $x_{n+1}=x_c$로 $x$값이 업데이트 될 수 도 있습니다. 그러나, 경사 하강법에서는 항상 $f(x_n)>f(x_{n+1})$이 지켜집니다. 시뮬레이션 담금질에서는 $x_c$는 $x_n$에 의존을 하는 값일 수 도 있고, 그렇지 않고 정의역 전체 공간에서 하나의 원소를 임의로 혹은 정해진 규칙에 의해서 뽑아 낼 수 도 있지만, 경사 하강법에서는 $x_{n+1}$은 $x_n$과 목적합수의 $x_n$에서의 미분값으로 인해 정확이 정해집니다.