Convex Optimization

1. 개요

Convex Optimization(볼록 최적화)은 목적 함수와 제약 조건이 convex function(볼록 함수) 및 convex set(볼록 집합)인 경우를 다루는 최적화 기법이다. 볼록 최적화는 많은 머신러닝 및 데이터 과학 문제에서 필수적인 역할을 하며, 비교적 빠르고 효율적으로 풀 수 있는 특성을 갖는다.

---

2. 볼록 최적화 문제 정의

볼록 최적화 문제는 다음과 같이 정의된다.

subject to:

여기서:

• f(x) 는 convex function
• 제약 조건:
  • $g_i(x)$ 는 convex function (볼록 함수)
  • $a_j^T x = b_j$ 는 affine function (선형 함수)

즉, 목적 함수가 볼록이고, 제약 조건이 볼록 집합을 형성하면 볼록 최적화 문제이다.

---

3. 볼록 집합 (Convex Set)

집합 ( C ) 가 볼록 집합(convex set) 이려면 임의의 두 점 $x_1, x_2 \in C 와 0 \leq \theta \leq 1$ 에 대해:

즉, 두 점을 잇는 선분이 항상 집합 ( C ) 안에 존재해야 한다.

예제

• 볼록 집합: 직선, 볼록 다각형, 원, 볼록 다면체
• 비볼록 집합: 말굽 모양, 별 모양 다각형

---

4. 볼록 함수 (Convex Function)

함수 $f: \mathbb{R}^n \to \mathbb{R}$ 가 볼록 함수(convex function) 이려면 임의의 두 점 $x, y$ 와 $0 \leq \theta \leq 1$ 에 대해 다음을 만족해야 한다.

즉, 함수의 그래프가 chord(접속하는 선분)보다 아래에 위치해야 한다.

볼록 함수의 조건

1. 1차 조건 (First-order condition)

   $f(y) \geq f(x) + \nabla f(x)^T (y-x)$
   • 기울기가 증가하거나 일정해야 한다.

2. 2차 조건 (Second-order condition)

   $\nabla^2 f(x) \succeq 0$
   • 헤시안 행렬(Hessian matrix)이 양의 준정부호(positive semidefinite) 이면 ( f(x) ) 는 볼록 함수이다.

예제

• $f(x) = x^2$(볼록)
• $f(x) = e^x$ (볼록)
• $f(x) = \log x$ (오목)
• $f(x) = -x^2$ (오목)

---

5. 강한 볼록성 (Strong Convexity)

함수 $f(x)$ 가 강한 볼록 함수(strongly convex function) 이려면, 존재하는 상수 $m > 0$ 에 대해:

즉, 일정한 곡률을 가지며 더 빠르게 증가하는 함수이다. 강한 볼록성은 최적화 알고리즘의 수렴 속도를 높인다.

---

6. 라그랑주 이론과 이중성 (Lagrange Duality)

최적화 문제를 해결하는 한 가지 접근 방식은 라그랑주 승수법(Lagrange Multipliers) 을 사용하는 것이다.

라그랑지안 함수

• $\lambda \geq 0$ : 이중 변수 (dual variables)
• $g_i(x) \leq 0$, $h_j(x) = 0$ : 제약 조건

라그랑주 함수의 이중 함수 (dual function) 는 다음과 같이 정의된다.

이중 문제는 이를 최대화하는 형태로 나타난다.

이중성의 종류

• 약한 이중성(Weak Duality): 항상 $d^* \leq p^*$ (최적 이중 값이 항상 최적 원 문제 값 이하)
• 강한 이중성(Strong Duality): $d^* = p^*$ (이중 문제가 원 문제를 완전히 해결)

---

7. KKT 조건 (Karush-Kuhn-Tucker Conditions)

볼록 최적화에서 최적 해를 찾기 위한 필수 조건.

KKT 조건

1. Primal feasibility: 제약 조건을 만족해야 함.
   $g_i(x^*) \leq 0, \quad h_j(x^*) = 0$
2. Dual feasibility: 이중 변수는 0보다 커야 함.
   $\lambda_i \geq 0$
3. Complementary slackness: 제약 조건이 활성화될 경우 라그랑주 승수가 0이 될 수 있음.
   $\lambda_i g_i(x^*) = 0$
4. Stationarity: 목적 함수의 그라디언트와 제약 조건의 조합이 0이어야 함.
   $\nabla f(x^*) + \sum_{i=1}^{m} \lambda_i \nabla g_i(x^*) + \sum_{j=1}^{p} \nu_j \nabla h_j(x^*) = 0$

KKT 조건을 만족하면 최적 해 $x^*$ 을 찾을 수 있다.

---

8. 선형 계획법 (Linear Programming, LP)

• 목적 함수와 제약 조건이 선형 함수인 경우

  $\min_{x} c^T x, \quad \text{subject to } Ax \leq b$

• 이중 문제:

  $\max_{\lambda} -b^T \lambda, \quad \text{subject to } A^T \lambda = c, \quad \lambda \geq 0$

---

9. 이차 계획법 (Quadratic Programming, QP)

• 목적 함수가 이차 함수인 경우

  $\min_{x} \frac{1}{2} x^T Q x + c^T x, \quad \text{subject to } Ax \leq b$

• 이중 문제:

  $\max_{\lambda} -\frac{1}{2} (c + A^T \lambda)^T Q^{-1} (c + A^T \lambda) - b^T \lambda$

• SVM (Support Vector Machine) 최적화에서 활용됨.

---

10. 결론

• 볼록 최적화는 선형 계획법(LP), 이차 계획법(QP), 라그랑주 이론 등을 포함한 강력한 수학적 도구를 제공.
• 볼록 최적화 문제는 수렴성이 보장되며, 뉴럴 네트워크 학습 및 머신러닝 모델 최적화에 널리 사용됨.
• KKT 조건, 이중성 등을 통해 최적해를 구할 수 있음.

LG Aimers 과정 중 Mathematics for ML 강의자료로 공부하며 정리해 본 내용입니다.