내점법

최적설계 수치해석 마지막 수정: 2026-07-27 04:22:11

1. 개요[편집]

내점법 Interior Point Method
약칭	IPM
분류	제약 최적화 알고리즘
돌파구	Karmarkar(1984)
이론 정비	Nesterov & Nemirovskii(1994)
반복 수	O(√m log(1/ε))
적용 부류	LP · QP · SOCP · SDP

심플렉스는 우리에 갇힌 동물처럼 벽만 따라 걷는다. 내점법은 그냥 방 한가운데를 가로질러 간다.

내점법(interior point method, IPM)은 부등식 제약이 있는 최적화 문제를 실행가능 영역의 내부를 관통하는 점열로 푸는 알고리즘 계열이다. 제약 경계를 절대 밟지 않도록 목적함수에 발산하는 벌칙항(배리어)을 얹고, 그 벌칙의 세기를 점점 줄여 가면서 뉴턴-랩슨법 스텝을 밟아 경계 위의 최적해로 접근한다.

이 문서는 알고리즘 자체만 다룬다. 볼록성이 왜 축복인지는 볼록 최적화, 최적성의 필요조건은 카루시-쿤-터커 조건, 승수의 의미는 라그랑주 승수법, 목적함수가 2차인 경우의 문제 부류는 이차계획법 문서로 넘긴다. 여기서 볼 것은 “그래서 그 KKT 조건을 컴퓨터가 어떻게 실제로 푸느냐”다.

2. 심플렉스와의 대비[편집]

선형계획법의 국룰은 1947년 단치히(G. Dantzig)의 심플렉스법이었다. 실행가능 다면체의 꼭짓점에서 꼭짓점으로 모서리를 타고 이동하는 방식으로, 실무 성능은 훌륭하지만 최악의 경우 반복 수가 지수적이라는 흠이 있다. 1972년 클리-민티(Klee–Minty)가 만든 찌그러진 초입방체는 심플렉스가 $2^n$ 개의 꼭짓점을 전부 방문하도록 만든다.¹

1979년 하치얀(L. Khachiyan)이 타원체법으로 LP가 다항시간 문제임을 증명했지만, 실전에서는 심플렉스보다 압도적으로 느려서 “이론적 승리, 실무적 참패”로 끝났다. 판을 뒤집은 것이 1984년 카마카르(N. Karmarkar)의 사영 스케일링 알고리즘이다. $O(n^{3.5}L)$ 의 다항시간 보장을 가지면서 동시에 대형 LP에서 심플렉스를 실측으로 이겨 버렸고, AT&T가 이걸로 특허를 내고 통신망 최적화에 투입하면서 최적화 학계 전체가 뒤집어졌다. 이후 20년간 상용 솔버는 “심플렉스 vs 내점법” 두 엔진을 모두 탑재하는 것이 표준이 됐다.

3. 로그 배리어와 중심 경로[편집]

현대적 서술은 카마카르의 원본보다 로그 배리어(log barrier) 관점이 깔끔하다. 문제를

\min_x \; c^{\mathsf T} x \quad \text{s.t.} \quad a_i^{\mathsf T} x \le b_i,\; i = 1,\dots,m

로 두면, 부등식 제약을 다음 함수로 대체한다.

\phi(x) = -\sum_{i=1}^{m} \log\!\left(b_i - a_i^{\mathsf T} x\right)

$\phi$ 는 실행가능 영역 내부에서만 유한하고 경계에 다가가면 $+\infty$ 로 발산한다. 즉 배리어 자체가 제약 역할을 대신한다. 이제 벌칙 세기 $t>0$ 을 붙여

\min_x \; t\,c^{\mathsf T} x + \phi(x)

를 풀면, 각 $t$ 마다 유일한 해 $x^\star(t)$ 가 나온다. 이 점들이 $t$ 를 키우며 그리는 곡선이 중심 경로(central path)다. 핵심 정리 하나: $x^\star(t)$ 에서의 쌍대 간극(duality gap)은 정확히

c^{\mathsf T} x^\star(t) - p^\star \;\le\; \frac{m}{t}

