Unconstrained Optimum Design, Part II

Inexact Line Search, Newton-Type Methods, and Direct Search

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

이 장에서는 unconstrained optimum design의 계산 효율과 수렴속도를 개선하는 방법을 정리한다. Exact line search를 대체하는 inexact conditions, Hessian을 사용하는 Newton method, first-order information으로 curvature를 근사하는 quasi-Newton method를 유도한다. 이어서 convergence order를 비교하고 derivative 없이 function values만 사용하는 direct-search methods를 살펴본다.


Line-Search Setting

현재 design $x^{(k)}$와 descent direction $d^{(k)}$가 주어졌다고 하자. Line-search function은

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

이고 descent condition은

\[c^{(k)T}d^{(k)}<0, \qquad c^{(k)}=\nabla f\!\left(x^{(k)}\right)\]

이다. Chain rule에 의해

\[f^{\prime}(\alpha) = \nabla f\!\left(x^{(k)}+\alpha d^{(k)}\right)^Td^{(k)},\]

따라서

\[f^{\prime}(0)=c^{(k)T}d^{(k)}<0.\]

Exact line search는 $f^{\prime}(\alpha_k)=0$을 요구하지만, 복잡한 design analysis에서는 한 번의 function 또는 gradient evaluation도 큰 비용을 가질 수 있다. Chapter 11의 line-search methods는 정확한 minimum 대신 충분한 감소와 적절한 step length를 보장하는 데 초점을 둔다.

Polynomial interpolation은 known values로 $q(\alpha)=a_0+a_1\alpha+a_2\alpha^2$를 구성하고, $a_2>0$일 때 $\bar\alpha=-a_1/(2a_2)$를 trial minimum으로 사용한다. 세 function values를 맞추거나 이미 알려진 $f(0)$, $f^{\prime}(0)$과 하나의 trial value를 이용할 수 있다. 새 function value를 비교하여 interval을 갱신하므로 dense interval search보다 evaluations를 줄일 수 있다.


Armijo Rule

$0<\rho<1$을 정하고 linear reference function을

\[q(\alpha) = f(0)+\rho\alpha f^{\prime}(0)\]

로 둔다. Armijo sufficient-decrease condition은

\[f(\alpha) \leq f(0)+\rho\alpha f^{\prime}(0)\]

이다. $f^{\prime}(0)<0$이므로 오른쪽은 current value보다 작으며, accepted step은 predicted linear decrease의 일정 비율 이상을 실제로 감소시킨다.

Backtracking은 initial step, 보통 $\alpha=1$에서 시작하여 condition이 실패할 때마다 $\eta>1$에 대해

\[\alpha\leftarrow\frac{\alpha}{\eta}\]

로 줄인다. 반대로 작은 trial step에서 시작한다면 Armijo condition을 만족하는 동안 $\alpha$를 $\eta$배 증가시키고, condition이 깨지기 직전의 값을 선택할 수 있다.

Armijo condition만으로는 지나치게 작은 step도 허용된다. 따라서 충분한 decrease뿐 아니라 slope가 충분히 완화되었는지를 검사하는 curvature condition이 필요하다.


Wolfe and Goldstein Conditions

$0<\rho<\beta<1$일 때 Wolfe conditions는 Armijo condition과

\[f^{\prime}(\alpha) \geq \beta f^{\prime}(0)\]

를 함께 요구한다. 두 번째 식은 accepted point에서 slope가 initial negative slope보다 충분히 증가했음을 뜻한다.

Strong Wolfe curvature condition은

\[\left|f^{\prime}(\alpha)\right| \leq \beta\left|f^{\prime}(0)\right|\]

이다. 이는 large positive slope도 배제하여 trial point가 line minimum을 심하게 지나치는 것을 막는다.

Goldstein conditions는 $0<\rho<1/2$에 대해

\[f(0)+(1-\rho)\alpha f^{\prime}(0) \leq f(\alpha) \leq f(0)+\rho\alpha f^{\prime}(0)\]

로 쓴다. Upper bound는 sufficient decrease를, lower bound는 step이 너무 작지 않음을 검사한다. 다만 $\rho$의 선택에 따라 exact line minimum이 acceptable interval에서 제외될 수 있으므로 quasi-Newton methods에는 Wolfe conditions가 더 적합하다.


Gradient Geometry

Level surface $f(x)=\text{constant}$ 위의 curve를 $x(s)$라 하자. Curve를 따라 $f$가 변하지 않으므로

\[0 = \frac{df}{ds} = \nabla f(x)^T\frac{dx}{ds}\]

따라서 gradient는 level surface의 모든 tangent directions에 orthogonal하다. 한편 unit direction $u$에 대한 directional derivative는

