쌍대성

최적설계 수치해석 마지막 수정: 2026-08-15 04:27:09

1. 개요[편집]

쌍대성 Duality
구성	라그랑주 함수 L(x,λ,ν) → 쌍대함수 g(λ,ν) = inf_x L
약쌍대성	d* ≤ p* — 볼록·비볼록 가리지 않고 항상
강쌍대성	볼록 + 슬레이터 조건 ⟹ d* = p*
항상 참인 사실	쌍대문제는 원문제가 무엇이든 볼록(오목 최대화)
해석	승수 = 그림자 가격 = 제약 완화의 한계가치

쌍대성은 하나의 최적화 문제(원문제, primal)에 짝이 되는 다른 최적화 문제(쌍대문제, dual)를 대응시켜, 한쪽의 임의의 실행가능점이 다른 쪽 최적값의 경계를 증명하게 만드는 구조다. 최소화 문제라면 쌍대의 값은 언제나 원문제 최적값 이하이고, 좋은 조건에서는 두 값이 정확히 일치한다.¹

이 구조가 왜 최적화 이론의 절반을 차지하는지는 세 가지로 정리된다. 첫째, 증명서를 준다 — 쌍대 실행가능점 하나면 “내 답이 최적에서 얼마나 떨어져 있는가”를 증명할 수 있다. 둘째, 어려운 문제를 쉬운 문제로 바꾼다 — 변수가 백만 개인데 제약이 열 개면 쌍대는 10차원 문제다. 셋째, 분해를 가능하게 한다 — 결합 제약만 승수로 빼내면 나머지가 서로 독립인 부분문제로 쪼개진다. 분산 최적화와 교대방향 승수법이 전부 이 세 번째 줄에서 나온다.

이 문서는 최적화의 쌍대성을 다룬다. 전자기학의 전기-자기 쌍대, 평면그래프의 쌍대그래프, 벡터공간의 쌍대공간 등은 이름만 같고 별개다(사실 완전히 무관하지는 않지만, 여기서는 다루지 않는다).

2. 라그랑주 쌍대함수[편집]

표준형 문제를 잡는다.

p^\star = \min_x f_0(x) \quad \text{s.t.}\quad f_i(x) \le 0\ (i=1..m),\quad h_j(x) = 0\ (j=1..p)

제약을 목적함수 안으로 흡수해 라그랑주 함수를 만든다.

L(x,\lambda,\nu) = f_0(x) + \sum_i \lambda_i f_i(x) + \sum_j \nu_j h_j(x)

여기서 $\lambda \succeq 0$ 이고 $\nu$ 는 부호 자유다. $x$ 에 대해 최소화한 것이 쌍대함수다.

g(\lambda,\nu) = \inf_x L(x,\lambda,\nu)

즉시 나오는 두 가지 사실이 이 문서의 뼈대다.

쌍대함수는 항상 오목하다. $L$ 은 $(\lambda,\nu)$ 에 대해 아핀이고, 아핀함수 족의 하한은 언제나 오목이기 때문이다. $f_0$ 이 뭐든, 제약이 뭐든, 원문제가 정수계획이든 비볼록이든 상관없다. 따라서 쌍대문제 $\max_{\lambda\succeq0,\nu} g(\lambda,\nu)$ 는 언제나 볼록 문제다.

쌍대함수는 항상 하계다(약쌍대성). 실행가능한 $\tilde x$ 에 대해 $f_i(\tilde x)\le0$ , $h_j(\tilde x)=0$ , $\lambda\succeq0$ 이므로

g(\lambda,\nu) \le L(\tilde x,\lambda,\nu) = f_0(\tilde x) + \underbrace{\textstyle\sum_i \lambda_i f_i(\tilde x)}_{\le 0} + 0 \le f_0(\tilde x)

양변에 최적화를 취하면 $d^\star = \sup g \le p^\star$ . 증명이 두 줄이다. 이 두 줄이 분지한정법의 가지치기부터 볼록 솔버의 정지 조건까지 전부를 떠받친다.

3. 강쌍대성 — 언제 간극이 사라지나[편집]

$p^\star - d^\star \ge 0$ 을 쌍대 간극(duality gap)이라 부른다. 이게 0이면 강쌍대성이다.

