내부점법

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 정의
- 3.1. 볼록 계획법 문제의 정의
- 3.2. 프로그램의 크기와 수치적 해결사
4. 유형
5. 경로 추적 방법
6. 프라이멀-듀얼 내부점 방법
7. 내부점 방법으로 해결 가능한 볼록 계획법 유형
8. 구현
참조

1. 개요

내부점 방법은 1967년 I. I. 디킨에 의해 처음 발견되었으며, 볼록 계획법 문제를 해결하기 위한 알고리즘이다. 1984년 나렌드라 카르마르카르는 선형 계획법을 위한 내부점 방법인 카르마르카르 알고리즘을 개발하여 이 분야에 대한 관심을 높였다. 내부점 방법은 포텐셜 감소 방법, 경로 추적 방법, 프라이멀-듀얼 방법 등 다양한 유형이 있으며, 특히 프라이멀-듀얼 방법이 널리 사용된다. 이 방법들은 선형 계획법, 2차 제약 2차 계획법, Lp 노름 근사, 기하 계획법, 반정부호 계획법 등 다양한 볼록 계획법 문제를 효율적으로 해결하는 데 사용된다.

더 읽어볼만한 페이지

선형 계획법 - 자료 포락 분석
자료 포락 분석(DEA)은 여러 입력과 출력을 가진 의사결정단위(DMU)의 효율성을 측정하는 방법으로, 선형 계획법을 활용해 경험적 생산 기술 경계를 추정하며, 생산 함수 형태를 가정할 필요 없이 여러 입출력을 동시에 고려할 수 있지만, 변수 선택에 민감하다는 단점도 있다.
선형 계획법 - 일차 부등식
일차 부등식은 미지수의 최고차항이 1차인 부등식으로, ax > b, ax < b, ax ≥ b, ax ≤ b (단, a ≠ 0)의 형태로 표현되며, 해를 구하는 것은 부등식을 만족하는 미지수 x의 값을 찾는 것이고, 연립일차부등식은 각 부등식을 동시에 만족하는 해를 구하는 것을 목표로 한다.
최적화 알고리즘 - 기댓값 최대화 알고리즘
최적화 알고리즘 - 유전 알고리즘
유전 알고리즘은 생물 진화 과정을 모방하여 최적해를 탐색하는 계산 최적화 기법으로, 해를 유전자로 표현하고 적합도 함수를 통해 평가하며 선택, 교차, 돌연변이 연산을 반복하여 최적해에 근접하는 해를 생성하며, 성능은 매개변수에 영향을 받고 초기 수렴 문제 해결을 위한 다양한 변형 기법과 관련 기법이 존재한다.

내부점법

2. 역사

내부점 방법은 1967년 소련의 수학자 I. I. 디킨에 의해 처음 발견되었다.^[1] 1980년대 중반 미국에서 재조명받으며, 선형 계획법과 볼록 최적화 문제 해결에 획기적인 발전을 가져왔다.

2. 1. 카르마르카르 알고리즘의 등장과 초기 발전

1984년, 나렌드라 카르마르카르는 선형 계획법을 위한 카르마르카르 알고리즘을 개발했는데,^[2] 이는 다항 시간(

O(n^{3.5} L)

연산, 여기서 ''n''은 변수의 수, ''L''은 비트 수)에 실행되며 실제 문제에서도 매우 효율적인 것으로 나타났다. 카르마르카르의 연구는 내부점 방법에 대한 학계의 관심이 급증하는 계기가 되었다.

2. 2. 경로 추적 방법과 자기 일치 장벽 함수

제임스 레네가는 1986년에 처음으로 실행 시간이

O(n^{3} L)

인 '경로 추적' 내부점법을 발명했다.^[3] 이 방법은 카르마르카르 알고리즘보다 이론적으로 더 빠른 성능을 보였다. 이후 레네가의 방법은 자기 일치 장벽 함수를 사용하여 선형 계획법뿐만 아니라 볼록 집합을 인코딩함으로써 볼록 최적화 문제 전반으로 확장되었다.^[3]

유리 네스테로프와 아르카디 네미로프스키는 모든 볼록 집합을 인코딩할 수 있는 특수한 종류의 장벽 함수를 개발하여 내부점 방법의 이론적 발전에 크게 기여하였다. 그들은 알고리즘의 반복 횟수가 해의 차원과 정확도에 대한 다항식으로 제한된다는 것을 보장했다.^[5]^[3]

2. 3. 프라이멀-듀얼 내부점 방법의 발전

프라이멀-듀얼 경로 추적 내부점 방법은 현재 가장 성공적인 내부점 방법으로 간주된다.^[6] 메로트라 예측자-수정자 방법은 이 방법 클래스의 대부분 구현에 기반을 제공한다.^[6]

2. 4. 초기 연구와 한계

