7.102 능동 제약 조건과 비능동 제약 조건

1. 능동 제약과 비능동 제약의 정의

부등식 제약 $g_i(\mathbf{x}) \leq 0$ 이 점 $\mathbf{x}$ 에서 등호로 성립하면, 즉 $g_i(\mathbf{x}) = 0$ 이면, 해당 제약을 능동 제약(active constraint) 또는 활성 제약이라 한다. 엄격한 부등호 $g_i(\mathbf{x}) < 0$ 으로 성립하면 비능동 제약(inactive constraint) 또는 비활성 제약이라 한다.

점 $\mathbf{x}$ 에서의 능동 집합(active set)을 다음과 같이 정의한다.

$\mathcal{A}(\mathbf{x}) = \{i \in \{1, \ldots, m\} : g_i(\mathbf{x}) = 0\}$

등식 제약 $h_j(\mathbf{x}) = 0$ 은 모든 허용 점에서 항상 능동이다. 비능동 부등식 제약 $i \notin \mathcal{A}(\mathbf{x})$ 는 국소적으로 여유(slack) $-g_i(\mathbf{x}) > 0$ 를 가지므로, $\mathbf{x}$ 의 충분히 작은 근방에서는 해당 제약이 실질적으로 존재하지 않는 것과 같다.

2. 능동 집합의 중요성

최적점 $\mathbf{x}^*$ 에서의 능동 집합 $\mathcal{A}(\mathbf{x}^*)$ 의 식별은 제약 최적화 해법의 핵심이다. 만약 $\mathcal{A}(\mathbf{x}^*)$ 를 미리 알고 있다면, 원래의 부등식 제약 문제를 능동 제약만을 등식 제약으로 갖는 등식 제약 문제로 환원할 수 있다.

$\min_{\mathbf{x}} f(\mathbf{x}) \quad \text{subject to} \quad g_i(\mathbf{x}) = 0, \; i \in \mathcal{A}(\mathbf{x}^*)$

이 등식 제약 문제는 라그랑주 승수법으로 효율적으로 풀 수 있다. 문제는 $\mathcal{A}(\mathbf{x}^*)$ 가 사전에 알려져 있지 않다는 점이며, 이를 반복적으로 식별하는 것이 능동집합법(active set method)의 핵심 과제이다.

3. 엄격 상보성과 퇴화

3.1 엄격 상보성(Strict Complementarity)

KKT 점 $(\mathbf{x}^*, \boldsymbol{\mu}^*)$ 에서 모든 능동 제약 $i \in \mathcal{A}(\mathbf{x}^*)$ 에 대해 $\mu_i^* > 0$ 이 성립하면, 엄격 상보성(strict complementarity)이 만족된다고 한다. 즉, 각 부등식 제약에 대해 $g_i(\mathbf{x}^*) < 0$ 또는 $\mu_i^* > 0$ 중 정확히 하나가 엄격하게 성립한다.

엄격 상보성이 성립하면 능동 집합의 식별이 용이하며, 수치적 알고리즘의 수렴 속도가 향상된다.

3.2 퇴화(Degeneracy)

능동 제약 $i \in \mathcal{A}(\mathbf{x}^*)$ 에 대해 $\mu_i^* = 0$ 인 경우를 퇴화 또는 약 능동(weakly active)이라 한다. 이 경우 해당 제약이 능동인지 비능동인지를 승수 정보만으로는 판별할 수 없으며, 수치적 해법에서 능동 집합의 진동(chattering)이 발생할 수 있다. 퇴화는 실용적 해법의 설계에서 특별한 주의를 요하는 상황이다.

4. 능동집합법(Active Set Method)

능동집합법은 추정된 능동 집합 $\mathcal{W}_k$ (작업 집합, working set)를 반복적으로 갱신하면서 최적해를 찾는 알고리즘이다.

4.1 기본 절차

초기 허용 점 $\mathbf{x}_0$ 와 초기 작업 집합 $\mathcal{W}_0 = \mathcal{A}(\mathbf{x}_0)$ 를 설정한다.
작업 집합의 제약을 등식 제약으로 취급하여 등식 제약 이차 하위 문제를 풀고, 탐색 방향 $\mathbf{d}_k$ 를 구한다.
$\mathbf{d}_k = \mathbf{0}$ 이면 라그랑주 승수를 검사한다.

모든 $\mu_i \geq 0$ 이면 KKT 조건이 만족되어 최적이다.
$\mu_i < 0$ 인 제약이 존재하면, 가장 음의 승수를 갖는 제약을 작업 집합에서 제거하고 2단계로 돌아간다.

$\mathbf{d}_k \neq \mathbf{0}$ 이면, 비능동 제약을 위반하지 않는 최대 스텝 크기를 계산한다. 새로 능동이 되는 제약이 있으면 작업 집합에 추가한다.

4.2 제약 추가와 제거

제약 추가(constraint addition): 비능동 제약이 스텝에 의해 능동이 되면 작업 집합에 추가한다. 스텝 크기는 다음과 같이 제한된다.

$\alpha_k = \min\left(1, \min_{i \notin \mathcal{W}_k, \, \nabla g_i^T\mathbf{d}_k > 0} \frac{-g_i(\mathbf{x}_k)}{\nabla g_i(\mathbf{x}_k)^T\mathbf{d}_k}\right)$

제약 제거(constraint dropping): 작업 집합 내의 제약 중 음의 승수를 갖는 것을 제거한다. 이는 해당 제약의 비능동화가 목적 함수를 개선할 수 있음을 의미한다.

5. 능동 집합 식별의 실용적 전략

5.1 내점법에서의 식별

내점법(interior point method)에서는 반복이 진행됨에 따라 비능동 제약의 여유(slack) $-g_i(\mathbf{x}_k)$ 가 양의 값을 유지하는 반면, 능동 제약의 여유는 영에 접근한다. 적절한 임계값 $\epsilon$ 을 설정하여 $\lvert g_i(\mathbf{x}_k) \rvert < \epsilon$ 이면 능동으로 식별하는 방법이 사용된다.

5.2 SQP에서의 식별

순차적 이차 계획법(SQP)에서는 매 반복의 이차 하위 문제의 해로부터 능동 집합이 추정되며, 수렴 과정에서 능동 집합이 안정화된다. 최적해 근방에서 능동 집합이 정확히 식별되면, SQP는 이차 수렴을 달성한다.

6. 로봇 공학에서의 능동 제약 분석

로봇 운동 중 능동 제약의 식별은 제어기 설계에 직접적인 영향을 미친다.

관절 한계에서의 능동 제약: 관절이 물리적 범위의 경계에 도달하면 해당 제약이 능동이 되며, 제어 자유도가 하나 감소한다. 능동 관절 한계의 승수 $\mu_i^*$ 는 해당 관절에 가해지는 구속 반력에 대응한다.

접촉 역학에서의 능동 제약: 보행 로봇의 접촉 계획에서 접촉 제약(비관입, 마찰 원추)의 능동/비능동 구분은 접촉 상태(접촉/비접촉, 점착/미끄러짐)의 식별에 직접 대응한다. 상보성 조건 $\mu_i g_i = 0$ 은 접촉력이 존재하려면 접촉이 능동( $g_i = 0$ )이어야 하고, 비접촉( $g_i < 0$ )이면 접촉력이 영( $\mu_i = 0$ )이어야 함을 나타낸다.

7. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical Optimization. Academic Press.
Fletcher, R. (1987). Practical Methods of Optimization (2nd ed.). Wiley.
Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.

version: 1.0