타원체 방법

썸네일|오른쪽|그래프 예시
수학적 최적화에서 **타원체 방법**()은 볼록 집합 위에서 볼록 함수를 최소화하는 반복법이다. 타원체 방법은 매 단계마다 부피가 균일하게 감소하는 일련의 타원면들을 생성하여 볼록 함수의 최소값을 포함한다.

유리수 데이터를 가진 실행 가능한 선형 계획법 문제에 특화될 때, 타원체 방법은 입력 크기에 대해 다항식 단계 내에서 최적 해를 찾는 알고리즘이다.

## 역사
타원체 방법은 오랜 역사를 가지고 있다. 반복법으로서 초기 버전은 나움 Z. 쇼어에 의해 소개되었다. 1972년, 실제 볼록 최소화를 위한 근사 알고리즘이 아르카디 네미로프스키와 데이비드 B. 유딘(유딘)에 의해 연구되었다.

유리수 데이터를 가진 선형 계획법 문제를 푸는 알고리즘으로서 타원체 알고리즘은 레오니트 하치얀에 의해 연구되었다. 하치얀의 업적은 선형 프로그램의 다항 시간 해법을 증명한 것이다. 이것은 이론적인 관점에서 중요한 진전이었다. 당시 선형 문제를 푸는 표준 알고리즘은 단체법 (알고리즘)으로, 일반적으로 문제 크기에 선형적으로 비례하는 실행 시간을 가지지만, 문제 크기에 대해 지수적으로 비례하는 예시도 존재했다. 따라서 모든 경우에 대해 다항식으로 보장되는 알고리즘을 갖는 것은 이론적인 돌파구였다.

하치얀의 연구는 선형 프로그램을 푸는 알고리즘의 실행 시간이 다항식임을 처음으로 증명할 수 있음을 보여주었다. 그러나 실제로는 이 알고리즘은 상당히 느리고 실용적인 관심은 거의 없었지만, 훨씬 더 실용적인 용도로 판명된 후속 작업에 영감을 주었다. 특히, 내부점법인 카르마카르의 알고리즘은 실제적으로 타원체 방법보다 훨씬 빠르다. 카르마카르의 알고리즘은 최악의 경우에도 더 빠르다.

타원체 알고리즘은 계산 복잡도 이론가들이 문제의 차원과 데이터의 크기에 따라 달라지지만 행 수에는 의존하지 않는 (최악의 경우) 경계를 달성할 수 있도록 했기 때문에 수년 동안 조합 최적화 이론에서 중요하게 유지되었다. 21세기에 들어서야 유사한 복잡도 특성을 가진 내부점 알고리즘이 등장했다.

## 설명

볼록 최소화 문제는 다음 요소들로 구성된다.

* 벡터 x (n 변수 포함)에 대해 최소화할 볼록 함수 f_0(x): \mathbb{R}^n \to \mathbb{R};
* 함수 f_i가 볼록인 형식 f_i(x) \leqslant 0의 볼록 부등식 제약 조건; 이 제약 조건들은 볼록 집합 Q를 정의한다.
* 형식 h_i(x) = 0의 선형 등식 제약 조건.

또한, 최소화자 x^*를 포함하는 초기 타원면 \mathcal{E}^{(0)} \subset \mathbb{R}^n이 다음과 같이 정의된다.

:\mathcal{E}^{(0)} = \left \{z \in \mathbb{R}^n \ : \ (z - x_0)^T P_{(0)}^{-1} (z-x_0) \leqslant 1   \right \}

여기서 P_{(0)} \succ 0이고 x_0는 \mathcal{E}의 중심이다.

마지막으로, 볼록 집합 Q에 대한 분리 오라클의 존재가 필요하다. 점 x\in  \mathbb{R}^n이 주어졌을 때, 오라클은 다음 두 가지 답변 중 하나를 반환해야 한다.

* "점 x는 Q에 있다", 또는 -
* "점 x는 Q에 없으며, 또한 x를 Q로부터 분리하는 초평면이 여기 있다", 즉 모든 y\in Q에 대해 c\cdot x 인 벡터 c.
타원체 방법의 결과는 다음 중 하나이다:

