1. 기본 용어 정리
데이터를 가지고 학습할 때, 우리의 목표는 다음과 같다.
f(x)를 최소로 하는 solution을 찾는 것이다.
문제에 따라서 f(x)를 최대화 해야 하는 경우도 있고, 최소화 해야 하는 경우도 있다.
전자는 error나 cost, 후자는 probability가 있겠다.
무엇을 최적화하는지에 따라 관점이 달라지는 것이다!
위의 식은 unconstrained optimization이라면, convex optimization에서 정의하는 식은 다음과 같이 constrained optimization이다.
- f(x) : objective function
- g(x) : Inequality constraints
- h(x) : Equality contraints
- subject to는 줄임말로 s.t. 으로 많이 적는다.
이런 제약 조건을 만족하는 x를 feasible solutions (실현 가능한 솔루션)이라고 한다.
x들을 모아놓은 집합은 feasible set이라고 한다.
feasible set 중에서 min f(x)를 만드는 x를 optimal solution이라고 한다. (아래 그림에서 x*)
$$solution = argmin_xf(x)$$
- local minimum : 어떤 값 주변에서 함수를 가장 작게 만드는 점에서의 값 (극솟값)
(주의 : 미분이 0일 필요 없음.)
- global minimum : 극솟값 중 가장 작은 값
- local maximum : 어떤 값 주변에서 함수를 가장 크게 만드는 점에서의 값 (극댓값)
(주의 : 미분이 0일 필요 없음.)
- global maximum : 극댓값 중 가장 큰 값
즉, 극소와 극대는 미분이 0인 지점의 값을 의미하는 것이 아니다.
극솟값, 극댓값에서 우연히 미분 값이 0이 될 수는 있지만, 미분이 0이라고 해서 모두 극소, 극대인 것은 아니라는 뜻이다.
아래의 예시에서 처럼, 주변보다만 크거나 작으면 된다.
2. Convex Optimization Problem
f(x)가 convex이고, feasible set이 convex이면, Convex Optimization Problem이다.
Convex는 '볼록한'이라는 뜻을 가지고 있다.
(1) f(x)가 convex
function에 대한 convex의 정의는, 단어 뜻 그대로 '볼록한' 모양을 가지면 된다.
이를 수식으로 표현하면,
정의역에 포함되는 모든 $x_1, x_2$에 대해, $\alpha \in [0, 1]$
$$f(\alpha{x_1} + (1-\alpha)x_2) \leq f(x_1) + (1-\alpha)f(x_2)$$
부등호 기준 왼쪽은 x1과 x2 사이의 x값에 대한 함수값을 의미한다.
만약 $\alpha$가 $\frac{1}{2}$이라면, x1과 x2의 중간값의 함수값인 것을 쉽게 알 수 있다.
부등호 기준 오른쪽은 f(x1)과 f(x2) 사이의 함수값을 의미한다.
y축 기준으로 값을 봤을 때, $\alpha$가 $\frac{1}{2}$이라면 f(x1)과 f(x2)의 중간값인 것을 알 수 있다.
따라서, x1과 x2에서의 두 점을 이은 직선이 함수값보다 크다면, convex하다고 말할 수 있다.
Jensen's inequality라고도 부른다.
(2) feasible set이 convex
정의역 ($S$)에 포함되는 모든 $x_1, x_2$에 대해, $\alpha \in [0, 1]$에 대해
$$\alpha{x_1} + (1-\alpha)x_2 \in S$$
정의역 내의 두 벡터가 나타내는 선분 위의 점을 다 나타낼 수 있음을 의미한다.
아래의 그림에서 왼쪽은 convex set이지만, 오른쪽은 non-convex set이다.
정리해보면,
모든 x에 대해서 $f''(x)\geq 0$을 만족한다면 f는 convex function이다.
x가 스칼라가 아니라, 벡터 (f가 다변수 함수)일 때도 동일하다.
'값'에 대해서 최소를 구하고 싶은 것이기 때문에, 함수에 벡터가 입력되어도 출력은 스칼라여야 한다.
헤시안 행렬을 구하면 위와 같다.
헤시안 행렬이 모든 벡터 z에 대해 Positive-semi definite라면 f는 Convex function이다.
모든 벡터 z에 대해 Positive-semi definite 인지를 확인하기 위해서 위와 같은 작업을 해주면 된다!
위의 예시에서는 0보다 항상 크거나 같기 때문에 f가 convex하다고 말할 수 있다.
1. convex optimization problem은 local minimum이 global minimum이다.
2. convex optimization problem은 f(x)가 convex하고, feasible set이 convex하면 된다.