벌점법

최적설계 수치해석 구조해석 마지막 수정: 2026-08-13 04:51:19

1. 개요[편집]

벌점법 Penalty Method
다른 이름	외부 벌점법(exterior penalty), 벌칙함수법
기본형	f(x) + (μ/2)‖c(x)‖²
수렴	μ → ∞ 에서만 정확해
대가	헤세 행렬 조건수가 μ 에 비례해 폭발
정확 벌점	ℓ₁ 벌점 — 유한 μ 에서 정확, 대신 비평활
후계자	증강 라그랑주법, 내점법

제약을 지키라고 설득하는 대신, 안 지키면 벌금을 물린다. 문제는 벌금을 얼마로 매기느냐다.

벌점법(penalty method)은 제약 최적화 문제를 제약 위반량에 벌점 계수를 곱해 목적함수에 더한 무제약 문제의 열(sequence)로 바꿔 푸는 방법이다. 등식 제약 문제 $\min f(x)$ s.t. $c(x) = 0$ 에 대해 가장 표준적인 형태는 이차 벌점 함수다.

Q(x;\mu) = f(x) + \frac{\mu}{2}\lVert c(x)\rVert_2^2

부등식 제약 $g_i(x) \le 0$ 이면 위반한 만큼만 세는 $\frac{\mu}{2}\sum_i \max(0, g_i(x))^2$ 를 쓴다. 그러고는 $\mu_1 < \mu_2 < \cdots \to \infty$ 로 키우며 각 $\mu_k$ 에서 무제약 최소화를 풀고, 앞의 해를 다음 문제의 초기값으로 넘긴다.

발상이 워낙 단순해서 제약 최적화를 처음 배울 때 거의 반드시 만나게 되고, 실제로 유전 알고리즘처럼 제약을 다룰 문법이 없는 알고리즘에 제약을 밀어 넣는 유일한 실용적 방법이기도 하다. 그런데 정직한 평가는 이렇다 — 순수한 이차 벌점법은 범용 비선형 계획 솔버로는 쓰이지 않는다. 이 문서는 그 이유(조건수)와, 그 결함을 각각 다른 방향에서 고친 두 갈래 — 정확 벌점과 승수 갱신 — 을 정리한다. 승수 갱신 쪽 이야기의 본편은 증강 라그랑주법, 안쪽에서 접근하는 배리어 계열은 내점법에 있다.

2. 무엇이 보장되고 무엇이 안 되는가[편집]

먼저 좋은 소식. $\mu_k \to \infty$ 이고 각 $x^k$ 가 $Q(\cdot;\mu_k)$ 의 전역 최소점이면, $\{x^k\}$ 의 임의의 집적점은 원 문제의 전역 최소점이다. 증명 아이디어도 소박하다 — $Q(x^k;\mu_k) \le Q(x^*;\mu_k) = f(x^*)$ 이므로 벌점항이 $f(x^*) - f(x^k)$ 이하로 눌려 있고, $\mu_k$ 가 커지면 $\lVert c(x^k)\rVert \to 0$ 일 수밖에 없다. 제약 없이 시작할 수 있고 실행가능해를 몰라도 된다는 점, 그리고 목적함수와 제약을 블랙박스로만 접근해도 된다는 점이 이 방법의 실질적 장점이다.

이제 나쁜 소식. $x_\mu$ 가 $Q(\cdot;\mu)$ 의 정류점이면 $\nabla f(x_\mu) + \mu J(x_\mu)^\top c(x_\mu) = 0$ 이고, 이를 카루시-쿤-터커 조건의 $\nabla f + J^\top \lambda^* = 0$ 과 나란히 놓으면

\mu\, c(x_\mu) \;\approx\; \lambda^{*} \qquad\Longrightarrow\qquad \lVert c(x_\mu)\rVert = O(1/\mu)

