7.105 증강 라그랑지안 방법

1. 이차 벌점법과 라그랑주 승수법의 결합

증강 라그랑지안 방법(Augmented Lagrangian method)은 이차 벌점법의 악조건 문제를 라그랑주 승수의 추정으로 해결하는 방법이다. 순수 이차 벌점법에서는 $\rho \to \infty$ 로 보내야 정확한 해에 수렴하지만, 증강 라그랑지안 방법에서는 유한한 $\rho$ 에서도 라그랑주 승수가 정확히 추정되면 제약을 정확히 만족하는 해에 수렴한다.

2. 등식 제약에 대한 증강 라그랑지안

등식 제약 문제 $\min f(\mathbf{x})$ subject to $\mathbf{h}(\mathbf{x}) = \mathbf{0}$ 에 대해 증강 라그랑지안 함수를 다음과 같이 정의한다.

$\mathcal{L}_A(\mathbf{x}, \boldsymbol{\nu}; \rho) = f(\mathbf{x}) + \boldsymbol{\nu}^T\mathbf{h}(\mathbf{x}) + \frac{\rho}{2}\lVert \mathbf{h}(\mathbf{x}) \rVert^2$

이 함수는 라그랑지안 $f + \boldsymbol{\nu}^T\mathbf{h}$ 에 이차 벌점 항 $\frac{\rho}{2}\lVert \mathbf{h} \rVert^2$ 를 가산한 것이다.

3. 알고리즘

증강 라그랑지안 방법(또는 승수법, method of multipliers)의 절차는 다음과 같다.

초기 승수 추정 $\boldsymbol{\nu}_0$ , 벌점 매개변수 $\rho_0 > 0$ 을 설정한다.
$k = 0, 1, 2, \ldots$ 에 대해:
$\quad$ 내부 최소화: $\mathbf{x}_{k+1} = \arg\min_{\mathbf{x}} \mathcal{L}_A(\mathbf{x}, \boldsymbol{\nu}_k; \rho_k)$
$\quad$ 승수 갱신: $\boldsymbol{\nu}_{k+1} = \boldsymbol{\nu}_k + \rho_k \mathbf{h}(\mathbf{x}_{k+1})$
$\quad$ 벌점 매개변수 갱신: 제약 위반이 충분히 감소하지 않으면 $\rho_{k+1} = \sigma \rho_k$ ( $\sigma > 1$ ), 그렇지 않으면 $\rho_{k+1} = \rho_k$
$\quad$ 수렴 판정

4. 승수 갱신의 직관

내부 최소화에서의 정류 조건은 다음과 같다.

$\nabla f(\mathbf{x}_{k+1}) + \nabla\mathbf{h}(\mathbf{x}_{k+1})^T[\boldsymbol{\nu}_k + \rho_k\mathbf{h}(\mathbf{x}_{k+1})] = \mathbf{0}$

이를 라그랑주 필요 조건과 비교하면, $\boldsymbol{\nu}_k + \rho_k\mathbf{h}(\mathbf{x}_{k+1})$ 이 라그랑주 승수의 추정치 역할을 한다. 승수 갱신 $\boldsymbol{\nu}_{k+1} = \boldsymbol{\nu}_k + \rho_k\mathbf{h}(\mathbf{x}_{k+1})$ 는 바로 이 관계를 반영한 것이며, 쌍대 경사 상승법(dual gradient ascent)으로 해석된다.

5. 이차 벌점법 대비 이점

증강 라그랑지안 방법의 핵심 이점은 벌점 매개변수 $\rho$ 를 무한대로 보내지 않아도 된다는 점이다. 라그랑주 승수가 최적 승수 $\boldsymbol{\nu}^*$ 에 수렴하면, 유한한 $\rho$ 에서도 정확한 해가 산출된다. 이로 인해 내부 최소화 하위 문제의 조건수가 제한되며, 수치적 안정성이 유지된다.

구체적으로, 이차 벌점법에서 내부 문제의 헤시안 조건수가 $O(\rho)$ 인 반면, 증강 라그랑지안에서는 $O(1)$ 로 유계이다(승수가 정확할 때). 이는 내부 최소화를 효율적으로 수행할 수 있게 한다.