* 다면체 Q 내의 임의의 점 (즉, 임의의 실행 가능한 점), 또는 -
* Q가 비어 있음을 증명.

어디에서나 0인 함수의 부등식 제약 최소화는 단순히 실행 가능한 점을 식별하는 문제에 해당한다. 선형 계획법 문제는 선형 실행 가능성 문제(즉, 일부 선형 부등식 및 등식 제약 조건 하에서 0 함수를 최소화)로 환원될 수 있음이 밝혀졌다. 이를 수행하는 한 가지 방법은 원시 및 이중 선형 프로그램을 하나의 프로그램으로 결합하고, 원시 해의 값이 이중 해의 값보다 나쁘지 않다는 추가 (선형) 제약 조건을 추가하는 것이다. 다른 방법은 선형 프로그램의 목표를 추가 제약 조건으로 처리하고 이진 탐색을 사용하여 최적 값을 찾는 것이다.

## 제약 없는 최소화
알고리즘의 k번째 반복에서, 우리는 타원체의 중심에 있는 점 x^{(k)}를 가지고 있다.

:\mathcal{E}^{(k)} = \left \{x \in \mathbb{R}^n \ : \ \left (x-x^{(k)} \right )^T P_{(k)}^{-1} \left (x-x^{(k)} \right ) \leqslant 1   \right \}.

우리는 절단 평면 오라클에 질의하여 다음을 만족하는 벡터 g^{(k+1)} \in \mathbb{R}^n을 얻는다.

:g^{(k+1)T} \left (x^* - x^{(k)} \right ) \leqslant 0.

그러므로 우리는 다음을 결론짓는다.

:x^* \in \mathcal{E}^{(k)} \cap \left \{z \ : \ g^{(k+1)T} \left (z - x^{(k)} \right ) \leqslant 0 \right \}.

우리는 \mathcal{E}^{(k+1)}을 위에서 설명한 반타원체를 포함하는 최소 부피의 타원체로 설정하고 x^{(k+1)}를 계산한다. 업데이트는 다음과 같이 주어진다.

:\begin{align}
x^{(k+1)} &= x^{(k)} - \frac{1}{n+1} P_{(k)} \tilde{g}^{(k+1)} \\
P_{(k+1)} &= \frac{n^2}{n^2-1} \left(P_{(k)} - \frac{2}{n+1} P_{(k)} \tilde{g}^{(k+1)} \tilde{g}^{(k+1)T} P_{(k)} \right )
\end{align}

여기서

:\tilde{g}^{(k+1)} = \left (\frac{1}{\sqrt{g^{(k+1)T} P_{(k)} g^{(k+1)}}} \right )g^{(k+1)}.

정지 기준은 다음 속성에 의해 주어진다.

:\sqrt{g^{(k)T}P_{(k)}g^{(k)}} \leqslant \epsilon \quad  \Rightarrow \quad f (x^{(k)} ) - f \left(x^* \right ) \leqslant \epsilon.

## 부등식 제약 최소화
제약 최소화를 위한 알고리즘의 k번째 반복에서, 우리는 이전과 같이 타원체 \mathcal{E}^{(k)}의 중심에 있는 점 x^{(k)}를 가지고 있다. 우리는 또한 현재까지의 실행 가능한 반복의 가장 작은 목적 함수 값을 기록하는 f_{\rm{best}}^{(k)} 값 목록을 유지해야 한다. 점 x^{(k)}가 실행 가능한지에 따라 다음 두 작업 중 하나를 수행한다:

* x^{(k)}가 실행 가능하면, 다음을 만족하는 부분 기울기 g_0를 선택하여 제약 없는 경우와 본질적으로 동일한 업데이트를 수행한다.

::g_0^T  (x^*-x^{(k)}  ) + f_0 (x^{(k)}  ) - f_{\rm{best}}^{(k)} \leqslant 0

