[Convex Optimization#1] Optimization Problem과 Convex Optimization

Optimization Problem이란?

최적화 문제(optimization problem)는 한 줄로 요약하면 여러 후보 중에서 가장 좋은 값을 찾는 문제다. ML에서는 cost function을 최소화하는 파라미터를 찾는 것이 곧 최적화 문제가 된다. linear regression의 MSE를 줄이든, cross-entropy loss를 줄이든, 결국 하고 있는 일은 optimization이다. 

 

Standard From

수학적으로 optimization problem은 다음과 같은 표준형(standard form)으로 쓴다.

 

$$\begin{aligned}
\min_{x \in D} \quad & f(x) \\
\text{subject to} \quad & g_i(x) \leq 0, \quad i = 1, \dots, m, \\
& h_j(x) = 0, \quad j = 1, \dots, r
\end{aligned}$$

 

각 구성 요소를 정리하면

 

• $x \in \mathbb{R}^n$: optimization variable: 우리가 최적의 값을 찾고자 하는 변수다.
• $f: \mathbb{R}^n \to \mathbb{R}$: objective function(또는 cost function): 이걸 최소화하는 게 목표다.
• $g_i$: inequality constraint: "이 조건 이하여야 한다"는 제약(constraint).
• $h_j$: equality constraint: "이 조건을 정확히 만족해야 한다"는 제약.

 

모든 제약조건을 만족하는 영역을 feasible domain이라 하고, 그 안에서 $f$를 최소화하는 $x$를 $x^*$, 즉 optimal solution이라 부른다. 

 

Explicit vs Implicit Constraints

제약조건은 두 종류로 나뉜다.

 

Explicit constraint

문제에 직접 명시된 제약이다. 위 standard form의 $g_i$, $h_j$가 이에 해당한다. explicit constraint가 아예 없는 문제를 unconstrained problem이라 부른다.

 

Implicit constraint

명시하지 않아도 함수의 정의역에서 자연스럽게 따라오는 제약이다. 모든 함수 $(f, g_i, h_j)$의 정의역의 교집합으로 결정된다.

 

$$D = \operatorname{dom}(f) \cap \bigcap_{i=1}^{m} \operatorname{dom}(g_i) \cap \bigcap_{j=1}^{r} \operatorname{dom}(h_j)$$

 

예를 들어 $\min \log(x)$라는 문제가 있으면, $log$의 정의역이 $x > 0$이므로 $x > 0$이 implicit constraint가 된다. 이걸 explicit하게 쓰면 아래와 같다.

 

$$\begin{aligned}
\min \quad & \log(x) \\
\text{subject to} \quad & x > 0
\end{aligned}$$

 

optimization  problem은 거의 모든 분야에 등장한다. 몇 가지 예시를 보면

 

• protfolio optimization: 각 자산에 대한 투자 비중(variable)을 정하고, 예산이나 최소 수익 같은 제약(constraint) 하에서 위험도(objective)를 최소화한다.
• Model fitting: 모델 파라미터(variable)를 조절해서, 파라미터에 대한 사전 정보 같은 제약(constraint) 하에서 예측 오차(objective)를 최소화한다. 

 

여기까지가 일반적인 optimization problem의 틀이다. 문제는, 이 일반적인 형태는 풀기가 매우 어렵다는 것이다. objective function이 울퉁불퉁하면 local minimum에 빠지기 쉽고, 제약조건의 형태에 따라 feasible domain이 복잡해질 수 있다. 그래서 등장한 것이 convex optimization이다.

 

---

 

Convex Optimization Problem

convex optimization은 일반적인 optimization problem에 구조적 제약을 추가한 특수한 형태다. standard form은 동일하지만 다음 조건이 붙는다.

 

• objective function $f$가 convex function이다.
• inequality constraint $g_i$가 모두 convex function이다.
• equality constraint $h_j$가 모두 affine function이다.

 

affine function은 $h_j(x) = a^T_jx + b_j$ 형태, 즉 linear function에 상수를 더한 것이다. 

 

그렇다면 convex function이란 뭘까? 이걸 이해하려면 convex set부터 시작해야 한다.

 

Convex Set

집합 $C$ 안의 임의의 두 점 $x_1, x_2$를 잇는 선분이 다시 $C$에 포함되면, $C$를 convex set이라 한다.

 

두 점 사이의 선분은 다음과 같이 정의된다.

 

$$x = \theta x_1 + (1 - \theta)x_2, \quad 0 \leq \theta \leq 1$$

 

따라서 convex set의 조건은

 

$$x_1, x_2 \in C, \quad 0 \leq \theta \leq 1 \implies \theta x_1 + (1-\theta)x_2 \in C$$

 

직관적으로, 집합 안의 아무 두 점을 골라서 직선으로 이어도 그 직선이 집합 바깥으로 나가지 않으면 convex set이다. 원, 타원, 직사각형 같은 도형이 convex ste이고, 초승달이나 별 모양처럼 오목하게 파인 부분이 있는 도형은 non-convex이다.

 

출처: https://medium.com/@heliyahasani/1-convex-sets-and-functions-modern-optimization-techniques-687736d78f80

 

Convex Function

$f: \mathbb{R}^n \to \mathbb{R}$이 convex function이려면 두 가지 조건을 만족해야 한다.

 

• $\text{dom}(f)$d이 convex set이다.
• 임의의 $x, y \in \text{dom}(f)$와 $ 0 \leq \theta \leq 1$에 대해:

$$f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y)$$

 

 