\[\frac{df}{dt}=c^Tu=\|c\|\cos\theta\]

이다. $u=c/|c|$에서 maximum increase rate $|c|$을, $u=-c/|c|$에서 maximum decrease rate $-|c|$을 얻는다. 이는 steepest-descent direction $d=-c$의 local geometric 근거이다.

Exact line search를 사용하는 steepest descent에서는

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

$d^{(k)}=-c^{(k)}$이므로

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

즉 exact line search 아래에서 successive steepest-descent directions은 orthogonal하며, elongated level sets에서는 이 성질이 zigzagging과 느린 수렴을 만든다.


Scaling of Design Variables

Positive-definite quadratic의 Hessian을 $H$라 하면 condition number는

\[r = \frac{\lambda_{\max}(H)}{\lambda_{\min}(H)}\]

이다. $r$가 크면 level sets가 길게 늘어나고 steepest descent가 느려진다. Scaling의 목적은 transformed variables에서 Hessian의 condition number를 줄이는 것이다.

일반적인 symmetric positive-definite Hessian의 eigendecomposition을

\[H=Q\Lambda Q^T\]

라 하면

\[x=Q\Lambda^{-1/2}z\]

를 통해

\[H_z = \Lambda^{-1/2}Q^THQ\Lambda^{-1/2} = I\]

를 얻는다. 따라서 transformed Hessian의 condition number는 $1$이다. $H$가 diagonal이면 이는 $x=Dy$, $D_{ii}=1/\sqrt{H_{ii}}$로 단순화된다. Nonquadratic problem에서는 Hessian이 design에 따라 변하고 optimum의 Hessian을 미리 알 수 없으므로 scaling matrix 역시 approximation에 의존한다.


Classical Newton Method

현재 point $x$ 부근에서 second-order Taylor approximation은

\[f(x+\Delta x) \approx f(x)+c^T\Delta x+\frac{1}{2}\Delta x^TH\Delta x,\]

여기서

\[c=\nabla f(x), \qquad H=\nabla^2f(x)\]

이다. Quadratic model의 stationarity condition은

\[c+H\Delta x=0\]

이므로 nonsingular $H$에 대해 Newton change는

\[\Delta x=-H^{-1}c\]

이다. 실제 계산에서는 inverse를 만들지 않고 linear system

\[H\Delta x=-c\]

를 직접 푼다.

Classical Newton method는 unit step

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

를 사용한다. Positive-definite quadratic function에서는 Taylor model이 exact하므로 한 iteration에 minimum을 얻는다. General nonlinear function에서는 unit step이 목적함수 감소를 보장하지 않으며, Hessian 계산에 $n(n+1)/2$개의 second derivatives가 필요하다.


Modified Newton Method

Newton change를 search direction으로 사용하고 line search를 결합하면

\[H^{(k)}d^{(k)}=-c^{(k)},\] \[x^{(k+1)} = x^{(k)}+\alpha_kd^{(k)}\]

인 modified Newton method를 얻는다. Direction의 descent property는

\[c^{(k)T}d^{(k)} = -c^{(k)T}\left[H^{(k)}\right]^{-1}c^{(k)}<0\]

로 검사한다. $H^{(k)}\succ0$이면 $c^{(k)}\neq0$에서 항상 성립한다.

$H^{(k)}$가 singular이면 direction을 정의할 수 없고, indefinite이면 Newton direction이 ascent direction이 될 수 있다. 따라서 각 iteration에서 positive definiteness 또는 descent condition을 확인해야 한다. Modified Newton method는 적절한 line search와 positive-definite Hessian 아래에서 안정성을 얻고, solution 부근에서는 classical Newton의 빠른 local convergence를 유지한다.


Marquardt Modification

Marquardt method는 Hessian에 positive diagonal shift를 더한다.

\[d^{(k)} = -\left[H^{(k)}+\lambda_kI\right]^{-1}c^{(k)}, \qquad \lambda_k>0.\]

$\lambda_k$가 충분히 크면

\[d^{(k)} \approx -\frac{1}{\lambda_k}c^{(k)},\]

이므로 steepest-descent step처럼 작동한다. $\lambda_k$가 작아지면 Newton direction에 가까워진다.

  • Trial direction이 목적함수를 감소시키지 않으면 $\lambda_k$를 증가시켜 direction을 다시 계산한다.
  • Trial direction이 성공하면 design을 갱신하고 $\lambda_k$를 감소시킨다.

따라서 solution에서 멀리 떨어진 영역에서는 gradient method의 안정성을, solution 부근에서는 Newton method의 효율을 얻는다.


Quasi-Newton Condition

