Unconstrained Optimum Design, Part I

Descent Directions, Line Search, and Conjugate Gradients

Reference: Jasbir Singh Arora, Introduction to Optimum Design, 4th ed., Academic Press, 2017, Ch. 10.

이 장에서는 unconstrained optimum design을 반복적으로 푸는 기본 구조를 정리한다. 각 iteration에서 search direction과 step size를 분리하여 결정하고, descent condition으로 목적함수의 감소를 보장한다. 이어서 one-dimensional line search, steepest-descent method, Fletcher–Reeves conjugate-gradient method를 유도하고 각각의 수렴 특성을 비교한다.


Unconstrained Design Problem

다음 unconstrained problem을 생각하자.

\[\underset{x\in\mathbb{R}^n}{\operatorname{minimize}} \quad f(x).\]

Numerical method는 starting design $x^{(0)}$에서 시작하여 design sequence

\[x^{(0)},x^{(1)},x^{(2)},\ldots\]

를 생성한다. 현재 design에서 다음 design으로의 변화량을

\[\Delta x^{(k)}=x^{(k+1)}-x^{(k)}\]

라 하면 basic iteration은

\[x^{(k+1)}=x^{(k)}+\Delta x^{(k)}\]

이다. Design change를 search direction $d^{(k)}$와 positive step size $\alpha_k$로 분해하면

\[\Delta x^{(k)}=\alpha_k d^{(k)}, \qquad \alpha_k>0,\]

따라서

\[x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)}\]

를 얻는다. Multivariable optimization의 한 iteration은 direction-finding subproblem과 step-size determination subproblem으로 나뉜다.


General Iterative Algorithm

Unconstrained optimization의 일반적인 반복 절차는 다음과 같다.

  1. Starting design $x^{(0)}$을 정하고 $k=0$으로 둔다.
  2. 현재 design $x^{(k)}$에서 search direction $d^{(k)}$를 계산한다.
  3. Convergence criterion을 만족하면 종료한다.
  4. $d^{(k)}$ 방향에서 positive step size $\alpha_k$를 계산한다.
  5. $x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)}$로 갱신하고 반복한다.

알고리즘 사이의 차이는 주로 $d^{(k)}$와 $\alpha_k$를 결정하는 방법에서 발생한다. Search direction은 local geometry를 이용해 감소 방향을 정하고, line search는 그 방향을 따라 이동할 거리를 정한다.


Descent Direction

현재 design에서 목적함수가 감소하려면

\[f\!\left(x^{(k)}+\alpha_kd^{(k)}\right) < f\!\left(x^{(k)}\right)\]

이어야 한다. Gradient를

\[c^{(k)}=\nabla f\!\left(x^{(k)}\right)\]

로 두고 first-order Taylor expansion을 적용하면

\[f\!\left(x^{(k)}+\alpha_kd^{(k)}\right) = f\!\left(x^{(k)}\right) + \alpha_kc^{(k)T}d^{(k)} + o(\alpha_k).\]

$\alpha_k>0$가 충분히 작을 때 목적함수 감소를 보장하는 조건은

\[c^{(k)T}d^{(k)}<0\]

이다. 이를 descent condition이라 하고, 이 조건을 만족하는 $d^{(k)}$를 descent direction이라 한다.

Dot product의 부호로부터 $c^{(k)}$와 $d^{(k)}$ 사이의 각은 $90^{\circ}$보다 크다. 따라서 descent direction은 gradient가 가리키는 최대 증가 방향의 반대쪽 half-space에 놓인다.


Convergence and Rate of Convergence

Descent method는 매 iteration에서

\[f\!\left(x^{(k+1)}\right) < f\!\left(x^{(k)}\right)\]

을 만들도록 구성된다. Chapter 10에서 global convergence는 starting point와 무관하게 어떤 local optimum point로 수렴한다는 뜻이다. Local information만 사용하는 descent method가 global minimum으로의 수렴을 보장한다는 의미는 아니다.

Convergence criterion은 보통 first-order necessary condition을 근사하여

\[\left\|c^{(k)}\right\| = \left\|\nabla f\!\left(x^{(k)}\right)\right\| <\epsilon\]