* x^{(k)}가 실행 불가능하고 j번째 제약 조건을 위반하면, 실행 가능성 절단으로 타원체를 업데이트한다. 우리의 실행 가능성 절단은 모든 실행 가능한 z에 대해 다음을 만족해야 하는 f_j의 부분 기울기 g_j일 수 있다.

::g_j^T  (z-x^{(k)} ) + f_j (x^{(k)}  )\leqslant 0

## 볼록 프로그램에서의 성능
### 이론적 실행 시간 복잡도 보장
실수 RAM 모델에서 타원체 방법의 실행 시간 복잡도 보장은 다음 정리에 의해 주어진다.

형태의 볼록 최적화 문제군을 고려해보자: **f(x)를 최소화하되, x는 G 안에 있어야 한다**, 여기서 f는 볼록 함수이고 G는 볼록 집합(유클리드 공간 Rn의 부분 집합)이다. 이 문제군 내의 각 문제 p는 데이터 벡터 Data(p)로 표현되는데, 예를 들어 함수 f와 실행 가능 영역 G를 나타내는 행렬 및 벡터의 실수 값 계수들이다. 문제 p의 크기, Size(p),는 Data(p)의 요소(실수) 수로 정의된다. 다음 가정이 필요하다:

# G (실행 가능 영역)는:
#* 경계가 있다;
#* 비어 있지 않은 내부를 가진다 (따라서 엄격하게 실행 가능한 점이 있다);
# Data(p)가 주어졌을 때, poly(Size(p)) 산술 연산을 사용하여 다음을 계산할 수 있다:
#* G를 포함하는 타원체;
#* G의 부피에 대한 하한 'MinVol(p)>0'.
# Data(p)와 Rn의 점 x가 주어졌을 때, poly(Size(p)) 산술 연산을 사용하여 다음을 계산할 수 있다:
#* G에 대한 분리 오라클 (즉: x가 G에 있음을 단언하거나, x를 G로부터 분리하는 초평면을 반환한다).
#* f에 대한 1차 오라클 (즉: f(x)의 값과 부분 기울기 f**(x)를 계산한다).
이러한 가정 하에, 타원체 방법은 "R-다항식"이다. 이는 모든 문제 인스턴스 ''p''와 모든 근사 비율 ''ε''>0에 대해 다음을 만족하는 해 x를 찾는 방법이 존재한다는 것을 의미한다:
<blockquote><math>f(x) - \min_G f \leq \varepsilon\cdot  [\max_G f - \min_G f] </math>,</blockquote>
다음 산술 연산 수를 사용하여:
<blockquote><math>Poly(Size(p))\cdot \ln\left(\frac{V(p)}{\epsilon}\right) </math></blockquote>
여기서 ''V''(''p'')는 데이터에 의존하는 양이다. 직관적으로, 이는 각 추가 정확도 자리에 필요한 연산 수가 Size(''p'')에 대해 다항식이라는 것을 의미한다. 타원체 방법의 경우:
<blockquote><math>V(p) = \left[\frac{Vol(\text{initial ellipsoid})}{Vol(G)}\right]^{1/n} \leq\left[\frac{Vol(\text{initial ellipsoid})}{MinVol(p)}\right]^{1/n} </math>.</blockquote>
타원체 방법은 최대 <math>2(n-1)n\cdot \ln\left(\frac{V(p)}{\epsilon}\right) </math> 단계를 필요로 하며, 각 단계는 Poly(Size(p)) 산술 연산을 필요로 한다.

=== 실제 성능 ===
타원체 방법은 평면 위치 문제와 같은 저차원 문제에서 사용되며, 여기서 [[수치 안정성|수치적으로 안정적]]이다. 네미로프스키와 벤-탈은 변수 수가 최대 20-30개일 때 효율적이라고 말한다. 이는 제약 조건의 수가 수천 개라도 마찬가지인데, 반복 횟수가 제약 조건의 수에 의존하지 않기 때문이다. 그러나 변수가 많은 문제에서는 반복 횟수가 O(''n''<sup>2</sup>)로 증가하므로 타원체 방법은 매우 비효율적이다.