1960년대 초, 안토니 V. 피아코와 가스 P. 매코믹 등은 장벽 함수를 사용하여 비선형 계획법 문제를 해결하는 방법을 연구했다.^[4] 이들은 주로 일반적인 비선형 계획법을 위해 이 방법을 개발했다. 그러나 당시에는 순차적 이차 계획법(SQP)과 같은 다른 비선형 계획법 알고리즘이 더 경쟁력이 있었기 때문에, 내부점 방법은 상대적으로 주목받지 못하고 나중에 버려졌다.^[4]

3. 정의

내부점법은 볼록 계획법 문제를 해결하기 위해 사용되는 방법이다.^[1]

3. 1. 볼록 계획법 문제의 정의

볼록 계획법 문제는 다음과 같이 정의된다.

:minimize ''f''(''x'')

:subject to ''x'' ∈ ''G''.

여기서 ''f''는 볼록 함수이고, ''G''는 볼록 집합이다. 일반성을 잃지 않고, 목적 함수 ''f''는 선형 함수라고 가정할 수 있다.

일반적으로 볼록 집합 ''G''는 볼록 부등식과 선형 등식 집합으로 표현된다. 선형 등식은 선형 대수를 사용하여 제거할 수 있으므로, 간단하게 볼록 부등식만 있다고 가정하고, 문제는 다음과 같이 표현할 수 있다. 여기서 ''g_i''는 볼록 함수이다.

:minimize ''f''(''x'')

:subject to ''g_i''(''x'') ≤ 0 for ''i'' = 1, ..., ''m''.

3. 2. 프로그램의 크기와 수치적 해결사

제약 조건 함수가 어떤 패밀리(예: 이차 함수)에 속한다고 가정하면, 프로그램은 유한한 '계수 벡터'로 표현될 수 있다. 이 계수 벡터의 차원을 프로그램의 '크기'라고 한다. '수치적 해결사'는 주어진 계수 벡터에 대해 유한한 산술 연산을 사용하여 일련의 근사해를 생성하는 알고리즘이다. 수치적 해결사는 다항식(polynomial) 시간 안에 해를 찾는 것을 목표로 한다.

4. 유형

내부점 방법은 크게 세 가지 유형으로 분류할 수 있다.

'''포텐셜 감소 방법''': 카르마커 알고리즘이 최초의 방법이다.
'''경로 추적 방법''': 제임스 레니가^[7]와 클로비스 곤자가^[8]의 알고리즘이 최초의 방법이다.
'''프라이멀-듀얼 방법'''^[7]^[8]

4. 1. 포텐셜 감소 방법 (Potential-Reduction Methods)

카르마커 알고리즘은 최초의 포텐셜 감소 방법이다.^[7] 목적 함수와 장벽 함수의 조합으로 정의되는 포텐셜 함수를 최소화하는 방식으로 작동한다.

4. 2. 경로 추적 방법 (Path-Following Methods)

제임스 레니가^[7]와 클로비스 곤자가^[8]의 알고리즘이 최초의 경로 추적 방법이다. 이 방법은 장벽 파라미터를 점차적으로 증가시키면서, 중심 경로(central path)를 따라 최적해로 수렴한다.

4. 3. 프라이멀-듀얼 방법 (Primal-Dual Methods)

프라이멀-듀얼 방법은 프라이멀 문제와 듀얼 문제의 해를 동시에 찾아가는 방법이다. 이 방법은 KKT 조건(Karush-Kuhn-Tucker conditions)의 변형된 형태인 "교란된 상보성" 조건을 활용한다.^[7]^[8] 현재 가장 널리 사용되는 내부점 방법이다.

주쌍대내점법의 아이디어는 단순하며, 제약 조건이 있는 비선형 최적화 문제에도 적용이 가능하다. 여기서는 단순화를 위해 제약식이 모두 부등식으로 주어지는 비선형 최적화 문제를 고려한다.

:'''최소화:'''

f(x)

:'''조건:'''

c(x) \geq 0,  x \in \mathbb{R}^n, c(x) \in \mathbb{R}^m~~~~(1)

이 최적화 문제의 로그 배리어 함수는 다음과 같다.

:

B(x,\mu) = f(x) - \mu \sum_{i=1}^m \ln(c_i(x))~~~~(2)

여기서

\mu

는 양의 스칼라이며, 때로는 "배리어 파라미터"라고도 불린다. 이

\mu

가 0으로 수렴해 가면,

B(x, \mu)

가 최적해에 수렴해 간다.

전술한 배리어 함수의 기울기는

:

g_b = g - \mu \sum_{i=1}^m \frac{1}{c_i (x)} \nabla c_i (x)~~~~(3)

가 된다. 단,

g

는 원래 함수

f(x)

의 기울기이며,

\nabla c_i

는

c_i

의 기울기를 나타낸다.

주 값

x

에 더하여, 쌍대 값

\lambda \in \mathbb{R}^m

을 라그랑주 승수로서 도입한다.

:

\forall i=1, \ldots, m, c_i(x) \lambda_i = \mu~~~~(4)

이 조건은 때때로 섭동 상보성 조건이라고도 불린다. 식 (4)를 식 (3)에 적용하면 다음을 얻는다.

:

