7.81 필요 최적 조건과 충분 최적 조건

1. 필요 조건과 충분 조건의 구별

최적화 이론에서 필요 조건(necessary condition)과 충분 조건(sufficient condition)의 구별은 근본적으로 중요하다. 필요 조건은 최적해가 반드시 만족해야 하는 조건이지만, 이 조건을 만족하는 모든 점이 최적해인 것은 아니다. 충분 조건은 이 조건을 만족하는 점이 반드시 최적해임을 보장한다. 수학적으로 표현하면 다음과 같다.

• 필요 조건: \mathbf{x}^*가 최적해이면 조건 \mathcal{C}가 성립한다. (\text{최적} \Rightarrow \mathcal{C})
• 충분 조건: 조건 \mathcal{C}가 성립하면 \mathbf{x}^*는 최적해이다. (\mathcal{C} \Rightarrow \text{최적})

2. 비제약 최적화의 1차 필요 조건

2.1 정류점 조건

f: \mathbb{R}^n \to \mathbb{R}이 \mathbf{x}^*에서 미분 가능하고, \mathbf{x}^*가 국소 최소점이면 다음이 성립한다.

\nabla f(\mathbf{x}^*) = \mathbf{0}

이 조건을 1차 필요 조건(first-order necessary condition) 또는 정류점 조건(stationarity condition)이라 한다. 그래디언트가 영인 점을 정류점(stationary point)이라 하며, 정류점은 극소점, 극대점, 안장점 중 하나일 수 있다.

증명 개요: \mathbf{x}^*가 국소 최소점이면 임의의 방향 \mathbf{d}에 대해 f(\mathbf{x}^* + \alpha \mathbf{d}) \geq f(\mathbf{x}^*)가 충분히 작은 \alpha > 0에서 성립한다. 1차 테일러 전개에 의해 f(\mathbf{x}^* + \alpha \mathbf{d}) \approx f(\mathbf{x}^*) + \alpha \nabla f(\mathbf{x}^*)^T \mathbf{d}이므로, \nabla f(\mathbf{x}^*)^T \mathbf{d} \geq 0이 모든 \mathbf{d}에 대해 성립해야 한다. \mathbf{d}와 -\mathbf{d} 양쪽 모두에 대해 이 부등식이 성립하려면 \nabla f(\mathbf{x}^*)^T \mathbf{d} = 0이 모든 \mathbf{d}에 대해 성립해야 하므로, \nabla f(\mathbf{x}^*) = \mathbf{0}이다.

3. 비제약 최적화의 2차 조건

3.1 차 필요 조건

f가 \mathbf{x}^*에서 두 번 연속 미분 가능하고, \mathbf{x}^*가 국소 최소점이면 다음이 성립한다.

\nabla f(\mathbf{x}^*) = \mathbf{0}, \quad \nabla^2 f(\mathbf{x}^*) \succeq 0 \quad (\text{양의 반정치})

즉, 정류점에서의 헤시안 행렬이 양의 반정치여야 한다. 이는 정류점의 국소적 곡률이 모든 방향에서 비음수임을 의미한다.

3.2 차 충분 조건

f가 \mathbf{x}^*에서 두 번 연속 미분 가능하고, 다음의 조건이 성립하면 \mathbf{x}^*는 엄밀한 국소 최소점(strict local minimizer)이다.

\nabla f(\mathbf{x}^*) = \mathbf{0}, \quad \nabla^2 f(\mathbf{x}^*) \succ 0 \quad (\text{양정치})

양정치 조건은 헤시안의 모든 고유값이 양수임을 요구하며, 이는 \mathbf{x}^* 근방에서 f가 모든 방향으로 강하게 증가함을 보장한다. 양의 반정치이지만 양정치가 아닌 경우(즉, 영 고유값이 존재하는 경우)에는 2차 정보만으로는 최소점 여부를 판정할 수 없으며, 고차 미분 정보가 필요하다.

4. 등식 제약 최적화의 최적 조건

4.1 라그랑주 필요 조건