Quasi-Newton methods는 second derivatives를 직접 계산하지 않고 successive design과 gradient differences로 Hessian 또는 inverse Hessian을 갱신한다. 다음 vectors를 정의하자.

\[s^{(k)} = x^{(k+1)}-x^{(k)} = \alpha_kd^{(k)},\] \[y^{(k)} = c^{(k+1)}-c^{(k)}.\]

Local quadratic model에서는

\[y^{(k)}\approx Hs^{(k)}.\]

따라서 Hessian approximation은 secant equation

\[H^{(k+1)}s^{(k)}=y^{(k)}\]

을, inverse approximation $A^{(k+1)}\approx H^{-1}$은

\[A^{(k+1)}y^{(k)}=s^{(k)}\]

을 만족하도록 갱신한다. Update는 symmetry와 positive definiteness를 보존해야 한다. Positive-definite approximation은 생성된 direction이 descent direction이 되도록 보장한다.


DFP Inverse-Hessian Update

$A^{(k)}$를 inverse Hessian approximation이라 하자. Search direction은

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

이고, line search와 design update 후

\[z^{(k)}=A^{(k)}y^{(k)}\]

를 정의한다. Davidon-Fletcher-Powell update는

\[A^{(k+1)} = A^{(k)} + \frac{s^{(k)}s^{(k)T}}{s^{(k)T}y^{(k)}} - \frac{z^{(k)}z^{(k)T}}{y^{(k)T}z^{(k)}}.\]

$A^{(0)}=I$이면 첫 direction은 steepest-descent direction이다. Curvature condition

\[s^{(k)T}y^{(k)}>0\]

과 suitable line search 아래에서 $A^{(k)}$는 positive definite로 유지된다. 그러면

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

이므로 매 search direction이 descent direction이다. Strictly convex quadratic에서는 approximation이 최대 $n$ updates 안에 exact inverse Hessian으로 수렴한다.


BFGS Hessian Update

BFGS method는 Hessian approximation $H^{(k)}$을 직접 갱신하고

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

를 풀어 direction을 구한다. Chapter 11의 update는

\[H^{(k+1)} = H^{(k)}+D^{(k)}+E^{(k)},\] \[D^{(k)} = \frac{y^{(k)}y^{(k)T}}{y^{(k)T}s^{(k)}}, \qquad E^{(k)} = \frac{c^{(k)}c^{(k)T}}{c^{(k)T}d^{(k)}}\]

로 쓴다. $c^{(k)T}d^{(k)}<0$이므로 두 번째 correction은 negative curvature correction의 역할을 한다. 이는 secant equation을 만족하면서 Hessian model을 새 gradient information에 맞춘다.

$H^{(0)}=I$이면 첫 iteration은 steepest descent와 같다. Accurate line search와 positive-curvature condition 아래에서 BFGS update는 positive definiteness를 보존하므로 direction의 descent property도 유지된다. Numerical stability를 위해 Hessian 자체 대신 Cholesky factors를 갱신할 수도 있다.


Order of Convergence

Sequence ${x^{(k)}}$가 $x^{\star}$로 수렴한다고 하자. 가장 큰 $p>0$에 대해

\[0 \leq \lim_{k\to\infty} \frac{\left\|x^{(k+1)}-x^{\star}\right\|} {\left\|x^{(k)}-x^{\star}\right\|^p} <\infty\]

이면 convergence order가 $p$라고 한다. 이 limit을

\[\beta = \lim_{k\to\infty} \frac{\left\|x^{(k+1)}-x^{\star}\right\|} {\left\|x^{(k)}-x^{\star}\right\|^p}\]

로 쓰면 $\beta$는 convergence ratio 또는 asymptotic error constant이다.

  • $p=1$이고 $0<\beta<1$이면 linear convergence이다.
  • $p=2$이면 quadratic convergence이다.
  • $p=1$로 두었을 때 $\beta=0$이면 superlinear convergence이다.

Order는 sequence의 asymptotic tail에서 정의된다. 따라서 초기 iterations의 빠른 decrease만으로 asymptotic convergence rate를 판단할 수 없다.


Convergence Rates of the Methods

Positive-definite quadratic

\[q(x)=\frac{1}{2}x^TQx-b^Tx\]

에 대해 error function을

\[E(x) = \frac{1}{2}(x-x^{\star})^TQ(x-x^{\star})\]

로 둔다. $r=\lambda_{\max}(Q)/\lambda_{\min}(Q)$이면 exact line search를 사용하는 steepest descent는

\[E\!\left(x^{(k+1)}\right) \leq \left(\frac{r-1}{r+1}\right)^2 E\!\left(x^{(k)}\right)\]

