비평활 최적화

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

1. 개요[편집]

비평활 최적화 Nonsmooth Optimization
대상	미분 불가능한 목적·제약함수
미분 대체물	부분미분 ∂f (볼록) · 클라크 일반화 기울기 (국소 립시츠)
최적성 조건	0 ∈ ∂f(x)
블랙박스 하한	O(1/√k) — 부분경사법이 이미 최적
탈출구	구조를 쓴다 — 근접 연산자, 모로 포락, 다발법

비평활 최적화는 목적함수나 제약함수가 정의역의 일부 또는 전부에서 미분 불가능한 최적화 문제, 그리고 미분 대신 부분미분(subdifferential)이나 일반화 기울기를 써서 그런 문제를 다루는 이론·알고리즘의 총칭이다. 여기서 “비평활”은 $C^1$ 이 아니라는 뜻일 뿐, 연속성마저 버린다는 뜻은 아니다. 대개는 볼록이거나 최소한 국소 립시츠인 함수를 전제한다.

입문 교재를 보면 비평활은 병리적 예외처럼 보이지만, 실제 최적화 문제에서는 사실상 기본값이다. 최댓값 함수 $\max_i f_i(x)$ , ℓ1 노름, 전변분, 집합의 지시함수, 정확 벌점함수, 접촉·마찰의 상보 조건, ReLU 신경망 — 이 바닥에서 쓰는 물건 중 매끄러운 게 오히려 소수다. 매끄러움이 깨지는 자리는 대개 문제의 본질이 사는 자리이기도 하다. ℓ1의 꺾인 점이 정확히 “성분이 0이 되는” 곳이고, 최댓값 함수의 꺾인 점이 정확히 “최악 시나리오가 바뀌는” 곳이다. 매끄럽게 뭉개 버리면 풀기는 편해지지만 그 정보를 잃는다.¹

2. 부분미분과 0 ∈ ∂f[편집]

볼록함수 $f$ 의 점 $x$ 에서의 부분미분은 그래프를 그 점에서 아래로 받치는 아핀함수의 기울기를 전부 모은 집합이다.

\partial f(x) = \bigl\{\, g \;:\; f(y) \ge f(x) + \langle g,\, y - x\rangle \quad \forall y \,\bigr\}

원소 하나하나를 부분경사(subgradient)라 부른다. $f$ 가 $x$ 에서 미분 가능하면 $\partial f(x) = \{\nabla f(x)\}$ 로 한 점이 되고, 꺾인 점에서는 집합이 부풀어 오른다. $f(t)=|t|$ 라면 $\partial f(0) = [-1,1]$ 이다. 정의역 내부에서 $\partial f(x)$ 는 항상 비어 있지 않고 볼록·콤팩트다.

여기서 최적성 조건이 한 줄로 떨어진다.

x^\star \in \arg\min f \iff 0 \in \partial f(x^\star)

정의를 그대로 읽으면 증명이 끝난다 — $0$ 이 부분경사면 $f(y) \ge f(x^\star)$ 가 모든 $y$ 에 대해 성립하니까. 매끄러운 경우의 $\nabla f = 0$ 과 달리 이건 볼록에서 필요충분이고, “기울기가 0인 점” 대신 “0을 품은 집합”을 찾는 문제로 바뀐다. 등식이 포함으로, 방정식이 포함 관계(inclusion)로 승격되는 것이 비평활 세계의 문법이다.

실전에서 자주 쓰는 계산 규칙 두 개.

합의 규칙 $\partial(f+g) = \partial f + \partial g$ . 공짜가 아니다. 두 함수의 상대 내부가 겹친다는 식의 정칙성 조건이 필요하고, 이게 깨지면 좌변이 우변보다 클 수 있다.
최댓값 규칙(단스킨 정리) $f = \max_i f_i$ 이고 $f_i$ 가 매끄러우면 $\partial f(x) = \mathrm{conv}\{\nabla f_i(x) : i \in I(x)\}$ , 여기서 $I(x)$ 는 최댓값을 달성하는 지표 집합이다. 최악 시나리오가 둘 이상 동률이면 그만큼 부분미분이 넓어진다 — 강건 최적화의 해가 왜 하필 여러 시나리오가 동시에 걸리는 점에 앉는지가 이 식에 다 들어 있다.

