카루시-쿤-터커 조건

편집 역사 토론
수치해석 최적설계 마지막 수정: 2026-07-19 04:29:53

1. 개요[편집]

카루시-쿤-터커 조건
Karush–Kuhn–Tucker Conditions
약칭KKT 조건
역할제약 최적화의 1차 필요조건
일반화 대상라그랑주 승수법(등식 제약)
제안Karush(1939) · Kuhn & Tucker(1951)
주요 응용접촉 해석, 소성, 위상 최적화

제약이 없는 최적화의 답은 “기울기 = 0”이다. 제약이 생기면 답은 “기울기 = 제약이 밀어내는 힘”이 된다.

카루시-쿤-터커 조건(Karush–Kuhn–Tucker conditions, KKT 조건)은 부등식 제약과 등식 제약이 함께 있는 최적화 문제에서, 어떤 점이 국소 최적해가 되기 위해 만족해야 하는 1차 필요조건이다. 등식 제약만 다루던 라그랑주 승수법을 부등식 제약으로 확장한 것이며, 현대 제약 최적화 이론과 거의 모든 수치 최적화 알고리즘의 종료 판정 기준이 여기서 나온다.

핵심 아이디어는 이렇다. 제약이 없다면 최적점에서 기울기가 0이어야 한다. 제약이 있다면 기울기가 0일 필요는 없고, 다만 더 내려가려는 방향이 전부 제약에 막혀 있으면 된다. 이 “막혀 있음”을 대수적으로 표현한 것이 KKT 조건이다.

2. 문제 설정[편집]

표준형 문제를 다음과 같이 둔다.

min⁡xf(x)s.t.gi(x)≤0    (i=1,…,m),hj(x)=0    (j=1,…,p)\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{s.t.} \quad g_i(\mathbf{x}) \le 0 \;\; (i=1,\dots,m), \quad h_j(\mathbf{x}) = 0 \;\; (j=1,\dots,p)

라그랑지안을 다음처럼 정의한다.

L(x,λ,ν)=f(x)+∑i=1mλi gi(x)+∑j=1pνj hj(x)\mathcal{L}(\mathbf{x}, \boldsymbol{\lambda}, \boldsymbol{\nu}) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i\, g_i(\mathbf{x}) + \sum_{j=1}^{p} \nu_j\, h_j(\mathbf{x})

λi\lambda_i와 νj\nu_j가 라그랑주 승수(쌍대변수)다. 부등식 제약에 붙는 λi\lambda_i에는 부호 제약이 붙는다는 점이 등식 제약과의 결정적 차이다.

3. KKT 조건의 네 항목[편집]

x∗\mathbf{x}^*가 국소 최적해이고 적절한 제약 자격조건을 만족한다면, 다음을 모두 만족하는 (λ∗,ν∗)(\boldsymbol{\lambda}^*, \boldsymbol{\nu}^*)가 존재한다.

정상성(stationarity) — 라그랑지안의 기울기가 0이다.

∇f(x∗)+∑iλi∗∇gi(x∗)+∑jνj∗∇hj(x∗)=0\nabla f(\mathbf{x}^*) + \sum_{i} \lambda_i^* \nabla g_i(\mathbf{x}^*) + \sum_{j} \nu_j^* \nabla h_j(\mathbf{x}^*) = \mathbf{0}

원시 가능성(primal feasibility) — gi(x∗)≤0g_i(\mathbf{x}^*) \le 0이고 hj(x∗)=0h_j(\mathbf{x}^*) = 0이다. 당연한 소리지만 조건 목록에 정식으로 들어간다.

쌍대 가능성(dual feasibility) — λi∗≥0\lambda_i^* \ge 0이다. 부등식 제약은 한쪽 방향으로만 밀 수 있기 때문이다. 벽은 당길 수 없고 밀기만 한다.

상보 여유(complementary slackness) — 모든 ii에 대해

λi∗ gi(x∗)=0\lambda_i^*\, g_i(\mathbf{x}^*) = 0

이 마지막 항목이 KKT의 정수(精髓)다. 제약이 느슨하면(gi<0g_i < 0, 즉 벽에서 떨어져 있으면) 그 제약의 승수는 0이어야 한다. 반대로 승수가 양수라면 제약은 반드시 활성(gi=0g_i = 0)이어야 한다. 닿지 않은 벽은 힘을 주지 않는다.

4. 기하학적 직관[편집]

정상성 조건을 옮겨 쓰면 −∇f=∑iλi∇gi+∑jνj∇hj-\nabla f = \sum_i \lambda_i \nabla g_i + \sum_j \nu_j \nabla h_j이다. 좌변은 “내려가고 싶은 방향”, 우변은 “활성 제약들의 법선 벡터를 음이 아닌 계수로 조합한 것”이다. 즉 최적점에서 하강 방향은 활성 제약 법선들이 만드는 원뿔 안에 정확히 갇혀 있다. 어디로 움직여도 목적함수가 늘어나거나 제약을 위반한다는 뜻이다.

물리적으로 읽으면 더 직관적이다. 공을 그릇에 굴려 넣으면 중력(−∇f-\nabla f)과 그릇 표면의 수직항력(λ∇g\lambda \nabla g)이 평형을 이루는 곳에서 멈춘다. 수직항력은 밀기만 하고(λ≥0\lambda \ge 0), 표면에 닿아 있을 때만 존재한다(λg=0\lambda g = 0). KKT 조건은 그냥 이 상식의 수학적 번역이다.

승수 λi\lambda_i의 값에도 의미가 있다. 제약 우변을 조금 완화했을 때 최적값이 얼마나 개선되는지를 나타내는 잠재가격(shadow price) 이다. 설계 최적화에서 어떤 제약이 진짜 발목을 잡는지 판별할 때 이 값을 본다.

