변분부등식

수치해석 최적설계 고체역학 마지막 수정: 2026-08-14 04:14:26

1. 개요[편집]

변분부등식 Variational Inequality
약칭	VI(K, F)
정의	x* ∈ K, ⟨F(x), y − x⟩ ≥ 0 (∀y ∈ K)
동치 형태	0 ∈ F(x) + N_K(x) — 일반화 방정식
특수 사례	F = ∇f 이면 제약 최적화의 1차 조건, K = ℝⁿ₊ 이면 상보성 문제
표준 해법	사영법, 외부 경사법, 반평활 뉴턴법
고전	Fichera (1964), Lions–Stampacchia (1967)

등식은 “여기서 멈춰라”라고 말하지만, 부등식은 “이쪽으로는 더 갈 수 없다”라고만 말한다. 최적화가 아닌 문제에도 그 말이 필요할 때가 있다.

변분부등식(variational inequality)은 볼록집합 $K \subseteq \mathbb{R}^n$ 과 사상 $F : K \to \mathbb{R}^n$ 이 주어졌을 때, 다음을 만족하는 $x^\star \in K$ 를 찾는 문제다.

\langle F(x^\star),\, y - x^\star \rangle \ \ge\ 0 \qquad \forall\, y \in K

이것을 VI $(K,F)$ 라 쓴다. 기하학적으로는 ” $K$ 안의 어느 방향으로 움직여도 $F(x^\star)$ 와 예각을 이룬다”, 즉 $-F(x^\star)$ 가 $x^\star$ 에서 $K$ 밖을 향한다는 뜻이다. 볼록집합의 법선원뿔 $N_K$ 로 옮겨 쓰면 한 줄로 줄어든다.

0 \in F(x^\star) + N_K(x^\star), \qquad N_K(x) = \{\, v : \langle v, y-x\rangle \le 0 \ \ \forall y \in K \,\}

$K = \mathbb{R}^n$ 이면 $N_K = \{0\}$ 이라 그냥 $F(x^\star)=0$ 이다. 즉 VI 는 “방정식을 볼록집합 위로 옮겨 놓은 것” 이고, 제약이 없으면 원래의 비선형 방정식으로 되돌아온다.

왜 굳이 이런 틀이 필요한가. 제약이 붙은 문제를 다루는 익숙한 방법은 카루시-쿤-터커 조건을 세워 등식·부등식 연립계로 바꾸는 것이다. 그런데 애초에 최소화할 목적함수가 없는 문제들이 있다 — 여러 참가자가 각자 다른 목적을 최소화하는 균형, 마찰 접촉, 도로망의 통행 배분. 이때 KKT 로 가는 길은 막히지만 VI 는 그대로 성립한다. 이 문서는 그 “부등식 제약을 목적함수 없이 다루는 틀”로서의 VI 에 초점을 둔다. 아핀 특수 사례의 실무는 선형 상보성 문제에, 관련 연산자 이론은 단조 작용소에 있다.

2. 최적화의 1차 조건이 특수 사례인 이유[편집]

$F = \nabla f$ 이고 $f$ 가 미분 가능하면 VI $(K,\nabla f)$ 는 정확히 $\min_{x\in K} f(x)$ 의 1차 최적성 조건이다.

\langle \nabla f(x^\star), y - x^\star\rangle \ge 0 \quad \forall y \in K

“실행가능 방향 어느 쪽으로도 함수가 안 줄어든다”는 그 조건 그대로다. $f$ 가 볼록이면 이건 전역 최적성과 동치이고, 아니면 정류성만 준다.

그렇다면 반대 방향은 어떤가. 주어진 $F$ 가 어떤 $f$ 의 그래디언트로 쓰이려면 야코비안 $\nabla F(x)$ 가 대칭이어야 한다(푸앵카레 보조정리). 이 대칭성이 깨지는 순간 퍼텐셜 $f$ 는 존재하지 않고, VI 는 어떤 최적화 문제로도 환원되지 않는다. 이것이 VI 를 독립된 대상으로 만드는 결정적 지점이다.

\nabla F \text{ 대칭} \iff \exists f,\ F = \nabla f \iff \text{VI 가 최적화 문제}