이다. 제약이 $m$ 개일 때 $t = m/\varepsilon$ 까지만 키우면 $\varepsilon$ -최적해가 보장된다는 뜻. 종료 조건이 휴리스틱이 아니라 증명된 상한이라는 점이 심플렉스와 결정적으로 다르다.²

2변수 선형계획을 로그 배리어로 푸는 실측 커널. 안쪽에서 출발한 점이 2×2 뉴턴 스텝과 실행가능 백트래킹 라인서치로 중심 경로를 따라가고, 매 중심화 단계마다 t가 μ배씩 커지며 최적 꼭짓점으로 빨려 들어간다. μ 슬라이더를 키우면 바깥 반복(중심화 단계)은 줄지만 단계당 뉴턴 반복이 늘어나는 트레이드오프가 그대로 보인다.

4. 배리어법과 원-쌍대 내점법[편집]

같은 아이디어를 구현하는 방식은 크게 두 갈래다.

순차 배리어법(sequential barrier method)은 위 식을 그대로 이중 루프로 돌린다. 바깥 루프가 $t \leftarrow \mu t$ 로 벌칙을 키우고, 안쪽 루프가 라인서치를 곁들인 뉴턴법으로 중심화 문제를 푼다. 바깥 반복 수는 $\lceil \log(m/(\varepsilon t_0)) / \log \mu \rceil$ 로 딱 떨어진다. $\mu$ 를 크게 잡으면(예: 50~100) 바깥 반복은 몇 번 안 되지만 매 단계 뉴턴이 오래 걸리고, 작게 잡으면(예: 2) 반대가 된다. 실무에서 $\mu = 10 \sim 20$ 이 무난하다고 알려진 이유가 이 트레이드오프가 꽤 평평하기 때문이다.

원-쌍대 내점법(primal-dual IPM)은 원 변수와 쌍대 변수를 처음부터 같이 굴린다. 표준형 LP $\min c^{\mathsf T}x$ s.t. $Ax = b,\, x \ge 0$ 의 KKT 조건은

A^{\mathsf T} y + s = c, \quad Ax = b, \quad x_i s_i = 0, \quad x, s \ge 0

인데, 여기서 상보성 조건만 $x_i s_i = \sigma\mu$ ( $\mu = x^{\mathsf T}s/n$ ) 로 살짝 풀어 준 뒤 그 비선형 연립방정식에 뉴턴법을 한 번 때린다. 배리어법과 달리 안쪽 루프를 수렴시키지 않고 한 스텝마다 $\mu$ 도 같이 줄인다는 게 차이. 실측 성능이 훨씬 좋아 오늘날 상용 솔버의 기본값이다.

여기에 얹히는 표준 기법이 메로트라 예측자-교정자(Mehrotra predictor-corrector, 1992)다. 먼저 $\sigma = 0$ 인 아핀 스케일링 방향(예측자)을 구해 “제약을 무시하고 얼마나 갈 수 있나”를 재고, 그 결과로 중심화 파라미터를 $\sigma = (\mu_{\text{aff}}/\mu)^3$ 처럼 적응적으로 정한 다음, 예측자에서 생긴 2차 오차항을 보정한 방향(교정자)을 다시 푼다. 같은 행렬 분해를 두 번 재사용하므로 추가 비용은 삼각 후방대입뿐인데 반복 수는 확 줄어드는, 가성비 甲의 트릭.

5. 자기일치 배리어와 복잡도[편집]

“왜 하필 로그냐”에 답한 것이 네스테로프와 네미롭스키의 자기일치(self-concordance) 이론이다. 1변수 볼록함수 $f$ 가 자기일치라는 것은

