1. Convex Optimization

Convex Sets

집합 $X \subseteq \mathbb{R}^d$가 convex 하려면, 임의의 $u, v \in X$와 $\lambda \in [0, 1]$에 대해 다음을 만족해야 합니다:

$$
\lambda u + (1 - \lambda) v \in X
$$

즉, 두 점을 잇는 선분이 전부 집합 내에 포함되어야 합니다.

Examples of Convex Sets

1. Empty set 및 Singletons (공집합 및 싱글톤 집합 ${v}$)
2. Norm ball: 노름 공은 중심이 $c$이고 반지름이 $r$인 공으로 정의되며, 다음과 같습니다:
   $$
   {x \in \mathbb{R}^d : |x - c| \leq r}
   $$
3. Ellipsoid: 타원체는 중심이 $c$이고, 양의 정부호 행렬 $P$를 사용하는 타원체로 정의되며, 다음과 같습니다:
   $$
   {x \in \mathbb{R}^d : (x - c)^T P (x - c) \leq 1}
   $$
4. Hyperplane: 초평면은 다음과 같이 정의됩니다:
   $$
   {x \in \mathbb{R}^d : a^T x = b}
   $$
   여기서 $a \in \mathbb{R}^d$, $b \in \mathbb{R}$입니다.
5. Half-space: 반공간은 다음과 같이 정의됩니다:
   $$
   {x \in \mathbb{R}^d : a^T x \leq b}
   $$
   여기서 $a \in \mathbb{R}^d$, $b \in \mathbb{R}$입니다.
6. Polyhedron: 유한한 반공간의 교집합으로 정의되며, 다음과 같습니다:
   $$
   {x \in \mathbb{R}^d : Ax \leq b}
   $$
   여기서 $A \in \mathbb{R}^{m \times d}$, $b \in \mathbb{R}^m$입니다.
7. Polytope: bounded된 polyhedron으로, 유한 벡터 집합의 convex hull로 정의됩니다.
8. Simplex: 단순체는 다음과 같이 정의됩니다:
   $$
   {x \in \mathbb{R}^d : 1^T x = 1, x \geq 0}
   $$
   이는 $e_1, e_2, \dots, e_d$의 convex hull과 동일합니다.
9. Nonnegative orthant: 비음수 직교좌표계는 다음과 같이 정의됩니다:
   $$
   \mathbb{R}^d_+ = {x \in \mathbb{R}^d : x \geq 0}
   $$
10. Positive orthant: 양의 직교좌표계는 다음과 같이 정의됩니다:
    $$
    \mathbb{R}^d_{++} = {x \in \mathbb{R}^d : x > 0}
    $$
11. Norm cone: 노름 원뿔은 다음과 같이 정의됩니다:
    $$
    {(x, t) \in \mathbb{R}^d \times \mathbb{R} : |x| \leq t}
    $$
12. Positive semidefinite cone: 양의 준정규 행렬의 원뿔입니다.

Convex Functions

함수 $f : \mathbb{R}^d \to \mathbb{R}$가 convex 하려면, 정의역이 convex하고, 모든 $x, y \in \text{dom}(f)$에 대해 다음을 만족해야 합니다:

$$
f(\lambda x + (1 - \lambda) y) \leq \lambda f(x) + (1 - \lambda) f(y), \quad 0 \leq \lambda \leq 1
$$

즉, 두 점 $x$와 $y$ 사이의 점에서 함수 $f$의 값은 $f(x)$와 $f(y)$를 잇는 직선보다 작거나 같습니다.

Examples of Convex Functions

1. Exponential function: 지수 함수 $e^{ax}$는 $a \in \mathbb{R}$일 때 convex입니다.
2. Power function: 제곱 함수 $x^a$는 $a \geq 1$일 때 convex이고, $a < 0$일 때 $x > 0$에서 convex입니다.
3. Logarithm: 로그 함수 $\log x$는 $x > 0$에서 concave입니다.
4. Negative entropy: 음의 엔트로피 $x \log x$는 $x > 0$에서 convex입니다.
5. Linear function: 선형 함수 $a^T x + b$는 convex이면서 concave입니다.
6. Quadratic function: 이차 함수 $\frac{1}{2} x^T A x + b^T x + c$는 $A \succeq 0$일 때 convex입니다.
7. Least squares loss: 최소 제곱 손실 $|b - A x|_2^2$는 모든 $A$에 대해 convex입니다.
8. Norm: 모든 노름 $|\cdot|$는 convex입니다.
9. Maximum eigenvalue of a symmetric matrix: 대칭 행렬의 최대 고유값은 convex입니다.

Operations Preserving Convexity

다음 연산들은 convex성을 유지하는 특징이 있습니다:

Set Operations