심지어 "작은" 크기의 문제에서도 수치적 불안정성과 실제적인 성능 저하를 겪는다.

=== 이론적 중요성 ===
타원체 방법은 [[조합 최적화]]에서 중요한 이론적 기법이다. [[계산 복잡도 이론]]에서 타원체 알고리즘은 복잡성이 열의 수와 계수의 디지털 크기에 따라 달라지지만 행의 수에는 의존하지 않기 때문에 매력적이다.

타원체 방법을 사용하여 많은 [[볼록 집합에서의 알고리즘 문제]]가 다항 시간 동치임을 보일 수 있다.

== 선형 프로그램에서의 성능 ==
[[레오니트 하치얀]]은 타원체 방법을 [[선형 계획법]]의 특별한 경우에 적용했다: **cTx를 최소화하되, Ax ≤ b를 만족해야 한다**, 여기서 A,b,c의 모든 계수는 유리수이다. 그는 선형 프로그램이 다항 시간 안에 해결될 수 있음을 보여주었다. 다음은 하치얀 정리의 개요이다.

**1단계: 최적화를 탐색으로 축소**. [[선형 계획법 쌍대성]] 정리는 위의 최소화 문제를 탐색 문제로 축소할 수 있음을 말한다: **Ax ≤ b ; ATy = c ; y ≤ 0 ; cTx=bTy를 만족하는 x,y를 찾아라.** 첫 번째 문제는 두 번째 문제가 해결 가능할 때만 해결 가능하다. 문제가 해결 가능할 경우, 두 번째 문제 해의 ''x''-성분은 첫 번째 문제의 최적 해이다. 따라서 지금부터는 다음 문제를 해결해야 한다고 가정할 수 있다: **Rz ≤ r을 만족하는 z ≥ 0을 찾아라**. 모든 유리수 계수를 공통 분모로 곱하여 모든 계수가 정수라고 가정할 수 있다.

**2단계: 탐색을 실행 가능성 확인으로 축소**. 문제 **Rz ≤ r을 만족하는 z ≥ 0을 찾아라**는 이진 결정 문제로 축소될 수 있다: "**Rz ≤ r을 만족하는 z ≥ 0이 존재하는가?**". 이는 다음과 같이 수행될 수 있다. 결정 문제에 대한 답이 "아니오"이면, 탐색 문제에 대한 답은 "없음"이고, 우리는 완료된다. 그렇지 않으면, 첫 번째 부등식 제약 조건 ''R<sub>1</sub>z'' ≤ ''r<sub>1</sub>''를 취한다. 이를 등식 ''R<sub>1</sub>z'' = ''r<sub>1</sub>''로 바꾸고, 결정 문제를 다시 적용한다. 답이 "예"이면 등식을 유지하고, 답이 "아니오"이면 부등식이 불필요하다는 의미이므로 제거할 수 있다. 그런 다음 다음 부등식 제약 조건으로 진행한다. 각 제약 조건에 대해 등식으로 변환하거나 제거한다. 마지막으로, 등식 제약 조건만 남게 되며, 이는 선형 방정식 시스템을 해결하는 어떤 방법으로도 해결할 수 있다.

**3단계**: 결정 문제는 다른 최적화 문제로 축소될 수 있다. 잔여 함수 f(z) := max[(Rz)<sub>1</sub>-r<sub>1</sub>, (Rz)<sub>2</sub>-r<sub>2</sub>, (Rz)<sub>3</sub>-r<sub>3</sub>,...]를 정의한다. 분명히, ''f''(''z'')≤0은 ''Rz'' ≤ ''r''일 때만 성립한다. 따라서 결정 문제를 해결하려면 최소화 문제 min<sub>''z''</sub> ''f''(''z'')를 해결하는 것으로 충분하다. 함수 ''f''는 볼록하다 (선형 함수들의 최댓값이다). 최소값을 ''f''*로 나타낸다. 그러면 결정 문제에 대한 답은 f*≤0일 때만 "예"이다.