3. 클라크 일반화 기울기 — 볼록을 벗어나면[편집]

볼록이 아니면 위 정의가 통째로 무너진다(받치는 아핀함수가 없을 수 있다). 대안이 클라크 일반화 기울기다. $f$ 가 국소 립시츠면 라데마허 정리에 의해 거의 모든 점에서 미분 가능하므로, 미분 가능한 점들에서의 그래디언트 극한을 모아 볼록포를 취한다.

\partial_C f(x) = \mathrm{conv}\Bigl\{\, \lim_{k} \nabla f(x_k) \;:\; x_k \to x,\ f \text{ 가 } x_k \text{ 에서 미분가능} \,\Bigr\}

$f$ 가 볼록이면 이것이 볼록 부분미분과 일치하고, $C^1$ 이면 $\{\nabla f(x)\}$ 로 돌아온다. 좋은 확장이다. 문제는 정지성이 약해진다는 것. $0 \in \partial_C f(x)$ 를 클라크 정지점이라 부르는데, $f(t) = -|t|$ 를 보면 $\partial_C f(0) = [-1,1] \ni 0$ 이라 원점이 정지점으로 판정된다. 그런데 원점은 최소가 아니라 최대다. 비볼록·비평활에서 알고리즘이 보장하는 것은 대개 “클라크 정지점으로의 수렴”이고, 그게 최소점이라는 보장은 어디에도 없다. 약볼록 함수처럼 구조를 하나 더 가정하고 나서야 이야기가 진전된다.

4. 부분경사법 — 이건 하강법이 아니다[편집]

가장 단순한 알고리즘은 그래디언트 자리에 부분경사를 꽂는 것이다.

x^{k+1} = x^k - \eta_k\, g^k, \qquad g^k \in \partial f(x^k)

이름은 하강법 비슷한데, 하강법이 아니다. $f(x,y) = |x| + 2|y|$ 를 점 $(1,0)$ 에서 보자. 여기서 $\partial f = \{1\} \times [-2,2]$ 이므로 $g = (1,2)$ 는 정당한 부분경사다. 스텝을 밟으면 $(1-\eta,\,-2\eta)$ 로 가고 값은

f = |1-\eta| + 4\eta = 1 + 3\eta > 1

즉 아무리 작은 스텝을 밟아도 함수값이 오른다. 매끄러운 세계의 직관 — “그래디언트 반대로 조금만 가면 무조건 내려간다” — 이 여기서 깨진다. 그래서 부분경사법에는 라인서치가 없다. 스텝을 줄여도 개선이 안 되니 검색할 게 없기 때문이다. 대신 스텝 수열을 미리 정해서 밀어붙이고, 지금까지 본 최솟값 $f_{\text{best}}^k = \min_{j\le k} f(x^j)$ 를 따로 들고 다닌다.²

그럼 뭐가 줄어드는가. 함수값이 아니라 최적해까지의 거리다. $\|x^{k+1}-x^\star\|^2 \le \|x^k-x^\star\|^2 - 2\eta_k(f(x^k)-f^\star) + \eta_k^2\|g^k\|^2$ 라는 부등식이 성립하고, 여기서 수렴 해석이 전부 나온다. $\|g\| \le L$ , $\|x^0 - x^\star\| \le R$ 이고 $T$ 스텝을 쓸 때 $\eta = R/(L\sqrt{T})$ 로 두면

\min_{k \le T} f(x^k) - f^\star \;\le\; \frac{LR}{\sqrt{T}}