등식 제약 최적화 문제 \min f(\mathbf{x}) subject to \mathbf{h}(\mathbf{x}) = \mathbf{0} (\mathbf{h}: \mathbb{R}^n \to \mathbb{R}^p)에서, \mathbf{x}^*가 국소 최소점이고 제약 자격(constraint qualification)이 성립하면, 라그랑주 승수 \boldsymbol{\nu}^* \in \mathbb{R}^p가 존재하여 다음이 성립한다.

\nabla f(\mathbf{x}^*) + \sum_{j=1}^{p} \nu_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}

\mathbf{h}(\mathbf{x}^*) = \mathbf{0}

라그랑지안 함수 \mathcal{L}(\mathbf{x}, \boldsymbol{\nu}) = f(\mathbf{x}) + \boldsymbol{\nu}^T\mathbf{h}(\mathbf{x})를 사용하면, 이 조건은 \nabla_{\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\nu}^*) = \mathbf{0}으로 간결하게 표현된다.

기하학적으로 해석하면, 최적점에서 목적 함수의 그래디언트는 제약 곡면에 접하는 방향의 성분이 없어야 하며, 이는 \nabla f(\mathbf{x}^*)가 제약 함수들의 그래디언트가 이루는 부분 공간에 놓여야 함을 의미한다.

4.2 제약 자격 조건

라그랑주 필요 조건이 성립하기 위해서는 제약 자격(constraint qualification)이 만족되어야 한다. 가장 일반적인 조건은 다음과 같다.

선형 독립 제약 자격(LICQ): 활성 제약(active constraint)의 그래디언트 벡터들이 \mathbf{x}^*에서 선형 독립이다. 즉, \nabla h_1(\mathbf{x}^*), \ldots, \nabla h_p(\mathbf{x}^*)가 선형 독립이면, 라그랑주 승수 \boldsymbol{\nu}^*가 유일하게 결정된다.

LICQ가 성립하지 않으면 라그랑주 승수가 존재하지 않거나 유일하지 않을 수 있으며, 이 경우 더 약한 제약 자격(예: 망가사리안-프로모비츠 조건)을 검증해야 한다.

4.3 차 충분 조건 (등식 제약)

\mathbf{x}^*에서 1차 라그랑주 조건이 만족되고, 라그랑지안의 헤시안이 제약 곡면의 접선 공간(tangent space)에 제한했을 때 양정치이면, \mathbf{x}^*는 엄밀한 국소 최소점이다. 접선 공간은 다음과 같이 정의된다.

\mathcal{T} = \{ \mathbf{d} \in \mathbb{R}^n : \nabla h_j(\mathbf{x}^*)^T \mathbf{d} = 0, \; j = 1, \ldots, p \}

충분 조건은 다음과 같다.

\mathbf{d}^T \nabla^2_{\mathbf{x}\mathbf{x}} \mathcal{L}(\mathbf{x}^*, \boldsymbol{\nu}^*) \mathbf{d} > 0, \quad \forall \mathbf{d} \in \mathcal{T}, \; \mathbf{d} \neq \mathbf{0}

이는 제약 조건과 양립 가능한 모든 방향에서 라그랑지안의 곡률이 양수임을 요구한다.

5. 부등식 제약 최적화의 KKT 조건

5.1 KKT 필요 조건

일반적인 제약 최적화 문제

\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \leq 0, \; h_j(\mathbf{x}) = 0

에서 \mathbf{x}^*가 국소 최소점이고 적절한 제약 자격이 성립하면, 라그랑주 승수 \boldsymbol{\mu}^* \in \mathbb{R}^m, \boldsymbol{\nu}^* \in \mathbb{R}^p가 존재하여 다음의 카루시-쿤-터커(Karush-Kuhn-Tucker, KKT) 조건이 성립한다.

정류 조건(stationarity):

\nabla f(\mathbf{x}^*) + \sum_{i=1}^{m} \mu_i^* \nabla g_i(\mathbf{x}^*) + \sum_{j=1}^{p} \nu_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}

원초 허용 가능성(primal feasibility):

g_i(\mathbf{x}^*) \leq 0, \quad h_j(\mathbf{x}^*) = 0

쌍대 허용 가능성(dual feasibility):

\mu_i^* \geq 0, \quad i = 1, \ldots, m

상보성 조건(complementary slackness):

