타원체법

수학적 최적화에서 타원체 방법은 볼록함수를 최소화하기 위한 반복적인 방법이다. 타원형 방법은 합리적인 데이터로 실현 가능한 선형 최적화 문제를 해결하는 데 특화된 경우 입력 크기에서 다항식인 여러 단계에서 최적의 솔루션을 찾는 알고리즘이다.

타원체 방법은 모든 단계에서 부피가 균일하게 감소하여 볼록함수의 미니마이저를 둘러싸는 일련의 타원체를 생성한다.

역사

타원체 방법은 긴 역사를 가지고 있다. 반복적인 방법으로 Naum Z가 예비 버전을 도입했다. 쇼어. 1972년 아르카디 네미로프스키와 데이비드 B에 의해 실제 볼록 최소화용 근사 알고리즘이 연구되었다. 유딘(주딘). 이성적인 데이터로 선형 프로그래밍 문제를 해결하기 위한 알고리즘으로서 타원형 알고리즘은 레오니드 카치얀에 의해 연구되었다. 카치얀의 업적은 선형 프로그램의 다항식 시간 해결 가능성을 증명하는 것이었다. 이는 이론적 관점에서 주목할 만한 조치였다. 당시 선형 문제를 해결하기 위한 표준 알고리즘은 simplex 알고리즘으로, 일반적으로 문제의 크기에서는 선형이지만, 문제의 크기에서는 지수적인 예가 존재하는 런타임을 가지고 있다. 그런 만큼 모든 경우에 다항식이 보장되는 알고리즘을 갖는 것은 이론적 돌파구처럼 보였다.

카치얀의 연구는 처음으로, 런타임이 다항식이라고 증명될 수 있는 선형 프로그램을 푸는 알고리즘이 있을 수 있다는 것을 보여주었다. 그러나 실제로 알고리즘은 훨씬 더 실용적으로 밝혀진 후기 작업에 대한 영감을 제공했지만 상당히 느리고 실질적인 관심은 거의 없다. 구체적으로는 인테리어 포인트 방식인 카르마르카의 알고리즘이 실제 타원체 방식보다 훨씬 빠르다. 카르마르카의 알고리즘도 최악의 경우 더 빠르다.

타원형 알고리즘은 복잡성 이론가들이 문제의 치수 및 데이터의 크기에 따라 달라지는 (최악의 경우) 한계를 달성할 수 있게 해주지만 행의 개수에 따라 달라지지 않기 때문에 여러 해 동안 결합 최적화 이론에서 중요한 것으로 남아 있었다.^[1][2][3][4] 21세기에 들어서야 유사한 복잡성을 가진 내부 지점 알고리즘이 나타났다.^{[citation needed]}

설명

볼록 최소화 문제는 다음과 같은 성분으로 구성된다.

• 볼록 함수 $f{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}x}$)${\displaystyle }$: ${\displaystyle R\mathbb{}}$ n${\displaystyle {}^{}}$→ R ${\$에 대해 벡터 $x{\displaystyle }$ ${\displaysty x}($n 변수 포함)를 통해 최소화할 것$$;
• ${\displaystyle \mathrm{f}}$ ${\displaystyle i_{}}$( ${\displaystyle x}$) ${\displaystyle ⩽}$ 0 ${\displaystyle f_{i}(x)\leqslant 0}$ 형식의 볼록불평등 제약조건$,$ 여기서 ${\displaystyle {함수}_{}}$ $f{\displaystyle {}_{}}$ i ${\$는 볼록 집합 Q ${\displaysty Q}$를 정의한다$.$
• $h{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle 0}$ ${\displaystyle h_{i}(x)=0}$ 형식의 선형 동등 제약 조건$.$

${\displaystyle {\mathrm{또한}}^{}}$ 초기 타원체 $E{\displaystyle {\mathcal{}}^{}}$( 0${\displaystyle {}^{}}$) ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {\mathbb{}}^{}}$ ${\$이(가) 제공된다.

${\displaystyle {\mathcal{E}^{{0}=\좌측\{z\in \mathb {R}^{n}\\ (z-x_{0})^{{0}^{{}}}^{{}}}}}}}{}}}}}}}}}}T}P_{(0)}^{-1}(z-x_{0})\leqslant 1\right\}}}$