g - A^T \lambda = 0 ~~~~ (5)

단, 행렬

A

는 제약

c(x)

의 야코비 행렬이다.

식 (5)가 나타내는 것은 함수

f(x)

의 기울기가 제약식의 기울기에 의해 뻗어 나가는 부분 공간 안에 존재한다는 것이다. 이 때 작은

\mu

에 의한 섭동 상보성 조건은, 최적해가

c_i(x)=0

의 경계 부근에 존재하거나, 혹은 제약

c_i(x)

의 기울기

g

가 거의 0이라는 것을 나타낸다.

식 (4) 및 식 (5)에 대해 뉴턴법을 사용하여

(x, \lambda)

를 갱신해 가는 것을 고려하면, 그 갱신 폭

(p_x, p_\lambda)

는 다음 선형 방정식의 해로 주어진다.

:

\begin{pmatrix} W & -A^T \\ \Lambda A & C \end{pmatrix}\begin{pmatrix}p_x \\ p_{\lambda} \end{pmatrix} =\begin{pmatrix} -g + A^T \lambda \\ \mu 1 - C \lambda \end{pmatrix}

단, 행렬

W

는 함수

B(x,\mu)

의 헤세 행렬이며, 대각 행렬

\Lambda

는

\lambda

를 대각 성분으로 갖는다. 또한,

C

는

C_{ii}=c_i(x)

인 대각 행렬이다.

식 (1), (4), 그리고

\mu > 0

으로부터

:

\lambda \geq 0

이 각 스텝에 부과된다. 이 조건을 유지하기 위해, 적절한 스텝 갱신 폭

\alpha

를 선택하고,

:

(x, \lambda) \rightarrow (x + \alpha p_x, \lambda + \alpha p_\lambda)

함으로써, 최적해를 향해 수렴해 간다.

5. 경로 추적 방법

내부점법에서 경로 추적 방법은 특정 증가 수열 t₁, t₂, ...를 따라 함수 ''x''*를 추적하는 방법이다. 즉, ''x_i'' - ''x''*(''t_i'')가 ''i''가 무한대로 접근함에 따라 0에 접근하도록, ''x''*(''t_i'')에 충분히 근사한 ''x_i''를 계산한다. 그러면 ''x_i''는 원래 문제 (P)의 최적 해에 접근한다.^[7]^[8]^[3]

이를 위해 장벽 함수 b(x), 페널티 파라미터 ''t_i'' 결정 정책, 뉴턴의 방법과 같은 무제한 최적화 솔버가 필요하다. 각 ''x_i''는 다음 문제 (''P_i+1'')를 풀기 위한 시작점으로 사용된다.

5. 1. 기본 아이디어

제약 조건이 있는 볼록 최적화 문제 (P)는 장벽 함수를 추가하여 제약 조건이 없는 문제로 변환할 수 있다. 장벽 함수 ''b''는 실행 가능한 영역 ''G''의 내부에서 정의된 매끄러운 볼록 함수이며, {''x_j''} in interior(G)의 극한이 ''G''의 경계에 있는 수열에 대해

\lim_{j\to \infty} b(x_j)=\infty

를 만족한다. 즉, 경계에 가까워질수록 무한대로 발산하는 성질을 갖는다. 또한 ''b''는 비퇴화되어 있다고 가정한다. 즉, interior(G)의 모든 x에 대해

b''(x)

가 양의 정부호 함수이다.

이제 다음과 같은 프로그램 집합을 생각한다.

(''P_t'') : t * f(x) + b(x)를 최소화

여기서 ''t''는 페널티 파라미터이다. 이 프로그램은 ''b''가 ''G''의 내부에서만 정의되므로 기술적으로는 제약이 있지만, 실제로 이 함수를 최소화하는 과정에서 ''b''가 무한대로 접근하는 경계에는 접근하지 않기 때문에 제약 조건이 없는 문제처럼 해결할 수 있다. (''P_t'')는 고유한 해 ''x''*(''t'')를 가지며, ''x''*는 ''t''의 연속 함수이며 이를 ''중앙 경로''라고 한다. ''t''가 무한대로 접근할 때 ''x''*의 모든 극한점은 원래 프로그램 (P)의 최적 해이다.

'''경로 추적 방법'''은 특정 증가 수열 t₁, t₂, ...를 따라 함수 ''x''*를 추적하는 방법이다. 즉, ''x_i'' - ''x''*(''t_i'')가 ''i''가 무한대로 접근함에 따라 0에 접근하도록, ''x''*(''t_i'')에 충분히 근사한 ''x_i''를 계산한다. 그러면 ''x_i''는 (P)의 최적 해에 접근한다. 이를 위해 장벽 함수 b(x), 페널티 파라미터 ''t_i'' 결정 정책, (''P_i'')를 풀고 ''x_i''를 찾기 위한 뉴턴의 방법과 같은 무제한 최적화 솔버가 필요하다. 각 ''x_i''는 다음 문제 (''P_i+1'')를 풀기 위한 시작점으로 사용할 수 있다.^[7]^[8]^[3]