5. 제약 자격조건이라는 함정[편집]

KKT 조건이 필요조건이 되려면 제약 자격조건(constraint qualification, CQ)이 필요하다. 이게 없으면 최적해인데도 KKT 조건을 만족하는 승수가 아예 존재하지 않는 병리적 사례가 나온다.

  • LICQ: 활성 제약들의 기울기 벡터가 선형독립이면 충분하다. 가장 흔히 쓰이는 조건이고, 이때 승수는 유일하다.
  • 슬레이터 조건: 볼록 문제에서 부등식 제약을 강부등식으로 만족하는 내부점이 하나라도 있으면 된다. 볼록 최적화의 표준 가정.

한편 충분조건은 별개 문제다. 일반적으로 KKT를 만족해도 최적해라는 보장은 없다(안장점이나 국소 최대점일 수 있다). 다만 문제가 볼록이고 CQ가 성립하면 KKT는 필요충분조건이 되어 전역 최적해를 보증한다. 볼록 최적화가 대접받는 이유가 여기 있다.

6. 수치 알고리즘과의 연결[편집]

실제 최적화 솔버는 사실상 KKT 조건을 푸는 기계다.

  • 능동집합법(active set method): 어떤 제약이 활성인지 추측해 등식 제약 문제로 바꿔 풀고, 승수 부호(λ≥0\lambda \ge 0)가 위반되면 집합을 갱신한다. 상보 여유를 조합 탐색으로 처리하는 방식.
  • 내점법(interior point method): 상보 여유를 λigi=−μ\lambda_i g_i = -\mu로 완화한 뒤 μ→0\mu \to 0으로 보낸다. 조합 폭발을 피하고 뉴턴-랩슨법으로 매끄럽게 따라갈 수 있어 대규모 문제의 표준이 됐다.
  • 순차 이차계획법(SQP): 매 반복에서 라그랑지안을 2차 근사한 부분문제를 풀어 KKT 점으로 접근한다. 비선형 제약이 많은 공학 설계 최적화의 주력.
  • 벌칙법·증강 라그랑지안: 제약 위반에 벌점을 부과해 무제약 문제로 바꾼 뒤 경사하강법 계열로 푼다. 구현이 쉬운 대신 벌칙 계수가 커지면 조건수가 망가진다.

수렴 판정도 결국 KKT 잔차로 한다. 정상성 잔차와 상보 여유 잔차가 허용치 아래로 떨어지면 “수렴했다”고 선언한다.1

7. 해석 분야에서의 KKT[편집]

CAE에서 KKT 조건은 최적화 모듈 밖에서도 튀어나온다. 부등식 제약이 물리 그 자체인 경우가 많기 때문이다.

접촉 해석 의 시뇨리니(Signorini) 조건이 대표적이다. 간극 g≥0g \ge 0(파고들 수 없음), 접촉압력 p≥0p \ge 0(당길 수 없음), 그리고 p g=0p\,g = 0(떨어져 있으면 압력 0). 정확히 상보 여유 구조이며, 이를 이산화하면 선형 상보성 문제가 되어 제약 해결기와 물리엔진 솔버가 이걸 푼다.

소성 이론의 하중-제하 조건도 같은 형태다. 항복함수 ϕ≤0\phi \le 0, 소성 승수 γ˙≥0\dot{\gamma} \ge 0, γ˙ ϕ=0\dot{\gamma}\,\phi = 0. 응력이 항복면 안이면 소성 변형은 0이고, 소성 변형이 일어나면 응력은 항복면 위에 있어야 한다. 소성 상태를 판정하는 반환 사상(return mapping) 알고리즘은 본질적으로 KKT 조건을 만족시키는 국소 뉴턴 반복이다.

위상 최적화 의 고전적 최적성 판정 기준(optimality criteria) 갱신식 역시 체적 제약에 대한 KKT 조건을 정리해 얻은 것이다. 민감도 해석으로 기울기를 뽑고 이분법으로 승수를 맞추는 그 과정이 곧 KKT 풀기다.

8. 여담[편집]

이름이 세 사람인 사연이 있다. 쿤(H. W. Kuhn)과 터커(A. W. Tucker)가 1951년 논문으로 이 조건을 널리 알렸고 한동안 “쿤-터커 조건”으로 불렸는데, 1970년대에 윌리엄 카루시(William Karush)가 1939년 시카고대 석사논문에서 이미 동일한 결과를 얻었다는 사실이 재발견됐다.2 학계는 뒤늦게 이름을 앞에 붙여줬다. 출판되지 않은 석사논문의 비극이자, 우선권 분쟁이 드물게 평화적으로 마무리된 사례다.3

9. 관련 문서[편집]

10. Footnotes[편집]

  1. 그래서 최적화 로그에 “KKT error”라는 열이 찍힌다. 목적함수가 더 이상 안 줄어든다고 수렴한 게 아니다. KKT 잔차가 죽어야 수렴한 것이다. 목적함수만 보고 만족하다가 제약 위반 상태로 끝나는 게 초보의 국룰 실수. ↩

  2. 카루시의 논문은 지도교수의 권유로도 출판되지 않았다. 당시에는 그 결과가 그다지 대단해 보이지 않았다는 회고가 남아 있다. 12년 뒤 같은 정리가 선형계획법 붐과 함께 학문 하나를 여는 열쇠가 될 줄은 아무도 몰랐다. ↩

  3. 참고로 프리츠 존(Fritz John)이 1948년에 제안한 유사 조건도 있다. 목적함수 기울기에도 승수를 붙여 제약 자격조건 없이도 성립하도록 만든 버전으로, KKT가 깨지는 병리적 사례를 다룰 때 등판한다. ↩