으로 둔다. 이 조건은 stationary point에 가까워졌음을 나타내지만, 그 점이 local minimum인지 판정하려면 curvature 또는 문제 구조를 함께 확인해야 한다.

Rate of convergence는 acceptable solution에 도달하기까지 필요한 iteration 수와 function evaluation 수로 비교한다. 일반적으로 first-order information만 사용하는 방법보다 second-order information 또는 그 근사를 사용하는 방법이 빠르지만, iteration당 계산 비용은 더 크다.


Line-Search Subproblem

$d^{(k)}$가 주어졌다고 하자. Trial step $\alpha$에 대한 design은

\[x(\alpha)=x^{(k)}+\alpha d^{(k)}\]

이고, line-search function을

\[\bar f(\alpha) = f\!\left(x^{(k)}+\alpha d^{(k)}\right)\]

로 정의한다. 이후에는 책의 표기에 따라 $\bar f(\alpha)$를 간단히 $f(\alpha)$로 쓴다. 그러면

\[f(0)=f\!\left(x^{(k)}\right)\]

이고, chain rule에 의해

\[f^{\prime}(0) = \nabla f\!\left(x^{(k)}\right)^Td^{(k)} = c^{(k)T}d^{(k)}.\]

$d^{(k)}$가 descent direction이면 $f^{\prime}(0)<0$이므로 작은 positive $\alpha$에서 목적함수가 감소한다. Step-size subproblem은

\[\underset{\alpha>0}{\operatorname{minimize}} \quad f(\alpha)\]

라는 one-dimensional minimization problem이다.


Exact Step Size and Orthogonality

$f(\alpha)$가 미분 가능하고 line minimum이 interior point에서 얻어진다면 exact step size $\alpha_k$는

\[\frac{df(\alpha_k)}{d\alpha}=0\]

을 만족한다. Chain rule을 적용하면

\[\frac{df(\alpha_k)}{d\alpha} = \nabla f\!\left(x^{(k)}+\alpha_kd^{(k)}\right)^Td^{(k)}.\]

$x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)}$이므로

\[c^{(k+1)T}d^{(k)}=0.\]

따라서 exact line search 이후의 gradient는 직전 search direction에 orthogonal하다. 이 식은 analytical step size를 구하는 equation이면서 numerical line search의 정확도를 검사하는 termination criterion이다. Strict local minimum을 확인하려면 추가로

\[\frac{d^2f(\alpha_k)}{d\alpha^2}>0\]

을 검사한다.


Analytical solution을 얻기 어렵다면 function values를 비교하여 minimum을 포함하는 interval을 줄인다. Numerical line search는 관심 interval에서 $f(\alpha)$가 하나의 minimum만 갖는 unimodal function이라고 가정한다.

Minimum point $\alpha^{\star}$를 포함하는 bounds를 $\alpha_l$과 $\alpha_u$라 하면 interval of uncertainty는

\[I=\alpha_u-\alpha_l\]

이다. Interval-reducing method는 다음 두 phase로 구성된다.

  • Phase I: $\alpha^{\star}$를 포함하는 initial interval $[\alpha_l,\alpha_u]$를 bracket한다.
  • Phase II: Function values를 비교하여 minimum이 존재할 수 없는 subinterval을 제거한다.

종료 조건은

\[I<\epsilon\]

이고, 최종 approximation은

\[\alpha^{\star}\approx\frac{\alpha_l+\alpha_u}{2}\]

로 둔다.


Equal-Interval Searches

Equal-interval search는 fixed increment $\delta>0$를 사용하여

\[\delta,2\delta,3\delta,\ldots\]

에서 function value를 계산한다. 처음으로

\[f(q\delta)<f\!\left((q+1)\delta\right)\]

가 성립하면 minimum을 지나쳤다고 판단하여

\[\alpha_l=(q-1)\delta, \qquad \alpha_u=(q+1)\delta, \qquad I=2\delta\]

로 bracket한다. Phase II에서는 smaller increment를 사용하여 같은 절차를 반복한다. 방법은 단순하지만 $\delta$가 너무 작으면 initial bracketing에 많은 evaluations가 필요하다.

Alternate equal-interval search는 현재 interval의 trisection points