5. 2. 다항 시간 알고리즘

레니가^[7]와 곤자가^[8]는 특정 조건을 만족하는 경로 추적 방법이 다항 시간 안에 선형 계획법 문제를 해결할 수 있음을 증명했다. 이 방법은 다음 조건을 만족한다:

제약 조건 및 목표는 선형 함수이다.
장벽 함수는 로그 장벽 함수이다: b(x) := - sum''_j'' log(''-g_j''(''x'')).
페널티 매개변수 ''t''는 기하 급수적으로 업데이트된다. 즉, $t_{i+1} := \mu \cdot t_i$ 이며, 여기서 ''μ''는 상수이다 (이들은 $\mu = 1+0.001\cdot \sqrt{m}$ 을 사용했는데, 여기서 ''m''은 부등식 제약 조건의 수이다).
뉴턴의 방법을 솔버로 사용하며, ''t''의 각 단계마다 뉴턴의 단일 단계가 수행된다.

이 경우 ''x_i'' - ''x''*(''t_i'')의 차이는 최대 0.01을 유지하고, f(''x_i'') - f*는 최대 2*''m''/''t_i''임을 증명했다. 따라서 해의 정확도는 1/''t_i''에 비례한다. 즉, 정확도를 한 자리수 더 높이려면 ''t_i''를 2 (또는 다른 상수 인자)로 곱하면 충분하며, 이는 O(sqrt(''m'')) 뉴턴 단계를 필요로 한다. 각 뉴턴 단계는 O(''m n''²) 연산을 수행하므로, 총 복잡도는 정확도 자릿수에 대해 O(''m^3/2 n''²) 연산이다.

유리 네스테로프는 이 아이디어를 선형 계획법에서 비선형 계획법으로 확장했다. 그는 위 증명에 사용된 로그 장벽의 주요 속성이 유한 장벽 매개변수를 가진 자기 일치라는 점에 주목했다. 따라서, 실행 가능한 영역에 적합한 자기 일치 장벽 함수를 찾을 수 있다면, 다양한 종류의 볼록 프로그램들이 경로 추적 방법을 사용하여 다항 시간 내에 해결될 수 있다.^[3]

5. 3. 자기 일치 장벽 함수의 확장

유리 네스테로프는 로그 장벽 함수의 주요 속성인 자기 일치성을 이용하여 내부점법을 선형 계획법에서 비선형 계획법 문제로 확장했다.^[3] 그는 실행 가능한 영역에 적합한 자기 일치 장벽 함수를 찾을 수 있다면, 다양한 볼록 계획법 문제를 다항 시간 내에 해결할 수 있다고 보았다.^[3]

5. 4. 세부 사항

"표준 형식"의 볼록 최적화 문제 (P)는 다음과 같다.

> '''최소화 ''c''^T''x'' s.t. ''x'' in ''G'''''

여기서 ''G''는 볼록하고 닫혀 있으며, 유계라고 가정한다. (충분히 큰 ''R''에 대해 제약 조건 |''x''|≤''R''을 추가하여 쉽게 유계로 만들 수 있다).^[3]

내부점법을 사용하기 위해 ''G''에 대한 자기 일치 장벽이 필요하다. ''b''를 ''G''에 대한 ''M''-자기 일치 장벽이라고 하고, 여기서 ''M''≥1은 자기 일치 매개변수이다. ''G'' 내부의 모든 점 x에 대해 ''b''의 값, 기울기 및 헤세 행렬을 효율적으로 계산할 수 있다고 가정한다.

모든 ''t''>0에 대해, ''페널티 목적 함수'' '''f_t(x) := t''c''^T''x +'' b(''x'')'''를 정의한다. 최소화점의 경로는 '''x*(t) := arg min f_t(x)'''로 정의한다. 증가하는 수열 ''t_i''를 따라 이 경로를 근사하는데, 이 수열은 특정 비자명한 2단계 초기화 절차에 의해 초기화되며, 다음 규칙에 따라 업데이트된다:

t_{i+1} := \mu \cdot t_i

.

각 ''t_i''에 대해, ''f_ti''의 근사 최소값을 찾고 ''x_i''로 표기한다. 근사 최소값은 다음 "근접 조건"을 만족하도록 선택된다 (''L''은 ''경로 공차''):

>

\sqrt{[\nabla_x f_t(x_i)]^T [\nabla_x^2 f_t(x_i)]^{-1} [\nabla_x f_t(x_i)]} \leq L

.

''x_i''₊₁를 찾기 위해, ''x_i''에서 시작하여 감쇠 뉴턴 방법을 적용한다. 위의 "근접 관계"가 충족될 때까지 이 방법을 여러 단계 적용하며, 이 관계를 만족하는 첫 번째 점을 ''x_i''₊₁로 표기한다.^[3]

5. 5. 수렴성과 복잡도

내부점 방법의 수렴 속도는 모든 ''i''에 대해 다음 공식으로 주어진다.^[3]

