지지함수

최적설계 수치해석 게임 개발 마지막 수정: 2026-08-16 04:33:52

1. 개요[편집]

지지함수 Support Function
정의	h_C(x) = sup { ⟨x, y⟩ : y ∈ C }
정체	볼록집합을 지지초평면의 절편으로 기술한 것
성질	양의 1차 동차 · 볼록 · 하반연속
대응	닫힌 볼록집합 ↔ 닫힌 열선형(sublinear) 함수, 일대일
계산 응용	GJK · 절단평면 · 도달가능집합

지지함수는 볼록집합을 “점들의 모임”이 아니라 **“그 집합을 받치는 초평면들의 위치”**로 다시 쓴 표현이다. $\mathbb{R}^n$ 의 공집합 아닌 집합 $C$ 에 대해

h_C(x) = \sup_{y \in C} \langle x, y \rangle

로 정의한다. 기하적으로 읽으면 이렇다 — 방향 $x$ 를 잡고 그 방향의 법선을 가진 초평면을 무한히 먼 곳에서 밀고 들어와 $C$ 에 처음 닿았을 때, 그 초평면이 $\{y : \langle x,y\rangle = h_C(x)\}$ 다. 즉 지지함수는 **모든 방향에서 잰 “집합의 끝 위치”**를 한꺼번에 기록한 장부다.

이 표현이 유용한 이유는 두 가지다. 첫째, 볼록집합에 대한 연산 상당수가 지지함수 쪽에서는 덧셈이나 최댓값 같은 초등 연산으로 바뀐다. 둘째, 집합을 명시적으로 저장하지 않고 “방향을 주면 값을 돌려주는 오라클”로만 다룰 수 있게 된다. GJK 알고리즘이 민코프스키 차를 실제로 만들지 않고도 충돌을 판정하는 것, 절단평면법이 제약 집합 전체를 모르는 채로 최적화를 진행하는 것이 전부 이 두 번째 성질 덕이다.¹

2. 기본 성질과 일대일 대응[편집]

정의에서 곧바로 나오는 것들.

양의 1차 동차: $h_C(\lambda x) = \lambda\, h_C(x)$ , $\lambda \ge 0$ .
열가법성(subadditive): $h_C(x_1+x_2) \le h_C(x_1)+h_C(x_2)$ . 위 둘을 합치면 $h_C$ 는 볼록이며, 상한의 정의상 언제나 하반연속이다.
$C$ 가 무엇이든 $h_C = h_{\overline{\mathrm{conv}}\,C}$ . 지지함수는 볼록성과 폐포 이외의 정보를 전부 버린다. 거꾸로 말하면 닫힌 볼록집합만이 지지함수로 완전히 복원된다.
$h_C$ 가 어디서나 유한 $\iff$ $C$ 가 유계.
$\partial h_C(x) = \arg\max_{y\in C}\langle x,y\rangle$ — 즉 **부미분이 그 방향의 접촉면(face)**이다. 최댓값을 주는 점이 유일하면 $h_C$ 는 그 방향에서 미분가능하고, 접촉면이 면 전체면 부미분이 그 면 전체가 된다. $C$ 의 모서리(꼭짓점)와 $h_C$ 의 매끄러움이 서로 뒤바뀌어 대응한다는 뜻이다.

그리고 결정적인 것 하나. 위 성질은 지지함수를 완전히 특징짓는다. $h:\mathbb{R}^n\to(-\infty,+\infty]$ 가 고유하고 양의 1차 동차이며 볼록·하반연속이면(즉 닫힌 열선형이면), 반드시 어떤 닫힌 볼록집합의 지지함수이고 그 집합은

C = \bigl\{\, y \in \mathbb{R}^n \;:\; \langle x, y\rangle \le h(x) \ \ \forall x \,\bigr\}

로 유일하게 복원된다. 닫힌 볼록집합 전체와 닫힌 열선형 함수 전체 사이의 일대일 대응이며, 이것이 이 문서 나머지 전부의 근거다. 집합에 대한 명제를 함수에 대한 명제로 번역해도 정보 손실이 없다는 허가증이기 때문이다.

3. 집합 연산이 함수 연산으로 바뀐다[편집]

지지함수가 진짜 힘을 발휘하는 지점.

h_{C+D} = h_C + h_D, \qquad h_{\overline{\mathrm{conv}}(C\cup D)} = \max\{h_C,\, h_D\}, \qquad h_{\lambda C} = \lambda\, h_C \ (\lambda\ge 0)

h_{AC}(x) = h_C(A^\top x), \qquad h_{-C}(x) = h_C(-x)

첫 식이 특히 중요하다. 민코프스키 합이 지지함수 쪽에서는 그냥 덧셈이 된다. 볼록다면체 두 개의 민코프스키 합을 정점 리스트로 계산하려면 조합적 폭발을 감수해야 하지만, 지지함수로는 두 오라클을 더하면 끝이다. 강체 두 개의 충돌 판정이 “차집합 도형이 원점을 품는가”로 환원되고 그 도형을 만들 필요가 없는 이유가 바로 이것이다.