|f'''(x)| \le 2 f''(x)^{3/2}

를 만족한다는 뜻이다. 이 조건은 곡률이 너무 급격히 변하지 않음을 보장하고, 그 결과 뉴턴법의 수렴 해석이 좌표계에 무관해진다 — 즉 스케일링을 바꿔도 반복 수 상한이 그대로다. 여기에 배리어 파라미터 $\nu$ 를 붙인 $\nu$ -자기일치 배리어를 쓰면 총 뉴턴 반복 수가

O\!\left(\sqrt{\nu}\,\log(1/\varepsilon)\right)

로 나온다. 부등식 $m$ 개짜리 로그 배리어는 $\nu = m$ 이므로 그 유명한 $O(\sqrt{m}\log(1/\varepsilon))$ 이 된다. 이 이론의 진짜 위력은 LP를 넘어선 확장에 있다. 2차 원뿔에는 $-\log(t^2 - \|u\|^2)$ , 반정부호 원뿔에는 $-\log\det X$ 라는 자기일치 배리어가 존재하므로, 반정부호 계획법까지 같은 알고리즘 뼈대로 다항시간에 풀린다. SeDuMi·SDPT3·MOSEK 같은 원뿔 솔버가 전부 이 골격 위에 서 있다.³

6. 대규모 희소 선형계 풀이[편집]

내점법의 반복 수는 몇십 번이면 끝나므로, 실전 성능은 사실상 매 반복에서 KKT 선형계를 얼마나 빨리 푸느냐로 결정된다. 뉴턴 방정식을 정리하면 두 가지 형태가 나온다.

형태	크기	성질	특징
정규방정식	$m \times m$	양의 정부호	촐레스키 분해 가능, 밀집 열에 취약
증강 시스템	$(n+m) \times (n+m)$	준정부호 대칭	희소성 보존, LDLᵀ + 피벗팅 필요

정규방정식 $A D^2 A^{\mathsf T} \Delta y = r$ 은 대칭 양의 정부호라 피벗팅 없이 촐레스키로 밀 수 있어 빠르다. 문제는 $A$ 에 밀집 열(dense column)이 하나라도 있으면 $AD^2A^{\mathsf T}$ 가 통째로 밀집 행렬이 되어 희소행렬 이점이 증발한다는 것. 그래서 밀집 열을 따로 떼어 셔먼-모리슨으로 처리하거나, 아예 증강 시스템을 쓴다. 증강 시스템은 부정부호지만 준정부호(quasi-definite) 구조라 정규화만 조금 넣어 주면 고정 피벗 순서로 LDLᵀ 분해가 가능하다.

또 하나의 고질병은 조건수다. 수렴이 진행되면 $D = \mathrm{diag}(x_i/s_i)^{1/2}$ 의 원소들이 0과 $\infty$ 로 갈라지며 KKT 행렬 조건수가 $10^{16}$ 을 넘긴다. 그럼에도 내점법이 멀쩡히 도는 것은, 이 병적 조건화가 구조적이어서 오차가 정작 중요한 부분공간에는 거의 실리지 않기 때문이다.⁴ 그래도 마지막 몇 자리를 원하면 반복 세밀화(iterative refinement)를 붙이는 게 국룰이고, 초대형 문제에서는 아예 크리로프 부분공간법 + 전용 전처리기로 KKT 계를 반복적으로 푸는 접근도 쓴다.

이 모든 기계가 실시간으로 돌아가는 대표적 현장이 모델 예측 제어다. 밀리초마다 QP를 새로 푸는데, 이전 해가 좋은 초기값이 되어 주는 활성집합법과 웜스타트가 어려운 대신 반복 수가 문제 크기에 거의 둔감한 내점법이 지금도 치고받는 중이다.

7. 관련 문서[편집]

그래도 심플렉스는 죽지 않았다. 평균적 경우 해석(스필먼-텡의 매끄러운 해석, 2004)에 따르면 실무 문제에서 심플렉스의 반복 수는 사실상 다항적이다. “최악의 경우”를 만나려면 누군가 작정하고 행렬을 설계해야 한다. ↩
그래서 내점법 솔버 로그에는 반복마다 primal objective, dual objective, gap이 나란히 찍힌다. 잔차가 내려가길 기도해야 하는 CFD 사용자 입장에서는 부러운 광경이다. ↩
Nesterov, Y. & Nemirovskii, A. (1994). Interior-Point Polynomial Algorithms in Convex Programming. 이 책 이후 “새 문제 부류를 만나면 자기일치 배리어부터 찾는다”가 최적화 이론의 표준 반응이 됐다. ↩
이 현상을 정리한 것이 M. H. Wright와 S. J. Wright의 일련의 논문이다. 요약하면 “조건수는 폭발하지만 계산된 방향의 오차는 얌전하다”는 것. 수치해석 교과서의 조건수 공포증을 배신하는 반례라서 처음 보면 킹받는다. ↩

내점법