: ''c''^T''x''_i - c* ≤ 2M|2M^영어/''t''₀ * μ^-i

\mu = \left(1+r/\sqrt{M}\right)

로 설정하면, ''x''_i에서 ''x''_i+1로 이동하는 데 필요한 뉴턴 단계 수는 ''r''과 ''L''에만 의존하는 고정된 수 이하이다. 특히, ''ε''-근사해(즉, ''c''^T''x'' - c* ≤ ''ε''인 ''G'' 내의 ''x''를 찾는 것)를 찾기 위해 필요한 총 뉴턴 단계 수는 다음과 같다.^[3]

: O(1) × sqrt|sqrt^영어(M) × ln|ln^영어(M|M^영어/(''t''₀ × ''ε'') + 1)

여기서 상수 계수 O(1)은 ''r''과 ''L''에만 의존한다. 2단계 초기화 절차에 필요한 뉴턴 단계 수는 다음과 같다.^[3]

: O(1) × sqrt|sqrt^영어(M) × ln|ln^영어(M|M^영어/(1 - π_x*f(''x'')) + 1) + O(1) × sqrt|sqrt^영어(M) × ln|ln^영어(MVar|MVar^영어_G(''c'')/''ε'' + 1)

여기서 상수 계수 O(1)은 ''r''과 ''L''에만 의존하며, Var_G(''c'') := max_x∈G ''c''^T''x'' - min_x∈G ''c''^T''x''이고, ''x''는 ''G'' 내부의 어떤 점이다. 전반적으로, ''ε''-근사해를 찾는 전체 뉴턴 복잡성은 다음을 초과하지 않는다.

: O(1) × sqrt|sqrt^영어(M) × ln|ln^영어(''V''/''ε'' + 1), 여기서 V는 문제에 의존하는 상수이다: ''V'' = Var|Var^영어_G(''c'')/(1 - π_x*f(''x''))

각 뉴턴 단계는 O(''n''³)의 산술 연산을 소요한다.

5. 6. 초기화: 1단계 방법

내부점 방법의 경로를 초기화하려면 실행 가능한 영역 ''G''의 상대적 내부의 점이 필요하다. 즉, ''G''가 부등식 ''g_i''(''x'') ≤ 0으로 정의된 경우, 1,...,''m''의 모든 ''i''에 대해 ''g_i''(''x'') < 0인 ''x''가 필요하다. 이러한 점이 없는 경우, '''1단계 방법'''을 사용하여 이를 찾아야 한다.^[4]

간단한 1단계 방법은 다음 볼록 프로그램을 푸는 것이다.

:최소화 s

:조건 ''g_i(x)'' ≤ ''s'' (for ''i'' = 1, ..., ''m'')

최적해를 x*, ''s''*로 나타낸다.

만약 ''s''* < 0이면 x*가 원래 문제의 내부점이고, 원래 문제를 푸는 "2단계"로 넘어갈 수 있다.
만약 ''s''* > 0이면 원래 프로그램은 실행 불가능하다는 것을 알 수 있다. 즉, 실행 가능한 영역이 비어 있다.
만약 ''s''* = 0이고 어떤 해 x*에 의해 도달되면, 문제는 실행 가능하지만 내부점이 없으며, 도달되지 않으면 문제는 실행 불가능하다.

이 프로그램의 경우 내부점을 얻는 것은 쉽다. 임의로 ''x'' = 0을 취하고 ''s''를 max(''f''₁(0),...,''f_m''(0))보다 큰 숫자로 취할 수 있다. 따라서 내부점 방법을 사용하여 해결할 수 있다. 그러나 실행 시간은 log(1/''s''*)에 비례한다. ''s''*가 0에 가까워질수록, 1단계 문제에 대한 정확한 해를 찾는 것이 점점 더 어려워지고, 따라서 원래 문제가 실행 가능한지 여부를 결정하는 것이 더 어려워진다.

5. 7. 실제 고려 사항

이론적으로 페널티 매개변수가

\mu = \left(1+r/\sqrt{M}\right)

의 속도로 증가한다고 가정할 때, 최악의 경우 필요한 뉴턴 단계 수는

O(\sqrt{M})

이다. 이론적으로 ''μ''가 2 이상으로 더 크면, 필요한 뉴턴 단계의 최악의 경우 수는

O(M)

이다. 그러나 실제로는 더 큰 ''μ''가 훨씬 더 빠른 수렴을 이끈다. 이러한 방법을 "장단계 방법"이라고 한다.^[3] 실제로는 ''μ''가 3과 100 사이인 경우, 제약 조건의 수에 관계없이 프로그램은 20-40 뉴턴 단계 내에 수렴한다(물론 각 뉴턴 단계의 실행 시간은 제약 조건의 수에 따라 증가한다). 이 범위 내에서 ''μ''의 정확한 값은 성능에 거의 영향을 미치지 않는다.^[4]

6. 프라이멀-듀얼 내부점 방법

