최적화에서 Convex가 그렇게 중요하다고 들은 기억이 있어서 정리해 보려고 한다.

Convex? Convex set?

우선 Convex set이란
기하학 및 최적화 이론에서 중요한 개념으로, 임의의 두 점을 선택했을 때 이 두 점을 연결하는 선분이 항상 그 집합 내부에 포함되는 집합을 말한다.

조금 더 공식적으로 설명하자면,
$S$라는 집합이 유클리드 공간 또는 벡터 공간 내에 있다고 할 때, 만약 임의의 두 점 $x$와 $y$가 $S$에 속한다면, $x$와 $y$ 사이를 연결하는 모든 점들이 $S$에 속하면 $S$는 convex set이라고 한다.

이를 식으로 표현하면 아래와 같다!

단 여기서 $\lambda$는 $0 \leq \lambda \leq 1$를 만족하는 실수다

대표적인 Convex set의 예를 찾는다면 2차원 평면에서의 원, 정사각형, 삼각형 등이 있다.

전역 최적해의 보장
Convex 함수에서 최적화 문제를 풀 때, 전역 최적해를 쉽게 찾을 수 있다!

Convex 집합에서 정의된 convex 함수는 극소점이 반드시 전역 최소점임을 보장합니다. 즉, 함수 $f(x)$가 convex이고 정의역이 convex 집합 $C$라면, $f(x)$의 모든 극소점은 동시에 전역 최소점이 된다

이는 최적화 문제를 풀 때, 탐색하는 해가 지역 최적해에 갇히는 문제가 없음을 의미합니다. 이 때문에 convex 함수는 최적화 문제에서 많이 선호된다

그래서 왜 중요한데?

Convex 함수에서는 그 지점에서 미분계수가 0인 것과 최소인 것이 필요충분조건 관계를 가진다

정말 간단하게 말하자면 극소값이 곧 최소값이 되기 때문이다!!

그래서 많은 non-convex 문제들을 convex 문제로 바꾸려는 시도가 많이 있다고 한다.

Convex 에서 local minimum = global minimum인 것을 증명해보자

