# 내부점법 (Interior Point Method)

## 1. 개요
**내부점법(Interior Point Method)**은 제약 조건이 있는 최적화 문제에서 실행 가능 영역(Feasible Region)의 내부를 통해 최적해로 접근하는 수치 최적화 알고리즘의 한 부류이다. 주로 선형 계획법(Linear Programming, LP) 및 비선형 계획법(Nonlinear Programming, NLP)에서 사용되며, 특히 **볼록 최적화 문제(Convex Optimization Problem)**에서 전역 최적점(Global Optimum)을 효율적으로 찾아내는 것을 목적으로 한다. 제약 조건을 함수 형태의 페널티로 변환하여 무제약 최적화 문제처럼 처리함으로써 해를 탐색한다.

## 2. 기본 원리 및 작동 방식

### 2.1 장벽 함수 (Barrier Function)
내부점법의 핵심은 부등식 제약 조건 $g_i(x) \le 0$을 목적 함수에 통합하는 **장벽 함수**를 사용하는 것이다. 가장 대표적인 로그 장벽 함수(Logarithmic Barrier Function)는 다음과 같이 정의된다.

$$\min f(x) - \mu \sum_{i=1}^{m} \ln(-g_i(x))$$

여기서 $\mu > 0$는 **장벽 파라미터(Barrier Parameter)**이다. 제약 조건의 경계인 $g_i(x) \to 0$에 가까워질수록 $\ln(-g_i(x))$ 값은 $-\infty$로 발산하며, 그 앞에 붙은 마이너스($-$) 부호로 인해 전체 목적 함수 값은 $+\infty$로 급격히 증가하게 된다. 결과적으로 알고리즘이 해를 탐색할 때 제약 조건의 경계를 넘지 않고 항상 실행 가능 영역의 **내부(Interior)**에 머물게 강제하는 '장벽' 역할을 한다.

**[로그 장벽 함수의 시각적 개념]**
*(그래프 묘사: $x$축이 변수, $y$축이 함수값일 때, 제약 조건 경계선에 가까워질수록 함수값이 수직으로 급격히 상승하는 형태의 곡선이 나타나며, $\mu$가 작아질수록 이 장벽의 폭이 좁아지며 실제 경계선에 밀착되는 모습)*

### 2.2 중심 경로 (Central Path)
장벽 파라미터 $\mu$의 값에 따라 최적점 $x^*(\mu)$가 결정된다. $\mu$가 매우 클 때는 장벽 함수의 영향력이 커져 영역의 중심부로 수렴하고, $\mu$를 점진적으로 0으로 줄여나가면 $x^*(\mu)$는 실제 제약 조건이 있는 문제의 최적해 $x^*$로 수렴하게 된다. 이 $\mu$의 변화에 따라 이동하는 최적점들의 궤적을 **중심 경로(Central Path)**라고 한다.

## 3. KKT 조건과 최적성 조건

내부점법의 수렴성과 해의 타당성을 검증하기 위해 **KKT(Karush-Kuhn-Tucker) 조건**을 활용한다. 이는 제약 조건이 있는 최적화 문제에서 최적해가 갖추어야 할 필요조건이다.

### 3.1 KKT 조건의 구성
목적 함수 $f(x) = c^T x$와 제약 조건 $Ax = b, x \ge 0$이 주어졌을 때, 라그랑주 승수(Lagrange Multiplier) $y$와 슬랙 변수(Slack Variable) $s$를 도입한 KKT 조건은 다음과 같다.

1. **원시 가능성 (Primal Feasibility):** $Ax = b, x \ge 0$
2. **쌍대 가능성 (Dual Feasibility):** $A^T y + s = c, s \ge 0$
3. **상보성 조건 (Complementary Slackness):** $x_i s_i = 0 \quad (\forall i=1, \dots, n)$

내부점법에서는 상보성 조건 $x_i s_i = 0$을 $x_i s_i = \mu$로 완화하여 계산하며, $\mu \to 0$일 때 원래의 KKT 조건을 만족하게 된다.

## 4. 주요 알고리즘 및 유형