프라이멀-듀얼 내부점 방법은 최적화 문제에서 해를 찾는 방법 중 하나이다. 이 방법은 원래 변수(프라이멀 변수)와 라그랑주 승수에서 영감을 얻은 쌍대 변수(듀얼 변수)를 함께 사용하여 최적해를 찾는다.^[9]^[10]

이 방법은 다음 세 가지 주요 개념을 기반으로 한다.

1. 로그 배리어 함수: 제약 조건을 만족하는 영역 안에서 해를 찾도록 돕는 함수이다.

2. 교란된 상보성 조건: 프라이멀 변수와 듀얼 변수 간의 관계를 나타내는 조건이다.

3. 뉴턴 방법: 최적해를 향해 반복적으로 나아가는 방법이다.

이러한 개념들을 활용하여 프라이멀-듀얼 내부점 방법은 효율적으로 최적해를 찾을 수 있다.

6. 1. 비선형 최적화 문제로의 확장

프라이멀-듀얼 방법은 제약 조건이 있는 비선형 최적화 문제에도 적용할 수 있다.^[9]^[10] 설명을 위해, 다음 부등식 제약 조건이 있는 비선형 최적화 문제를 고려한다.

\begin{aligned}\operatorname{minimize}\quad & f(x) \\\text{subject to}\quad&x \in \mathbb{R}^n,\\&c_i(x) \ge 0 \text{ for } i = 1, \ldots, m,\\\text{where}\quad & f : \mathbb{R}^{n} \to \mathbb{R},\ c_i : \mathbb{R}^{n} \to \mathbb{R}.\end{aligned}

이 문제는 제약 조건이 없는 목적 함수로 변환하여 해결할 수 있다. (1)과 관련된 로그 배리어 함수는 다음과 같다.

B(x,\mu) = f(x) - \mu \sum_{i=1}^m \log(c_i(x)).

여기서

\mu

는 작은 양의 스칼라("배리어 매개변수")이다.

\mu

가 0으로 수렴하면

B(x,\mu)

의 최소값은 (1)의 해로 수렴한다.

미분 가능한 함수

h : \mathbb{R}^n \to \mathbb{R}

의 기울기는

\nabla h

로 표시된다. 배리어 함수의 기울기는 다음과 같다.

\nabla B(x,\mu) = \nabla f(x) - \mu \sum_{i=1}^m \frac{1}{c_i(x)} \nabla c_i(x).

원래("프라이멀") 변수

x

외에 듀얼 변수

\lambda \in \mathbb{R} ^m

을 도입한다.

c_i(x) \lambda_i = \mu,\quad \forall i = 1, \ldots, m.

위 식 (4)는 KKT 조건에서 "상보적 완화"와 유사하여 "교란된 상보성" 조건이라고 불린다.

배리어 함수의 기울기가 0인

(x_\mu, \lambda_\mu)

를 찾는다. 식 (4)에서

1/c_i(x) = \lambda_i / \mu

를 (3)에 대입하면 기울기에 대한 다음 방정식을 얻는다.

\nabla B(x_\mu, \lambda_\mu) = \nabla f(x_\mu) - J(x_\mu)^T \lambda_\mu = 0,

여기서 행렬

J

는 제약 조건

c(x)

의 야코비안이다.

(5)의 직관은

f(x)

의 기울기가 제약 조건의 기울기에 의해 span되는 부분 공간에 있어야 한다는 것이다. 작은

\mu

를 갖는 "교란된 상보성" (4)는 해가 경계

c_i(x) = 0

근처에 있거나, 기울기

\nabla f

의 제약 조건 성분

c_i(x)

법선에 대한 투영이 거의 0이 되어야 한다는 조건으로 이해할 수 있다.

(p_x, p_\lambda)

를

(x, \lambda)

를 반복적으로 업데이트하기 위한 탐색 방향이라고 하자. (4)와 (5)에 뉴턴의 방법을 적용하면

(p_x, p_\lambda)

에 대한 다음 방정식을 얻는다.

\begin{pmatrix}H(x, \lambda) & -J(x)^T \\\operatorname{diag}(\lambda) J(x) & \operatorname{diag}(c(x))\end{pmatrix}\begin{pmatrix}p_x  \\p_\lambda\end{pmatrix}=\begin{pmatrix}

\nabla f(x) + J(x)^T \lambda \\

\mu 1 - \operatorname{diag}(c(x)) \lambda\end{pmatrix},

여기서

H

는

B(x, \mu)

의 헤세 행렬이고,

\operatorname{diag}(\lambda)

는

\lambda

의 대각 행렬이며,

\operatorname{diag}(c(x))

는

c(x)

의 대각 행렬이다.

(1), (4) 때문에 다음 조건이 각 단계에서 적용되어야 한다.

:

\lambda \ge 0

이는 적절한

\alpha

를 선택하여 수행할 수 있다.

:

(x,\lambda) \to (x + \alpha p_x, \lambda + \alpha p_\lambda).

6. 2. 로그 배리어 함수와 듀얼 변수