\[\alpha_a=\alpha_l+\frac{I}{3}, \qquad \alpha_b=\alpha_l+\frac{2I}{3}\]

를 비교한다. $f(\alpha_a)<f(\alpha_b)$이면 $[\alpha_l,\alpha_b]$를, 반대이면 $[\alpha_a,\alpha_u]$를 유지한다. 매 iteration에서 interval은 $2I/3$로 줄지만 두 개의 새로운 function evaluations가 필요하다.


Golden-section search는 한 iteration에서 계산한 function value 하나를 다음 iteration에서 재사용한다. Golden ratio의 reciprocal을

\[\tau = \frac{\sqrt{5}-1}{2} \approx0.618\]

이라 하면

\[\tau^2+\tau-1=0.\]

Current interval $[\alpha_l,\alpha_u]$에서 두 interior points를

\[\alpha_a=\alpha_l+(1-\tau)I, \qquad \alpha_b=\alpha_l+\tau I\]

로 둔다. 여기서 $1-\tau\approx0.382$이다.

  • $f(\alpha_a)<f(\alpha_b)$이면 $[\alpha_l,\alpha_b]$를 유지한다.
  • $f(\alpha_a)>f(\alpha_b)$이면 $[\alpha_a,\alpha_u]$를 유지한다.
  • 두 값이 같으면 $[\alpha_a,\alpha_b]$를 유지할 수 있다.

선택된 새 interval의 length는 $\tau I$이고, 기존 interior point 하나가 새 partition의 interior point가 된다. 따라서 첫 partition 이후에는 iteration당 하나의 새로운 function evaluation만 필요하다.

Phase I의 bracketing에서도 increment를 $1.618$배씩 증가시키면 minimum을 빠르게 둘러쌀 수 있다. Initial step이 너무 커서 $f(\delta)>f(0)$이면 $f(\delta)<f(0)$이 될 때까지 $\delta$를 줄여 descent step을 확보한다.


Steepest-Descent Direction

Gradient $c=\nabla f(x)$는 목적함수가 가장 빠르게 증가하는 방향이다. 따라서 Euclidean norm을 기준으로 가장 빠르게 감소하는 unit direction은 negative gradient 방향이다.

실제로 $|d|=1$인 direction에 대한 local rate of change는 $c^Td$이다. Cauchy–Schwarz inequality로부터

\[c^Td\geq-\|c\|\|d\|=-\|c\|\]

이고 equality는

\[d=-\frac{c}{\|c\|}\]

일 때 성립한다. Direction의 scale은 step size에 흡수할 수 있으므로 steepest-descent method는

\[d^{(k)}=-c^{(k)} = -\nabla f\!\left(x^{(k)}\right)\]

를 사용한다. $c^{(k)}\neq0$이면

\[c^{(k)T}d^{(k)} = -\left\|c^{(k)}\right\|^2 <0,\]

따라서 negative gradient는 항상 descent direction이다.


Steepest-Descent Algorithm

Steepest-descent algorithm은 다음과 같다.

  1. $x^{(0)}$과 tolerance $\epsilon>0$을 정한다.
  2. $c^{(k)}=\nabla f(x^{(k)})$를 계산한다.
  3. $|c^{(k)}|<\epsilon$이면 종료한다.
  4. $d^{(k)}=-c^{(k)}$로 둔다.
  5. $f(x^{(k)}+\alpha d^{(k)})$를 최소화하는 $\alpha_k$를 line search로 구한다.
  6. $x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)}$로 갱신한다.

Exact line search를 사용하면

\[c^{(k+1)T}c^{(k)}=0\]

이므로 successive gradients와 steepest-descent directions가 orthogonal하다. 이 성질은 좁고 긴 level set에서 zigzagging을 만들 수 있다.

Steepest descent는 단순하고 robust하지만 다음 한계를 갖는다.

  • 각 iteration이 이전 search-direction information을 직접 재사용하지 않는다.
  • First-order information만 사용하므로 minimum 부근에서 느려질 수 있다.
  • Optimum에서 Hessian의 condition number가 크면 convergence가 느리다.
  • 초기에는 목적함수가 크게 감소하지만 이후 감소량이 급격히 작아질 수 있다.