교집합은 사정이 다르다. $h_{C\cap D} \le \min\{h_C,h_D\}$ 이지만 등호가 성립하지 않는다. 교집합의 지지함수는 오히려 $h_C$ 와 $h_D$ 의 하한 합성곱

h_{C\cap D} = \overline{\bigl(h_C \,\square\, h_D\bigr)} \qquad (\text{적절한 정칙성 조건 아래})

으로 나온다. 즉 합집합 쪽은 max로 쉽고 교집합 쪽은 하한합성곱으로 어렵다. 도달가능집합 계산이 합집합·민코프스키 합만 있는 한 정확하지만 교차 제약이 끼는 순간 근사로 내려가는 이유가 여기 있다.

4. 켤레와 지시함수[편집]

르장드르-펜셸 변환의 언어로 보면 지지함수의 정체는 한 줄이다. 집합 $C$ 의 지시함수 $\delta_C$ ( $C$ 안이면 0, 밖이면 $+\infty$ )에 대해

\delta_C^* = h_C, \qquad h_C^* = \delta_{\overline{\mathrm{conv}}\,C}

즉 지지함수와 지시함수는 서로의 켤레다. 켤레 변환의 성질과 위 절의 항등식들이 정확히 대응한다는 것도 확인해 두면 좋다 — $h_{C+D}=h_C+h_D$ 는 “하한합성곱의 켤레는 켤레의 합”이라는 일반 법칙에 $\delta_C \square \delta_D = \delta_{C+D}$ 를 대입한 것이고, 교집합 쪽의 어려움은 “합의 켤레가 켤레의 하한합성곱”이 정칙성 조건을 요구한다는 사실 그대로다. 쌍대성 일반론은 르장드르-펜셸 변환과 쌍대성 문서에 있으니 여기서는 반복하지 않는다.

노름과의 관계도 이 틀 안에 있다. 임의의 노름 $\|\cdot\|$ 의 쌍대 노름은 단위공의 지지함수다.

\|x\|_* = h_{B}(x) = \sup_{\|y\|\le 1}\langle x,y\rangle

$\ell_1$ 공의 지지함수가 최대절댓값 노름이고 그 반대도 성립한다는, 압축센싱 논문 첫 페이지의 그 문장이 지지함수의 특수 사례다.

5. 계산 — support mapping과 오라클[편집]

실무에서 쓰는 것은 값 $h_C(x)$ 보다 최댓값을 달성하는 점 $s_C(x) \in \arg\max_{y\in C}\langle x,y\rangle$ 인 경우가 많다. 전자를 지지함수, 후자를 지지 사상(support mapping)이라 구분해 부른다. 부미분 성질에 의해 $s_C(x)$ 는 $h_C$ 의 부기울기이므로, 지지 사상 하나만 있으면 함수값과 기울기를 동시에 얻는 셈이다.

GJK 알고리즘. 볼록체마다 지지 사상만 구현해 두면 나머지가 전부 자동이다. 구는 $c + r\,x/\|x\|$ , 볼록다면체는 정점 중 내적 최대인 것, 캡슐·원기둥도 닫힌 형태로 나온다. 그리고 민코프스키 차의 지지 사상은 $s_{A\ominus B}(x) = s_A(x) - s_B(-x)$ 로 조립된다 — 도형을 만들지 않고 오라클만 합성하는 것이다. 충돌 감지의 좁은 단계 전체가 이 한 줄 위에 서 있다.
절단평면법·번들법. 제약 집합이 지수 개의 부등식으로 주어졌거나 아예 암묵적일 때, 필요한 것은 “현재 점이 집합 안인가, 아니면 위반된 부등식 하나를 내놓아라”라는 분리 오라클뿐이다. 그리고 분리 오라클은 지지함수 평가와 같은 물건이다 — $h_C(x) < \langle x, \hat y\rangle$ 이면 $x$ 가 분리 초평면의 법선이다. 타원체법과 절단평면법이 “다항시간 알고리즘은 분리 오라클만 있으면 된다”는 형태로 정리되는 근거이며, 번들법이 비매끄러운 목적함수를 부기울기들의 max로 근사하는 것도 지지함수 표현의 재사용이다.²
도달가능집합. 선형 시스템 $\dot x = Ax + Bu$ , $u(t) \in U$ 의 시각 $T$ 도달가능집합은 민코프스키 적분이고, 지지함수는 적분으로 정확히 계산된다. $h_{R(T)}(p) = h_{e^{AT}X_0}(p) + \int_0^T h_{BU}\!\bigl(B^\top e^{A^\top (T-s)}p\bigr)\,ds$ 집합을 다면체나 존노토프로 표현하면 시간이 갈수록 정점 수가 폭발하지만, 지지함수 표현에서는 방향 하나당 스칼라 적분 하나로 끝난다. 하이브리드 시스템 도달가능성 도구(SpaceEx 계열)가 이 표현을 채택한 이유다. 다만 방향을 유한 개만 샘플링하면 결과는 항상 바깥 근사(외포)라는 점은 잊으면 안 된다.