로그 배리어 함수를 사용하여 제약 조건이 없는 목적 함수를 정의한다. 원래 문제 (1)은 다음과 같이 정의된다.^[9]^[10]

:

\begin{aligned}\operatorname{minimize}\quad & f(x) \\\text{subject to}\quad&x \in \mathbb{R}^n,\\&c_i(x) \ge 0 \text{ for } i = 1, \ldots, m,\\\text{where}\quad & f : \mathbb{R}^{n} \to \mathbb{R},\ c_i : \mathbb{R}^{n} \to \mathbb{R}.\end{aligned}

이 문제는 로그 배리어 함수를 통해 제약 조건이 없는 문제로 변환된다.

:

B(x,\mu) = f(x) - \mu \sum_{i=1}^m \log(c_i(x)). \quad (2)

여기서

\mu

는 작은 양의 스칼라 ("배리어 매개변수")이다.

\mu

가 0으로 수렴하면

B(x,\mu)

의 최소값은 (1)의 해로 수렴한다.

라그랑주 승수에서 영감을 얻은 듀얼 변수

\lambda \in \mathbb{R} ^m

를 도입한다. 이 변수는 다음의 "교란된 상보성" 조건을 만족한다.

:

c_i(x) \lambda_i = \mu,\quad \forall i = 1, \ldots, m. \quad (4)

이 조건은 KKT 조건의 "상보적 완화"와 유사하다.

(4)에서

1/c_i(x) = \lambda_i / \mu

를 (3)에 대입하면, 배리어 함수의 기울기가 0이 되는 지점

(x_\mu, \lambda_\mu)

를 찾을 수 있다.

:

\nabla B(x_\mu, \lambda_\mu) = \nabla f(x_\mu) - J(x_\mu)^T \lambda_\mu = 0, \quad (5)

여기서

J

는 제약 조건

c(x)

의 야코비안이다. (5)는

f(x)

의 기울기가 제약 조건의 기울기에 의해 span되는 부분 공간에 있어야 함을 의미한다.

6. 3. 뉴턴 방법 적용

KKT 조건에서 "상보적 완화"와 유사한 "교란된 상보성" 조건 (4)과 배리어 함수의 기울기가 0이라는 조건 (5)을 결합하여 뉴턴의 방법을 적용한다.^[9]^[10]

(4)와 (5)에 뉴턴 방법을 적용하면 탐색 방향

(p_x, p_\lambda)

에 대한 다음 선형 시스템을 얻는다.

:

\begin{pmatrix}H(x, \lambda) & -J(x)^T \\\operatorname{diag}(\lambda) J(x) & \operatorname{diag}(c(x))\end{pmatrix}\begin{pmatrix}p_x  \\p_\lambda\end{pmatrix}=\begin{pmatrix}

\nabla f(x) + J(x)^T \lambda \\

\mu 1 - \operatorname{diag}(c(x)) \lambda\end{pmatrix},

여기서

H

는

B(x, \mu)

의 헤세 행렬이고,

\operatorname{diag}(\lambda)

는

\lambda

의 대각 행렬이며,

\operatorname{diag}(c(x))

는

c(x)

의 대각 행렬이다.

(1), (4) 식에 의해 다음 조건

:

\lambda \ge 0

을 각 단계에서 적용해야 한다. 이는 적절한

\alpha

를 선택하여 수행할 수 있다.

:

(x,\lambda) \to (x + \alpha p_x, \lambda + \alpha p_\lambda).

6. 4. 수렴 과정

주쌍대내점법(primal-dual interior point method)의 핵심은 각 반복 단계에서 듀얼 변수(

\lambda

)가 양수 값을 유지하도록 스텝 크기(

\alpha

)를 조절하는 것이다.^[9]^[10] 이 조건을 만족시키기 위해 적절한

\alpha

를 선택하여 프라이멀 변수(

x

)와 듀얼 변수(

\lambda

)를 업데이트한다.

:

(x,\lambda) \to (x + \alpha p_x, \lambda + \alpha p_\lambda)

이러한 업데이트 과정을 통해 프라이멀 변수와 듀얼 변수는 점차 최적해로 수렴해 간다.

7. 내부점 방법으로 해결 가능한 볼록 계획법 유형

내부점 방법으로 효율적으로 해결할 수 있는 볼록 계획법의 몇 가지 특수한 경우는 다음과 같다.^[3]

선형 계획법 (Linear Programs)
2차 제약 2차 계획법 (Quadratically Constrained Quadratic Programs, QCQP)
L_p 노름 근사 (L_p Norm Approximation)
기하 계획법 (Geometric Programs)
반정부호 계획법 (Semidefinite Programs, SDP)

7. 1. 선형 계획법 (Linear Programs)

선형 계획법은 내부점법으로 효율적으로 해결할 수 있는 가장 기본적인 유형의 볼록 계획법 문제이다. 다음과 같은 형태의 선형 계획법을 고려해 보자.

\begin{aligned}\operatorname{최소화}\quad & c^\top x \\\text{제약 조건}\quad& Ax \leq b.\end{aligned}.