이 나온다. 제약 위반이 $1/\mu$ 로만 줄어든다. 위반을 $10^{-8}$ 까지 몰아내려면 $\mu \sim 10^{8}$ 을 써야 한다는 뜻이고, 이것이 “ $\mu\to\infty$ 가 이론적 장식이 아니라 실제 요구사항”이라는 말의 의미다. 부산물로 얻는 것 하나는 승수 추정치다 — $\mu c(x_\mu)$ 가 라그랑주 승수의 근사값이라는 사실은 뒤에 나올 모든 개선의 출발점이 된다.

3. 조건수라는 청구서[편집]

$\mu$ 를 키우는 데 드는 비용은 헤세 행렬에 그대로 찍힌다.

\nabla^2_{xx} Q = \underbrace{\nabla^2 f + \mu\sum_i c_i \nabla^2 c_i}_{O(1)\text{ 수준}} \;+\; \mu\, J^\top J

$J^\top J$ 는 제약의 법선 방향(= $J^\top$ 의 상공간)에서만 $O(\mu)$ 크기의 고유값을 만들고, 제약에 접하는 방향의 곡률은 $O(1)$ 로 남는다. 그래서 조건수가 $\mu$ 에 정비례해 커진다. $\mu = 10^{8}$ 이면 배정도 유효자릿수 16자리 중 8자리를 조건수에만 헌납하는 셈이라, 내부 뉴턴 반복이 해보다 먼저 무너진다.

특히 아픈 것은 두 가지다. 첫째, 계곡이 극단적으로 좁고 길어져 경사하강·준-뉴턴법 계열이 사실상 못 움직인다. 둘째, 함수값 자체가 $f(x) + \frac{\mu}{2}\lVert c\rVert^2$ 에서 큰 두 항의 차로 계산되는 국면이 오면 유효 자릿수가 상쇄로 날아간다. 잔차가 어느 순간부터 안 줄고 진동하는데 제약은 잘 만족되고 있다면 십중팔구 이 병이다.

이 병이 내점법의 조건수 폭발과 다르다는 점은 짚어 둘 만하다. 내점법에서도 KKT 행렬 조건수가 $10^{16}$ 을 넘기지만 그 병적 조건화는 구조적이어서 계산된 방향의 오차가 얌전한 반면, 벌점법의 이상조건화는 그런 보호막 없이 그대로 뉴턴 방향을 오염시킨다.¹ 그래서 실무 조언은 늘 같다 — $\mu$ 를 처음부터 크게 주지 말고, 낮은 $\mu$ 의 해를 워밍 스타트로 넘기며 단계적으로 키워라. 이 점열을 $\mu$ 에 대한 호모토피 경로로 읽으면, $x(\mu)$ 가 매끄러운 곡선을 그리므로 외삽으로 초기값을 잡는 것도 가능하다.

4. 정확 벌점 — 유한한 μ 로 끝내기[편집]

$\mu\to\infty$ 가 문제라면, 유한한 $\mu$ 에서 정확히 원 문제의 해가 나오는 벌점 함수를 쓰면 된다. 제곱 대신 절댓값을 쓰는 것이 답이다.

\phi_1(x;\mu) = f(x) + \mu\sum_i |c_i(x)| + \mu\sum_j \max\big(0,\, g_j(x)\big)

이것이 ℓ₁ 정확 벌점 함수다. 핵심 정리는 다음과 같다. $x^*$ 가 KKT 조건을 만족하는 국소해이고 승수가 $\lambda^*$ 일 때,

\mu > \lVert \lambda^{*}\rVert_\infty \;\Longrightarrow\; x^{*}\text{는 }\phi_1(\cdot;\mu)\text{의 국소 최소점}

즉 가장 큰 승수보다 큰 벌점 계수 하나만 잡으면 그걸로 끝이다. 직관은 간단하다. 이차 벌점은 제약 근처에서 기울기가 0으로 사그라들어 목적함수의 잡아당김을 이길 수 없지만, 절댓값은 제약면에서 기울기가 $\mu$ 로 살아 있어 $\mu$ 가 승수보다 크면 밖으로 나가려는 힘을 정면으로 눌러버린다.