6. 기하 — 폭, 평균폭, 혼합부피[편집]

볼록체 $K$ 의 단위벡터 $u$ 방향 폭(width)은

w_K(u) = h_K(u) + h_K(-u)

로 두 지지초평면 사이의 간격이다. 모든 방향으로 평균을 내면 평균폭이 되고, 이는 $K$ 의 내재부피(intrinsic volume) 중 하나에 비례하는 기하적 불변량이다. 폭이 모든 방향에서 같은 볼록체를 정폭도형(constant width)이라 부르며, 뢸로 삼각형이 원 말고도 그런 도형이 있다는 반례로 유명하다.

한 걸음 더 나가면 혼합부피가 나온다. 볼록체들의 민코프스키 합의 부피 $\mathrm{vol}(\lambda_1 K_1 + \cdots + \lambda_m K_m)$ 은 $\lambda$ 들에 대한 $n$ 차 동차 다항식이 되고, 그 계수 $V(K_{i_1},\dots,K_{i_n})$ 이 혼합부피다. $K + rB$ 의 경우가 슈타이너 공식이며, 여기서 표면적과 평균폭이 계수로 떨어진다. 혼합부피들 사이에는 알렉산드로프-펜셸 부등식

V(K_1,K_2,K_3,\dots,K_n)^2 \;\ge\; V(K_1,K_1,K_3,\dots,K_n)\,V(K_2,K_2,K_3,\dots,K_n)

이 성립하며, 등주부등식·브룬-민코프스키 부등식이 이것의 특수 사례로 떨어진다. 지지함수는 이 이론에서 계산 도구 노릇을 한다 — 혼합부피가 지지함수를 표면적 측도에 대해 적분한 형태로 표현되기 때문이다.³

7. 한계[편집]

지지함수 표현이 만능은 아니다.

볼록집합만 다룬다. 비볼록 집합을 넣으면 볼록 폐포로 조용히 바뀌어 나온다. 오목한 메시를 GJK에 그냥 넣으면 안 되는 이유가 이것이고, 볼록 분해가 필수 전처리인 것도 같은 사정이다.
교집합에 약하다. 앞서 본 대로 교집합은 지지함수 쪽에서 하한합성곱이 되어 닫힌 형태가 잘 안 나온다. 제약이 교차로 쌓이는 문제에서는 표현의 이점이 빠르게 사라진다.
유한 방향 샘플링은 근사다. $h_K$ 를 $m$ 개 방향에서만 평가해 다면체로 복원하면 결과는 $K$ 를 포함하는 외포이며, 차원이 커질수록 필요한 방향 수가 지수적으로 는다. “지지함수로 하면 정확하다”는 말은 오라클을 정확히 평가할 때만 참이다.
수치적 예민함. 최댓값을 주는 점이 여러 개인 방향(면·모서리에 수직인 방향)에서 지지 사상이 불연속으로 튄다. GJK 구현의 절반이 퇴화 처리인 이유이며, 부기울기가 집합값이라는 이론적 사실이 부동소수점에서 그대로 대가를 청구하는 사례다.

8. 관련 문서[편집]

그래서 지지함수는 “볼록집합의 푸리에 변환” 비슷한 위치에 있다. 원래 표현(정점 리스트)에서 어려운 연산(민코프스키 합)이 변환 쪽에서 쉬운 연산(덧셈)이 되고, 반대로 원래 쉬운 연산(교집합 판정)이 변환 쪽에서 어려워진다. 어느 쪽 표현을 쓸지는 결국 “지금 하려는 연산이 어느 쪽에서 싼가”의 문제다. ↩
그뢰첼-로바스-슈라이버가 정리한 “분리와 최적화의 등가성”이 이 이야기의 정점이다. 볼록집합 위에서 선형함수를 최적화하는 것과 그 집합에 대한 분리 오라클을 갖는 것이 (다항시간 환산 아래) 같은 난이도라는 결과인데, 부등식이 지수 개인 조합 다면체 위의 선형계획이 다항시간에 풀리는 사례들이 전부 여기서 나온다. 요컨대 집합을 다 적을 필요는 없고 지지함수만 부를 수 있으면 된다. ↩
혼합부피 계산 자체는 무섭도록 어렵다. 다면체의 혼합부피를 정확히 계산하는 문제는 #P-난해로 알려져 있고, 그럼에도 이 양이 대수기하(BKK 경계 — 다항식 연립계의 해 개수 상한)와 조합론(순열 상수)에 동시에 나타나 여러 분야가 같은 벽 앞에 모여 있다. 지지함수는 이 벽을 넘게 해 주지는 않지만, 적어도 벽이 어디 있는지는 정확히 그려 준다. ↩