로그 장벽 함수를 사용하여 경로 추적 방법을 적용할 수 있다. 다음과 같은 장벽을 사용한다.

b(x) := -\sum_{j=1}^m \ln(b_j - a_j^T x).

함수

b

는 파라미터 ''M''=''m'' (제약 조건의 수)을 갖는 자기 일치적이다. 따라서 경로 추적 방법에 필요한 뉴턴 단계 수는 O(''mn''²)이고, 총 실행 시간 복잡도는 O(''m''^3/2 ''n''²)이다.

7. 2. 2차 제약 2차 계획법 (Quadratically Constrained Quadratic Programs, QCQP)

다음과 같은 형태의 2차 제약 2차 계획법(QCQP)이 주어질 때:

:

\begin{aligned}\operatorname{minimize}\quad & d^\top x \\\text{subject to}\quad& f_j(x) := x^\top A_j x + b_j^\top x + c_j \leq 0 \quad \text{ for all } j = 1, \dots, m,\end{aligned}

여기서 모든 행렬 ''A_j''는 양의 반정부호 행렬이다.

다음 장벽을 사용하여 경로 추적 방법을 적용할 수 있다.

:

b(x) := -\sum_{j=1}^m \ln(-f_j(x)).

함수

b

는 매개변수 ''M''=''m''을 갖는 자기 일치 장벽이다. 뉴턴 복잡도는 O(''(m+n)n''²)이고, 총 실행 시간 복잡도는 O(''m''^1/2 (m+n) ''n''²)이다.

7. 3. Lp 노름 근사 (Lp Norm Approximation)

노름을 최소화하는 문제는 내부점법을 사용하여 해결할 수 있다.^[1]

다음과 같은 형태의 문제를 고려해 보자.

\begin{aligned}\operatorname{minimize}\quad & \sum_j |v_j - u_j^\top x|_p\end{aligned},

여기서 각

u_j

는 벡터이고, 각

v_j

는 스칼라 값이며,

|\cdot|_p

는

1< p < \infty

인 L_p 노름이다. 표준 형태로 변환한 후, 파라미터 ''M''=4''m''인 자기 일치 장벽을 사용하여 경로 추적 방법을 적용할 수 있다. 뉴턴 복잡도는 O(''(m+n)n''²)이고, 총 실행 시간 복잡도는 O(''m''^1/2 (m+n) ''n''²)이다.^[1]

7. 4. 기하 계획법 (Geometric Programs)

기하 계획법(Geometric Program)은 특정 형태의 비선형 계획법 문제로, 내부점 방법을 사용하여 해결할 수 있다. 다음은 기하 계획법 문제의 한 형태이다.

:

\begin{aligned}\operatorname{minimize}\quad & f_0(x) := \sum_{i=1}^k c_{i0} \exp(a_i^\top x) \\\text{subject to}\quad& f_j(x) := \sum_{i=1}^k c_{ij} \exp(a_i^\top x) \leq d_j \quad \text{ for all } j = 1, \dots, m.\end{aligned}

이 문제는 파라미터 2''k''+''m''을 갖는 자기 일치 장벽을 가지고 있다. 경로 추적 방법은 뉴턴 복잡도 O(''mk''²+''k''³+''n''³)과 총 복잡도 O((''k+m'')^1/2[''mk''²+''k''³+''n''³])을 가진다.

7. 5. 반정부호 계획법 (Semidefinite Programs, SDP)

내부점 방법은 반정부호 계획법을 푸는 데 사용될 수 있다.^[3]

8. 구현

IPOPT는 비선형 계획법 문제를 풀기 위한 오픈 소스 소프트웨어 패키지이다. C++와 포트란으로 작성되었지만, C, 자바, 파이썬, R 등 다른 프로그래밍 언어에서도 사용할 수 있는 인터페이스가 존재한다.^[1] 카네기 멜론 대학교의 Andreas Wächter와 Carl Laird가 개발했다.^[1]

IPOPT는 내부점 방법을 구현하며, 필터 라인 서치 방법을 사용하여 전역 수렴을 보장한다.^[1]

참조

_[1] 논문 Iterative solution of problems of linear and quadratic programming. https://zbmath.org/?[...]
_[2] 간행물 Proceedings of the sixteenth annual ACM symposium on Theory of computing – STOC '84
_[3] 서적 Interior point polynomial-time methods in convex programming https://citeseerx.is[...]
_[4] 서적 Convex Optimization Cambridge University Press
_[5] 논문 The interior-point revolution in optimization: History, recent developments, and lasting consequences
_[6] 논문 Interior-point methods
_[7] 논문 A polynomial-time algorithm, based on Newton's method, for linear programming https://doi.org/10.1[...] 1988-01-01
_[8] 간행물 An Algorithm for Solving Linear Programming Problems in O(n3L) Operations https://doi.org/10.1[...] Springer 2023-11-22
_[9] 논문 On the Implementation of a Primal-Dual Interior Point Method
_[10] 서적 Primal-Dual Interior-Point Methods SIAM

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com