[Convex Optimization] Convex optimization이란?

 

 

그럼 저희가 주로 다루게 될 convex optimization이란 무엇일까요?

1. Convex optimization problem

Optimization problem에서 objective function 와 inequality constraint function이 convex이고 equality constraint function이 affine 이라는 조건이 추가됩니다. 

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

 

affine 함수라는 것은 위와 같이 linear function에 상수합이 해 놓은 형태의 함수를 의미합니다. 

 

2. Convex Function

함수 \(f: \mathbf{R}^n \to \mathbf{R}\) 가 Convex function이라는 것은 정의역 \(\mathrm{dom}(f)\)이 convex set이고, 임의의 \(x, y \in \mathrm{dom}(f)\)와 임의의 \(\theta \in [0, 1]\) 에 대해 아래 부등식을 만족한다는 의미입니다. \[f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta) f(y)\]

https://www.xenonstack.com/glossary/concave-and-convex-function

예전에 고등학교 때 "아래로 볼록"이니 "위로 볼록"이니 했던 개념. 그거 맞습니다.

심화) Stricly convex와 Storngly convex

Strictly convex 

함수 \(f: \mathbf{R}^n \to \mathbf{R}\) 가 Strict convex function 이라는 것은 정의역 \(\mathrm{dom}(f)\)이 convex set이고, 임의의 \(x, y \in \mathrm{dom}(f)\) (\(x \neq y\)) 와 임의의 \(\theta \in (0, 1)\) 에 대해 아래 부등식을 만족한다는 의미입니다. \[ f(\theta x + (1-\theta)y) < \theta f(x) + (1-\theta) f(y) \]

참고로, 만약 strict convex 함수 \(f\)가 convex set \(C\) 위에서 최소값을 가진다면 그 최소값을 달성하는 점은 유일하게 존재합니다. 

Strongly convex

함수 \(f: \mathbf{R}^n \to \mathbf{R}\) 가 \(mu\)-Strong convex function 이라는 것은 정의역 \(\mathrm{dom}(f)\)이 convex set이고, 어떤 상수 \(mu>0\)에 대해 다음 조건을 만족한다는 의미입니다. 

 

정의1)

$$f(\theta x + (1-\theta)y) \le \theta f(x) + (1-\theta) f(y) - \frac{1}{2}\mu \theta (1-\theta) \|x-y\|^2$$

 

• \(mu\)는 modulus of strong convexity이며, 함수의 convex 정도를 나타낸다. \(mu > 0\)
• \(\|\cdot\|\)는 Euclidean norm, L2-norm입니다.

정의2)

 \(f − {\mu \over 2}\| x \|_{2}^{2}\) 가 convex function이면  함수 \(f\)는 strong convex이다

 

Strictly convex는 그래프에 '평평한' 부분이 없다는 것을 의미합니다. 즉, 두 점을 잇는 선분이 그래프와 겹치는 경우가 없다는 뜻이구요. Strong convex는 그래프가 최소한 '어느 정도' 굽어져있다는 것을 정량적으로 명시합니다. 

직관적으로 이해해보면 당연히도 strongly convex하면 strictly convex하겠죠? 

참고로 함수\(-f\)가 convex이면 \(f\)는 concave라고 합니다. (위로볼록 아래로 볼록 말고 오목 or 볼록이라고 하는 거네요)

 

3. Convex Set

set \(C \subseteq \mathbf{R}^n\)가 convex set이라는 것은 집합 \(C\) 내의 임의의 두 점 \(x, y \in C\)를 잇는 선분 위의 모든 점이 다시 \(C\)에 포함된다는 의미입니다.

\(\theta x + (1-\theta)y \in C\) , \(\theta \in [0, 1]\)

Convex set(Left) and non-convex set(Right) Research Gate uploaded by  Masaaki Nagahara

 

뭔가 똑같은 접두어 Convex를 썼는데 두 개의 개념이 어떻게 연관되어 있는 걸까요? 일단 Convex function을 정의할 때 정의역과 치역이 Convex set이 되어야 한다고 하긴 했는데요. 또 한 가지 측면에서 주목할 점이 있습니다. 

 

함수 \(f\)가 convex function일 필요충분조건은 그 함수의 epigraph \(\mathrm{epi}(f)\)가 convex set일 조건이다.

 

epigraph란 무엇이냐?

함수 \( f: \mathbf{R}^n \to \mathbf{R} \)의 epigraph는 함수의 그래프 위에 있거나 그래프 자체에 있는 모든 점들의 집합을 의미합니다. 이미지적으로는 함수의 그래프 위의 공간을 지칭합니다.  \[\mathrm{epi}(f) = \{ (x, t) \in \mathbf{R}^{n+1} \mid x \in \mathrm{dom}(f), f(x) \le t \}\] 

출처: wikipedia

 

학교에서 시험문제를 푸는 것이 아닌 다음에야 사실 내가 풀고자 하는 문제가 convex인지 아닌지 애매한 경우들이 있죠. 그럴 때 그게 convex optimization인지 아닌지 체크해보는 방법으로 epgraph의 convex set여부를 따져본다고 합니다. 

 

4. Convex Optimization의 특성

1) feasible set의 convexity

: convex optimization 문제에서 목적 함수 \(f_{0}\)와 부등식 제약함수 \(f_{i}\)가 convex function이고 등식 제약 함수가 affine 함수라면 feasible set은 항상 convex set이 된다. 

 

2) Nice property of convex optimization problems

Convex 함수의 local minimum은 항상 global minimum이다.

 

증명은

https://convex-optimization-for-all.github.io/contents/chapter01/2021/01/28/01_02_convex_optimization_problem/

01-02 Convex optimization problem · 모두를 위한 컨벡스 최적화

를 참고하시면 좋을 것 같습니다. 

 

결과적으로 Convex optimization 의 특성 덕분에 non-convex문제에 비해서 효율적이고 안정적으로 해결할 수 있습니다. Linear programming, Quadratic Programming, Conic Programming 등은 모두 convex optimization 문제의 special case입니다.