7.104 벌점법과 장벽법

1. 제약을 목적 함수에 통합하는 접근

벌점법(penalty method)과 장벽법(barrier method)은 제약 최적화 문제를 비제약 또는 구간 제약 최적화 문제의 연속으로 변환하여 푸는 방법이다. 제약 조건의 위반 또는 경계에의 접근에 대한 벌칙(penalty) 또는 장벽(barrier)을 목적 함수에 가산하고, 벌칙/장벽의 세기를 점진적으로 증가/감소시키면서 원래 제약 문제의 해에 수렴한다.

2. 이차 벌점법(Quadratic Penalty Method)

2.1 등식 제약에 대한 이차 벌점

등식 제약 문제 $\min f(\mathbf{x})$ subject to $\mathbf{h}(\mathbf{x}) = \mathbf{0}$ 에 대해 이차 벌점 함수를 다음과 같이 구성한다.

$Q(\mathbf{x}; \rho) = f(\mathbf{x}) + \frac{\rho}{2}\lVert \mathbf{h}(\mathbf{x}) \rVert^2 = f(\mathbf{x}) + \frac{\rho}{2}\sum_{j=1}^{p} h_j(\mathbf{x})^2$

여기서 $\rho > 0$ 은 벌점 매개변수이다. $\rho$ 를 증가시키면서 $Q(\mathbf{x}; \rho)$ 를 반복적으로 최소화하면, 해 $\mathbf{x}^*(\rho)$ 는 원래 제약 문제의 해에 수렴한다.

2.2 부등식 제약에 대한 이차 벌점

부등식 제약 $g_i(\mathbf{x}) \leq 0$ 에 대해서는 위반 시에만 벌점을 부과한다.

$Q(\mathbf{x}; \rho) = f(\mathbf{x}) + \frac{\rho}{2}\sum_{i=1}^{m} [\max(0, g_i(\mathbf{x}))]^2$

2.3 한계

이차 벌점법의 주요 한계는 악조건(ill-conditioning)이다. $\rho \to \infty$ 에서 벌점 항의 곡률이 과도하게 커져 헤시안의 조건수가 $O(\rho)$ 로 증가하며, 수치적 최적화가 어려워진다. 이론적으로는 $\rho \to \infty$ 에서 정확한 해가 얻어지지만, 실용적으로는 유한한 $\rho$ 에서의 근사해에 잔여 제약 위반이 존재한다.

3. 정확 벌점법(Exact Penalty Method)

3.1 $\ell_1$ 벌점

$P_1(\mathbf{x}; \rho) = f(\mathbf{x}) + \rho \sum_{j=1}^{p} \lvert h_j(\mathbf{x}) \rvert + \rho \sum_{i=1}^{m} \max(0, g_i(\mathbf{x}))$

충분히 큰 유한한 $\rho$ 에서 $P_1$ 의 최소점이 원래 문제의 최적해와 일치하는 성질을 갖는다. 구체적으로, $\rho > \max_i(\mu_i^*)$ ( $\mu_i^*$ 는 최적 라그랑주 승수)이면 정확한 해가 보장된다. 그러나 $\ell_1$ 벌점 함수는 미분 불가능한 점을 가지므로, 비매끄러운 최적화 기법이 필요하다.

4. 장벽법(Barrier Method) / 내점법(Interior Point Method)

4.1 로그 장벽 함수

부등식 제약 $g_i(\mathbf{x}) \leq 0$ 에 대해 로그 장벽(logarithmic barrier)을 사용한다.

$B(\mathbf{x}; \tau) = f(\mathbf{x}) - \tau \sum_{i=1}^{m} \ln(-g_i(\mathbf{x}))$

여기서 $\tau > 0$ 은 장벽 매개변수이다. $-\ln(-g_i)$ 는 $g_i \to 0^-$ 일 때 $+\infty$ 로 발산하여, 허용 영역의 경계에 대한 무한 장벽을 형성한다. 따라서 최소화 과정에서 반복열이 항상 허용 영역의 내부(interior)에 머물게 되며, 이것이 “내점법“이라는 명칭의 유래이다.