**4단계**: 최적화 문제 min<sub>''z''</sub> ''f''(''z'')에서, ''z''는 문제 데이터의 비트 길이인 ''L''에 대해 변의 길이가 2''<sup>L</sup>''인 상자 안에 있다고 가정할 수 있다. 따라서 우리는 유계 볼록 프로그램을 가지며, 이는 타원체 방법으로 ''L''에 대한 다항식 시간에 임의의 정확도 ε까지 해결할 수 있다.

**5단계**: 만약 f*>0이면, f*>2<sup>-poly(L)</sup>이 어떤 다항식에 대해 성립함을 증명할 수 있다. 따라서 정확도 ε=2<sup>-poly(L)</sup>을 선택할 수 있다. 그러면 타원체 방법으로 찾은 ε-근사 해는 f*>0일 때만 양수이고, 이는 결정 문제가 해결 불가능할 때만 성립한다.

== 변형 ==
타원체 방법은 각 단계에서 어떤 절단면이 사용되는지에 따라 여러 변형이 있다.

=== 다양한 절단 ===
**중앙 절단 타원체 방법**에서, 절단은 항상 현재 타원체의 중심을 통과한다. 입력은 유리수 ''ε''>0, **약한 분리 오라클**에 의해 주어진 볼록체 ''K'', 그리고 S(0,''R'') (원점 주위 반지름 R의 구)이 ''K''를 포함하는 숫자 ''R''이다. 출력은 다음 중 하나이다:

* (a) K에서 최대 ''ε'' 거리 내에 있는 벡터, 또는 --
* (b) 타원체 E(**A**,**a**)가 ''K''를 포함하고 E(**A**,**a**)의 부피가 최대 ''ε''인 양의 정부호 행렬 **A**와 점 **a**.

단계 수는 <math>N := \lceil 5n \log(1/\epsilon) + 5n^2 \log(2R)\rceil</math>이고, 필요한 정확도 자릿수는 ''p'' := 8''N''이며, 분리 오라클의 필요한 정확도는 ''d'' := 2<sup>−''p''</sup>이다.

**깊은 절단 타원체 방법**에서, 절단은 각 단계에서 타원체의 절반 이상을 제거한다. 이것은 ''K''가 비어 있음을 더 빨리 발견하게 한다. 그러나 ''K''가 비어 있지 않을 때는 중앙 절단 방법이 실행 가능한 점을 더 빨리 찾는 예시도 있다. 깊은 절단 사용은 실행 시간의 차수에는 영향을 미치지 않는다.

**얕은 절단 타원체 방법**에서, 절단은 각 단계에서 타원체의 절반 미만을 제거한다. 이 변형은 실제로는 그다지 유용하지 않지만, 이론적 중요성을 지닌다: 다른 변형으로는 도출할 수 없는 결과를 증명할 수 있게 한다. 입력은 유리수 ''ε''>0, **얕은 분리 오라클**에 의해 주어진 볼록체 ''K'', 그리고 S(0,''R'')이 ''K''를 포함하는 숫자 ''R''이다. 출력은 양의 정부호 행렬 **A**와 점 **a**로, 다음 중 하나를 만족한다:

* (a) 타원체 E(**A**,**a**)가 오라클에 의해 "고난"으로 선언되었거나, 또는 -
* (b) ''K''가 E(**A**,**a**)에 포함되고 E(**A**,**a**)의 부피가 최대 ''ε''이다.

단계 수는 <math>N := \lceil 5n(n+1)^2 \log(1/\epsilon) + 5n^2(n+1)^2 \log(2R) + \log(n+1)\rceil</math>이고, 필요한 정확도 자릿수는 ''p'' := 8''N''이다.

=== 다른 타원체 ===
또한 [[외접원|외접 타원체]]와 [[내접 도형|내접 타원체]] 방법 사이에도 구별이 있다.