을 만족한다. 따라서 linear convergence이고, $r$가 커질수록 ratio가 $1$에 가까워져 느려진다. $r=1$이면 한 iteration에 수렴한다.

Chapter 11의 비교 결과는 다음과 같다.

  • Hessian이 solution에서 positive definite이고 충분히 smooth하면 Newton method는 local quadratic convergence를 갖는다.
  • Positive-definite quadratic에서 conjugate-gradient method는 최대 $n$ steps 안에 종료한다.
  • General nonlinear function의 conjugate-gradient method는 complete cycle의 관점에서 quadratic-type improvement를 기대하며 periodic restart를 사용한다.
  • DFP approximation이 exact inverse Hessian에 가까워질수록 effective condition number가 $1$에 가까워져 superlinear behavior를 보인다.
  • Hessian의 continuity와 boundedness 등 적절한 assumptions 아래에서 BFGS method는 superlinear convergence를 갖는다.


Direct-search methods는 derivatives 대신 function values만 사용한다. Univariate search는 coordinate direction $e_i$를 따라

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

로 한 variable씩 최소화한다. 구현은 단순하지만 coordinate directions에 고정되어 작은 steps와 cycling이 발생할 수 있다.

Hooke-Jeeves method는 exploratory search와 pattern search를 결합한다.

  • Exploratory search: 각 coordinate에서 positive와 negative trial move를 비교하고 목적함수를 감소시키는 move를 채택한다.
  • Pattern search: Successive base points의 차이
\[d^{(k)}=x^{(k)}-x^{(k-1)}\]

를 이용해 temporary point

\[x_p^{(k+1)} = x^{(k)}+t d^{(k)}, \qquad t>1\]

를 만든다.

Temporary point에서 exploratory search가 성공하면 새 base point로 채택한다. 실패하면 current base point로 돌아가 coordinate step sizes를 줄인다. Step-size norm이 tolerance보다 작아지면 종료한다.


Nelder-Mead Simplex Method

$n$-dimensional space에서 simplex는 $n+1$개의 vertices로 구성된다. Function values를

\[f_1\leq f_2\leq\cdots\leq f_{n+1}\]

로 정렬하고 best point를 $x^L$, worst point를 $x^W$라 하자. Worst point를 제외한 $n$개 points의 centroid는

\[x^C=\frac{1}{n}\sum_{j=1}^{n}x^{(j)}\]

이다. Simplex는 다음 operations으로 이동한다.

Reflection

\[x^R = (1+\alpha_R)x^C-\alpha_Rx^W, \qquad 0<\alpha_R\leq1.\]

Expansion

\[x^E = (1+\alpha_E)x^C-\alpha_Ex^W, \qquad \alpha_E>1.\]

Outside contraction

\[x^Q = x^R+\alpha_Q(x^R-x^C), \qquad -1<\alpha_Q<0.\]

Inside contraction

\[x^Q = x^C+\alpha_Q(x^C-x^W), \qquad -1<\alpha_Q<0.\]

Shrinkage

\[x^{(j)} \leftarrow x^L+\delta\left(x^{(j)}-x^L\right), \qquad 0<\delta<1.\]

Reflection point가 개선되면 expansion을 시도하고, 충분히 개선되지 않으면 contraction을 수행한다. Contraction도 실패하면 simplex를 best point 방향으로 shrink한다. Simplex size, function-value spread, iteration 또는 function-evaluation limit을 termination criterion으로 사용한다.

Nelder-Mead method는 gradient를 요구하지 않고 nonsmooth function에도 적용할 수 있지만, derivative를 사용하지 않는다는 사실만으로 general convergence가 보장되는 것은 아니다. Search geometry와 termination tolerance를 함께 관리해야 한다.


Summary

  • Quadratic interpolation은 제한된 function information으로 line minimum을 근사하며, Armijo·Wolfe·Goldstein conditions는 exact line search를 대신한다.
  • Gradient는 level surface에 normal이고 maximum local increase direction이며, exact line search를 사용한 successive steepest-descent directions은 orthogonal하다.
  • Variable scaling은 transformed Hessian의 condition number를 줄여 first-order method의 수렴을 개선한다.
  • Newton method는 Hessian model을 사용하여 빠르게 수렴하지만 positive definiteness, linear-system solution, second derivatives가 필요하다.
  • Marquardt method는 diagonal shift로 steepest-descent behavior와 Newton behavior를 연결한다.
  • DFP와 BFGS는 secant information으로 inverse Hessian 또는 Hessian을 갱신하고 suitable conditions에서 positive definiteness와 superlinear convergence를 얻는다.
  • Hooke-Jeeves와 Nelder-Mead는 function values만으로 search geometry를 갱신하는 대표적인 direct-search methods이다.