교과서적 예가 두 사람이 각자 자기 비용을 최소화하는 게임이다. 참가자 $i$ 가 $\min_{x_i \in K_i} \theta_i(x_i, x_{-i})$ 를 푼다면 균형점은 $F(x) = (\nabla_{x_1}\theta_1, \dots, \nabla_{x_N}\theta_N)$ 인 VI 의 해이고, 이 $F$ 의 야코비안은 일반적으로 비대칭이다. 내시 균형이 최적화가 아니라 균형인 이유가 여기에 있다. 안장점 문제 $\min_x\max_y L(x,y)$ 도 $F = (\nabla_x L, -\nabla_y L)$ 로 놓으면 VI 이며, $L$ 이 볼록-오목이면 $F$ 는 단조지만 대칭은 결코 아니다.¹

3. 상보성 문제와의 관계[편집]

$K = \mathbb{R}^n_+$ 인 경우를 직접 써 보면 VI 가 무엇인지 손에 잡힌다. $\langle F(x^\star), y - x^\star\rangle \ge 0$ 을 모든 $y \ge 0$ 에 대해 요구하면 다음과 동치가 된다.

x^\star \ge 0, \qquad F(x^\star) \ge 0, \qquad \langle x^\star, F(x^\star)\rangle = 0

이것이 비선형 상보성 문제(NCP)다. 성분별로는 $x_i^\star \ge 0$ , $F_i(x^\star)\ge 0$ , 그리고 둘 중 최소 하나는 0. 여기서 $F(x)=Mx+q$ 로 아핀화하면 선형 상보성 문제가 되고, $K$ 가 일반 다면체이고 $F$ 가 아핀이면 아핀 변분부등식(AVI)이라 부르며 역시 LCP 로 환원된다.

포함 관계를 정리하면 이렇다.

설정	문제 이름	대표 무대
$K = \mathbb{R}^n$	비선형 방정식 $F(x)=0$	뉴턴-랩슨법
$K = \mathbb{R}^n_+$	NCP	균형·상보성
$K$ 다면체, $F$ 아핀	AVI / LCP	접촉, 이차계획법
$K$ 볼록, $F=\nabla f$	제약 최적화	볼록 최적화
$K$ 볼록, $F$ 비대칭	진짜 VI	균형 문제
$K$ 가 $x$ 에 의존	준변분부등식 (QVI)	쿨롱 마찰

마지막 줄이 특히 고약하다. 쿨롱 마찰에서 접선력의 허용 범위 $\|\lambda_t\| \le \mu\lambda_n$ 이 미지수인 법선력에 의존하므로 실행가능 집합 자체가 해에 따라 움직인다. 이렇게 $K = K(x)$ 인 문제를 QVI 라 하고, 존재성 이론부터 알고리즘까지 전부 한 단계 어려워진다.

4. 어디서 튀어나오는가[편집]

단측 접촉(시뇨리니 문제). 탄성체가 강체 바닥에 놓였을 때 “파고들지 않는다 + 당기지 않는다 + 둘 중 하나는 0”이 그대로 VI 다. 피케라(1964)가 존재성을 증명하고 리옹스와 스탐파키아(1967)가 일반 이론으로 정리한 것이 이 분야의 출발점이다. 변위장을 미지수로 두면 $K$ 는 “관통하지 않는 변위들”의 볼록 원뿔이고, 마찰이 없으면 에너지 범함수의 최소화(제1종 VI), 마찰이 붙으면 비미분 항이 생겨(제2종 VI) 또는 QVI 로 넘어간다. 실무는 접촉 해석 참고.
장애물 문제와 자유경계 문제. 막을 장애물 위에 씌우면 “닿은 영역”과 “떠 있는 영역”의 경계가 미지수다. 이산화하면 LCP, 연속 상태로는 VI. 미국식 옵션의 조기행사 경계, 다공질 매질의 침투면, 저널 베어링의 캐비테이션이 전부 같은 골격이다.
교통망 균형. 워드롭(1952)의 사용자 균형 — “실제로 쓰이는 모든 경로의 통행시간이 같고, 안 쓰이는 경로는 그보다 나쁘다” — 은 정확히 상보성 조건이다. 링크 통행시간이 자기 링크의 유량에만 의존하면 베크만(1956)의 등가 볼록계획으로 풀리지만, 교차로 상호작용이나 양방향 간섭이 있으면 야코비안이 비대칭이 되어 퍼텐셜이 사라진다. 스미스(1979)와 다페르모스(1980)가 VI 정식화를 도입한 것이 바로 이 비대칭 사례 때문이다.
공간가격 균형·전력시장. 생산자·소비자·수송비가 얽힌 균형은 목적함수가 없는 대표적 문제이며 NCP/VI 로 모형화된다. GAMS 의 MCP(mixed complementarity problem) 인터페이스와 PATH 솔버가 이 시장을 위해 존재한다.