$O(1/\sqrt{k})$ 다. $\epsilon$ 정확도에 $O(1/\epsilon^2)$ 반복 — 경사하강법의 $O(1/\epsilon)$ , 가속의 $O(1/\sqrt{\epsilon})$ 과 비교하면 처참하다. 더 나쁜 소식은 이게 개선 불가능하다는 것이다. 네미로프스키-유딘의 정보이론적 하한에 따르면, 차원이 반복 수보다 크고 오라클이 “점 하나 주면 값과 부분경사 하나”만 돌려주는 블랙박스 모형에서는 어떤 1차 알고리즘도 $\Omega(LR/\sqrt{T})$ 를 못 넘는다. 부분경사법은 이미 최적이고, 그래서 느리다.

참고로 이론적으로는 하강 방향이 존재하긴 한다. $\partial f(x)$ 의 최소 노름 원소 $g_{\min}$ 을 잡으면 $-g_{\min}$ 이 최급강하 방향이다. 다만 그걸 구하려면 부분미분 집합 전체를 알아야 하는데, 블랙박스 오라클은 원소 하나만 준다. 이 간극을 표본으로 메우려는 것이 그래디언트 샘플링(gradient sampling) 계열이다 — 현재 점 근방에서 그래디언트를 여러 개 뽑아 볼록포를 만들고 그 안의 최소 노름 원소로 내려간다.

5. 탈출구는 구조다 — 근접 연산자와 모로 포락[편집]

하한이 $O(1/\sqrt{k})$ 라는 말은 정확히 “블랙박스 모형에서는”이라는 단서를 달고 있다. 실제 문제는 블랙박스가 아니다. 대개 이런 꼴이다.

\min_x \; f(x) + g(x), \qquad f \text{ 는 매끄러움},\ g \text{ 는 비평활이지만 정체를 안다}

$g$ 의 정체를 안다는 건 근접 연산자를 닫힌 형태로 계산할 수 있다는 뜻이다. $\mathrm{prox}_{\lambda g}(v) = \arg\min_x \{g(x) + \frac{1}{2\lambda}\|x-v\|^2\}$ . $g = \lambda\|\cdot\|_1$ 이면 연성 임계화 한 줄, 지시함수면 사영 한 번. 이 추가 정보를 쓰면 근접 경사법(ISTA)이 $O(1/k)$ , 네스테로프 가속을 얹은 FISTA가 $O(1/k^2)$ 를 낸다. 비평활한데도 매끄러운 문제의 수렴률을 회복한다. 하한을 깬 게 아니라 하한이 가정한 오라클보다 더 많이 알고 있는 것이다.

같은 이야기를 다른 각도에서 하는 것이 **모로 포락**이다.

M_{\lambda f}(x) = \min_u \Bigl\{ f(u) + \tfrac{1}{2\lambda}\|u-x\|^2 \Bigr\}

이 함수는 $C^1$ 이고 그래디언트가 $1/\lambda$ -립시츠인데, 최솟값과 최소점이 원래 $f$ 와 완전히 같다. 절댓값의 모로 포락이 후버 함수라는 것이 대표 예다. 여기서 자주 하는 오해 하나 — 비평활을 매끄럽게 만드는 도구는 무어-펜로즈 유사역행렬 같은 선형대수 물건이 아니라 이 포락, 즉 이차항과의 **하한 합성곱**이다. 포락의 그래디언트가 원함수 부분미분의 최소 노름 원소를 자동으로 뽑아 준다는 점까지 포함해서, 비평활 최적화의 “매끄럽게 보기” 관점은 대부분 여기서 나온다.

포락의 사촌으로 네스테로프 평활화(2005)가 있다. $f(x) = \max_{u\in Q}\{\langle Ax,u\rangle - \varphi(u)\}$ 꼴의 최대최소 함수에 근접함수를 $\mu$ 만큼 섞어 매끄럽게 만든 뒤 가속법을 돌리면, $\mu \sim \epsilon$ 선택에서 총 복잡도가 $O(1/\epsilon)$ 이 된다. 부분경사법의 $O(1/\epsilon^2)$ 대비 제곱근만큼의 이득이며, 대가는 ” $f$ 가 저 최대최소 꼴로 명시적으로 쓰여 있어야 한다”는 구조 요구다.