볼록 + 슬레이터 조건이면 성립한다. 슬레이터 조건은 “비아핀 부등식 제약을 엄격히 만족하는 실행가능점이 하나라도 존재한다”는 요구다. 등식·아핀 제약은 엄격성이 필요 없다는 정련된 판본이 실무에서 쓰인다.
선형계획은 제약자격이 아예 필요 없다. 원·쌍대 중 하나라도 실행가능하고 유계면 두 값이 일치한다. 자세한 것은 선형계획법 쪽 — 그 문서가 심플렉스법·상보여유와 함께 다룬다.
볼록인데도 간극이 나는 경우가 있다. 슬레이터가 깨지는 병리적 예제들이 그것이며, 그래서 “볼록이니까 강쌍대성”은 반쪽짜리 문장이다.
비볼록이면 대개 간극이 난다. 이유는 르장드르-펜셸 변환 언어로 정확히 설명된다 — 쌍대를 두 번 거치면 원함수가 아니라 그 닫힌 볼록 포락이 돌아오고, 간극이 정확히 그 차이다.
그런데 비볼록이면서도 간극이 0인 놀라운 사례들이 있다. 신뢰영역 부분문제(구 제약 아래의 비볼록 이차식 최소화)가 대표로, S-보조정리 덕에 쌍대 간극이 정확히 0이다. 신뢰 영역 방법이 매 스텝 비볼록 부분문제를 풀면서도 전역해를 얻는 근거가 여기다. 이런 걸 숨은 볼록성(hidden convexity)이라 부른다.

4. 상보여유는 어디서 나오는가[편집]

강쌍대성이 성립하고 최적해 $x^\star$ , $(\lambda^\star,\nu^\star)$ 가 존재한다고 하자. 부등식 사슬을 그대로 따라가면 된다.

f_0(x^\star) = g(\lambda^\star,\nu^\star) = \inf_x L(x,\lambda^\star,\nu^\star) \le L(x^\star,\lambda^\star,\nu^\star) = f_0(x^\star) + \sum_i \lambda_i^\star f_i(x^\star) \le f_0(x^\star)

양 끝이 같으므로 중간의 부등호가 전부 등호여야 한다. 첫 번째 등호에서 ” $x^\star$ 는 $L(\cdot,\lambda^\star,\nu^\star)$ 의 최소점”이 나오고(= 정상성 조건), 두 번째에서

\lambda_i^\star f_i(x^\star) = 0 \quad \forall i

상보여유가 나온다. 제약이 느슨하면 승수가 0, 승수가 양수면 제약이 딱 붙어 있다. 이 두 조건에 원·쌍대 실행가능성을 더한 것이 카루시-쿤-터커 조건이며, 그쪽 문서가 네 항목과 제약자격 함정을 자세히 다룬다. 여기서 강조할 것은 KKT가 하늘에서 떨어진 조건이 아니라 위 사슬을 등호로 만드는 요구사항의 목록이라는 점이다.

5. 승수는 그림자 가격이다[편집]

쌍대변수에 물리적 의미를 주는 것은 섭동 함수다. 우변을 $u$ 만큼 흔들어 본다.

p^\star(u) = \inf_x \{ f_0(x) : f_i(x) \le u_i \}

원문제가 볼록이면 $p^\star$ 도 볼록이고, 강쌍대성 아래에서 전역 부등식

p^\star(u) \ \ge\ p^\star(0) - \lambda^{\star\top} u

가 성립한다. $p^\star$ 가 미분 가능하면 여기서 $\lambda_i^\star = -\partial p^\star(0)/\partial u_i$ 가 떨어진다. 즉 승수는 제약을 한 단위 완화했을 때 최적값이 개선되는 비율이다. 경제학에서 이걸 그림자 가격(shadow price)이라 부르고, 자원 $b_i$ 한 단위를 더 사 올 만한 값어치가 있는지를 판정하는 데 그대로 쓴다. 승수가 0인 제약을 완화하는 데 예산을 쓰는 것은 정의상 낭비다.

공학에서도 같은 물건이 정확히 그 자리에 있다.

**접촉 해석**의 접촉압력이 비관통 제약의 승수다. 상보여유가 곧 “떨어져 있으면 압력 0”인 시뇨리니 조건이고, 이산화하면 선형 상보성 문제가 된다.
강체 구속의 반력, 혼합 유한요소에서의 압력·응력 변수도 전부 승수다. 비압축성 유동의 압력이 $\nabla\cdot u=0$ 의 승수라는 관점은 유한요소법과 안장점 문제의 표준 서술이다.
구조 최적화에서 활성 응력 제약의 승수 크기는 곧 “이 제약을 조금 풀면 무게가 얼마나 줄어드는가”로 읽히며, 민감도 해석의 수반변수와 같은 종류의 정보다.
부등식 승수가 부호를 갖는 이유도 이 해석으로 설명된다. 벽은 밀 수만 있고 당길 수 없다.

6. 켤레로 본 쌍대 — 펜셸[편집]

