7.115 볼록 최적화 문제의 전역 최적성

1. 볼록 최적화의 정의

볼록 최적화 문제는 다음의 형태를 갖는다.

$\min_{\mathbf{x}} \quad f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \leq 0, \; i = 1, \ldots, m, \quad \mathbf{A}\mathbf{x} = \mathbf{b}$

여기서 $f$ 와 $g_i$ 는 볼록 함수이고, 등식 제약은 아핀이다. 허용 영역 $\mathcal{F} = \{\mathbf{x} : g_i(\mathbf{x}) \leq 0, \mathbf{A}\mathbf{x} = \mathbf{b}\}$ 은 볼록 집합이 된다.

2. 전역 최적성의 핵심 정리

정리: 볼록 최적화 문제의 모든 국소 최적해는 전역 최적해이다.

증명: $\mathbf{x}^*$ 가 국소 최적해이지만 전역 최적해가 아니라고 가정하면, $f(\mathbf{y}^*) < f(\mathbf{x}^*)$ 인 허용점 $\mathbf{y}^*$ 가 존재한다. $f$ 가 볼록이므로 $\theta \in (0, 1)$ 에 대해

$f(\theta \mathbf{y}^* + (1-\theta)\mathbf{x}^*) \leq \theta f(\mathbf{y}^*) + (1-\theta) f(\mathbf{x}^*) < f(\mathbf{x}^*)$

허용 영역이 볼록이므로 $\theta \mathbf{y}^* + (1-\theta)\mathbf{x}^*$ 도 허용이다. $\theta$ 를 충분히 작게 하면 이 점은 $\mathbf{x}^*$ 의 근방에 있으면서 $f$ 값이 더 작으므로, $\mathbf{x}^*$ 가 국소 최적해라는 가정에 모순된다.

이 정리는 볼록 최적화의 가장 중요한 구조적 성질이다. 비볼록 문제에서는 국소 최적해가 전역 최적해가 아닐 수 있으므로, 문제의 볼록성을 식별하는 것이 전역 최적해의 보장을 위해 핵심적이다.

3. KKT 조건의 충분성

볼록 문제에서 슬레이터 조건이 만족되면, KKT 조건은 전역 최적의 필요 충분 조건이다.

필요성: $\mathbf{x}^*$ 가 최적이면 KKT 조건을 만족하는 $(\boldsymbol{\mu}^*, \boldsymbol{\nu}^*)$ 가 존재한다.
충분성: KKT 조건을 만족하는 $(\mathbf{x}^*, \boldsymbol{\mu}^*, \boldsymbol{\nu}^*)$ 에서 $\mathbf{x}^*$ 는 전역 최적해이다.

이 충분성은 볼록 함수에 대해 1차 조건 $\nabla f(\mathbf{x}^*)^T(\mathbf{y} - \mathbf{x}^*) \geq 0$ 이 전역 최적을 보장하는 성질에 기인한다.

4. 쌍대성과 강쌍대성

4.1 라그랑주 쌍대 문제

라그랑주 쌍대 함수를 다음과 같이 정의한다.

$d(\boldsymbol{\mu}, \boldsymbol{\nu}) = \inf_{\mathbf{x}} \mathcal{L}(\mathbf{x}, \boldsymbol{\mu}, \boldsymbol{\nu})$

쌍대 문제는 $\max_{\boldsymbol{\mu} \geq \mathbf{0}, \boldsymbol{\nu}} d(\boldsymbol{\mu}, \boldsymbol{\nu})$ 이다. 약쌍대성(weak duality)에 의해 쌍대 최적값 $d^*$ 는 원초 최적값 $f^*$ 의 하한이다: $d^* \leq f^*$ .

4.2 강쌍대성

볼록 문제에서 슬레이터 조건(강 허용 가능한 점의 존재)이 성립하면, 강쌍대성(strong duality)이 보장된다: $d^* = f^*$ . 쌍대 간극(duality gap)이 영이므로, 쌍대 문제를 풀어 원초 문제의 최적값을 정확히 결정할 수 있다.

5. 볼록 최적화의 계산 복잡도

볼록 최적화 문제는 다항 시간 내에 임의의 정확도 $\epsilon$ 로 풀 수 있다. 내점법에 의한 볼록 문제의 반복 횟수는 $O(\sqrt{m}\log(1/\epsilon))$ 이며, 이는 문제 규모의 다항 함수이다. 이 효율성은 비볼록 문제와의 근본적 차이로, 비볼록 문제에서는 전역 최적해를 찾는 것이 일반적으로 NP-어려운 문제에 속한다.

6. 볼록 재정식화

비볼록으로 보이는 문제가 적절한 변수 변환이나 재정식화를 통해 볼록 문제로 변환될 수 있는 경우가 있다. 이를 볼록 재정식화(convex reformulation) 또는 숨은 볼록성(hidden convexity)의 식별이라 한다.

예: 경로를 따른 시간 최적 궤적 생성에서, 변수 치환 $b(s) = \dot{s}^2$ 를 통해 비볼록 문제가 볼록 QP로 변환된다.

7. 볼록 이완(Convex Relaxation)

비볼록 문제를 직접 볼록 문제로 변환할 수 없는 경우, 볼록 이완(convex relaxation)을 통해 전역 최적값의 하한을 구할 수 있다.

반정치 이완(SDP relaxation): 비볼록 이차 제약을 행렬 부등식으로 이완한다.
선형 이완: 정수 변수를 연속 구간으로 이완한다.

이완 문제의 최적값은 원래 문제의 전역 최적값에 대한 하한을 제공하며, 이 하한이 국소 해법에 의해 얻어진 상한과 비교되어 해의 품질을 평가하는 데 사용된다.

8. 로봇 공학에서의 함의

볼록 최적화의 전역 최적성 보장은 로봇 공학에서 다음의 실용적 함의를 갖는다.

전신 운동 제어의 QP: 볼록 QP이므로 전역 최적 토크/가속도가 보장된다.
선형 MPC: 선형 모델 + 이차 비용의 결합이 볼록이므로 전역 최적 제어가 보장된다.
볼록 경로 최적화: 안전 복도(safe corridor) 내에서의 궤적 최적화가 볼록으로 정식화 가능한 경우, 전역 최적 궤적이 보장된다.

9. 참고 문헌

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Nesterov, Y. (2004). Introductory Lectures on Convex Optimization: A Basic Course. Springer.
Bertsekas, D. P. (2009). Convex Optimization Theory. Athena Scientific.
Ben-Tal, A., & Nemirovski, A. (2001). Lectures on Modern Convex Optimization. SIAM.

version: 1.0