활성집합법

최적설계 수치해석 마지막 수정: 2026-07-28 04:53:19

1. 개요[편집]

활성집합법(active-set method)은 부등식 제약이 붙은 최적화 문제에서, 최적해에서 등호로 딱 붙어 있을 제약의 집합(활성 집합)을 추정한 뒤 그 추정을 등식 제약만 있는 부분문제로 바꿔 풀고, 결과를 보고 추정을 고쳐 나가는 반복법이다. 아이디어를 한 줄로 줄이면 이렇다.

부등식 제약 문제가 어려운 이유는 어느 제약이 걸릴지 모른다는 조합적 불확실성 때문이다. 어느 게 걸릴지 안다면 나머지는 그냥 선형대수다.

즉 활성집합법은 연속 최적화 문제 속에 숨어 있는 조합 문제를 한 번에 한 제약씩 풀어 나간다. 선형계획법의 심플렉스법이 바로 이 틀의 LP 특수화이며, 이차계획법 솔버의 양대 계보 중 하나가 활성집합법이다(다른 하나가 내점법).

2. 문제 설정과 KKT 조건[편집]

볼록 QP를 기준으로 쓰면 다음과 같다. $G$ 는 대칭 반정부호.

\min_{x} \; \tfrac{1}{2} x^{\top} G x + c^{\top} x \quad \text{s.t.} \quad a_i^{\top} x = b_i \; (i \in \mathcal{E}), \quad a_i^{\top} x \ge b_i \; (i \in \mathcal{I})

점 $x$ 에서의 활성 집합은 $\mathcal{A}(x) = \mathcal{E} \cup \{ i \in \mathcal{I} : a_i^\top x = b_i \}$ 이다. 카루시-쿤-터커 조건은

Gx + c = \sum_{i \in \mathcal{A}(x^{*})} \lambda_i a_i, \qquad \lambda_i \ge 0 \; (i \in \mathcal{I}), \qquad \lambda_i (a_i^{\top} x^{*} - b_i) = 0

마지막 상보성 조건이 문제의 핵심이다. 각 부등식 제약마다 “붙었거나(승수 $\ge 0$ ) 놀거나(승수 $=0$ )” 둘 중 하나 — 제약이 $p$ 개면 원리적으로 $2^p$ 가지 경우의 수다. 전수조사는 당연히 불가능하고, 활성집합법은 이 조합을 한 반복에 한 원소씩 바꿔가며 국소적으로 탐색한다.

3. 작업집합과 등식제약 부분문제[편집]

알고리즘이 들고 다니는 현재 추정치를 작업집합(working set) $\mathcal{W}_k$ 라 부른다. 활성 집합의 부분집합이면서 그 안의 제약 기울기 $a_i$ 들이 일차독립이 되도록 관리한다.¹

반복 $k$ 에서 $\mathcal{W}_k$ 의 제약을 전부 등식으로 취급하고, 현재 점 $x_k$ 에서의 이동량 $p$ 에 대한 등식제약 QP를 푼다. $g_k = G x_k + c$ 일 때

\min_{p} \; \tfrac{1}{2} p^{\top} G p + g_k^{\top} p \quad \text{s.t.} \quad a_i^{\top} p = 0, \; i \in \mathcal{W}_k

이건 그냥 KKT 선형계다. $A_W$ 를 $\mathcal{W}_k$ 의 제약 행렬이라 하면

\begin{bmatrix} G & -A_W^{\top} \\ A_W & 0 \end{bmatrix} \begin{bmatrix} p \\ \hat{\lambda} \end{bmatrix} = \begin{bmatrix} -g_k \\ 0 \end{bmatrix}

부정치(indefinite) 안장점 계라 LU 분해를 그냥 때리면 안 되고, 두 갈래 정석이 있다. 영공간법(null-space)은 $A_W Z = 0$ 인 $Z$ 를 QR 분해로 잡아 축소 헤세 $Z^\top G Z$ 를 촐레스키로 푼다 — 제약이 많아 자유도가 작을 때 유리. 치역공간법(range-space)은 $G^{-1}$ 을 쓸 수 있을 때 슈어 보수 $A_W G^{-1} A_W^\top$ 로 승수를 먼저 푼다 — 제약이 적을 때 유리.

4. 작업집합 갱신 규칙[편집]

부분문제를 푼 뒤 분기는 두 가지뿐이다.

(1) $p \ne 0$ — 움직인다. 그대로 $x_k + p$ 로 가면 작업집합 밖의 부등식을 뚫을 수 있으므로 비율 검정으로 스텝을 자른다.

\alpha_k = \min\left(1, \; \min_{i \notin \mathcal{W}_k,\; a_i^{\top} p < 0} \frac{b_i - a_i^{\top} x_k}{a_i^{\top} p}\right)

$\alpha_k < 1$ 이면 최소값을 준 제약이 차단 제약(blocking constraint)이고, 이를 $\mathcal{W}_{k+1}$ 에 추가한다. 심플렉스법의 비율 검정과 완전히 같은 논리다.

(2) $p = 0$ — 현재 작업집합에 대해서는 최적이다. 이때 승수 $\hat{\lambda}$ 를 본다. 부등식에서 온 승수가 전부 0 이상이면 KKT를 전부 만족하므로 종료. 음수인 승수가 있다면 그 제약은 “누르고 있는 방향이 반대” — 즉 그 제약을 놓아주면 목적함수가 더 내려간다는 뜻이므로, 가장 음수인 것 하나를 골라 작업집합에서 제거한다.²