### 4.1 프라이멀-듀얼 내부점법 (Primal-Dual Interior Point Method)
단순 장벽법이 원시 문제(Primal Problem)만을 다루는 것과 달리, 프라이멀-듀얼법은 원시 변수 $x$와 쌍대 변수 $(y, s)$를 동시에 업데이트한다. 뉴턴 방법(Newton's Method)을 사용하여 KKT 시스템의 비선형 방정식을 선형화하고, 매 반복마다 다음의 방향 벡터 $(\Delta x, \Delta y, \Delta s)$를 계산하여 이동한다.

**알고리즘 단계:**
1. **초기화:** $x > 0, s > 0$인 초기점 설정 및 $\mu > 0$ 설정.
2. **방향 계산:** 뉴턴 시스템을 통해 $\Delta x, \Delta y, \Delta s$를 계산.
3. **스텝 크기 결정:** $x$와 $s$가 양수(내부점)를 유지하도록 하는 최대 스텝 크기 $\alpha$를 결정.
4. **업데이트:** $x \leftarrow x + \alpha \Delta x, y \leftarrow y + \alpha \Delta y, s \leftarrow s + \alpha \Delta s$.
5. **파라미터 갱신:** $\mu$를 감소시키고, 수렴 조건(Duality Gap $\le \epsilon$)을 만족할 때까지 반복.

### 4.2 알고리즘 비교
| 구분 | 단순 장벽법 (Barrier Method) | 프라이멀-듀얼법 (Primal-Dual) |
| :--- | :--- | :--- |
| **접근 방식** | 원시 문제의 페널티 함수 최소화 | 원시-쌍대 변수 동시 최적화 |
| **수렴 속도** | 상대적으로 느림 | 매우 빠름 (초선형 수렴) |
| **계산 복잡도** | 내부 루프에서 무제약 최적화 문제 해결 필요 | KKT 시스템의 선형 방정식 풀이 |
| **안정성** | $\mu$ 감소 속도에 매우 민감함 | 상대적으로 안정적이며 효율적임 |

## 5. 수렴성 증명 및 파라미터 전략

### 5.1 수렴성 증명 (Convergence Analysis)
내부점법의 수렴성은 주로 **쌍대성 간극(Duality Gap)**의 감소를 통해 증명된다.
- 쌍대성 간극은 $\text{Gap} = c^T x - b^T y = x^T s$로 정의된다.
- 프라이멀-듀얼법에서 $\mu$를 $\mu_{k+1} = \sigma \mu_k$ ($\sigma < 1$) 형태로 업데이트할 때, 매 반복마다 쌍대성 간극이 기하급수적으로 감소함이 수학적으로 증명되어 있다.
- 결과적으로 반복 횟수 $k$가 $\mathcal{O}(\sqrt{n} \log(1/\epsilon))$ 수준에서 수렴하며, 이는 다항 시간(Polynomial Time) 내에 최적해에 도달함을 의미한다.

### 5.2 장벽 파라미터 $\mu$ 업데이트 전략
$\mu$를 너무 빠르게 줄이면 경계에 부딪혀 수렴에 실패하고, 너무 느리게 줄이면 계산 시간이 과도하게 늘어난다.
- **선형 감소 전략:** $\mu_{k+1} = \sigma \mu_k$ (상수 $\sigma \in (0, 1)$ 사용).
- **적응형 전략 (Adaptive Strategy):** 현재의 쌍대성 간극 $\eta = x^T s / n$을 계산하여 $\mu = \sigma \eta$로 설정. 이는 현재 해의 상태에 맞춰 동적으로 장벽의 강도를 조절하는 방식이다.

## 6. 심플렉스법(Simplex Method)과의 비교

| 비교 항목 | 심플렉스법 (Simplex) | 내부점법 (Interior Point) |
| :--- | :--- | :--- |
| **이동 경로** | 다면체의 꼭짓점(Vertex)을 따라 이동 | 실행 가능 영역의 내부를 가로질러 이동 |
| **시간 복잡도** | 최악의 경우 지수 시간 $\mathcal{O}(2^n)$ | 다항 시간 $\mathcal{O}(n^3 L)$ |
| **수렴 특성** | 정확한 꼭짓점 해를 빠르게 찾음 | 최적해 근처로 빠르게 수렴 (근사해) |
| **대규모 문제** | 변수가 많아지면 효율성 급감 | 대규모 희소 행렬(Sparse Matrix)에 유리 |
| **적용 범위** | 주로 선형 계획법(LP) | LP, QP, SDP 등 광범위한 최적화 |

## 7. 활용 분야 및 응용
내부점법은 계산 복잡도가 낮고 대규모 문제에 강점이 있어 다양한 산업 분야에서 활용된다.
- **물류 및 공급망 최적화:** 수만 개의 제약 조건이 있는 운송 경로 및 재고 최적화.
- **금융 포트폴리오 최적화:** 리스크를 최소화하고 수익을 최대화하는 이차 계획법(QP) 문제 해결.
- **반정부호 계획법(SDP):** 제어 이론, 신호 처리 및 기계 학습의 커널 최적화.
- **에너지 망 관리:** 전력 송전 효율 최적화 및 부하 분산 문제.

## 8. 구현 예제 및 도구

Python에서는 `SciPy`의 `optimize.linprog`나 전문 라이브러리인 `CVXOPT`를 통해 내부점법을 구현할 수 있다.

```python
import numpy as np
from scipy.optimize import linprog

# 목적 함수 계수 (Minimize: -1*x0 - 2*x1)
c = [-1, -2]

# 부등식 제약 조건 Ax <= b
# x0 + x1 <= 4
# -x0 + 2*x1 <= 2
A = [[1, 1], [-1, 2]]
b = [4, 2]

# 변수 범위 (x0 >= 0, x1 >= 0)
x0_bounds = (0, None)
x1_bounds = (0, None)

# 내부점법을 사용하여 최적화 수행
# SciPy 최신 버전에서는 'interior-point' 대신 'highs' 사용을 강력히 권장함
res = linprog(c, A_ub=A, b_ub=b, bounds=[x0_bounds, x1_bounds], method='highs')

print(f"최적해: {res.x}")
print(f"최적값: {res.fun}")
```

**주요 도구:**
- **CVXOPT:** 볼록 최적화(Convex Optimization) 전문 라이브러리로, 정교한 내부점법 구현체 제공.
- **Gurobi / CPLEX:** 상용 최적화 솔버로, 고도로 최적화된 내부점법 및 심플렉스법 하이브리드 알고리즘 탑재.
- **SciPy:** 일반적인 과학 계산용 라이브러리로, `method='highs'`를 통해 효율적인 내부점법 기반 솔버 인터페이스 제공.