* **외접 타원체 방법**에서는 각 반복에서 이전 타원체의 남은 부분을 ''포함하는'' ''가장 작은'' 부피의 타원체를 찾는다. 이 방법은 유딘(Yudin)과 네미로프스키(Nemirovskii)에 의해 개발되었다.
* **내접 타원체 방법*'에서는 각 반복에서 이전 타원체의 남은 부분에 *포함되는* 가장 큰 부피의 타원체를 찾는다. 이 방법은 타라소프(Tarasov), 하치얀(Khachian), 에를리히(Erlikh)에 의해 개발되었다.
이 방법들은 실행 시간 복잡도(아래에서 n은 변수의 수이고 엡실론은 정확도)에서 차이가 있다:

* 외접 방법은 <math>O(n^2) \ln \frac{1}{\epsilon} </math>번의 반복을 필요로 하며, 각 반복은 분리 초평면을 찾고 새로운 외접 타원체를 찾는 것으로 구성된다. 외접 타원체를 찾는 데는 <math>O(n^2) </math> 시간이 필요하다.
* 내접 방법은 <math>O(n) \ln \frac{1}{\epsilon} </math>번의 반복을 필요로 하며, 각 반복은 분리 초평면을 찾고 새로운 내접 타원체를 찾는 것으로 구성된다. 내접 타원체를 찾는 데는 어떤 작은 <math>\delta>0 </math>에 대해 <math>O(n^{3.5+\delta}) </math> 시간이 필요하다.

이 방법들의 상대적 효율성은 분리 초평면을 찾는 데 필요한 시간에 따라 달라지며, 이는 응용 분야에 따라 다르다: 실행 시간이 <math>O(n^{t}) </math>이고 <math>t\leq 2.5 </math>이면 외접 방법이 더 효율적이지만, <math>t> 2.5 </math>이면 내접 방법이 더 효율적이다.

== 관련 방법 ==
* [[무게 중심 방법]]은 개념적으로 더 간단한 방법이며, 더 적은 단계를 필요로 한다. 그러나 각 단계는 현재 실행 가능한 다면체의 무게 중심을 계산해야 하므로 계산 비용이 많이 든다.
* [[내부점법]] 또한 볼록 최적화 문제를 다항 시간 내에 해결할 수 있지만, 실제 성능은 타원체 방법보다 훨씬 우수하다.

== 내용주 ==
<references/>

== 더 읽어보기 ==
* Dmitris Alevras and Manfred W. Padberg, Linear Optimization and Extensions: Problems and Extensions, Universitext, Springer-Verlag, 2001. (Padberg의 문제와 해법.)
* V. Chandru and M.R.Rao, Linear Programming, Chapter 31 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 31-1 to 31-37.
* V. Chandru and M.R.Rao, Integer Programming, Chapter 32 in Algorithms and Theory of Computation Handbook, edited by M.J.Atallah, CRC Press 1999, 32-1 to 32-45.
* [[조지 B. 단치히|George B. Dantzig]] and Mukund N. Thapa. 1997. Linear programming 1: Introduction. Springer-Verlag.
* [[조지 B. 단치히|George B. Dantzig]] and Mukund N. Thapa. 2003. Linear Programming 2: Theory and Extensions. Springer-Verlag.
* [[로바스 라슬로|L. Lovász]]: An Algorithmic Theory of Numbers, Graphs, and Convexity, CBMS-NSF Regional Conference Series in Applied Mathematics 50, SIAM, Philadelphia, Pennsylvania, 1986
* Kattta G. Murty, Linear Programming, Wiley, 1983.
* [[만프레드 W. 파드버그|M. Padberg]], Linear Optimization and Extensions, Second Edition, Springer-Verlag, 1999.
* [[크리스토스 H. 파파디미트리우|Christos H. Papadimitriou]] and Kenneth Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Corrected republication with a new preface, Dover.
* [[알렉산더 슈리버|Alexander Schrijver]], Theory of Linear and Integer Programming*. John Wiley & sons, 1998, 

## 외부 링크
* EE364b, 스탠퍼드 대학교 강의 홈페이지

분류:조합 최적화
분류:선형 계획법
분류:볼록 최적화