공짜는 물론 아니다. 청구서는 비평활성으로 온다. $\phi_1$ 은 제약면에서 미분 불가능하므로 뉴턴법·준뉴턴법을 그대로 못 얹는다. 대응은 세 갈래다.

평활 근사 — 꺾인 부분을 매끄럽게 다듬는다. 다듬는 폭이 다시 $1/\mu$ 역할을 하게 되어 조건수 문제가 재림하는 경향이 있다.
비평활 전용 알고리즘 — 열분할·번들 계열의 비평활 최적화 도구를 쓴다.
머릿값 함수(merit function)로만 쓰기 — 이게 실무의 정답이다. $\phi_1$ 을 직접 최소화하지 않고, 순차 이차계획법이나 신뢰 영역 방법이 만든 스텝을 받아들일지 말지 판정하는 심판으로만 쓴다. 방향은 매끄러운 모델이 만들고, 전역 수렴은 정확 벌점이 보증한다.

여기서 유명한 함정이 하나 튀어나온다. 해 근처에서 SQP의 단위 스텝이 해까지의 거리를 제곱 차수로 줄이는데도 목적함수와 제약 위반이 둘 다 늘어 ℓ₁ 머릿값이 증가하고, 그래서 정작 좋은 스텝이 거부되어 초선형 수렴이 죽어 버리는 현상 — 마라토스 효과다. 원인은 제약이 곡률을 가질 때 선형화된 스텝이 2차 오차만큼 제약을 위반하는데, ℓ₁ 벌점은 그 위반을 1차로 세기 때문이다. 2차 보정 스텝을 덧붙이거나 비단조(watchdog) 수용 규칙을 쓰는 것이 표준 처방이다.

정확 벌점의 또 다른 얼굴이 $\ell_\infty$ 벌점이고, 아예 벌점 대신 “목적함수와 제약 위반을 두 축으로 놓고 파레토 지배로 수용 여부를 판정하는” 필터법도 같은 자리를 노린다. 벌점 계수 $\mu$ 를 사람이 고르지 않아도 된다는 것이 필터법의 세일즈 포인트다.

5. 배리어와의 대비, 그리고 승수와의 대비[편집]

제약을 목적함수에 녹이는 방법은 크게 밖에서 미는 것과 안에서 막는 것으로 갈린다.

	외부 벌점(이차)	내부 배리어(로그)
반복점 위치	실행불가능 영역을 가로지름	항상 엄격 실행가능
등식 제약	자연스럽게 처리	불가 (별도 처리 필요)
초기점 요구	아무 데서나 시작 가능	내부 실행가능점 필요
파라미터	μ → ∞	배리어 세기 t → ∞
조건수	μ에 비례, 보호막 없음	폭발하지만 구조적
현재 위상	범용 솔버에서는 은퇴	LP·QP·SOCP·SDP 주류

배리어 쪽이 이론적으로 훨씬 잘 정비된 것은 자기일치 배리어 이론 덕이며, 그 이야기는 내점법에 있다. 반대로 초기 실행가능점을 구하는 것 자체가 어려운 문제나 등식 제약이 지배적인 문제에서는 외부 벌점 계열이 여전히 자연스럽다.

그리고 벌점법의 결함을 가장 깔끔하게 고친 것이 **증강 라그랑주법**이다. 요점만 옮기면 이렇다 — 이차 벌점에 라그랑주 항 $\lambda^\top c(x)$ 를 하나 더 얹고, 앞에서 얻은 관계 $\lambda^* \approx \lambda + \mu c$ 를 그대로 승수 갱신 규칙으로 쓰면, $\mu$ 를 무한대로 보내는 대신 $\lambda$ 를 $\lambda^*$ 로 보내는 것으로 목표가 바뀐다. 정확 벌점처럼 유한 $\mu$ 에서 정확해에 도달하면서도 함수는 매끄럽게 남는다. 즉 이 문서의 두 절이 지적한 두 가지 병 — 부정확성과 비평활성 — 을 동시에 피한다. 벌점법을 배우는 실질적 이유의 절반은 그다음 장을 이해하기 위해서다.