1. Intersection: convex 집합들의 교집합은 convex입니다.
2. Scaling: $C$가 convex이고, $\alpha \in \mathbb{R}$일 때, $\alpha C = {\alpha x : x \in C}$는 convex입니다.
3. Minkowski sum: convex 집합 $C_1, C_2, \dots, C_k$의 Minkowski 합 $C_1 + \cdots + C_k = {x_1 + \cdots + x_k : x_i \in C_i}$는 convex입니다.
4. Cartesian product: convex 집합들의 데카르트 곱 $C_1 \times \cdots \times C_k = {(x_1, \dots, x_k) : x_i \in C_i}$는 convex입니다.
5. Affine image: convex 집합 $C$와 행렬 $A \in \mathbb{R}^{p \times d}, b \in \mathbb{R}^p$에 대해, affine 변환 $f(x) = A x + b$의 이미지 $f(C) = {A x + b : x \in C}$는 convex입니다.
6. Inverse affine image: affine 변환 $f(x) = A x + b$의 역상 $f^{-1}(C) = {x : A x + b \in C}$는 convex입니다.

Function Operations

1. Nonnegative weighted sum: $f_1, f_2, \dots, f_k : \mathbb{R}^d \to \mathbb{R}$가 convex 함수일 때, $\alpha_1 f_1 + \cdots + \alpha_k f_k$는 $\alpha_1, \dots, \alpha_k \geq 0$일 때 convex입니다.
2. Maximum of convex functions: convex 함수들의 최대값 $\max_{\gamma \in \Gamma} f_\gamma$는 convex입니다.
3. Minimizing out variables: $g(x, y)$가 convex 함수이고 $C$가 convex 집합일 때, $f(x) = \inf_{y \in C} g(x, y)$는 convex입니다.
4. Perspective function: $g(x)$가 convex 함수일 때, $f(x, t) = t g(x/t)$는 convex입니다.
5. Affine composition: $g : \mathbb{R}^p \to \mathbb{R}$가 convex이고, $A \in \mathbb{R}^{p \times d}, b \in \mathbb{R}^p$일 때, $f(x) = g(Ax + b)$는 convex입니다.
6. Composition: $h : \mathbb{R} \to \mathbb{R}$가 convex이고 비감소 함수일 때, $f = h \circ g$는 convex입니다.

Convex Optimization

Convex 최적화 문제는 convex 함수 $f$를 convex 집합 $C$ 위에서 최소화하는 문제입니다:

$$ \text{Minimize} \quad f(x) \quad \text{subject to} \quad x \in C $$

정확한 해를 구하기 어려울 때, $\epsilon$-optimal solution을 찾는 것이 목표입니다. 즉, 주어진 허용 오차 $\epsilon > 0$에 대해 다음을 만족하는 $x$를 찾습니다:

$$
f(x) \leq \min_{x \in C} f(x) + \epsilon
$$

First- and Second-Order Characterizations of Convex Functions

convex 함수의 특성을 1차 및 2차 미분으로 나타낼 수 있습니다. 이 절에서는 convex 함수의 1차 및 2차 미분을 이용한 특징들을 정리합니다.

First-Order Characterization (1차 미분을 이용한 특성)

함수 $f : \mathbb{R}^d \to \mathbb{R}$가 convex일 필요충분조건은 함수가 미분 가능하고, 다음 부등식을 만족하는 것입니다:

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

즉, 함수 $f$의 값은 모든 $x$에서 $f$의 접평면 위에 위치해야 합니다. 이는 함수가 한 점에서의 기울기와 접평면으로 다른 점들의 값을 예상할 수 있음을 의미합니다.

(1차 미분을 이용한 convex 함수의 특성)

$f : \mathbb{R}^d \to \mathbb{R}$가 미분 가능하다고 가정할 때, $f$가 convex일 필요충분조건은 다음과 같습니다:

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

ㄴ

Second-Order Characterization (2차 미분을 이용한 특성)

함수 $f$의 이차 미분인 Hessian 행렬 $\nabla^2 f(x)$을 이용하여 convex성을 판단할 수 있습니다.

Hessian Matrix (헤시안 행렬)

함수 $f : \mathbb{R}^d \to \mathbb{R}$가 2번 미분 가능할 때, 헤시안 행렬은 다음과 같이 정의됩니다:

$$
\nabla^2 f(x) = \begin{pmatrix}
\frac{\partial^2 f}{\partial x_1^2}(x) & \cdots & \frac{\partial^2 f}{\partial x_1 \partial x_d}(x) \
\vdots & \ddots & \vdots \
\frac{\partial^2 f}{\partial x_d \partial x_1}(x) & \cdots & \frac{\partial^2 f}{\partial x_d^2}(x)
\end{pmatrix}
$$

헤시안 행렬은 함수의 곡률을 나타내며, 모든 2차 미분이 연속이면 대칭 행렬이 됩니다.

(2차 미분을 이용한 convex 함수의 특성)

$f : \mathbb{R}^d \to \mathbb{R}$가 2번 미분 가능하다고 가정할 때, $f$가 convex일 필요충분조건은 다음을 만족하는 것입니다:

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

즉, 함수 $f$의 헤시안 행렬이 양의 준정부호(positive semidefinite)일 때 $f$는 convex입니다.

Example

다음은 convex 함수의 예시입니다:

• Quadratic function: 함수 $f(x) = \frac{1}{2} x^T A x + b^T x + c$는 $A \succeq 0$일 때 convex입니다.