[Convex Optimization] Optimization이란?

 

안녕하세요? 요번 포스팅 부터는 Stephen Boyd 교수님의 convex optimization 교재의 중요 내용을 정리해보도록 하겠습니다. 

"수학적인" 최적화 문제는 아래와 같이 나타낼 수 있습니다. 

 

$$ \begin{array}{ll} \text{minimize} & f_0(x) \\ \text{subject to} & f_i(x) \le 0, \quad i=1, \dots, m \\ & h_j(x) = 0, \quad j=1, \dots, p \end{array} $$

 

이 정의식의 각 요소는 아래와 같은 의미를 갖습니다. 

1) \(x = (x_1, \dots, x_n)\): 최적화하려는 변수(optimization variable) 벡터입니다. \(x \in \mathbf{R}^n\)

2) \(f_0: \mathbf{R}^n \to \mathbf{R}\) : 목적 함수(objective function)또는 비용 함수(cost function)를 나타냅니다. 

3) \(f_i: \mathbf{R}^n \to \mathbf{R}\), \(i=1, \dots, m\): 부등식 제약 함수(inequality constraint functions)을 나타냅니다. 이 함수들은 부등식 제약조건 \(f_i(x) \le 0\) 을 정의합니다. 

4) \(h_j: \mathbf{R}^n \to \mathbf{R}\), \(j=1, \dots, p\): 등식 제약 함수(equality constraint functions)를 나타냅니다. 이 함수들은 등식 제약조건 \(h_j(x) = 0\)을 정의합니다. 

 

이 때 최저화 문제의 정의역 (\( \mathcal{D} \))는 목적함수와 모든 제약 함수들의 교집합입니다. 

$$ \mathcal{D} = \mathrm{dom}(f_0) \cap \bigcap_{i=1}^m \mathrm{dom}(f_i) \cap \bigcap_{j=1}^p \mathrm{dom}(h_j) $$

 

주어진 모든 제약 조건을 만족하는 점 \(x \in \mathcal{D}\)를 실현가능한 해(feasible point)라고 합니다. 즉 \(f_i(x) \le 0\), \(h_j(x) = 0\) 를 만족한 \(x\)를 말합니다. 그리고 모든 실현 가능 해들의 집합을 feasible set이라고 합니다. 

 

목적 함수 \(f_0\)가 실현 가능 집합 내에서 가질 수 있는 최소값을 optimal value라고 합니다. 그리고 이것을 달성하도록 하는 feasible 해 \(x^{*}\)를 최적 해 (optimal point)라고 합니다. 모든 최적 해들의 집합을 최적해 집합이라고 합니다. 일반적으로 우리가 다루는 문제들은 이 중에서도 "Convex Optimiation"문제에 집중되어 있다고 할 수 있겠죠. 이 내용은 다음 포스팅에서 이어집니다.