승수의 부호가 곧 “이 제약을 계속 붙들고 있을 것인가”의 판정 기준이라는 점이 이 알고리즘의 미학이다. 볼록 QP에서 이 절차는 유한 번에 전역 최적해로 종료한다(퇴화가 있으면 선형계획법과 마찬가지로 순환 방지 규칙이 필요하다). 초기 실행가능점은 별도의 1단계(phase I) LP나 $\ell_1$ 벌점 문제로 구한다.

5. 원-쌍대 활성집합법[편집]

위 방법은 매 반복 원문제 실행가능성을 유지하는 원(primal) 활성집합법이다. 변형으로 쌍대 실행가능성을 유지하는 쌍대 활성집합법(Goldfarb-Idnani가 대표적)이 있고, 원·쌍대 변수를 동시에 다루는 원-쌍대 활성집합법(PDAS)도 있다.

PDAS의 핵심은 상보성 조건을 비평활 방정식 하나로 뭉치는 것이다. 예컨대 $\min(\lambda,\, a^\top x - b) = 0$ 꼴로 쓰면, 여기에 반평활 뉴턴법(semismooth Newton)을 적용한 것이 바로 PDAS와 동치임이 알려져 있다. 그래서 국소 초선형 수렴을 이론적으로 설명할 수 있고, 장애물 문제나 접촉 문제 같은 변분부등식 계열의 대형 문제에서 표준 도구로 쓰인다. 이 상보성 구조는 선형 상보성 문제와 그대로 이어진다 — 마찰 없는 접촉 해석에서 절점 접촉력의 부호와 침투량 사이 상보 조건이 정확히 같은 꼴이다.

6. 웜스타트와 MPC[편집]

활성집합법이 지금도 살아남은 결정적 이유가 웜스타트(warm start)다. 이유는 두 가지다.

정보의 재사용. 파라미터가 조금 바뀐 QP의 최적 활성 집합은 대개 이전 문제와 한두 제약만 다르다. 이전 해와 이전 작업집합에서 출발하면 반복 몇 번으로 끝난다.
인수분해 갱신. 작업집합이 한 반복에 원소 하나만 바뀌므로 $A_W$ 의 QR나 축소 헤세의 촐레스키 인수를 랭크-1 갱신으로 고칠 수 있다. 매번 처음부터 인수분해하는 비용을 $O(n^3)$ 에서 $O(n^2)$ 로 떨어뜨린다.

이 성질이 그대로 값이 되는 곳이 모델 예측 제어다. MPC는 제어 주기마다 구조가 동일하고 초기 상태만 바뀌는 QP를 밀리초 단위로 반복해서 푼다. 이전 주기의 해에서 한 스텝 밀어 온 것이 이번 주기의 거의 정답이므로, 웜스타트된 활성집합 솔버는 종종 반복 서너 번에 수렴한다. 파라미터를 이전 문제에서 현재 문제로 연속적으로 이동시키며 활성 집합이 바뀌는 지점만 처리하는 온라인 활성집합 전략(호모토피 방식)은 이 아이디어를 끝까지 밀어붙인 것이다.³

같은 이유로 순차 이차계획법(SQP) 내부 QP 솔버로도 활성집합법이 선호된다. 비선형 최적화의 바깥 반복이 진행되면 QP들도 서로 닮아 가기 때문이다.

7. 내점법과의 비교[편집]

항목	활성집합법	내점법
반복 수	문제 의존, 최악은 지수적	대체로 수십 회로 안정적
반복당 비용	인수분해 갱신으로 저렴	매 반복 전체 인수분해
웜스타트	매우 강함	어렵다(경계 근처 해가 중심 경로에서 벗어남)
대규모 희소 문제	불리	유리
해의 성격	정확한 활성 집합을 준다	경계에 점근적으로만 접근

정리하면 소·중규모 + 반복 재최적화 → 활성집합법, 대규모 일회성 → 내점법이다. 활성 집합의 정확한 식별이 그 자체로 정보가 되는 문제(어떤 제약이 설계를 지배하는지 알아야 하는 최적설계 상황)에서도 활성집합법 쪽이 읽기 좋은 답을 준다. 반대로 제약이 수십만 개인 위상 최적화류에서는 한 반복에 제약 하나씩 넣고 빼는 전략이 절망적으로 느려서 내점법이나 쌍대법으로 간다.⁴

8. 관련 문서[편집]

작업집합 ≠ 활성 집합이다. 퇴화한 점에서는 활성인 제약이 일차독립성을 깨뜨릴 수 있어서, 알고리즘은 그중 일부만 골라 붙들고 간다. 이 미묘한 구분을 대충 넘기면 KKT 행렬이 특이해지면서 승수가 폭발하는 즐거운 경험을 하게 된다. ↩
“가장 음수인 승수”를 고르는 건 심플렉스의 단츠히 규칙과 같은 발상인데, 승수의 크기는 제약의 스케일에 따라 달라진다. 그래서 실무 구현은 $\lambda_i / \lVert a_i \rVert$ 로 정규화해 비교한다. 제약식에 1000을 곱했다고 우선순위가 바뀌면 곤란하지 않은가. ↩
MPC 쪽 벤치마크에서 웜스타트된 활성집합 QP가 한 주기 수 마이크로초 대에 끝나는 사례가 보고된다. 물론 그건 상태 차원이 한 자릿수일 때 이야기고, 제약 개수를 늘리면 그 숫자는 아주 순순히 배신한다. ↩
제약을 전부 넣지 않고 위반된 것만 조금씩 추가하는 제약 생성(constraint generation)은 이 한계를 우회하는 고전 처방이다. 사실상 활성집합법을 문제 정의 수준에서 한 번 더 하는 셈. ↩