내부점법 (Interior Point Method)
정의
내부점법은 선형계획법(linear programming, LP) 및 보다 일반적인 볼록 최적화(convex optimization) 문제를 해결하기 위해 고안된 알고리즘군으로, 해의 탐색 경로가 feasible region(가능 영역)의 내부를 통과하도록 설계된 방법을 말한다. 외부점법(예: 심플렉스 방법)이 해의 꼭짓점(vertex)을 따라 이동하는 반면, 내부점법은 중심부의 연속적인 경로를 따라 최적점에 접근한다.
역사
- 1984년 나우르 엔도(N. Karmarkar)가 제안한 Karmarkar’s algorithm이 최초의 다항시간 내부점법으로 널리 알려졌다.
- 이후 프라임(프라임-듀얼) 방법, 장벽 함수(parabolic barrier) 방법, 경로 추종(path‑following) 방법 등 다양한 변형이 개발되었으며, 1990년대 초반부터 상용 LP 솔버에 구현되어 실무에서도 폭넓게 사용되고 있다.
주요 종류
| 구분 | 핵심 아이디어 | 대표 알고리즘 |
|---|---|---|
| 프라임-듀얼 방법 | primal(원문)와 dual(쌍대) 문제를 동시에 추적, 중심점 유지 | 프라임‑듀얼 경로 추종법 |
| 장벽 함수 방법 | 목표 함수에 로그 장벽(logarithmic barrier) 항을 추가해 feasible region 내부에 머무르게 함 | 로그 장벽 경로 추종법 |
| 경로 추종법 | 중심 경로(central path)를 연속적으로 따라가며 단계적으로 장벽 파라미터를 감소 | 포괄적 경로 추종 프레임워크 |
| 인코딩 방법 | 선형제약을 내부점 형태로 변환해 직접 적용 | 인코딩 기반 내부점법 |
알고리즘 개요 (일반적인 경로 추종법)
-
초기화
- 초기 feasible interior point $x^{(0)}$와 $s^{(0)}$ (슬랙 변수) 선택.
- 장벽 파라미터 $\mu > 0$ 설정.
-
Newton 단계
- KKT(Karush‑Kuhn‑Tucker) 조건에 대한 Newton 방정식을 풀어 검색 방향 $\Delta x, \Delta s$ 계산.
- 선형 시스템 $\begin{bmatrix} A & 0 \ 0 & A^T \end{bmatrix}$ 등은 효율적인 sparse factorization을 이용해 해결.
-
스텝 길이 선택
- Feasibility를 유지하기 위해 최대 허용 스텝 $\alpha$ 를 계산하고, 보통 $\alpha = \eta \min{1, \text{feasibility margin}}$ ( $\eta \in (0,1)$ ) 로 조정.
-
업데이트
- $x^{(k+1)} = x^{(k)} + \alpha \Delta x$
- $s^{(k+1)} = s^{(k)} + \alpha \Delta s$
-
장벽 파라미터 감소
- $\mu \leftarrow \sigma \mu$ ( $\sigma \in (0,1)$ ) 로 감소시키며 반복.
-
수렴 판정
- 원시·쌍대 잔차(residual)와 중심 잔차(centrality) 가 사전에 정해진 허용오차 이하가 되면 종료.
특징 및 장점
- 다항시간 복잡도: Karmarkar’s algorithm은 $O(\sqrt{n}L)$ (여기서 $n$은 변수 수, $L$은 입력 크기) 의 복잡도를 가지며, 이론적으로 심플렉스 방법보다 우수한 상한을 제공한다.
- 대규모 희소 문제에 강함: 내부점법은 행렬의 희소 구조를 활용한 효율적인 선형 시스템 풀이가 가능해, 수천~수백만 변수 규모의 LP에서도 실용적으로 사용된다.
- 정밀도: 경로를 연속적으로 추적하기 때문에 수치적 안정성이 높고, 고정밀 해를 얻기 용이하다.
한계 및 단점
- 구현 복잡성: Newton 단계와 스텝 길이 선택, 장벽 파라미터 관리 등 구현이 복잡하고, 높은 수준의 선형대수 라이브러리가 필요하다.
- 초기점 요구: feasible interior point가 필요하므로, 초기점 탐색(phase‑I) 과정이 추가 비용을 발생시킨다.
- 특정 구조에 비효율: 매우 작은 문제나 구조가 단순한 경우, 심플렉스 방법이 더 빠를 수 있다.
응용 분야
- 운송·물류 최적화 : 운송 네트워크, 배차 스케줄링
- 재무·포트폴리오 관리 : 위험 최소화, 투자 비중 최적화
- 전력 시스템 : 전력 흐름 최적화, 부하 배분
- 기계학습 : 서포트 벡터 머신(SVM) 등 대규모 이진/다중분류 문제의 라그랑지안 이중화(dual) 형태
- 통신·네트워크 설계 : 흐름 최적화, 라우팅 문제
주요 문헌 및 참고 자료
- Karmarkar, N. (1984). A New Polynomial‑time Algorithm for Linear Programming. Proceedings of the 26th IEEE Symposium on Foundations of Computer Science.
- Wright, S. J. (1997). Primal‑Dual Interior‑Point Methods. SIAM.
- Nesterov, Y., & Nemirovski, A. (1994). Interior‑Point Polynomial Algorithms in Convex Programming. SIAM.
- Andersen, E. D., & Ye, Y. (1998). On the Implementation of an Interior‑Point Method for Large‑Scale Linear Programming. Mathematical Programming.
- 박정현, 김성현 (2015). 내부점법을 이용한 대규모 선형계획 문제 해결. 한국산업공학회 논문집.
요약
내부점법은 선형계획 및 일반 볼록 최적화 문제를 다루는 강력한 수치해석 기법으로, 초기 feasible interior point부터 시작해 중심 경로(central path)를 따라 최적점에 도달한다. 다항시간 복잡도와 대규모 희소 행렬에 대한 효율성을 바탕으로 현대 상용 최적화 솔버의 핵심 알고리즘으로 자리 잡고 있다. 그러나 구현 난이도와 초기점 문제 등 몇몇 제한점도 존재한다.