르장드르-펜셸 변환

1. 개요

르장드르-펜셸 변환 Legendre–Fenchel Transform
다른 이름	볼록 켤레(convex conjugate), 쌍대 함수
정의	f*(y) = supx ( ⟨x, y⟩ − f(x) )
정립	Legendre(1787, 매끄러운 판) → Fenchel(1949) → Moreau, Rockafellar
항상 성립	f*는 f가 무엇이든 볼록·하반연속
대합성	f** = f ⟺ f가 고유·볼록·하반연속

르장드르-펜셸 변환은 함수 $f$ 를, 그 그래프 아래를 받치는 아핀함수들의 절편 정보로 다시 쓰는 변환이다. $\mathbb{R}^n$ 위의 확장실수값 함수 $f$ 에 대해

$$f^*(y) = \sup_{x \in \mathbb{R}^n} \bigl\{ \langle x, y\rangle - f(x) \bigr\}$$

로 정의하고, $f^*$ 를 $f$ 의 켤레(conjugate)라 부른다. 정의만 보면 그냥 sup이지만, 이 한 줄이 볼록 최적화의 쌍대성 전체, 통계역학의 자유에너지, 해밀토니안 역학의 정준 형식을 한꺼번에 떠받친다.

읽는 법은 이렇다. 기울기 $y$ 인 직선 $\langle x,y\rangle - c$ 를 아래에서 위로 밀어 올려 $f$ 의 그래프에 닿게 만들 때, 그 직선의 절편의 최댓값이 $-f^*(y)$ 다. 즉 함수를 “점 $(x, f(x))$ 의 집합”이 아니라 “그 아래를 받칠 수 있는 직선 $(y, \text{절편})$ 의 집합” 으로 표현하는 것 — 볼록집합을 경계점으로 기술할 것이냐 접평면(반공간)의 교집합으로 기술할 것이냐의 선택이며, 르장드르-펜셸 변환은 그 두 기술법 사이의 사전이다.¹

여기서 즉시 나오는 성질 하나. $f^*$ 는 $y$ 에 대한 아핀함수들의 상한이므로, $f$ 가 볼록이든 아니든 심지어 측정 불가능한 괴물이든 언제나 볼록이고 하반연속이다. 변환이 공짜로 볼록성을 만들어 낸다.

2. 펜셸-영 부등식과 부미분

정의에서 sup을 떼면 곧바로 펜셸-영 부등식이 나온다. 모든 $x, y$ 에 대해

$$f(x) + f^*(y) \ \ge\ \langle x, y\rangle$$

이고, 여기서 등호가 성립하는 조건이 전부다. $f$ 가 고유 볼록이면

$$f(x) + f^*(y) = \langle x, y\rangle \iff y \in \partial f(x) \iff x \in \partial f^*(y)$$

(마지막 동치는 $f$ 가 닫혀 있을 때). 즉 $\partial f$ 와 $\partial f^*$ 는 서로 역관계다. 매끄러운 경우로 좁히면 $y = \nabla f(x)$, $x = \nabla f^*(y)$ 이며, 이것이 고전 르장드르 변환에서 “미분이 새 변수가 된다”고 배우는 그 문장의 정확한 판본이다.

부수적으로 유용한 예도 여기서 떨어진다. $f(x) = \frac{1}{p}\lvert x\rvert^p$ 를 넣으면 $f^*(y) = \frac{1}{q}\lvert y\rvert^q$ ($1/p + 1/q = 1$)이므로 펜셸-영 부등식이 그대로 영 부등식 $\lvert xy\rvert \le \lvert x\rvert^p/p + \lvert y\rvert^q/q$ — 횔더 부등식의 씨앗 — 이 된다.

3. 이중공액 — 언제 되돌아오는가

$f^*$ 를 한 번 더 변환한 $f^{**}$ 는 무엇인가. 펜셸-모로 정리가 답한다.

$$f^{**} = f \iff f \text{ 가 고유(proper) · 볼록 · 하반연속}$$

그렇지 않으면 $f^{**}$ 는 $f$ 의 닫힌 볼록 포락(아래를 받치는 아핀함수들의 상한, 즉 $f$ 이하의 가장 큰 닫힌 볼록 함수)이다. 이 사실이 실무에서 갖는 의미는 뼈아프다 — 비볼록 함수를 켤레로 왕복시키면 볼록화된 것만 돌아온다. 비볼록 문제의 쌍대에 항상 쌍대 간극(duality gap)이 생기는 이유가 정확히 이것이고, 이산 최적화의 완화(relaxation)가 무엇을 잃는지도 여기서 설명된다.²

