[Optimization] Optimization of Univariate Functions 일변량 함수 최적화 정리 / 설명

Optimization of Univariate Functions

이 글에선, 추후 Univariate function optimization 알고리즘을 설명하기 앞서 알고리즘이 설정하는 상황을 설명하고자 한다.

한국어로 일변수 함수 최적화인 Univariate function optimization은 인풋받는 변수의 형태가 univariate이고 아웃풋의 형태가 scalar인 함수의 최솟값 혹은 최댓값을 찾는 문제이다. 본문에선 이 문제를 풀기위해 설정하는 구체적 가정을 설명한다.

---

• 가정

  • 함수

    • f is a univariate real fuction

    • $f: D \subset \mathbb{R} \rightarrow \mathbb{R}$

    • that has only one exact minimizer

    • $x^{*} = argmin_{x\in D}f(x)$

    • 즉, 하나의 최소값을 가지는 strictly convex한 univariate scalar 함수

  • 데이터

    • $D = [a,b]$ for some constants $a,b \in \mathbb{R}$

---

• 하고자 하는 것

  • $|\hat{x}-x^{*}| < \epsilon$

  • 위 조건을 만족하는 approximated minimizer $\hat{x}$ 찾기

  • $\hat{x}$을 찾기 위한 방법: Iterative algorithm

    • for a sequence $\{x_{n}\}_{n\geq 1}$ in $D$ that satisfies

    • $\exists n \in \mathbb{N} s.t. |x_{n}-x^{*}|<\epsilon$

    • 위 조건을 만족하는 $x_{n}$을 $\hat{x}$로 설정

    • $x_{n}=\hat{x}$

---

정리하면, 설정한 상황은 strictly convex한 함수 $f(x)$의 유일한 최솟값 $x^{*}$가 존재할 때, 이 최솟값을 approximate 하는 추정값 $\hat{x}$를 iterative algorithm을 이용해 구하는 것이다.