6. 다발법과 절단평면 — 구조를 모를 때[편집]

prox도 못 쓰고 평활화 표현도 없는데 부분경사법의 $O(1/\sqrt{k})$ 는 못 견디겠다면, 남는 카드는 모형을 쌓는 것이다. 지금까지 본 부분경사들로 아래를 받치는 조각선형 모형을 만든다.

\check{f}_k(x) = \max_{j \le k}\Bigl\{ f(x^j) + \langle g^j,\, x - x^j\rangle \Bigr\} \;\le\; f(x)

이 모형을 최소화하는 것이 켈리(1960)의 절단평면법이다. 볼록성 덕에 모형이 항상 하계이므로 하한이 공짜로 따라오지만, 그냥 최소화하면 반복점이 정의역 구석에서 구석으로 튀는 심한 지그재그가 난다 — 모형이 아직 정보가 없는 영역을 터무니없이 낙관적으로 보기 때문이다.

다발법(bundle method)은 여기에 안정화 항을 붙여 그 병을 고친다.

x^{k+1} = \arg\min_x \Bigl\{ \check{f}_k(x) + \tfrac{1}{2\mu_k}\|x - \hat{x}^k\|^2 \Bigr\}

$\hat x^k$ 는 안정점(stability center), 즉 지금까지 가장 좋았던 점이다. 새 점에서 값이 충분히 내려가면 안정점을 옮기고(serious step), 아니면 안정점은 그대로 두고 절단면만 하나 더 쌓는다(null step). 이름의 “다발”은 쌓아 둔 절단면 묶음을 가리키며, 개수가 무한정 늘지 않도록 오래된 면들을 하나의 집계 절단면으로 압축한다. 위 부분문제가 정확히 모형의 근접점 스텝이라는 점에서, 다발법은 “정확한 $f$ 의 prox를 못 구하니 모형의 prox를 대신 구한다”로 읽을 수 있다.

다발법이 실제로 밥값을 하는 대표 무대는 **쌍대성**이다. 라그랑주 쌍대함수 $g(\lambda) = \inf_x L(x,\lambda)$ 는 아핀함수들의 하한이라 항상 오목이고 거의 항상 비평활이며, 부분경사는 부분문제의 해에서 제약 위반량으로 공짜로 떨어진다. 정수계획의 라그랑주 완화, 확률계획의 벤더스 분해에서 상위 문제를 푸는 표준 도구가 다발법인 이유다.

7. 비평활은 어디서 오는가[편집]

발생원	형태	이 위키의 문서
최대최소·강건 설계	시나리오 최댓값	강건 설계
정확 벌점함수	제약 위반의 ℓ1 벌점	벌점법
희소 정규화	ℓ1, 핵 노름	라쏘 · 압축센싱
영상 복원	전변분	전변분 잡음제거
제약을 지시함수로	볼록집합 지시함수	볼록 최적화
접촉·마찰·소성	상보 조건, 항복면	접촉 해석 · 소성
신경망	ReLU, max pooling	심층 학습

벌점법 쪽 사정을 한 줄로 옮기면 이렇다 — 이차 벌점은 매끄럽지만 $\mu \to \infty$ 에서만 정확하고, ℓ1 정확 벌점은 유한한 $\mu$ 에서 정확해에 도달하는 대신 제약면에서 미분 불가능해진다. 정확성과 평활성을 동시에 가질 수 없다는 이 교환이 비평활 최적화가 공학 문제에 등장하는 가장 흔한 경로이며, 증강 라그랑주법이 승수를 도입해 그 교환을 피해 가는 것이 다음 장의 내용이다.