4. 켤레 사전

외워 두면 논문 읽는 속도가 달라지는 짝들.

• $f = \frac{1}{2}\lVert x\rVert_2^2$ → $f^* = \frac{1}{2}\lVert y\rVert_2^2$. 유일한 자기쌍대다. 유클리드 제곱거리가 최적화 이론에서 특권을 갖는 근원.
• $f = \iota_C$ (집합 $C$ 의 지시함수) → $f^* = \sigma_C$, 즉 지지함수 $\sigma_C(y)=\sup_{x\in C}\langle x,y\rangle$. 반대로 $\sigma_C$ 의 켤레는 $\iota_{\overline{\mathrm{conv}}\,C}$ 다. 제약과 목적함수가 서로 자리를 바꾼다.
• $f = \lVert x\rVert$ (임의의 노름) → $f^* = \iota_{B_*}$, 쌍대 노름의 단위공의 지시함수. $\ell_1$ 노름의 켤레가 $\ell_\infty$ 공의 지시함수라는 이 한 줄이 압축센싱의 쌍대 문제 전체를 만든다.
• $f = \frac{1}{p}\lVert x\rVert_p^p$ → $f^* = \frac{1}{q}\lVert y\rVert_q^q$.
• $f(x) = \log\sum_i e^{x_i}$ (로그합지수) → $f^*(y) = \sum_i y_i \log y_i$ (단, $y \ge 0$ 이고 $\sum_i y_i = 1$; 아니면 $+\infty$). 즉 로그합지수의 켤레는 확률 심플렉스 위의 음의 엔트로피이고, 두 사람을 잇는 그래디언트 사상 $\nabla f$ 가 바로 소프트맥스 함수다. 딥러닝의 로짓→확률 변환은 르장드르 쌍의 한쪽 미분이었던 셈이다.
• $f(x) = e^x$ → $f^*(y) = y\log y - y$ ($y > 0$).
• $f$ 가 $\mu$-강볼록 ⟺ $f^*$ 가 미분가능하고 $\nabla f^*$ 가 $\frac{1}{\mu}$-립시츠. 강볼록성과 매끄러움이 서로의 거울상이라는 이 대응이 1차 최적화 수렴률 표를 절반으로 줄여 준다.
• 모로 포락: $(M_{\lambda f})^* = f^* + \frac{\lambda}{2}\lVert\cdot\rVert^2$. 원 쪽에서 매끄럽게 하는 것 = 쌍대 쪽에서 강볼록하게 하는 것.

5. 물리에서의 같은 변환

열역학에서 배우는 르장드르 변환이 위의 것과 같은 연산이다. 내부에너지 $U(S,V)$ 에서 엔트로피를 온도로 바꿔 헬름홀츠 자유에너지 $F(T,V) = \inf_S \{U - TS\}$ 를, 부피를 압력으로 바꿔 엔탈피 $H(S,p)$ 를, 둘 다 바꿔 깁스 자유에너지 $G(T,p)$ 를 얻는다. 부호와 inf/sup 관례만 다를 뿐 정확히 $f \mapsto f^*$ 다. 시차 변수(extensive) ↔ 강도 변수(intensive)의 짝은 곧 $x \leftrightarrow y = \nabla f(x)$ 의 짝이고, 맥스웰 관계식은 $\nabla f^*$ 가 $\nabla f$ 의 역사상이라는 사실의 미분 판본이다.

고전역학도 마찬가지다. 라그랑주 역학의 $L(q,\dot q)$ 에서 정준운동량 $p = \partial L/\partial \dot q$ 로 갈아타면 해밀토니안

$$H(q,p) = \sup_{\dot q}\ \bigl\{\, p\cdot \dot q - L(q, \dot q) \,\bigr\}$$

가 나온다. 물리 교과서가 ”$L$ 이 $\dot q$ 에 대해 볼록해야 한다”고 슬쩍 요구하는 이유도, 그게 아니면 이중공액이 원래대로 돌아오지 않기 때문이다.³ 통계역학 쪽에서는 큐뮬런트 생성함수와 대편차 속도함수(rate function)의 관계 — 크라메르 정리 — 가 정확히 켤레쌍이다.

6. 펜셸 쌍대성과 알고리즘

두 볼록 함수의 합을 최소화하는 문제 $\min_x f(x) + g(Ax)$ 에는 펜셸 쌍대

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

