[최적화] convex optimization 기초

 

 

최적화 문제란?

여러 개의 선택 가능한 후보 중에서 최적의 해(Optimal value) 또는 최적의 해에 근접한 값을 찾는 문제

기계학습 분야에서는 비용함수(Cost function)을 최소화 혹은 최대화시키는 모델의 파라미터를 구하는 것.

convex optimization problem도 최적화 문제의 한 종류!

 

 

표현 형식

제약조건을 모두 만족하는 정의역에서 목적함수 $f$를 최소로 만드는 벡터 $x$를 $x^*$로 표시하고,

이를 최적해optimal solution라고 한다.

 

\begin{align}
&\min_{x \in D} && f(x) \\
&subject \ to && g_i(x) \le 0, i = 1,\cdots, m \\
&&&h_j(x) = 0, j = 1, \cdots, r
\end{align}

 

 

 

제약 조건

Explicit constraints : 최적화문제에 직접적으로 명시된 제약조건.

예) $g_i, h_i$

 

Implicit constraints : 직접적으로 명시되지 않은 제약조건.

예) 목적합수가 $log(x)$라고 할 때, $x > 0$

 

 

 

Convex Sets

원소인 두 점과 그 두 점 사이를 이은 선분이 모두 원소인 집합

 

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

 

$$x_1, x_2 \in C, \ 0\le\theta\le1 \Rightarrow \ \theta x_1 + (1-\theta)x_2 \in C$$

 

 

 

 

Convex functions

아래로 볼록한 함수.

x, y 사이에 있는 값들이 두 점을 이은 값보다 같거나 작음

 

$f:R^n \rightarrow R$ is convex if $dom(f)$ is a convex set and,

$f(\theta x+(1-\theta )y) \le \theta f(x) + (1-\theta)f(y)$ for all $x, y \in dom(f), 0 \le \theta \le 1$

 

 

 

함수 $f$의 위쪽 영역의 값이 convex set일 때, 함수 $f$는 convex function

 

epigraph of $f : R^n \rightarrow R$

epi $f = \{(x, t) \in R^{n+1}|x \in dom f, f(x) \le t \}$

 

 

 

 

[출처 및 참고]

https://web.stanford.edu/~boyd/cvxbook/

https://convex-optimization-for-all.github.io/

https://wikidocs.net/book/1896