4.2 중심 경로(Central Path)

각 $\tau > 0$ 에서 $B(\mathbf{x}; \tau)$ 의 최소점 $\mathbf{x}^*(\tau)$ 는 다음의 KKT 조건을 만족한다.

$\nabla f(\mathbf{x}^*(\tau)) + \sum_{i=1}^{m} \frac{\tau}{-g_i(\mathbf{x}^*(\tau))} \nabla g_i(\mathbf{x}^*(\tau)) = \mathbf{0}$

$\mu_i(\tau) = \tau/(-g_i(\mathbf{x}^*(\tau)))$ 로 정의하면, 이는 섭동된 KKT 조건 $\mu_i g_i = -\tau$ 에 해당한다. $\tau$ 를 영으로 감소시키면 $\mathbf{x}^*(\tau)$ 가 원래 문제의 최적해에 수렴하며, 매개변수 $\tau$ 에 의해 매개변수화된 경로 $\{\mathbf{x}^*(\tau) : \tau > 0\}$ 를 중심 경로라 한다.

4.3 장벽 매개변수의 갱신

각 외부 반복에서 $\tau$ 를 $\sigma$ 배로 축소한다( $\tau_{k+1} = \sigma \tau_k$ , $0 < \sigma < 1$ ). 내부 반복에서는 현재 $\tau$ 에 대한 장벽 문제를 뉴턴법으로 근사적으로 풀어 중심 경로 위의 점을 찾는다. 실용적 구현에서는 외부 반복과 내부 반복을 분리하지 않고 동시에 갱신하는 원시-쌍대(primal-dual) 내점법이 사용된다.

4.4 원시-쌍대 내점법

원시 변수 $\mathbf{x}$ 와 쌍대 변수 $\boldsymbol{\mu}$ 를 동시에 갱신하는 방법이다. 섭동된 KKT 시스템을 뉴턴법으로 풀어 갱신 방향을 결정한다.

$\begin{bmatrix} \nabla^2_{\mathbf{x}\mathbf{x}}\mathcal{L} & \nabla\mathbf{g}^T \\ \boldsymbol{\mu}\nabla\mathbf{g} & -\text{diag}(\mathbf{g}) \end{bmatrix} \begin{bmatrix} \Delta\mathbf{x} \\ \Delta\boldsymbol{\mu} \end{bmatrix} = -\begin{bmatrix} \nabla_{\mathbf{x}}\mathcal{L} \\ \boldsymbol{\mu} \odot \mathbf{g} + \tau\mathbf{1} \end{bmatrix}$

원시-쌍대 내점법은 이론적으로 다항 시간 수렴이 보장되며, 실용적으로도 매우 효율적이다.

5. 벌점법과 장벽법의 비교

특성	벌점법	장벽법(내점법)
초기점	허용 불필요(비허용 가능)	내부 허용점 필요
제약 위반	허용(점진적 감소)	없음(항상 내부)
수렴 매개변수	$\rho \to \infty$	$\tau \to 0$
악조건	$O(\rho)$	$O(1/\tau)$
정확 해	유한 $\rho$ 에서 가능( $\ell_1$ )	$\tau \to 0$ 에서 수렴

6. 로봇 공학에서의 응용

궤적 최적화에서의 장벽법: 장애물 회피 제약을 로그 장벽으로 포함하여 매끄러운 비제약 문제로 변환한다. 장벽의 세기를 조절하여 안전 마진과 궤적 품질 사이의 균형을 조정한다.

벌점 기반 접촉 모델: 로봇 접촉 시뮬레이션에서 비관입 제약을 벌점 스프링으로 처리하는 방법이 물리 엔진에서 널리 사용된다. 벌점 계수는 접촉 강성(contact stiffness)에 해당한다.

7. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
Fiacco, A. V., & McCormick, G. P. (1990). Nonlinear Programming: Sequential Unconstrained Minimization Techniques. SIAM.
Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.

version: 1.0