6. 해석 코드 안의 벌점[편집]

범용 최적화 솔버에서는 밀려났지만, 유한요소법 안에서 구속을 부과하는 방법으로서의 벌점법은 지금도 현역이다.

접촉 구속 — “관통하지 마라”를 관통량 $g_N$ 에 대한 $\frac{\varepsilon}{2}g_N^2$ 벌점으로 부과하면, 접촉면에 스프링 상수 $\varepsilon$ 짜리 스프링을 심는 것과 같다. 추가 자유도 없이 강성행렬이 양정부호로 유지된다는 것이 최대 장점이고, 대가는 유한한 관통량과 $\varepsilon$ 을 키울 때의 조건수 악화다. 정확히 이 문서 앞부분의 이야기가 구조해석 언어로 반복되는 것이며, 그래서 실무의 국룰은 증강 라그랑주 접촉이다. 세 방식의 비교표는 접촉 해석과 증강 라그랑주법에 있다.
다점 구속·강체 결합 — MPC나 tied 접촉을 벌점 스프링으로 부과하는 것도 흔하다. 벌점 계수를 주변 요소 강성의 $10^3$ ~ $10^6$ 배 정도로 잡는 경험칙이 널리 쓰이는데, 근거는 “구속이 충분히 세면서 조건수를 태우지는 않는” 절충점이다.
비압축성 — 비압축 조건 $\nabla\cdot\mathbf{u} = 0$ 을 체적탄성계수 $\lambda\lVert\nabla\cdot\mathbf{u}\rVert^2$ 로 벌하는 벌점 정식화는 압력 자유도를 없애 준다. $\lambda$ 를 키우면 요소 잠김이 발생하므로 선택적 축소적분과 세트로 다닌다.
니체 방법(Nitsche’s method) — 경계조건을 약형식에서 벌점으로 부과하되, 일관성 항을 함께 넣어 변분적으로 일관되게 만든 방법. 벌점 계수가 어떤 문턱값을 넘기만 하면 되고 무한대로 보낼 필요가 없다는 점에서, 앞 절의 “정확 벌점” 아이디어의 편미분방정식 판본으로 읽을 수 있다. 컷셀·레벨셋 방법 기반 비적합 격자에서 경계조건을 거는 표준 도구가 됐다.

이름이 같아서 헷갈리는 사례도 있다. 위상 최적화의 SIMP에서 말하는 “penalization”은 제약 위반에 대한 벌점이 아니라 중간 밀도의 강성을 $\rho^p$ 로 깎아 0/1로 몰아가는 보간 지수다. 목적이 정반대(제약 부과가 아니라 이산화 유도)이므로 같은 단어에 속으면 안 된다.² 유전 알고리즘류에서 제약 위반을 적합도에서 빼는 관행도 벌점법이 맞지만, 여기서는 $\mu$ 를 키우는 점열 자체가 없어서 “정적 벌점”이라 부르고 계수 선택이 순수하게 튜닝의 영역으로 떨어진다.³

7. 관련 문서[편집]

내점법의 이 성질(조건수는 폭발하는데 계산된 방향은 얌전하다)은 라이트 부부의 논문들이 정리한 유명한 반례다. 벌점법 쓰다가 같은 관용을 기대하면 안 된다. 저쪽은 구조가 지켜 주는 것이고 이쪽은 그냥 나쁜 것이다. ↩
같은 논문 안에서 “penalty parameter”가 두 뜻으로 쓰이는 경우도 있다. 구조 최적화 논문을 읽을 때 $p$ 가 SIMP 지수인지 제약 벌점인지부터 확인하는 습관이 정신건강에 이롭다. ↩
그래서 진화 알고리즘 논문의 절반은 벌점 계수를 세대에 따라 키우는 스케줄, 위반 정도에 따라 계수를 바꾸는 적응 규칙, 아예 제약을 별도 목적으로 올리는 다목적화 같은 변형을 제안한다. 이론적 보장이 없는 자리를 휴리스틱이 채우는 전형적인 풍경. ↩

벌점법