라그랑주 쌍대는 제약이 있는 문제의 언어인데, 현대 신호처리·통계에서 만나는 문제는 대개 제약 없이 합으로 쓰여 있다. 이때는 펜셸 쌍대가 자연스럽다.

\inf_x \bigl\{ f(x) + g(Ax) \bigr\} = \sup_y \bigl\{ -f^*(-A^\top y) - g^*(y) \bigr\}

$f^*$ 가 르장드르-펜셸 변환으로 얻는 켤레다. 사실 둘은 같은 이야기다 — $z = Ax$ 를 새 변수로 두고 등식 제약 $Ax - z = 0$ 에 승수를 붙이면 라그랑주 쌍대가 정확히 위 식이 된다. 켤레 사전(노름의 켤레는 쌍대 노름 공의 지시함수, 지시함수의 켤레는 지지함수 등)과 펜셸-영 부등식은 그쪽 문서에 있으니 여기서 반복하지 않는다. 실용적 요점만 옮기면, ℓ1 최소화의 쌍대가 ℓ∞ 공 위의 문제로 나오는 식의 구조 교환이 이 한 줄에서 전부 나오고, 기저 추구가 최적성 인증서를 제시할 수 있는 것도 쌍대 실행가능한 벡터를 하나 들고 있기 때문이다.

7. 쌍대가 볼록이라는 사실의 실용적 의미[편집]

1. 비볼록 문제에도 하한을 준다. 정수계획에서 어려운 제약만 승수로 완화하면(라그랑주 완화) 남는 문제가 배낭이나 최단경로처럼 다항시간에 풀리는 구조가 되고, 그 쌍대값이 분지한정 트리의 가지치기 경계가 된다. 완화가 주는 하한은 보통 LP 완화보다 촘촘하다. 다만 쌍대함수는 조각선형 오목이라 비평활이므로, 최대화에는 부분경사법이나 다발법이 필요하다 — 비평활 최적화 문서 참고.

2. 차원이 뒤집힌다. 원문제 변수가 $n$ , 제약이 $m$ 이면 쌍대는 $m$ 차원이다. $m \ll n$ 이면 쌍대를 푸는 것이 압도적으로 싸다. 반대 방향도 있다 — 아래 SVM은 특징 차원이 무한대여도 쌍대는 표본 수만큼의 변수만 갖는다.

3. 분해된다. 목적과 제약이 블록별로 분리 가능한데 결합 제약 하나가 블록들을 묶고 있다면, 그 제약만 승수로 빼내는 순간 $\inf_x L$ 이 블록별 독립 최소화로 쪼개진다.

\lambda^{k+1} = \bigl[\lambda^k + \alpha_k\, (\text{제약 위반량})\bigr]_+

각 블록이 현재 “가격” $\lambda$ 를 보고 독립적으로 최적화하고, 조정자는 수요-공급 불일치를 보고 가격을 올리거나 내린다. 이것이 쌍대 분해이며 경제학의 가격 조정 과정과 문자 그대로 같은 알고리즘이다. 순수 쌍대 상승법은 $g$ 가 미분 가능해야(= $L$ 의 최소점이 유일해야) 안정적이라 실전에서는 잘 안 쓰이고, 증강항을 붙여 그 요구를 없앤 증강 라그랑주법과 그것을 두 블록으로 쪼갠 교대방향 승수법이 실무 표준이다. 분산 학습·전력망 급전·다분야 최적화가 전부 이 계보에 있다.

8. SVM 쌍대와 커널 트릭[편집]

쌍대성이 알고리즘의 성격 자체를 바꿔 버린 가장 유명한 사례. 소프트 마진 서포트 벡터 머신의 원문제는

\min_{w,b,\xi}\ \tfrac12\|w\|^2 + C\sum_i \xi_i \quad \text{s.t.}\quad y_i(w^\top x_i + b) \ge 1 - \xi_i,\ \ \xi_i \ge 0

이고, 승수 $\alpha_i$ 를 붙여 $w,b,\xi$ 를 소거하면 쌍대가 이렇게 나온다.

\max_{\alpha}\ \sum_i \alpha_i - \tfrac12 \sum_{i,j} \alpha_i\alpha_j\, y_iy_j\, \langle x_i, x_j\rangle \quad \text{s.t.}\quad 0 \le \alpha_i \le C,\ \ \sum_i \alpha_i y_i = 0

읽을 지점이 세 개다.