먼저 $f(x)$가 Convex이고 feasible set $F$가 Convex이고
$f(x^*)$ : local minimum, $f(x')$는 local minimum이 아닌 최솟값이라고 해보자.

그렇다면 $f(x') < f(x^*)$ 이런 관계가 성립한다고 출발할 수 있다.
또한 convex 조건에 따라 아래의 식이 성립한다.

$f(x') < f(x^*)$ 이기에 아래와 같은 식이 성립한다.

우변에 $f(x^*)$를 더하고 다시 빼주자

$(1-\alpha)$ 항을 기준으로 식을 정리하자

여기서 $f(x') < f(x^*)$ 이기에 $f(x') -f(x^*) < 0$이다.
또한 $0 \leq \alpha \leq 1$ 이기에 $(1-\alpha)$ 항은 항상 양수를 가진다.

따라서 $(1-\alpha)(f(x') -f(x^*)$ 항은 항상 음수 값을 가지게 된다.

그래서 이와 같은 관계가 성립해야 한다

이제 가장 왼쪽의 식을 보자! $\alpha$가 1에 가까워질수록 $f(\alpha x^* +(1-\alpha)x')$식은 $f(x^*)$값에 가까워진다. 하지만 이러면 모순이다!

$f(x^*)$는 local minimum 값이다. 즉 주변에서 최소값을 가진다는 것이다.
하지만 $f(\alpha x^* +(1-\alpha)x')$ 이 식은 $x^*$주변을 보니 $x^*$보다 더 작은 값이 있다고 말하고 있다.

따라서 기존의 전제, $f(x') < f(x^*)$ 는 모순이 잇다.

여기서 set F가 feasible한 set이란 것이 제일 중요하다.
왜냐하면 이 조건이 없다면 다른 조건에 제약을 받게 되어서 $f(x') < f(x^*)$ 이 식이 성립할 수도 있기 때문이다.

따라서

local minimum point : feasible sol. 중에 주변에서 가장 작게 만드는 것
이라고 정리할 수 있다!

---

다른 증명 버전

🟦 Convex Function의 정의

함수 $f: \mathbb R^n \to \mathbb{R}$가 convex하다는 것은, 임의의 $x, y$ $\in \mathbb{R}^n$와 $\lambda \in [0, 1]$에 대해 다음 부등식이 성립함을 의미한다

이 부등식은 함수 $f$의 그래프가 두 점 $x$와 $y$를 잇는 직선보다 아래에 있음을 의미합니다. 이런 함수가 convex 함수다

극소값과 최소값의 개념

• 극소값 (local minimum): 함수 $f$의 한 점 $x^*$가 극소점이 되려면, $x^*$의 어떤 작은 근방에서$f(x^*) \leq f(x)$를 만족하는 $x$가 존재해야 한다

• 최소값 (global minimum): 함수 $f$의 한 점 $x^*$가 최소점이 되려면, $f(x^*) \leq f(x)$가 모든 $x \in \mathbb{R}^n$에 대해 성립해야 한다

증명: Convex Function에서 극소값이 최소값이 됨

$f$가 convex 함수이고, $x^*$가 $f$의 극소점이라고 가정하자,
이제,$x^*$가 최소점임을 보이기 위해 $x^*$가 최소점이 아니라면 모순이 생긴다는 것을 증명하겠다!

1. $x^*$가 극소점이므로, $\exists \delta > 0$에 대해 $f(x^*) \leq f(x)$ for all $\|x - x^*\| < \delta$

2. $x^*$가 최소점이 아니라고 가정,
   즉, $f(x^*) > f(y)$인 어떤 점 $y$가 존재한다고 하자

3. 이제 $x^*$와 $y$ 사이의 선분을 고려, $\lambda \in [0, 1]$에 대해,
   $z = \lambda x^* + (1 - \lambda) y$라 하면, convex 함수의 정의에 따라:

   $f(z) \leq \lambda f(x^*) + (1 - \lambda) f(y)$

4. $0 < \lambda < 1$인 경우를 고려하면,$f(y) < f(x^*)$이므로:

   $\lambda f(x^*) + (1 - \lambda) f(y) < f(x^*)$

   따라서 $f(z) < f(x^*)$가 된다! 이는 $z$가 $x^*$의 근방 내에 있으면서도 $f(z) < f(x^*)$를 만족하게 된다

5. 그러나, 이는 $x^*$가 극소점이라는 가정에 모순이 된다 왜냐하면 극소점에서는 그 근방에서 $f(x^*) \leq f(z)$이어야 하기 때문이다

따라서, $x^*$가 convex 함수 $f$의 극소점이라면, 그것은 반드시 최소점이 됩니다. 이로써 convex 함수에서는 극소값이 곧 최소값이 된다는 것이 증명되었다

---

🟦 Convex와 경사하강법

경사하강법(Gradient Descent)은 최적화 문제를 푸는 매우 일반적인 방법입니다. 경사하강법은 함수의 기울기(그래디언트)를 따라 내려가면서 최소점을 찾는 알고리즘입니다. Convex 함수에서 경사하강법이 특히 유용한 이유는 다음과 같습니다:

단일 극소점: Convex 함수는 극소점이 하나뿐이며, 그 극소점이 곧 전역 최소점입니다. 경사하강법을 사용할 때, 초기값에 관계없이 이 전역 최소점에 도달할 수 있습니다. 즉, 경사하강법이 수렴하는 해는 최적해임이 보장됩니다.

효율성: Convex 함수의 성질 덕분에 경사하강법이 비교적 빠르고 안정적으로 수렴합니다. 특히, 강한 convex성(strong convexity)을 갖는 함수에서는 수렴 속도가 더 빨라집니다.

단순성: Convex 함수에서는 경사하강법이 복잡한 최적화 알고리즘 없이도 쉽게 구현할 수 있으며, 그 결과의 신뢰성이 높습니다.

경사 하강법 작동 과정

1. 초기점 설정: 최적화를 시작할 초기점 $x_0$를 설정

2. 기울기 계산: 현재 위치 $x_t$에서의 기울기 $\nabla f(x_t)$를 계산합니다.

3. 갱신: 기울기의 반대 방향으로 한 걸음 나아갑니다. 갱신 식은 다음과 같다

여기서 $\alpha$는 학습률(learning rate)로, 한 걸음의 크기를 결정

4. 수렴: 더 이상 크게 변화하지 않을 때까지, 또는 미리 정의된 조건을 만족할 때까지 이 과정을 반복