\mu_i^* g_i(\mathbf{x}^*) = 0, \quad i = 1, \ldots, m

상보성 조건은 비활성(inactive) 제약(g_i(\mathbf{x}^*) < 0)에 대응하는 승수가 영(\mu_i^* = 0)임을 의미하며, 비영 승수(\mu_i^* > 0)를 갖는 제약은 반드시 활성(g_i(\mathbf{x}^*) = 0)이어야 한다.

5.2 KKT 충분 조건

KKT 조건이 만족되고, 라그랑지안의 헤시안이 임계 원추(critical cone) 위에서 양정치이면, \mathbf{x}^*는 엄밀한 국소 최소점이다. 임계 원추는 다음과 같이 정의된다.

\mathcal{C} = \left\{ \mathbf{d} \in \mathbb{R}^n : \begin{array}{l} \nabla g_i(\mathbf{x}^*)^T \mathbf{d} \leq 0, \; \forall i \in \mathcal{A}(\mathbf{x}^*) \\ \nabla g_i(\mathbf{x}^*)^T \mathbf{d} = 0, \; \forall i \in \mathcal{A}^+(\mathbf{x}^*) \\ \nabla h_j(\mathbf{x}^*)^T \mathbf{d} = 0, \; \forall j \end{array} \right\}

여기서 \mathcal{A}(\mathbf{x}^*) = \{i : g_i(\mathbf{x}^*) = 0\}는 활성 부등식 제약의 인덱스 집합이고, \mathcal{A}^+(\mathbf{x}^*) = \{i \in \mathcal{A}(\mathbf{x}^*) : \mu_i^* > 0\}는 양의 승수를 갖는 활성 제약의 인덱스 집합이다.

6. 볼록 문제에서의 최적 조건

볼록 최적화 문제에서 KKT 조건은 특별한 지위를 갖는다. f가 볼록, g_i가 볼록, h_j가 아핀(affine)이고 슬레이터(Slater) 조건(즉, 강 허용 가능한 점 \mathbf{x}_0가 존재하여 g_i(\mathbf{x}_0) < 0)이 성립하면, KKT 조건은 전역 최적의 필요 충분 조건이다. 즉, 볼록 문제에서는 KKT 점이 곧 전역 최적해이다.

이 성질은 볼록 최적화의 핵심적 이점으로, KKT 조건을 만족하는 점을 찾으면 전역 최적해를 확보할 수 있음을 의미한다. 반면, 비볼록 문제에서는 KKT 조건의 만족이 국소 최적성만을 보장한다.

7. 필요 조건과 충분 조건의 관계 요약

8. 로봇 공학에서의 실용적 함의

로봇 공학의 최적화 문제에서 필요 조건과 충분 조건의 구별은 다음과 같은 실용적 함의를 갖는다.

수치 해법의 종료 기준: 대부분의 수치적 최적화 알고리즘은 1차 필요 조건(KKT 조건)의 만족 여부를 종료 기준으로 사용한다. \lVert \nabla_{\mathbf{x}} \mathcal{L} \rVert < \epsilon, 상보성 잔차 \lvert \mu_i g_i \rvert < \epsilon 등이 실질적인 종료 판정에 사용된다.

국소 해의 품질 평가: 비볼록 로봇 최적화 문제에서 알고리즘이 수렴한 KKT 점이 양호한 국소 최적해인지 평가하기 위해, 축소 헤시안의 고유값 분석이 활용된다. 음의 고유값이 존재하면 해당 방향으로 목적 함수를 더 감소시킬 수 있음을 의미한다.

다중 초기점 전략: 비볼록 문제에서 전역 최적해를 추구하기 위해, 다양한 초기점에서 국소 최적화를 반복 수행하고, 얻어진 국소 최적해 중 최선의 것을 선택하는 전략이 사용된다.

9. 참고 문헌

• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
• Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.
• Luenberger, D. G., & Ye, Y. (2016). Linear and Nonlinear Programming (4th ed.). Springer.
• Bazaraa, M. S., Sherali, H. D., & Shetty, C. M. (2006). Nonlinear Programming: Theory and Algorithms (3rd ed.). Wiley.

version: 1.0