Conjugate Directions

Symmetric positive-definite matrix $A$에 대하여 directions $d^{(i)}$와 $d^{(j)}$가

\[d^{(i)T}Ad^{(j)}=0, \qquad i\neq j\]

를 만족하면 $A$-conjugate라 한다. Positive-definite quadratic function에서는 $A$를 Hessian으로 해석할 수 있다.

Steepest descent가 successive orthogonal directions을 사용하는 것과 달리 conjugate-gradient method는 Hessian geometry에 대해 conjugate한 directions을 생성한다. 이 directions은 이전 iteration의 정보를 포함하므로 quadratic valley를 더 직접적으로 가로지른다.


Fletcher–Reeves Method

첫 search direction은 steepest-descent direction과 같다.

\[d^{(0)}=-c^{(0)}.\]

$k\geq1$에서는

\[d^{(k)} = -c^{(k)}+\beta_kd^{(k-1)}\]

로 갱신한다. Fletcher–Reeves coefficient는

\[\beta_k^{\mathrm{FR}} = \frac{c^{(k)T}c^{(k)}}{c^{(k-1)T}c^{(k-1)}} = \frac{\left\|c^{(k)}\right\|^2}{\left\|c^{(k-1)}\right\|^2}\]

이다. Exact line search이면

\[c^{(k)T}d^{(k-1)}=0.\]

따라서

\[\begin{aligned} c^{(k)T}d^{(k)} &=-c^{(k)T}c^{(k)} +\beta_kc^{(k)T}d^{(k-1)} \\ &=-\left\|c^{(k)}\right\|^2<0, \end{aligned}\]

즉 Fletcher–Reeves direction도 descent condition을 만족한다.

Positive-definite quadratic function이 $n$개의 design variables를 가질 때 conjugate-gradient method는 exact arithmetic과 exact line search 아래에서 최대 $n$ iterations 안에 minimum을 찾는다. General nonlinear function에서는 conjugacy가 누적 오차로 약해질 수 있으므로 minimum을 찾지 못하면 매 $(n+1)$번째 iteration에서

\[d^{(k)}=-c^{(k)}\]

로 restart한다.


Other Conjugate-Gradient Coefficients

Successive gradient difference를

\[y^{(k)}=c^{(k)}-c^{(k-1)}\]

로 정의한다. 대표적인 coefficients는 다음과 같다.

\[\beta_k^{\mathrm{HS}} = \frac{c^{(k)T}y^{(k)}}{d^{(k-1)T}y^{(k)}},\] \[\beta_k^{\mathrm{FR}} = \frac{c^{(k)T}c^{(k)}}{c^{(k-1)T}c^{(k-1)}},\] \[\beta_k^{\mathrm{PR}} = \frac{c^{(k)T}y^{(k)}}{c^{(k-1)T}c^{(k-1)}}.\]

각각 Hestenes–Stiefel, Fletcher–Reeves, Polak–Ribière formula이다. Positive-definite quadratic function과 exact line search에서는 세 식이 equivalent하지만, general nonlinear function에서는 서로 다른 directions을 만든다. Chapter 10은 Fletcher–Reeves와 Polak–Ribière coefficients가 실용적으로 좋은 성능을 보이며, negative Polak–Ribière coefficient가 나타나면 restart하는 선택을 제시한다.


Summary

  • Unconstrained iterative method는 design change를 search direction과 positive step size로 분해한다.
  • $c^{(k)T}d^{(k)}<0$은 sufficiently small positive step에서 목적함수 감소를 보장하는 descent condition이다.
  • Exact line search는 $c^{(k+1)T}d^{(k)}=0$을 만족시키며, numerical line search에서는 이 식을 정확도 검사에 사용할 수 있다.
  • Equal-interval search는 단순하지만 evaluations가 많고, golden-section search는 기존 function value를 재사용하여 interval을 효율적으로 줄인다.
  • Steepest descent는 negative gradient를 사용하여 항상 descent direction을 얻지만 ill-conditioned problem에서 느릴 수 있다.
  • Conjugate-gradient method는 이전 direction을 이용하며 positive-definite quadratic problem에서 finite termination property를 갖는다.