7.114 볼록 집합과 볼록 함수의 정의

1. 볼록 집합의 정의

집합 $\mathcal{C} \subseteq \mathbb{R}^n$ 이 볼록(convex)이란, 집합 내의 임의의 두 점 $\mathbf{x}, \mathbf{y} \in \mathcal{C}$ 를 잇는 선분이 전체가 $\mathcal{C}$ 에 포함되는 것을 의미한다.

$\theta \mathbf{x} + (1 - \theta)\mathbf{y} \in \mathcal{C}, \quad \forall \theta \in [0, 1]$

기하학적으로 볼록 집합은 “움푹 들어간 부분이 없는” 집합이다. 공집합, 단일점, 직선, 반공간, 초평면은 모두 볼록 집합이다.

2. 볼록 집합의 예

초평면(hyperplane): $\{\mathbf{x} : \mathbf{a}^T\mathbf{x} = b\}$

반공간(halfspace): $\{\mathbf{x} : \mathbf{a}^T\mathbf{x} \leq b\}$

다면체(polyhedron): 유한 개의 반공간의 교집합 $\{\mathbf{x} : \mathbf{A}\mathbf{x} \leq \mathbf{b}\}$

타원체(ellipsoid): $\{\mathbf{x} : (\mathbf{x} - \mathbf{c})^T\mathbf{P}^{-1}(\mathbf{x} - \mathbf{c}) \leq 1\}$ , $\mathbf{P} \succ 0$

노름 공(norm ball): $\{\mathbf{x} : \lVert \mathbf{x} - \mathbf{c} \rVert \leq r\}$

양의 반정치 행렬의 원추: $\mathbb{S}_+^n = \{\mathbf{X} \in \mathbb{S}^n : \mathbf{X} \succeq 0\}$

3. 볼록 집합의 보존 연산

볼록 집합에 대한 다음의 연산은 볼록성을 보존한다.

교집합: 볼록 집합들의 교집합은 볼록이다.
아핀 사상: $\mathcal{C}$ 가 볼록이면 $f(\mathcal{C}) = \{f(\mathbf{x}) : \mathbf{x} \in \mathcal{C}\}$ 도 볼록이다 ( $f$ 가 아핀일 때).
스케일링과 이동: $\alpha\mathcal{C} + \mathbf{b}$ 는 볼록이다.
민코프스키 합: $\mathcal{C}_1 + \mathcal{C}_2 = \{\mathbf{x} + \mathbf{y} : \mathbf{x} \in \mathcal{C}_1, \mathbf{y} \in \mathcal{C}_2\}$ 는 볼록이다.

4. 볼록 함수의 정의

함수 $f: \mathbb{R}^n \to \mathbb{R}$ 이 볼록(convex)이란, 정의역이 볼록 집합이고 다음의 부등식이 성립하는 것이다.

$f(\theta \mathbf{x} + (1 - \theta)\mathbf{y}) \leq \theta f(\mathbf{x}) + (1 - \theta)f(\mathbf{y}), \quad \forall \mathbf{x}, \mathbf{y} \in \text{dom}(f), \; \forall \theta \in [0, 1]$

기하학적으로 함수의 그래프 위의 임의의 두 점을 잇는 선분(할선)이 그래프의 위에 놓인다. 엄격 볼록(strictly convex)은 $\theta \in (0, 1)$ 이고 $\mathbf{x} \neq \mathbf{y}$ 일 때 부등식이 엄격히 성립하는 경우이다.

$-f$ 가 볼록이면 $f$ 를 오목(concave)이라 한다.

5. 미분 가능 함수의 볼록성 판정

5.1 차 조건

$f$ 가 미분 가능하면, $f$ 가 볼록일 필요 충분 조건은 다음이다.

$f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x}), \quad \forall \mathbf{x}, \mathbf{y}$

이는 함수의 그래프가 모든 점에서의 접선(또는 접평면) 위에 놓임을 의미한다.

5.2 차 조건

$f$ 가 두 번 미분 가능하면, $f$ 가 볼록일 필요 충분 조건은 다음이다.

$\nabla^2 f(\mathbf{x}) \succeq 0, \quad \forall \mathbf{x}$

헤시안이 모든 점에서 양의 반정치이면 볼록이다. $\nabla^2 f(\mathbf{x}) \succ 0$ 이면 강볼록이다.

6. 볼록 함수의 예

아핀 함수: $f(\mathbf{x}) = \mathbf{a}^T\mathbf{x} + b$ (볼록이면서 동시에 오목)

이차 함수: $f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x} + \mathbf{c}^T\mathbf{x}$ ( $\mathbf{H} \succeq 0$ 일 때 볼록)

노름: $f(\mathbf{x}) = \lVert \mathbf{x} \rVert$ (임의의 노름은 볼록)

최대값 함수: $f(\mathbf{x}) = \max(x_1, \ldots, x_n)$

로그-합-지수: $f(\mathbf{x}) = \log(\sum_i e^{x_i})$

7. 볼록 함수의 보존 연산

비음 가중 합: $f_i$ 가 볼록이고 $w_i \geq 0$ 이면 $\sum_i w_i f_i$ 는 볼록이다.
최대값: $f_i$ 가 볼록이면 $f(\mathbf{x}) = \max_i f_i(\mathbf{x})$ 는 볼록이다.
아핀 합성: $f$ 가 볼록이면 $g(\mathbf{x}) = f(\mathbf{A}\mathbf{x} + \mathbf{b})$ 도 볼록이다.
상위 그래프: $f$ 가 볼록일 필요 충분 조건은 상위 그래프 $\text{epi}(f) = \{(\mathbf{x}, t) : f(\mathbf{x}) \leq t\}$ 가 볼록 집합인 것이다.

8. 강볼록 함수

$f$ 가 강볼록(strongly convex)이란, 매개변수 $\mu > 0$ 이 존재하여 $f(\mathbf{x}) - \frac{\mu}{2}\lVert \mathbf{x} \rVert^2$ 가 볼록인 것이다. 동치 조건으로 $\nabla^2 f(\mathbf{x}) \succeq \mu\mathbf{I}$ 이다. 강볼록 함수는 유일한 최소점을 가지며, 경사 하강법의 선형 수렴이 보장된다.

9. 로봇 공학에서의 볼록 구조

로봇 최적화에서 볼록성의 식별은 전역 최적해의 존재를 보장하고 효율적 알고리즘의 적용을 가능하게 하므로 매우 중요하다. 전신 운동 제어의 QP, 선형화된 MPC, 최소 노름 역기구학 등이 볼록 최적화에 해당하며, 이들 문제에서 전역 최적해를 신뢰성 있게 구할 수 있다.

10. 참고 문헌

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Rockafellar, R. T. (1970). Convex Analysis. Princeton University Press.
Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Springer.
Bertsekas, D. P. (2009). Convex Optimization Theory. Athena Scientific.

version: 1.0