이 부등식의 가하학적 의미가 핵심이다. 좌변은 $x$와 $y$ 사이의 한 점에서의 함수값이고, 우변은 $f(x)$와 $f(y)$를 잇는 직선 위의 값이다. 즉 그래프 위 임의의 두 점을 잇는 성분이 항상 그래프보다 위에 있다는 뜻이다. 아래로 볼록한 그릇 모양을 떠올리면 된다.

 

출처: https://thedatacopywriter.substack.com/p/what-is-a-convex-function

 

Convex set과 Convex Function의 관계: Epigraph

convex function과 convex set은 epigraph를 통해 연결된다. epigraph(epi = above)는 말 그대로 함수 그래프의 위쪽 영역을 모아놓은 집합이다. 

 

$$\operatorname{epi}(f) = \{ (x, t) \in \mathbb{R}^{n+1} \mid x \in \operatorname{dom}(f), f(x) \leq t \}$$

 

출처: https://ocw.mit.edu/courses/6-253-convex-analysis-and-optimization-spring-2012/be0c57671f3f5058c20fdbf7bf5ecdb8_MIT6_253S12_lec02.pdf

 

즉 $f$가 convex function이면 $\text{epi}(f)$는 convex set이고, 역도 성립한다. 함수가 convex인지 판별하는 문제를 집합이 convex인지 판별하는 문제로 바꿀 수 있다는 뜻이다.

 

Convex Optimization의 핵심 성질: Local = Global

convex optimization이 강력한 이유는 단 하나의 성질에 있다.

$f$가 convex이고 $x$가 local minimum이면, $x$는 global minimum이다.

 

non-convex 함수에서는 local minimum이 여러 개 존재할 수 있어서, gradient descent가 어떤 곳에서 출발하는야에 따라 다른 해에 도달한다. 하지만 convex 함수에서는 local minimum이 곧 global minimum이므로, 어디서 시작하든 같은 최적해에 수렴한다.

 

증명

 

convex function $f$에 대해 $x$가 locally optimal이지만 globaly optimal이 아니라고 가정하자. globally optimal point를 $y$라 하면, $f(y) < f(x)$이고, local minimum이므로 $\lVert y - x \rVert_2 > \rho$ (euclidian distance: $L_2$ norm) (어떤 양수 $\rho$에 대해)이다.

 

$\theta = \frac{\rho}{\lVert y - x \rVert_2}$로 놓고 $z = \theta y + (1 - \theta)x$를 만들면:

1. $z$는 두 feasible point의 convex combination이므로 feasible하다.
2. $\lVert z - x \rVert_2 = \theta \lVert y - x \rVert_2 = \frac{\rho}{2} < \rho$이므로 $z$는 $x$의 $\rho-$근방에 있다.
3. convexity에 의해 $f(z) \leq \theta f(y) + (1-\theta)f(x) < f(x)$이다.

 

2번과 3번을 합치면, $x$의 근방 안에 $f$값이 더 작은 $z$가 존재한다. 이는 $x$가 local minimum이라는 가정에 모순이다. 따라서 local minimum은 곧 global minimum이다. 

 

Convex Combination

증명에서 등장한 convex combination도 정리해두자,. $x_1, \cdots, x_k$에 대한 convex combination은 아래와 같다.

 

$$x = \theta_1 x_1 + \theta_2 x_2 + \cdots + \theta_k x_k, \quad \theta_1 + \cdots + \theta_k = 1, \quad \theta_i \geq 0$$

 

linear combination에 "계수가 양수이고 합이 1"이라는 조건이 붙은 것이다. 이전 선형대수 포스팅에서 다뤘던 linear combination의 특수한 경우로 볼 수있다. convex set $D$의 원소들에 대한 convex combination은 항상 다시 $D$에 속한다. 

 

---

 

ML에서 대부분의 학습은 non-convex optimizaiton이다. 딥러닝의 loss landscape는 수많은 local minimum와 saddle point가 존재하는 non-convex 함수이다. 그럼에도 convex optimization을 공부하는 이유가 있다. 첫째, convex optimization은 non-convex 문제를 이해하기 위한 기초 지식이다. gradient descent, constraint의 처리, duality 같은 개념이 모두 여기서 출발한다. 둘째, 실제로 convex인 문제도 많다. linear regression의 MSE, logistic regression의 cross-entropy는 모델이 파라미터에 대해 선형(또는 단일 sigmoid)이기 때문에 convex optimziation이 된다. 셋째, non-convex 문제를 convex 문제로 근사(convexs relaxation)하는 기법들이 실무에서 자주 쓰인다.

 

 

 

 

 

reference: 모두를 위한 컨벡스 최적화