증강 라그랑주법

편집 역사 토론
최적설계 수치해석 구조해석 마지막 수정: 2026-08-09 04:27:51

1. 개요[편집]

증강 라그랑주법
Augmented Lagrangian Method
다른 이름승수법(method of multipliers), PHR 방법
제안Hestenes(1969) · Powell(1969) · Rockafellar(1973~76)
핵심 식Lρ(x,λ) = f(x) + λᵀc(x) + (ρ/2)‖c(x)‖²
승수 갱신λ ← λ + ρ c(x)
쌍대 해석쌍대함수에 대한 근접점 알고리즘
대표 구현LANCELOT, ALGENCAN, ADMM 계열

증강 라그랑주법(augmented Lagrangian method, ALM)은 등식 제약 최적화 문제 min⁡f(x)\min f(x) s.t. c(x)=0c(x)=0 을, 보통의 라그랑지안에 이차 벌점항을 하나 더 얹은 함수

Lρ(x,λ)=f(x)+λ⊤c(x)+ρ2∥c(x)∥22L_\rho(x,\lambda) = f(x) + \lambda^{\top}c(x) + \frac{\rho}{2}\lVert c(x)\rVert_2^{2}

를 xx 에 대해 최소화하고 승수 λ\lambda 를 갱신하는 것을 번갈아 반복해서 푸는 방법이다. 이름 그대로 라그랑주 승수법에 벌점법을 증강(augment)한 물건인데, 두 방법의 단점을 서로가 가려 준다는 점이 핵심이다.

한 줄로 요약하면 이렇다. 벌점법은 ρ→∞\rho\to\infty 를 요구해서 조건수가 폭발하고, 순수 라그랑주 승수법은 안장점 문제라 최소화만으로는 못 풀린다. 증강 라그랑주법은 유한한 ρ\rho 로 정확한 해에 도달하면서 매 반복은 (국소적으로) 볼록한 최소화로 남는다.1

2. 벌점법은 왜 부족한가[편집]

제약을 그냥 이차 벌점으로 때리는 방법, 즉 min⁡xf(x)+ρ2∥c(x)∥2\min_x f(x) + \frac{\rho}{2}\lVert c(x)\rVert^2 을 생각하자. 이 문제의 최소점 xρx_\rho 에서 1차 조건은 ∇f+ρJ⊤c=0\nabla f + \rho J^\top c = 0 이다. 카루시-쿤-터커 조건의 ∇f+J⊤λ∗=0\nabla f + J^\top\lambda^* = 0 과 비교하면 ρ c(xρ)≈λ∗\rho\, c(x_\rho) \approx \lambda^*, 즉

∥c(xρ)∥=O(1/ρ)\lVert c(x_\rho)\rVert = O(1/\rho)

제약 위반이 1/ρ1/\rho 로만 줄어든다. 위반을 10−810^{-8} 로 만들려면 ρ∼108\rho \sim 10^{8} 을 써야 한다는 뜻. 그런데 헤세 행렬은

∇xx2=∇2f+ρ∑ici∇2ci+ρ J⊤J\nabla_{xx}^{2} = \nabla^{2}f + \rho\sum_i c_i \nabla^{2}c_i + \rho\,J^{\top}J

이고, J⊤JJ^\top J 는 제약의 법선 방향으로만 O(ρ)O(\rho) 크기의 고유값을 만든다. 접선 방향의 곡률은 O(1)O(1) 로 남으므로 조건수가 ρ\rho 에 비례해 커진다. ρ=108\rho=10^8 이면 배정도 부동소수점의 유효자릿수를 통째로 태우는 셈이라, 내부 뉴턴 반복이 먼저 무너진다.2 벌점법이 “개념은 쉬운데 실무에선 안 쓴다”는 평을 듣는 이유가 이것이다.

3. 이차항이 사서 주는 것 — 정확성[편집]

증강 라그랑지안의 1차 조건을 보자.

∇xLρ(x,λ)=∇f(x)+J(x)⊤(λ+ρ c(x))=0\nabla_x L_\rho(x,\lambda) = \nabla f(x) + J(x)^{\top}\big(\lambda + \rho\, c(x)\big) = 0

괄호 안이 KKT의 λ∗\lambda^* 자리에 그대로 앉아 있다. 승수 추정치가 정확하다면(λ=λ∗\lambda = \lambda^*) c(x∗)=0c(x^*)=0 인 진짜 해가 이 식을 만족한다 — 벌점법과 달리 ρ\rho 를 키울 필요가 전혀 없다. 남은 문제는 x∗x^* 가 Lρ(⋅,λ∗)L_\rho(\cdot,\lambda^*) 의 최소점이냐인데, 2차 충분조건이 성립하면 어떤 유한한 문턱값 ρˉ\bar\rho 가 존재해서 ρ>ρˉ\rho > \bar\rho 일 때 ∇xx2Lρ(x∗,λ∗)≻0\nabla^2_{xx}L_\rho(x^*,\lambda^*) \succ 0 이 된다.3 즉 유한한 ρ\rho 로 제약 최적화가 국소적으로 무제약 최소화가 된다.

