내점법 (Interior Point Method)

한 줄 정의: 실행가능영역의 경계를 따라 이동하는 단체법과 달리, 영역 내부에서 출발하여 장벽함수 또는 중심경로를 따라 최적해로 수렴해 가는 선형·볼록 최적화 알고리즘군입니다.

쉽게 풀면

단체법이 다면체의 모서리를 꼭짓점에서 꼭짓점으로 옮겨 다니며 답을 찾는다면, 내점법은 다면체 한가운데에서 출발해 내부를 가로질러 곧장 최적점 근처로 다가갑니다. 경계에 닿지 않도록 '벽에 가까워지면 벌점'을 주는 장벽함수를 쓰고, 벌점의 크기를 점점 줄여 가며 진짜 최적해에 접근합니다.

왜 중요한가

1984년 Karmarkar의 알고리즘으로 선형계획법이 다항시간에 풀린다는 것이 실용적으로 입증되었고, 대규모 희소 문제에서는 단체법보다 반복 횟수가 훨씬 적습니다. 현대 상용 솔버는 LP·QP·SOCP·SDP 등에 내점법을 기본 탑재하며, 볼록 최적화 전반의 표준 해법입니다.

논문에서는 이렇게 쓰입니다

"변수 200만 개 규모의 선형계획 모형은 원-쌍대 내점법(primal-dual interior point method)으로 약 40회 반복 만에 수렴하였다."

매우 큰 선형 문제를 내점법으로 적은 반복 횟수에 풀었다는 뜻입니다.

"내점법 해는 꼭짓점이 아닌 면의 내부에 위치하므로 기저해를 얻기 위해 교차(crossover) 절차를 추가로 수행하였다."

내점법이 주는 답이 모서리 점이 아니어서 단체법 형태의 답으로 바꾸는 후처리를 했다는 의미입니다.

조금 더 깊게 보면

가장 널리 쓰이는 원-쌍대 경로추종법은 KKT 조건의 상보성 조건 x_i s_i = 0 을 x_i s_i = μ 로 완화한 중심경로를 뉴턴법으로 따라가며 μ를 0으로 줄입니다. 반복 횟수는 문제 크기에 거의 무관하게 수십 회 수준이지만, 매 반복마다 큰 희소 선형방정식을 풀어야 하므로 촐레스키 분해 효율이 성능을 좌우합니다. 정수계획의 분지한정법에서는 웜스타트가 어려운 내점법보다 쌍대 단체법이 더 유리한 경우가 많습니다.

주의할 점

내점법은 최적면이 여러 점을 포함할 때 꼭짓점 해가 아닌 중심 해를 주므로 민감도분석이나 정수계획 분지에 바로 쓰기 어렵습니다. 또한 반복마다 메모리 요구가 커서 조밀한 행렬에는 부적합할 수 있고, 고정밀 해가 필요하면 교차 절차가 추가로 필요합니다.