가 붙는다(적절한 정칙성 조건 아래 등호). 라그랑주 쌍대성을 따로 배우지 않아도 이 한 줄에서 선형계획의 쌍대, SVM의 쌍대, 라쏘의 쌍대가 전부 나온다. 이 구조가 한쪽이 어려우면 다른 쪽을 풀어라를 정당화하며, 원시-쌍대 기법의 근거가 된다.

알고리즘 쪽 접점을 몇 개만 추리면 이렇다.

• 교대방향 승수법·더글러스-래치포드 — 분할되는 두 항이 사실 원시/쌍대 쌍이고, 스텝마다 $f$ 와 $g^*$ 를 번갈아 건드린다.
• 브레그만 발산 — $D_\varphi(x,y) = D_{\varphi^*}(\nabla\varphi(y), \nabla\varphi(x))$ 라는 쌍대 항등식이 성립해, 미러 하강의 수렴 해석이 켤레 공간에서 이뤄진다.
• 근접점 알고리즘의 모로 분해 $x = \mathrm{prox}_f(x) + \mathrm{prox}_{f^*}(x)$ — prox 계산을 통째로 쌍대로 넘기는 실전 트릭.
• 하한 합성곱 $(f\,\square\,g)(x) = \inf_u \{f(u)+g(x-u)\}$ 의 켤레가 $f^* + g^*$ 라는 것. 합↔하한합성곱이 켤레 아래에서 뒤집히는 이 성질이 모로 포락과 정보 기하의 여러 등식의 출처다.

계산 관점의 현실 감각 하나. 켤레는 정의상 sup, 즉 또 하나의 최적화 문제다. 사전에 있는 짝이면 공짜지만 없으면 종이 위의 대상이다. 그래서 실무 코드는 켤레를 “계산”하지 않는다 — 이미 아는 켤레쌍을 조립해 쓸 뿐이다.⁴

7. 관련 문서

• 볼록 최적화 · 모로 포락 · 근접점 알고리즘
• 브레그만 발산 · 정보 기하 · 쿨백-라이블러 발산
• 라그랑주 승수법 · 카루시-쿤-터커 조건 · 선형계획법
• 교대방향 승수법 · 근접 경사법 · 내점법
• 해밀토니안 역학 · 라그랑주 역학 · 깁스 자유에너지
• 소프트맥스 함수 · 압축센싱 · 헤세 행렬

8. Footnotes

1. 이름이 둘 붙은 데는 이유가 있다. 르장드르(1787)의 원래 변환은 $f$ 가 매끄럽고 강볼록이라 $\nabla f$ 가 전단사인 경우에만 정의됐다 — $f^*(y) = \langle (\nabla f)^{-1}(y), y\rangle - f((\nabla f)^{-1}(y))$. 펜셸(1949)이 이걸 sup으로 다시 써서 미분가능성 요구를 통째로 걷어냈고, 그 덕에 $\ell_1$ 노름이나 지시함수 같은 뾰족한 물건도 정상적으로 변환된다. 매끄러운 세계에서만 놀 거면 르장드르로 충분하지만, 이 바닥의 정규화항은 죄다 안 매끄럽다. ↩

2. 그래서 “쌍대 문제를 풀었더니 원 문제 최적값보다 작더라”는 상황은 버그가 아니라 정리의 결론이다. 쌍대 간극 = 원함수와 그 볼록 폐포 사이의 간격. 정수계획을 LP로 완화할 때 잃는 게 정확히 이 간격이고, 절단평면법은 그 간격을 조금씩 메우는 작업이다. ↩

3. 상대론적 자유입자 $L = -mc^2\sqrt{1-v^2/c^2}$ 를 변환하면 $H = \sqrt{p^2c^2 + m^2c^4}$ 가 예쁘게 나오는 것도, $L$ 이 $v$ 에 대해 강볼록이고 $\lvert v\rvert < c$ 에서 매끄럽기 때문이다. 볼록성이 깨지는 라그랑지언(예: 특이 라그랑지언)에서는 정준 형식으로의 이행이 막히고, 그때 필요한 게 디랙의 구속 해밀토니안 형식이다. ↩

4. 그래도 수치적으로 켤레를 계산해야 할 때가 있긴 하다. 1차원 격자 위에서라면 고속 르장드르 변환(Lucet의 알고리즘)이 $O(n)$ 에 이산 켤레를 구해 준다. 볼록 함수의 켤레가 기울기 순서를 보존한다는 성질을 써서 monotone stack 하나로 밀어붙이는 방식인데, 이런 게 있다는 사실 자체를 아는 사람이 드물다. ↩