다변수 함수(multi-variational function)의 최적화에 초점을 맞춘 내용들을 소개한다. 초점은 어떻게 국지적 모델(local model)을 사용해 어떤 수렴 조건이 만족될 때까지 설계 포인트를 점차적으로 개선해 나가는 것.

경사 상향 반복 시행

가장 일반적인 접근법은 국지적 모델을 기반으로 목적값을 최소화하는 스텝을 취함으로써 설계 포인트 $x$를 점차적으로 개선하는 방법이다. 1계 또는 2계 테일러 근사식으로부터 얻어질 수 있는데, 이러한 방법을 따르는 대표적인 방법은 descent direction method이다. 수행 순서는 아래와 같다.

1. $x^{(k)}$가 종료 조건을 만족하는지 체크한다. If True break; else continue

2. Gradient 또는 Hessian과 같은 국지적 정보를 사용해 경사 방향 $d^{(k)}$를 결정한다. 어떤 알고리즘은 $\Vert d^{(k)}\Vert=1$을 가정하지만, 항상 그런 것은 아니다.

3. 스텝 크기 또는 학습률 $\alpha^{(k)}$를 결정한다. 어떤 알고리즘은 스텝이 $f$를 최대한 감소시키고자 스텝 크기를 최적화한다.

4. 다음 설계 포인트를 다음 식에 따라 계산한다.

   $$ x^{(k+1)}\leftarrow x^{k}+\alpha^{k}d^{k} $$

라인 탐색 (Line Search)

스텝 팩터 $\alpha$를 최적화 해보자.

$$ \text{minimize}_\alpha\text{ }f(x+\alpha d) $$

# pseudo code of Julia
function line_search(f, x, d)
	objective = alpha -> f(x + alpha * d)
	a, b = bracket_minimum(objective) # 괄호법으로 대략적인 국지적 최소값의 범위를 제한
	alpha = minimize(objective, a, b) # (a,b)에서 alpha에 대해 미분을 수행
	return x + alpha * d
end

근사적 라인 탐색 (Approximate Line Search)

적당한 $\alpha$값을 찾기 위해 사용하는 아래 두 조건을 합쳐 울프 조건(Wolfe conditions)이라 한다.

아르미요 조건 (Armijo condition)

$$ af(x^{(k+1)})\leq f(x^{(k)})+\beta\alpha\nabla_{d^{(k)}}f(x^{(k)}) $$

각 스텝크기가 목적함수의 값이 충분히 감소하도록 강제하는 조건

곡률 조건 (Curvature condition)

$$ \nabla_{d^{(k)}}f(x^{(k+1)})\geq\sigma\nabla_{d^{(k)}}f(x^{(k)}) $$

다음 번의 수행에서 방향성 미분값이 더 작아지는 것을 요구하는 조건