[Convex Optimization] Convex 함수의 특성

 

1. Epigraph characterization

\(f\)가 convex이면 그 epigraph는 convex set이고 그 역도 성립합니다. (이전 포스팅에서 살펴본 내용이죠?)

\(f\) is convex \( \iff epi(f) = \{(x,t) \in \mathbb{R}^{n+1} \mid x \in \text{dom} f, f(x) \le t \} \)

 

2. Convex sublevel sets

함수 \(f\)가 convex이면 그 sublevel set도 convex입니다. 

 

하위 준위 집합(sublevel sets)는 함수가 특정 값보다 작거나 같은 값을 가지는 모든 입력(변수)들의 집합을 의미합니다. 이는 함수의 특정 "높이" 아래에 있는 정의역의 모든 점들을 모아 놓은 것입니다. 함수 \(f: \mathbf{R}^n \to \mathbf{R} \)와 어떤 상수 \( \alpha \in \mathbf{R} \)가 주어졌을 때 \(f\)의 \(\alpha\)-sublevel set은 다음과 같이 정의됩니다. 

$$C_\alpha = \{x \in \mathrm{dom}(f) \mid f(x) \le \alpha\}$$

 

3. First-order characterization

함수가 미분 가능하다는 가정을 추가했을 때, convexity를 도함수(gradient)의 속성을 통해 정의하는 방법입니다. convex function의 그래프가 그 어떤 접선(tangent line 또는 tangent hyperplane)보다 항상 위에 있거나 겹쳐진다는 기하학적 직관을 제공합니다.

 

함수 \(f: \mathbf{R}^n \to \mathbf{R} \)가 미분 가능하고 그 정의역 dom(\(f\))이 convex set이라고 할 때, 

\(f\) is convex \( \iff \) dom(\(f\)) 내의 임의의 두 점 \(x, y\)에 대해 \(f(y) \ge f(x) + \nabla f(x)^T (y-x)\)

 

https://math.stackexchange.com/questions/1518550/geometric-interpretation-of-first-order-condition

 

4. Second-order characterization

함수가 두 번 미분 가능할 때, 그 convexity를 Hessian matrix의 성질을 통해 판별하는 방법입니다. 이는 함수의 굽힘(curvature)을 정량적으로 파악하여 convexity를 확인하는 방법이라고 할 수 있겠습니다. 

 

함수 \(f: \mathbf{R}^n \to \mathbf{R} \)가 2번 미분 가능하고 그 정의역 dom(\(f\))이 convex set이라고 할 때, dom(\(f\)) 내의 모든 점 \(x\)에 대해 그 Hessian Matrix(\( \nabla^2 f(x) \))가 Positive semidefinite(PSD) 이라면 이 함수 \(f\)는 convex이고 그 역도 성립한다. 

$$ f \text{ is convex} \iff \nabla^2 f(x) \succeq 0 \quad \text{for all } x \in \mathrm{dom}(f) $$

 

Hessian matrix는 모든 second-order partial derivatives로 이루어진 정사각행렬입니다. $$(\nabla^2 f(x))_{ij} = \frac{\partial^2 f(x)}{\partial x_i \partial x_j}$$

matrix가 positive semidefinite 라는 것은 임의의 벡터 \(v \in \mathbf{R}^{n}\)에 대해  $$v^T \nabla^2 f(x) v \ge 0$$ 을 만족한다는 것을 의미합니다. 

 

저번 포스팅에서 Strict convex와 Strong convex에 대해서 알아봤었죠? 

함수 \(f: \mathbf{R}^n \to \mathbf{R} \)가 2번 미분 가능하고 strict convex일 필요충분 조건은 dom(\(f\)) 내의 모든 점 \(x\)에 대해 그 Hessian Matrix가 Positive definite(PD)이라는 것 입니다. 

$$\nabla^2 f(x) \succ 0 \quad \text{for all } x \in \mathrm{dom}(f)$$

이는 임의의 non-zero vector \(v \neq 0\)에 대해 \(v^T \nabla^2 f(x) v > 0\) 임을 의미합니다. 

 

함수 \(f: \mathbf{R}^n \to \mathbf{R} \)가 2번 미분 가능하고 \(\mu\)- strong convex일 필요충분 조건은 dom(\(f\)) 내의 모든 점 \(x\)에 대해 그 Hessian Matrix가 아래 조건을 만족한다는 뜻입니다. 

$$\nabla^2 f(x) \succeq \mu I \quad \text{for all } x \in \mathrm{dom}(f)$$

이는 임의의 vector \(v \in \mathbf{R}^{n} \)에 대해 \(v^T \nabla^2 f(x) v \ge \mu \|v\|^2\)  임을 의미합니다. 

 

5. Jensen's Inequality

이거 많이 봤던 부등식이네요. 확률론에서도 증명에 자주 동원되는..!

Convex 함수 내부에서 평균을 취하는 것보다 평균을 취한 후에 convex 함수를 적용하는 것이 더 작거나 같다는 의미입니다. (concave일 경우에는 부등호의 방향이 반대로 바뀝니다)

 

이 부등식은 입력의 형태에 따라서 다르게 표기할 수 있는데요, 본질은 같습니다. 

 

1) Discrete한 형태의 표기

함수 \(f\)가 convex함수이고 \(x_{1}, x_{2}, \dots, x_{n}\)이 \(f\)의 정의역 내에 있는 점들이며 \(\theta_{1}, \theta_{2}, \dots, \theta _{n}\) 이 \(\sum_{i=1}^n \theta_i = 1\) 조건을 만족하는 양의 weight \(\theta_{i} \ge 0 \)라고 하면 

$$f \left( \sum_{i=1}^n \theta_i x_i \right) \le \sum_{i=1}^n \theta_i f(x_i)$$

https://www.sciencedirect.com/topics/computer-science/jensen-inequality

2) 확률공간에서의 표기

함수 \(f\)가 convex 함수이고, \(X\)가 \(f\)의 정의역 내의 값을 가지는 확률 변수라고 하면 Jensen 부등식은 아래와 같습니다. 

$$f(E[X]) \le E[f(X)]$$

 

참고)

\(\ge\)는 우리가 일상적으로 사용하는 "숫자의 대소 비교"와 같은 의미를 가지는 반면, \(\succeq\)는 주로 행렬의 특성(PSD)이나 더 추상적인 순서 관계를 표현할 때 사용되는 기호라고 생각하시면 됩니다. 

 

---

Convextity를 유지하는 연산은 아래와 같습니다. 

1. Nonnegative linear combination

convex함수에 음수가 아닌 임의의 수를 곱하여 만들어진 함수도 convex이며

$$ f \text{ is convex} \quad \Rightarrow \qquad \alpha f \text{ is convex} \qquad (\alpha \ge 0) $$ 

convex 함수들의 음이 아닌 가중합 역시 convex

$$ f_1, \dots, f_n \text{ are convex} \qquad \Rightarrow \qquad \alpha_1 f_1 + \cdots + \alpha_n f_n \text{ is convex} \quad (\alpha_1, \dots, \alpha_n \ge 0) $$

 

2. 합성(Composition)

함수 \(f(x) = h(g(x))\) 의 형태로 합성될 때 볼록성이 유지되는 조건은 h와 g의 볼록성뿐만 아니라, \(h\)의 단조성(monotonicity)과 \(g\)의 convex/concave에 따라 달라집니다.

3. Pointwise maximum and supremum

4. Minimization function

5. Perspective function