5. 사영법 — 그리고 그것이 실패하는 지점[편집]

VI 의 알고리즘은 다음 고정점 특성에서 출발한다. 임의의 $\alpha>0$ 에 대해

x^\star \text{ 가 VI}(K,F)\text{ 의 해} \iff x^\star = \Pi_K\bigl(x^\star - \alpha F(x^\star)\bigr)

여기서 $\Pi_K$ 는 $K$ 위로의 유클리드 사영이다. 증명은 사영의 특성부등식 $\langle z - \Pi_K z,\, y - \Pi_K z\rangle \le 0$ 을 그대로 대입하면 끝난다. 이 고정점 식을 그냥 반복하면 사영법(projection method)이 된다.

x^{k+1} = \Pi_K\bigl(x^k - \alpha F(x^k)\bigr)

$F = \nabla f$ 이면 이건 투영 경사법 그 자체다. 수렴 조건은 정직하게 빡빡하다. $F$ 가 $\mu$ -강단조( $\langle F(x)-F(y), x-y\rangle \ge \mu\|x-y\|^2$ )이고 $L$ -립시츠면 반복 사상이 축소사상이 되어

0 < \alpha < \frac{2\mu}{L^2} \ \Longrightarrow\ \text{수축률} \sqrt{1 - 2\alpha\mu + \alpha^2 L^2} < 1

로 선형 수렴한다. 문제는 단조하기만 하고 강단조가 아니면 이게 통째로 무너진다는 것이다. $K=\mathbb{R}^2$ , $F(x) = (x_2, -x_1)$ 을 보자. $F$ 는 반대칭이라 $\langle F(x)-F(y),x-y\rangle = 0$ 으로 단조이고 해는 $x^\star=0$ 하나뿐인데,

\|x^{k+1}\|^2 = \|x^k - \alpha F(x^k)\|^2 = (1+\alpha^2)\|x^k\|^2

즉 어떤 스텝을 써도 나선을 그리며 발산한다. 목적함수가 있는 세계에서 자란 직관이 균형 문제에서 왜 안 먹히는지를 두 줄로 보여 주는 예다.²

6. 외부 경사법[편집]

코르펠레비치(1976)의 외부 경사법(extragradient method)이 이 병을 정확히 고친다. 사영을 한 번이 아니라 두 번 한다.

y^k = \Pi_K\bigl(x^k - \alpha F(x^k)\bigr), \qquad x^{k+1} = \Pi_K\bigl(x^k - \alpha F(y^k)\bigr)

핵심은 두 번째 줄에서 출발점은 $x^k$ 인데 방향은 미리 내다본 점 $y^k$ 에서 평가한다는 것이다. 앞의 회전 예제에 넣어 보면 한 스텝의 노름 배율이 $1-\alpha^2+\alpha^4$ 꼴로 바뀌어, $\alpha$ 가 충분히 작으면 실제로 줄어든다. 일반 정리는 이렇다 — $F$ 가 단조이고 $L$ -립시츠이며 해가 존재하면, $\alpha < 1/L$ 에서 전역 수렴한다. 강단조성이 필요 없다.

계보를 정리하면:

초앞점법(Popov, 1980) / 낙관적 경사법 — $F$ 평가를 반복당 한 번으로 줄인 변형. 최근 미니맥스 최적화에서 재발견되어 생성적 적대 신경망 훈련 안정화의 표준 트릭이 됐다.
전진-후진-전진(Tseng, 2000) — 사영이 비싼 경우를 겨냥한 변형.
초완화 사영법(Solodov–Svaiter) — 초평면 분리로 사영 횟수를 줄인다.
간극 함수(gap function) 최소화 — $g(x) = \max_{y\in K}\langle F(x), x-y\rangle$ 는 $K$ 위에서 항상 비음수이고 0 이 되는 점이 정확히 VI 의 해다. 그대로는 비평활이라, 후쿠시마(1992)가 이차항을 넣은 정칙화 간극 함수 $g_\alpha(x) = \max_{y\in K}\{\langle F(x),x-y\rangle - \frac{1}{2\alpha}\|y-x\|^2\}$ 로 미분 가능하게 만들어 무제약 최소화로 넘겼다. 알고리즘의 종료 판정 지표로도 이게 표준이다.