역학 쪽 접점도 우연이 아니다. 근접 연산자와 포락을 만든 장자크 모로 본인이 비평활 역학(nonsmooth mechanics)의 창시자이며, 시뇨리니 접촉 조건 $0 \le g \perp p \ge 0$ 이나 쿨롱 마찰의 원뿔 조건은 미분포함(differential inclusion)으로 쓰였을 때 가장 자연스럽다. 제약 해결기가 푸는 선형 상보성 문제가 결국 비평활 방정식이라는 점에서, 물리 엔진과 볼록해석은 생각보다 가까운 친척이다.

8. 실무 메모[편집]

유한차분으로 기울기를 검증하지 마라. 꺾인 점 근처에서 중심차분은 좌우 기울기의 평균 비슷한 값을 내놓는데, 그건 어느 부분경사와도 일치하지 않을 수 있다. “그래디언트 체크가 안 맞는다”의 절반은 버그가 아니라 kink다.
자동미분은 부분경사를 준다고 약속하지 않는다. ReLU의 0에서 프레임워크가 어떤 값을 돌려주는지는 그냥 구현 규약이고, 비평활 함수의 합성에서는 AD 결과가 클라크 부분미분 밖으로 나가는 예제도 만들 수 있다. 거의 모든 점에서는 옳다는 것이 현재의 정리 수준이다.³
정지 조건을 $\|\nabla f\| < \epsilon$ 으로 쓸 수 없다. 근접법을 쓴다면 근접 잔차 $\|x^{k+1}-x^k\|/\eta$ , 다발법이라면 모형과의 예측 감소량, 일반적으로는 $\epsilon$ -부분미분 기반 판정을 쓴다.
$f^\star$ 를 알거나 잘 추정할 수 있으면 폴랴크 스텝 $\eta_k = (f(x^k)-f^\star)/\|g^k\|^2$ 가 스텝 튜닝을 통째로 없애 준다. 쌍대 문제에서는 원 문제 값이 좋은 추정치로 쓰인다.
준-뉴턴법을 비평활 문제에 그냥 얹는 것은 이론상 정당화되지 않지만, 비정확 라인서치 BFGS가 실전에서 놀랍도록 잘 도는 것도 사실이다. 수렴 정리가 없다는 점만 알고 쓰면 된다.⁴

9. 관련 문서[편집]

그래서 “비평활해서 안 풀리니까 $\sqrt{t^2+\varepsilon^2}$ 로 뭉갰습니다”는 논문의 그 한 줄은 항상 다음 질문을 부른다. $\varepsilon$ 을 얼마로 뒀고, 그 선택이 답을 얼마나 바꿨는가. 모로 포락이 특별대우를 받는 이유가 정확히 이 질문에 “안 바꿨다”고 답할 수 있어서다. ↩
부분경사법을 처음 구현하면 목적함수 곡선이 톱니처럼 출렁이는 걸 보고 “발산했다”고 판단해 롤백하는 통과의례가 있다. 정상이다. 로그를 찍어야 할 건 $f(x^k)$ 가 아니라 $f_{\text{best}}^k$ 이며, 이건 정의상 단조 감소한다. ↩
볼테-포웰스의 보존장(conservative field) 이론이 이 상황을 정리한 결과다. AD가 뱉는 물건은 “거의 모든 점에서 그래디언트와 일치하는 집합값 사상”이고, 확률적 경사법의 수렴 해석은 클라크 부분미분이 아니라 이 보존장 위에서 이뤄진다. 즉 딥러닝 프레임워크가 계산하는 것은 정확히는 부분경사가 아니지만, 학습이 잘 되는 데는 지장이 없는 정도로만 다르다. ↩
루이스와 오버턴이 이 현상을 정면으로 조사한 적이 있는데, 결론이 “잘 되는데 왜 되는지는 모르겠다”에 가까웠다. 다만 종료 근처에서 헤세 근사의 조건수가 폭발하는 것이 관측되므로, 정지 조건을 그래디언트 노름으로 잡아 두면 영원히 안 멈추는 코드를 얻게 된다. ↩