이 관찰이 알고리즘 전체를 결정한다. 우리가 할 일은 ρ\rho 를 무한대로 보내는 게 아니라 λ\lambda 를 λ∗\lambda^* 로 보내는 것이다.

4. 알고리즘[편집]

xk+1  ←  arg⁡min⁡x  Lρk(x,λk)(근사 최소화로 충분)λk+1  ←  λk+ρk c(xk+1)ρk+1  ←  {γρk∥c(xk+1)∥>τ∥c(xk)∥ρk그 외\begin{aligned} &x^{k+1} \;\leftarrow\; \arg\min_x \; L_{\rho_k}(x, \lambda^k) \quad (\text{근사 최소화로 충분})\\ &\lambda^{k+1} \;\leftarrow\; \lambda^{k} + \rho_k\, c(x^{k+1})\\ &\rho_{k+1} \;\leftarrow\; \begin{cases}\gamma\rho_k & \lVert c(x^{k+1})\rVert > \tau \lVert c(x^{k})\rVert\\ \rho_k & \text{그 외}\end{cases} \end{aligned}

승수 갱신식은 위에서 유도한 λ∗≈λ+ρc\lambda^* \approx \lambda + \rho c 를 그대로 쓴 것이다. 표준 결과는

∥λk+1−λ∗∥  ≤  Mρk ∥λk−λ∗∥\lVert \lambda^{k+1}-\lambda^{*}\rVert \;\le\; \frac{M}{\rho_k}\,\lVert \lambda^{k}-\lambda^{*}\rVert

로, ρ\rho 가 문턱값을 넘으면 선형 수렴하고 ρ\rho 를 키울수록 수렴률이 좋아진다. 벌점법에서는 ρ\rho 를 키우는 것이 순수한 비용이었는데 여기서는 이득이라는 점이 재미있는 반전. 물론 조건수는 여전히 ρ\rho 를 따라가므로 실무 구현은 “제약 위반이 충분히 줄고 있으면 ρ\rho 를 안 건드린다”는 위 규칙으로 필요 이상 키우지 않는다. 내부 최소화를 정확히 풀 필요가 없다는 점(inexact ALM)도 큰 실용적 장점이다.

5. 쌍대 관점 — 실은 근접점 알고리즘[편집]

쌍대함수 q(λ)=inf⁡x{f(x)+λ⊤c(x)}q(\lambda) = \inf_x \{f(x)+\lambda^\top c(x)\} 는 오목하지만 대개 미분 불가능하다. 증강된 쌍대함수 qρ(λ)=inf⁡xLρ(x,λ)q_\rho(\lambda)=\inf_x L_\rho(x,\lambda) 를 계산하면 이 각진 함수가 매끄럽게 다듬어지는데, 이것이 정확히 qq 의 모로 포락(Moreau–Yosida 정규화)이다. 그리고

∇qρ(λ)=c(x(λ))\nabla q_\rho(\lambda) = c\big(x(\lambda)\big)

이므로 승수 갱신 λ←λ+ρc\lambda\leftarrow\lambda+\rho c 는 매끄러워진 쌍대함수 위의 스텝 ρ\rho 짜리 경사상승이다. 록카펠라(1976)는 이것을 더 강하게 정리했다 — 증강 라그랑주법은 쌍대문제에 근접점 알고리즘을 적용한 것과 완전히 동일하다.

λk+1=arg⁡max⁡λ  {q(λ)−12ρ∥λ−λk∥2}\lambda^{k+1} = \arg\max_{\lambda}\;\Big\{ q(\lambda) - \frac{1}{2\rho}\lVert \lambda-\lambda^{k}\rVert^{2}\Big\}

이 동치성 덕분에 근접점 알고리즘의 수렴 이론(볼록의 경우 대역 수렴, 강한 정칙성 아래 초선형 수렴)이 그대로 상속된다. 그리고 여기서 교대방향 승수법(ADMM)까지는 한 걸음이다. 목적함수가 f(x)+g(z)f(x)+g(z), 제약이 Ax+Bz=cAx+Bz=c 인 2블록 문제에서 LρL_\rho 를 (x,z)(x,z) 에 대해 동시에 최소화하는 대신 가우스-자이델식으로 한 번씩만 훑고 승수를 갱신하면 그게 ADMM이다. ALM은 정확한 결합 최소화, ADMM은 한 스윕 — 차이는 그것뿐인데 분산 최적화의 문이 열렸다.

6. 부등식 제약과 구현체[편집]

gi(x)≤0g_i(x)\le 0 는 슬랙 변수 si≥0s_i \ge 0 를 넣어 gi+si=0g_i + s_i = 0 으로 바꾼 뒤 ss 를 해석적으로 소거하면 정리된다. 결과가 PHR(Powell–Hestenes–Rockafellar) 형태다.

Lρ(x,λ)=f(x)+12ρ∑i(max⁡(0,  λi+ρ gi(x))2−λi2),λi←max⁡(0,  λi+ρ gi(x))L_\rho(x,\lambda) = f(x) + \frac{1}{2\rho}\sum_i\Big( \max\big(0,\;\lambda_i+\rho\,g_i(x)\big)^{2} - \lambda_i^{2}\Big), \qquad \lambda_i \leftarrow \max\big(0,\;\lambda_i + \rho\, g_i(x)\big)

max⁡(0,⋅)2\max(0,\cdot)^2 는 C1C^1 이지만 C2C^2 는 아니라서, 내부 최소화에 순수 뉴턴법을 쓰면 활성/비활성 경계에서 삐걱거린다. 실무 코드가 준-뉴턴법이나 신뢰 영역 방법을 내부 솔버로 쓰는 이유.

대표 구현으로는 등식 제약과 단순 상하한을 다루는 LANCELOT(Conn–Gould–Toint), 그리고 TANGO 프로젝트의 ALGENCAN(Birgin–Martínez)이 있다. 비선형 계획에서 내점법·순차 이차계획법에 비해 ALM의 매력은 워밍 스타트와 저정밀 내부 해에 관대하다는 점이라, 문제 규모가 크고 함수 평가가 비싼 최적설계·PDE 제약 최적화에서 여전히 현역이다.

7. CAE에서 — 접촉 구속의 국룰[편집]

접촉 해석에서 “관통하지 마라”는 조건 gN≥0g_N \ge 0, pN≤0p_N \le 0, gNpN=0g_N p_N = 0 는 전형적인 KKT 상보 조건이다. 이걸 유한요소법에 넣는 방법이 셋인데, 각각의 병이 뚜렷하다.

방식관통량시스템 성질추가 자유도
벌점법유한 (∝ 1/ε)양정부호 유지없음
순수 라그랑주 승수0 (엄밀)안장점, 부정부호접촉 승수
증강 라그랑주허용오차까지 0양정부호 유지없음(외부 반복)

순수 승수법은 강성행렬 대각에 0이 들어오는 안장점 시스템을 만들어서 표준 스카이라인·촐레스키 분해 기반 솔버를 못 쓰게 하고 inf-sup 조건까지 신경 써야 한다. 벌점법은 시스템 구조는 착하지만 관통이 남고, 없애려고 ε\varepsilon 을 키우면 강성행렬 조건수가 무너져 반복 솔버가 죽는다. 증강 라그랑주 접촉(Simo–Laursen 계열, 흔히 우자와 알고리즘식 외부 루프로 구현)은 적당한 ε\varepsilon 을 유지한 채 외부 반복으로 접촉압 승수를 갱신해서 관통을 허용오차까지 몰아낸다. 두 병을 동시에 피하는 대가는 외부 반복이 붙는 것뿐이라, 주요 상용 코드가 접촉 알고리즘 옵션으로 이걸 제공한다.4 비압축성 유동·요소 잠김 대책으로 쓰이는 증강 라그랑주 압력 처리도 같은 아이디어다.

8. 관련 문서[편집]

9. Footnotes[편집]

  1. 승수법이라는 이름은 헤스테네스와 파월이 1969년에 거의 동시에, 서로 모른 채 발표한 데서 왔다. 록카펠라가 1973~76년에 부등식 제약과 쌍대 이론을 붙여 지금 형태로 정리했고, 그래서 부등식 형태를 PHR 증강 라그랑지안이라 부른다. ↩

  2. “그냥 ρ\rho 를 101210^{12} 로 주면 되는 거 아님?” 하고 눌러 본 사람은 잔차가 어느 순간부터 안 줄고 진동하는 광경을 본다. 제약은 만족되는데 목적함수가 엉뚱한 데서 멈춰 있다면 십중팔구 벌점 조건수 때문이다. ↩

  3. 이 문턱값 ρˉ\bar\rho 는 이론적으로만 존재하고 실제로 계산해 주는 사람은 없다. 그래서 모든 구현이 “위반이 안 줄면 ρ\rho 를 10배” 같은 휴리스틱을 달고 있다. 최적화 코드의 절반은 이런 휴리스틱이다. ↩

  4. 접촉 해석 컨버전스 로그에서 “augmentation 1, 2, 3…”이 찍히는 게 바로 이 외부 승수 갱신이다. 이게 늘어나면 화가 나지만, 대안은 관통한 채로 결과를 내는 것이라는 걸 떠올리면 참을 만해진다. ↩