6. 부등식 제약으로의 확장

부등식 제약 $g_i(\mathbf{x}) \leq 0$ 에 대해서는 여유 변수(slack variable) $s_i \geq 0$ 을 도입하여 $g_i(\mathbf{x}) + s_i = 0$ 으로 등식화하거나, 다음의 변형된 증강 라그랑지안을 사용한다.

$\mathcal{L}_A(\mathbf{x}, \boldsymbol{\mu}; \rho) = f(\mathbf{x}) + \sum_{i=1}^{m} \frac{1}{2\rho}\left[\max(0, \mu_i + \rho g_i(\mathbf{x}))^2 - \mu_i^2\right]$

승수 갱신은 다음과 같다.

$\mu_{i,k+1} = \max(0, \mu_{i,k} + \rho_k g_i(\mathbf{x}_{k+1}))$

$\max$ 연산은 부등식 제약의 능동/비능동 구분을 반영한다.

7. 수렴 이론

적절한 조건(2차 충분 조건, LICQ 등)하에서 증강 라그랑지안 방법은 다음의 수렴 성질을 갖는다.

원초 수렴: $\mathbf{x}_k \to \mathbf{x}^*$ (원래 제약 문제의 국소 최적해)
쌍대 수렴: $\boldsymbol{\nu}_k \to \boldsymbol{\nu}^*$ (최적 라그랑주 승수)
수렴 속도: $\rho_k$ 가 고정이면 선형 수렴, $\rho_k$ 가 증가하면 초선형 수렴이 가능

8. ADMM(Alternating Direction Method of Multipliers)

증강 라그랑지안 방법의 중요한 변형으로, 목적 함수가 분리 가능한 구조 $f(\mathbf{x}) + g(\mathbf{z})$ subject to $\mathbf{A}\mathbf{x} + \mathbf{B}\mathbf{z} = \mathbf{c}$ 를 가질 때, $\mathbf{x}$ 와 $\mathbf{z}$ 를 교대로 최소화하는 방법이다.

$\mathbf{x}_{k+1} = \arg\min_{\mathbf{x}} \mathcal{L}_A(\mathbf{x}, \mathbf{z}_k, \boldsymbol{\nu}_k; \rho)$
$\mathbf{z}_{k+1} = \arg\min_{\mathbf{z}} \mathcal{L}_A(\mathbf{x}_{k+1}, \mathbf{z}, \boldsymbol{\nu}_k; \rho)$
$\boldsymbol{\nu}_{k+1} = \boldsymbol{\nu}_k + \rho(\mathbf{A}\mathbf{x}_{k+1} + \mathbf{B}\mathbf{z}_{k+1} - \mathbf{c})$

ADMM은 분산 최적화, 합의(consensus) 문제, 다중 로봇 시스템의 협력 계획 등에 응용된다.

9. 로봇 공학에서의 응용

접촉 포함 궤적 최적화: 접촉 제약을 증강 라그랑지안으로 처리하여, 접촉 전환을 부드럽게 최적화하는 방법이 연구되어 있다. 내부 최소화에서 접촉력과 운동 변수를 교대로 갱신한다.

다중 로봇 분산 계획: ADMM을 이용하여 다수의 로봇이 충돌 회피 제약을 만족하면서 각자의 궤적을 분산적으로 최적화하는 프레임워크가 구현된다.

제약된 모델 예측 제어: MPC의 부등식 제약을 증강 라그랑지안으로 처리하여, 비제약 최적화 해법을 내부 루프에 활용하는 방법이 실시간 로봇 제어에 적용된다.

10. 참고 문헌

Hestenes, M. R. (1969). “Multiplier and Gradient Methods.” Journal of Optimization Theory and Applications, 4(5), 303–320.
Powell, M. J. D. (1969). “A Method for Nonlinear Constraints in Minimization Problems.” In R. Fletcher (Ed.), Optimization. Academic Press.
Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers.” Foundations and Trends in Machine Learning, 3(1), 1–122.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

version: 1.0