변수가 특징 차원 $d$ 에서 표본 수 $n$ 으로 바뀌었다. $d \gg n$ 인 문제에서 이건 그 자체로 이득이다.
데이터가 오직 내적 $\langle x_i,x_j\rangle$ 로만 등장한다. 그 자리에 커널 $K(x_i,x_j)$ 를 꽂으면 특징 공간을 명시적으로 만들지 않고도 그 공간에서의 선형 분류를 수행하게 된다. 특징 차원이 무한대여도 상관없다. 이것이 커널 트릭이고, 쌍대로 넘어가지 않으면 애초에 이 문이 열리지 않는다.
상보여유가 서포트 벡터를 정의한다. $\alpha_i > 0$ 인 표본만 마진 위(또는 안)에 있고 나머지는 $\alpha_i = 0$ 이라 해에 전혀 기여하지 않는다. “결정 경계는 소수의 표본이 결정한다”는 SVM의 표어가 KKT 한 줄의 결과다.

9. 미니맥스로 보면[편집]

쌍대성은 순서 교환의 문제로도 읽힌다. $\sup_{\lambda\succeq0} L(x,\lambda)$ 는 $x$ 가 실행가능하면 $f_0(x)$ , 아니면 $+\infty$ 이므로

p^\star = \inf_x \sup_{\lambda \succeq 0} L(x,\lambda), \qquad d^\star = \sup_{\lambda \succeq 0} \inf_x L(x,\lambda)

즉 **약쌍대성 = “max-min ≤ min-max”**라는 일반 부등식의 한 사례일 뿐이다. 나중에 두는 쪽이 유리하다는, 게임의 상식 그대로다. 등호가 성립하는 조건이 미니맥스 정리이고(폰 노이만의 유한 행렬게임, 시온의 볼록-오목 일반화), 등호가 성립할 때 $(x^\star,\lambda^\star)$ 가 $L$ 의 **안장점**이 된다. 게임 이론의 혼합전략 균형과 선형계획 쌍대성이 사실상 같은 정리라는 것도 여기서 나오며, 네트워크의 최대유량-최소절단 정리 역시 같은 계보다(네트워크 흐름).

10. 실무 감각[편집]

상용 솔버가 찍어 주는 primal obj / dual obj / gap 세 줄이 위 이론 전부다. 상대 간극이 허용치 아래로 내려가면 멈춘다. 내점법에서는 이 간극이 중심 경로 매개변수로 $m/t$ 처럼 명시적으로 묶인다.
쌍대해를 그냥 믿기 전에 원문제 해가 유일한지 확인해야 한다. 원문제에 최적해가 여러 개면 쌍대는 퇴화하고, 승수 값이 솔버마다 다르게 나온다. 민감도 해석 보고서를 그대로 인용하기 전에 퇴화 여부를 보라는 실무 격언이 여기서 온다.
쌍대를 풀어 $\lambda^\star$ 를 얻었다고 $x^\star$ 가 자동으로 나오지는 않는다. $L(\cdot,\lambda^\star)$ 의 최소점이 유일하면 그 점이 답이지만, 유일하지 않으면(선형 목적함수가 흔한 사례) 별도의 원해 복원 절차가 필요하다. 정수계획의 라그랑주 완화에서 얻은 해가 원문제에서 실행 불가능한 광경은 이 때문에 일상적으로 벌어진다.²
쌍대 간극이 크다고 알고리즘이 틀린 게 아니다. 비볼록 문제에서 간극은 정리의 결론이다. 진짜 버그는 간극이 음수로 나오는 것이다 — 그건 원문제 해가 실행 불가능하거나 부호 규약을 틀린 것이다.³

11. 관련 문서[편집]

이 바닥에서 쌍대성을 처음 배우면 “그래서 쌍대문제를 풀라는 거야 말라는 거야”라는 실용적 혼란이 온다. 답은 “둘 다 본다”에 가깝다. 원 쪽은 답을, 쌍대 쪽은 그 답이 옳다는 증명을 준다. 증명 없는 답은 반복을 언제 멈출지 모르는 답이다. ↩
그래서 라그랑주 완화 기반 코드에는 거의 항상 “복원 휴리스틱”이 붙어 있다. 완화해가 준 정보로 실행가능해를 억지로 만들어 상한을 갱신하고, 쌍대에서 나온 하한과의 간극을 보고 가지치기한다. 이론이 준 것은 하한 하나뿐이고, 나머지 절반은 여전히 사람이 짠다. ↩
부호 규약 사고는 정말 흔하다. 최대화 문제를 최소화로 바꾸면서 승수 부호 제약을 안 뒤집거나, 제약을 $f_i(x)\le 0$ 이 아니라 $f_i(x)\ge 0$ 으로 써 놓고 같은 공식을 쓰는 경우다. 증상이 “간극이 음수”로 아주 정직하게 나오니, 최소한 진단은 쉽다. ↩

쌍대성