미니마이저 $∗{\$ x$^{*}$를 포함하는$$$여기$서 ${\displaystyle {\mathrm{P}}_{}}$ (${\displaystyle {}_{}}$0${\displaystyle {}_{}}$) ${\displaystyle {}_{}}$ 0 ${\displaystyle P_{0}\such 0}$ 및$$ $x{\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$ ${\$는 $E{\displaystyle \mathcal{}}$ ${\$ {$E}}$의 중심이다$.$

마지막으로 볼록 세트 $Q{\displaystyle }$ ${\displaystyle Q}$에 대한 절단면 오라클(분리 오라클이라고도 함$).$ 포인트 $x{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle {}^{}}$ ${\$ x$\in \mathb{R}$^{$n}}}$을$($를) 고려할 때 오라클은 다음 두 가지 대답 중 하나를 반환해야 한다.^[5]

• "$포인트{\displaystyle }$ x ${\displaystyle x}$은(는) $Q{\displaystyle }$ ${\displaystyle Q}$ "$$ 또는 -
• "그 포인트={\displaystyle x}가 아닌 Q{\displaystyle Q}에 있으며, 여기에 구분 초평면){\displaystyle x}Q{\displaystyle Q부터}", 즉 벡터 c{\displaystyle c}가 c⋅ x<>모든 y∈ Q{\displaystyle y\i을 요리⋅는 y{\displaystyle c\cdot x<, c\cdot y}.nQ}.

절단면 신탁의 한 예는 f의 하위 g에 의해 주어진다.^{[clarification needed]}

선형 프로그래밍에 적용

선형 프로그래밍의 맥락에서 $제약조건$은 모두 선형이며 Q ${\displaystyle$ Q$}$은 볼록$$ 폴리토프다. 그러면 분리 오라클은 다음과 같이 쉽게 구현할 수 있다.^[5] 제약 조건 $Q{\displaystyle }$=${\displaystyle }${ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle \le }$ ${\displaystyle b\}}$ ${\displaystyle$ Q$=\{x Ax\leq$ b$\}$과(와$$) 점 $x{\displaystyle }$∈ ${\displaystyle {}^{}}$ ${\$을(를) 고려할 때$,$ 오라클은 A ${\displaystyle x}$ ${\displaystyty Ax$

• 결과가 최대 $b{\displaystyle }$ ${\displaystyle b}$인 경우$,$ x ${\displaystyle x}$이(가) $Q{\displaystyle }$ ${\displaystyle Q$
• 그렇지 않으면 $적어도{\displaystyle }$ A의 행 $c{\displaystyle }$ ${\displaystyle$ $c$$}$이(가) 하나 있으며, c ${\displaystyle \cdot }$ x ${\displaystyle$ c$}$이(가) $b{\displaystyle }$ ${\displaystyle b}$의 해당 값보다 크며$$$,$ 이 $행{\displaystyle }$ c ${\displaysty c}$은 분리 하이퍼 평면을 제공한다.

이 신탁은 제약조건 수가 다항식인 한 다항식 시간에 실행된다. 일부 선형 최적화 문제에서는 제약조건 수가 기하급수적이더라도 다항식 시간에 작동하는 사용자 정의 분리 오라클을 작성할 수 있다. 두 가지 예는 다음과 같다.^[6]

• 최소 비용 수목 문제: 가중 지시 그래프와 그 안에 정점 r이 있는 경우, r에서 다른 정점으로 향하는 방향 경로를 포함하는 최소 비용의 하위 그래프를 찾으십시오. 문제는 정점의 각 부분집합에 대한 제약이 있는 LP로 제시될 수 있는데, 이것은 기하급수적인 제약조건 수입니다. 그러나 분리 오라클은 최소 절단 절차의 n-1 애플리케이션을 사용하여 구현할 수 있다.
• 최대 독립 집합 문제. 홀수 길이 사이클마다 제약을 받는 LP로 근사치를 구할 수 있다. 기하급수적으로 많은 사이클이 있지만, 최소 길이의 홀수 사이클만 찾아도 다항식 시간에 작동하는 분리 오라클을 구현할 수 있다.

타원체 방법의 출력은 다음과 같다.

• 폴리토프 $Q{\displaystyle }$ ${\displaystyle Q}$의 임의의 점(즉, 실현 가능한 모든 점) 또는 -
• $Q{\displaystyle }$ ${\displaystyle Q}$이(가) 비어 있다는$$ 증거.

어디에나 0인 함수의 불평등 제한적 최소화는 단순히 실현 가능한 지점을 식별하는 문제와 일치한다. 선형 프로그래밍 문제는 선형적 타당성 문제(예: 일부 선형 불평등과 평등 제약에 따른 영함수 최소화)로 축소될 수 있는 것으로 나타났다. 이를 위한 한 가지 방법은 원시 선형 프로그램과 이중 선형 프로그램을 함께 결합하고, 원시 용액의 가치가 이중 용액의 가치보다 나쁘지 않다는 추가(선형) 제약조건을 추가하는 것이다. 또 다른 방법은 선형 프로그램의 목적을 추가적인 제약조건으로 취급하고, 최적의 값을 찾기 위해 이진 검색을 사용하는 것이다.^{[citation needed]}

제약 없는 최소화

알고리즘의 k-th 반복에서 타원체 중심에 점$$ $x{\displaystyle {}^{}}$( $){\$가 있다.

${\displaystyle {\mathcal{E}^{{(k)}=\좌측\{x\in \mathb {R}^{n}\\\\좌측(x-x^{(k)\우측)^{T}P_{(k)^{-1}\왼쪽(x-x^{(k)}\오른쪽)\leqslant 1\right\}}$

벡터 $g{\displaystyle {}^{(k}}$+ ${\displaystyle 1^{}}$) ${\displaystyle {}^{}}$ ${\displaystyle {}^{}}$ ${\displaystyle {\mathbb{}}^{}}$ ${\$ g$^{(k+1)}\in \mathb {R}^{n}}$을(를) 얻기 위해 절단면 오라클을 쿼리한다.

${\displaystyle g^{(k+1)T}\왼쪽(x^{*}-x^{(k)}\오른쪽)\leqslant 0.}$

그러므로 우리는 다음과 같이 결론짓는다.

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

${\displaystyle E^{}}$ (k +$){\$을(를) 위에 설명한 하프엘립소이드를 포함하는 최소 볼륨의 타원체로 설정하고$$ $x{\displaystyle {}^{}}$(${\displaystyle {\mathrm{k}}^{}}$+ 1$){\$ x$^{(k+1)}$을(를) 계산한다$.$ 업데이트는 다음에 의해 제공됨

${\displaystyle{\begin}x^{(k+1)}&=x^{(k)-{\frac {1}{n+1}{n+1}{{{n+1}{\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{aligned}}}$

어디에

${\displaystyle {\tilde{g}^{(k+1)}=\좌측({\frac {1}{\sqrt{g^{(k+1)T_{(k)^{(k+1)}}}}}{(k)g^{(k+1)}}}}}.$

정지기준은 다음과 같은 속성에 의해 제시된다.

${\displaystyle {\sqrt{(k)T}P_{{(k)}g^{}}}}\leqslant \epslant \epsilon \quad \quad f\f\(x^{(k)\right)-f\f(x^{*\rig)\leqslant \epsilon.}$

불평등 구속적 최소화

제한적 최소화를 위한 알고리즘의 k번째 반복에서 우리는 전과 같이$$ 타원체 $E{\displaystyle {\mathcal{}}^{}}$( ${\displaystyle k^{}}$${\displaystyle {}^{}}$$){\$( k $){\$의 중심에$$ 점 $x{\displaystyle {}^{}}$ ${\displaystyle {(}^{}}$k$)$가 있다. 또한 우리는 지금까지 실현 가능한 반복의 최소 객관적 값을$$ $기록$하기 ${\displaystyle {위해\mathrm{}}_{}^{}}$ ${\displaystyle {\mathrm{f}}_{}^{}}$ ${\displaystyle {\mathrm{b}}_{}^{}}$ ${\displaystyle {\mathrm{e}}_{}^{}}$ s${\displaystyle {}_t^{}}$( k$$){\$displaystyle$f_${\rm{best}^{(k)}}}}$의 값 목록을 유지해야 한다. 포인트 $x{\displaystyle {}^{}}$( $){\$의 실현 가능$$ 여부에 따라 다음 두 가지 작업 중 하나를 수행한다.

• $x{\displaystyle {}^{}}$(${\displaystyle k^{}}$) ${\$ x$^{(k)}}}$이(가) 가능한 경우, 충족되는$$ 하위 g ${\$을 선택하여 제한되지 않은 사례와 본질적으로 동일한 업데이트를 수행하십시오.

${\displaystyle g_{0}^{{}^{T}\좌(x^{*}-x^{*}-x^{(k)}\우)+f_{0}\좌(x^{(k)}\우)-f_{\rm {best}^{(k)}\leqslant 0}$

• $x{\displaystyle {}^{}}$($){\$이(가) 실행 불가능하고$$ j-th 제약 조건을 위반하는 경우 타원체를 타당성 컷으로 업데이트한다. 우리의 타당성 감축은 f ${\displaystyle j_{}}$ ${\$$displaystyle g_{j$$}$의 하위 g ${\displaystyle j_{}}$ {\$displaystyle f_{j$}일 수 있으며, 이를$$ 충족해야 한다.

${\디스플레이 스타일 g_{j}^{T}\왼쪽(z-x^{(k)}\오른쪽)+f_{j}\왼쪽(x^{(k)\오른쪽)\leqslant 0}$

실현 가능한 모든 z에 대해

퍼포먼스

타원형 방식은 평면 위치 문제 등 저차원적인 문제에서 수적으로 안정성이 높은 곳에 사용된다. '작은' 문제에도 수치적 불안정과 실기 부진에 시달린다.

그러나 타원체 방법은 조합 최적화에 있어 중요한 이론적 기법이다. 계산 복잡성 이론에서 타원 알고리즘은 복잡성이 열의 수와 계수의 디지털 크기에 따라 달라지지만 행 수에 따라 달라지지 않기 때문에 매력적이다. 21세기에는 비슷한 성질을 가진 인테리어 포인트 알고리즘이 등장했다^{[citation needed]}.

메모들

추가 읽기

• Dmitris Alevras and Manfred W. Padberg, 선형 최적화 및 확장: 문제와 확장, Universitext, Springer-Verlag, 2001. (솔루션을 포함한 Padberg의 문제)
• V. Chandru 및 M.R.R.Rao, 선형 프로그래밍, M.J.Atallah, CRC Press 1999, 31-1 ~ 31-37이 편집한 알고리즘 및 계산 핸드북의 이론 31장.
• V. Chandru 및 M.R.R.Rao, 정수 프로그래밍, M.J.Atallah, CRC Press 1999, 32-1 ~ 32-45가 편집한 알고리즘 및 계산 핸드북의 이론 32장.
• 조지 B. 단치히와 무쿤드 N. 타파 1997. 선형 프로그래밍 1: 소개. 스프링거-베를라크.
• 조지 B. 단치히와 무쿤드 N. 타파. 2003. 선형 프로그래밍 2: 이론과 확장. 스프링거-베를라크.
• L. 로바스: 응용수학 50, SIAM, 필라델피아, 펜실베이니아, 1986년 CBMS-NSF 지역회의 시리즈, 숫자, 그래프 및 볼록성의 알고리즘 이론
• 카타 G. 1983년 와일리, Murty, Linear Programming, Wiley.
• M. Padberg, 선형 최적화 및 확장, Second Edition, Springer-Verlag, 1999.
• Christos H. Papadimitriou와 Kenneth Steiglitz, 결합 최적화: 알고리즘과 복잡성, 새로운 서문인 Dover로 수정됨.
• Alexander Schrijver, 선형 및 정수 프로그래밍 이론. 존 와일리 & 아들들, 1998년 ISBN 0-471-98232-6

외부 링크

• 스탠포드 과정 홈페이지 EE364b