수렴 속도가 정말 중요한 대규모 문제에서는 VI 를 NCP 로 바꾼 뒤 반평활 뉴턴법을 돌리는 것이 정석이다. 사영법 계열이 1차법의 안정성을 주는 대신 선형 수렴에 머무는 반면, 반평활 뉴턴은 국소 초선형·이차 수렴을 준다. 실무 코드(PATH, SEMISMOOTH, Siconos)가 전부 그 조합이다.

7. 존재성과 유일성[편집]

존재성. $K$ 가 유계인 볼록 컴팩트 집합이고 $F$ 가 연속이면 해가 존재한다(하르트만-스탐파키아). 증명은 사영 고정점 식 $x = \Pi_K(x-\alpha F(x))$ 에 브라우어 고정점 정리를 먹이는 것이 전부라, 최적화의 바이어슈트라스 정리와 정확히 같은 역할을 한다. $K$ 가 무계면 강제성(coercivity) 조건이 추가로 필요하다.
유일성. $F$ 가 엄격단조면 해가 많아야 하나, 강단조면 정확히 하나다.
민티 보조정리. $F$ 가 연속이고 단조면 원래의 VI 는 $\langle F(y), y - x^\star\rangle \ge 0\ \forall y\in K$ (민티 VI)와 동치다. 미지점에서의 $F$ 평가가 사라지므로 약수렴 논증과 무한차원 확장에서 결정적으로 쓰인다.

정리하면 VI 의 이론적 난이도를 결정하는 축은 볼록성이 아니라 단조성이다. 볼록 최적화에서 “볼록이면 다 된다”는 자리에, VI 에서는 “단조면 된다”가 들어간다. 그리고 단조성은 볼록성보다 넓다 — 어떤 볼록함수의 그래디언트도 단조지만, 단조 사상 중 그래디언트로 쓰이는 것은 대칭인 것들뿐이다.

8. 여담[편집]

VI 를 배우면 그동안 따로따로 외웠던 것들이 한 줄로 접힌다. KKT 조건, 시뇨리니 조건, 워드롭 원리, 상보성, 사영 경사법이 전부 같은 부등식의 다른 옷이다. 논문에서 “we formulate the problem as a VI”라는 문장이 나오면, 대개 최적화로 못 쓴다는 고백을 우아하게 한 것이다.
물리 엔진 프로그래머와 교통공학자와 마찰 접촉 연구자가 같은 학회에서 만나는 일은 거의 없지만, 셋 다 하는 일은 똑같이 “부등식 제약 딸린 비대칭 균형을 사영 반복으로 대충 푸는 것”이다.
비평활 함수의 최소화까지 담으려면 $F$ 를 집합값으로 확장한 포함 관계 $0 \in F(x) + \partial \iota_K(x)$ 로 가야 하고, 그러면 단조 작용소와 근접점 알고리즘의 세계로 그대로 이어진다. 마르티네가 1970년에 근접점법을 처음 제안한 논문 제목이 하필 “변분부등식의 정칙화”인 것도 우연이 아니다.³

9. 관련 문서[편집]

그래서 GAN 훈련이 그렇게 안 되는 것도 이 틀에서 설명된다. 판별자와 생성자의 결합 사상은 단조이긴 해도 대칭이 아니라 “내려갈 목적함수”가 없고, 그래서 손실 곡선을 아무리 노려봐도 학습이 잘 되는지 알 수 없다. 최적화 직관을 그대로 들고 오면 반드시 배신당한다. ↩
이 반례는 두 줄짜리라 강의 첫 시간에 나오는데도, 실무에서 같은 실수가 반복된다. “경사하강이 안 되네요”의 절반은 스텝 크기 문제지만 나머지 절반은 애초에 그래디언트가 아니었던 경우다. $\nabla F$ 의 대칭성을 확인하는 데는 유한차분 두 번이면 충분하다. ↩
Martinet, B. (1970). Régularisation d’inéquations variationnelles par approximations successives. 오늘날 딥러닝 논문에서 태연히 쓰이는 prox 연산자가, 원래는 마찰 접촉과 장애물 문제를 풀려고 만든 도구였다는 얘기다. 응용수학의 도구는 원산지를 잊고 팔려 다닌다. ↩