푸리에-모츠킨 제거

본 기사는 해당 기사에서 독일어로 번역된 텍스트로 확장될 수 있다. (2013년 9월) 중요한 번역 지침을 보려면 [표시]를 클릭하십시오. DeepL이나 Google Translation과 같은 기계 번역은 번역의 유용한 출발점이지만 번역자는 기계 번역된 텍스트를 단순히 영어 위키백과에 복사하는 것이 아니라 필요에 따라 오류를 수정하고 번역이 정확한지 확인해야 한다. 이 템플릿에 주제를 추가하는 것을 고려하십시오. 기본 카테고리에 이미 6,709개의 기사가 있으며, topic= 분류에 도움이 될 것이다. 신뢰할 수 없거나 품질이 낮은 텍스트는 번역하지 마십시오. 가능한 경우 외국어 기사에 제공된 참조 자료로 텍스트를 확인하십시오. 번역 출처에 대한 상호 언어 링크를 제공하여 번역에 수반되는 편집 요약에 저작권 귀속성을 제공해야 한다. 모델 속성 편집 요약 Content in this edit is translated from the existing German Wikipedia article at [[:de:]]; see its history for attribution. 또한 {{번역된 페이지}} 템플릿도 토크 페이지에 추가해야 한다. 자세한 내용은 Wikipedia:번역.

FME 방법으로도 알려진 푸리에-모츠킨 제거는 선형 불평등 시스템에서 변수를 제거하기 위한 수학 알고리즘이다. 그것은 실제 해결책을 산출할 수 있다.

이 알고리즘은 1826년 이 방법을 제안한 조셉 푸리에와^[1] 1936년 다시 발견한 테오도르 모츠킨의 이름을 따서 명명되었다.

제거

V라고 하는 변수 집합(여기서 선형 불평등)을 관계 시스템(여기서 선형 불평등)에서 제거하는 것은 같은 종류의 또 다른 시스템을 만드는 것을 의미하지만, V에 변수가 없는 경우, 두 시스템이 나머지 변수에 대해 동일한 해결책을 갖는 것을 의미한다.

모든 변수가 선형 불평등 시스템에서 제거되면, 지속적인 불평등 시스템을 얻게 된다. 그러면 결과 시스템이 참인지 거짓인지를 결정하는 것은 사소한 일이다. 원래 시스템에 해결책이 있는 경우에만 그렇다. 결과적으로, 모든 변수의 제거는 불평등 시스템이 해결책을 가지고 있는지 여부를 감지하는 데 사용될 수 있다.

${\displaystyle r_{}}$ ${\$ $n}$ 변수 x ${\$}에서$$ x ${\displaystyle r_{}}$ ${\$ $x_{r}$ 사이의 $시스템{\displaystyle }$$$ S ${\displaystyle S}$에서 제거할$$ 변수를 고려하십시오. 시스템의 선형 불평등은 ${\displaystyle x_{}}$ r ${\$에 대한 계수의 부호(양수, 음수 또는 null)에 따라 세 등급으로 분류할 수 있다$.$

• those inequalities that are of the form ${\displaystyle x_{r}\geq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$; denote these by ${\displaystyle x_{r}\geq A_{j}(x_{1},\dots ,x_{r-1})}$, for ${\displaystyle j}$ ranging from 1 to ${\displaystyle {}_{}}$${\$$A$$}$ 여기서 ${\displaystyle n_{}}$ A ${\$$A}$은(는) 그러한 불평등의 수입니다.
• those inequalities that are of the form ${\displaystyle x_{r}\leq b_{i}-\sum _{k=1}^{r-1}a_{ik}x_{k}}$; denote these by ${\displaystyle x_{r}\leq B_{j}(x_{1},\dots ,x_{r-1})}$, for ${\displaystyle j}$ ranging from 1 to ${\displaystyle {}_{}}$${\displaystyle n_{}}$ ${\displaystyle B_{}}$ ${\$ 여기서$$ $n{\displaystyle {}_{}}$ ${\displaystyle B_{}}$ ${\$은(는) 그러한 불평등의 수입니다.
• $x{\displaystyle {}_{}}$ ${\displaystyle r_{}}$ ${\$이(가) 역할을 하지$$ 않는 불평등, 단일 접속사 $conjunction{\displaystyle }$ ${\displaystyle \phi }$로 그룹화$.$

따라서 원래의 시스템은 다음과 같다.

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq x_{r}\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\$$점,B_{n_{B}(x_{1},\dots,x_{r-1})\웨지 \phi$ $\}.$

제거는 $\exists {\displaystyle \mathrm{}}$ ${\displaystyle {}_{}}$ ${\displaystyle r_{}}$ ${\displaystyle S{}_{}}$ ${\displaystyle \exists x_{r}~S}$에 해당하는 시스템을 생성하는 것으로 구성된다$.$ 분명히 이 공식은 다음과 같다.

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1$$}},\cHB,x_{r-1})\because \phi$

불평등

${\displaystyle \max(A_{1}(x_{1},\dots ,x_{r-1}),\dots ,A_{n_{A}}(x_{1},\dots ,x_{r-1}))\leq \min(B_{1}(x_{1},\dots ,x_{r-1}),\dots ,B_{n_{B}}(x_{1},\dots ,x_{r-1}))}$

$n{\displaystyle {}_{}}$ ${\displaystyle {}_{}{}_{}}$ ${\displaystyle B_{}}$ ${\$과 동일함$A}n_{B}}$ inequalities ${\displaystyle A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$, for ${\displaystyle 1\leq i\leq n_{A}}$ and ${\displaystyle 1\leq j\leq n_{B}}$.

따라서 우리는 ${\displaystyle {원래}_{}}$의 시스템을 x r ${\$ x_${r}$가 제거되는$$ 다른 시스템으로 변형시켰다. 출력 시스템에는${\displaystyle }$(${\displaystyle n}$- ${\displaystyle {}_{}}$ ${\displaystyle A_{}}$- ${\displaystyle n_{}}$ ${\displaystyle {}_{}}$)${\displaystyle }$+ ${\displaystyle {}_{}}$ ${\displaystyle A_{}}$ ${\displaystyle n_{}}$ B ${\$n_{n}이(가) 포함되어 있다는 점에 유의하십시오.$A}n_{B}$ 불평등$$. 특히 $n{\displaystyle {}_{}}$ ${\displaystyle A_{}}$= ${\displaystyle {}_{}}$ ${\displaystyle B_{}}$= ${\displaystyle n\mathrm{}}$/ ${\displaystyle 2}$ ${\displaystyle n_{$$A}=n_{B}=n/2$ 그러면 출력 불평등의 수는 ${\displaystyle n\mathrm{}}$ ${\displaystyle {2\mathrm{}}^{}}$/ 4 ${\displaystyle n^{2}/4}$이다$.$

예

다음과 같은 불평등 시스템을 고려하십시오.^{[2]: 100–102}

2x − 5y + 4z ≤ 10

3x − 6y + 3z ≤ 9

−x + 5y − 2z ≤ −7

−3x + 2y + 6z ≤ 12

x를 제거하기 위해 x의 관점에서 불평등을 쓸 수 있다.

x ≤ (10 + 5y - 4z)/2

x ≤ (9 + 6y - 3z)/3

x ≥ 7 + 5y - 2z

x ≥(-12 + 2y + 6z)/3

우리는 "불평등"과 "불평등"과 "불평등"을 가진 두 개의 불평등을 가지고 있다; 시스템은 각각의 "불평등"의 오른쪽이 적어도 "불평등"의 오른쪽이 된다면 해결책을 가지고 있다. 이러한 조합은 2*2개 입니다.

7 + 5y - 2z ≤(10 + 5y - 4z)/2

7 + 5y - 2z ≤ (9 + 6y - 3z)/3

(-12 + 2y + 6z)/3˚(10 + 5y - 4z)/2

(-12 + 2y + 6z)/3≤ (9 + 6y - 3z)/3

우리는 이제 한 가지 변수가 적은 새로운 불평등 시스템을 갖게 되었다.

복잡성

$n{\displaystyle }$ ${\displaystyle n}$ 불평등에$$ 대해 제거 단계를 실행하면 출력에서 최대 n ${\displaystyle {2\mathrm{}}^{}}$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle$ n$^{2}/4}$의 불평등이$$ 발생할 수 있으므로, $d{\displaystyle }${\$displaystyle d}$ 연속$$ 단계를 실행하면 $최대{\displaystyle \mathrm{}}$ 4${\displaystyle }$($n$/${\displaystyle {}^{}4\mathrm{}}$ ) ${\displaystyle {{2d}^{}}^{}}${\$displaystystyle$ 4(n$/$$4)^{2^{d},$ 이중 지수 복잡성이 발생할 수 있다. 이는 알고리즘이 많은 불필요한 제약조건(다른 제약조건에 의해 함축된 제약조건)을 발생시키기 때문이다. 필요한 제약조건의 수는 단일 지수로서 증가한다.^[3] 불필요한 제약조건은 선형 프로그래밍을 사용하여 감지할 수 있다.

임베르트 가속도 정리

임버트로^[4] 인한 두 개의 "가속성" 이론은 공식 유도 트리의 통사적 특성에만 근거한 중복 불평등을 제거하여 선형 프로그램이나 매트릭스 순위를 계산해야 하는 필요성을 감소시킨다.

$i{\displaystyle }$ ${\displaystyle i}$을(를) 생성하는 데 사용된$$ 초기 시스템 $S{\displaystyle }$ ${\displaystyle S}$의 불평등 지수 $집합$으로 불평등 ${\displaystyle {hi}_{}}$$$${\$$displaystyle$ $H_{i}$의 히스토리를 정의하십시오$.$ 따라서 초기 시스템의$$ 불평등 i${\displaystyle }i{\displaystyle }$ ${\displaystyle S}$ ${\$$displaystyle H_{i}=\{i\}}}$에 대한$$ ${\displaystyle {Hi}_{}}$=${\displaystyle }${${\displaystyle i\}}$ ${\$$displaystyle i\in S}.$ 새로운 불평등 $k$를 추가할 때${\displaystyle }$: ${\displaystyle A_{}}$ ${\displaystyle {}_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$,${\displaystyle }$…${\displaystyle }$, x ${\displaystyle r_{}}$- ${\displaystyle 1_{}}$) ${\displaystyle \le }$ ${\displaystyle B_{}}$ j${\displaystyle {}_{}}$( ${\displaystyle {x\mathrm{}}_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$… ,${\displaystyle }$x ${\displaystyle r_{}}$- ${\displaystyle 1_{}}$) ${\displaystyle k:$$A_{i}(x_{1},\dots ,x_{r-1})\leq B_{j}(x_{1},\dots ,x_{r-1})}$ (by eliminating ${\displaystyle x_{r}}$), the new history ${\displaystyle H_{k}}$ is constructed as ${\displaystyle H_{k}=H_{i}\cup H_{j}}$.

변수 ${\displaystyle {Ok}_{}}$=${\displaystyle }${ ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$,${\displaystyle }$…${\displaystyle }$, ${\displaystyle x_{}}$ ${\displaystyle r_{}}$- k${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle O_{k}=\{x_{r}},\ldots ,x_{r-k+1}\}}}$이(가) 공식적으로 제거되었다고 가정합시다. 각 불평등 $i{\displaystyle }$ ${\displaystyle$ i$}$은(는) 세트 ${\displaystyle O_{}}$ $k{\displaystyle {}_{}}$ ${\$$displaystyle$ $O_{k}$을(를) $E{\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}}$ ∪ I ${\displaystyle {}_{}}$ I$$∪ I {$_{$로 분할한다$.$

• ${\displaystyle E_{}}$ ${\displaystyle i_{}}$ ${\$ 즉 의도적으로 효과적으로 제거된 변수의 집합이다$.$ $x{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ {\$displaystyle x_{j}$의 역사 ${\displaystyle H_{}}$ i ${\displaystyle h_$${i$$}$에서 x j ${\$이(가) 제거된 결과 최소 1개의 불평등이 발생하는$$ 즉시 $변수{\displaystyle {}_{}}$ x j ${\$displaystystyle x_{j}가 설정된다$.$
• ${\displaystyle I_{}}$ ${\$ 암묵적으로 제거된 변수 집합, 즉 우연. 변수는 ${\displaystyle {Hi}_{}}$ ${\$의 하나 이상의 불평등에서 나타나지만 불평등 $i{\displaystyle }$ ${\displaystyle i}$ 또는 ${\displaystyle {Ei}_{}}$ ${\$에 나타나지 않으면 암시적으로 제거된다.
• ${\displaystyle R_{}}$ ${\displaystyle i_{}}$ ${\$ 남은 변수 모두$.$

비중복적 불평등은 그것의 역사가 미미하다는 속성을 가지고 있다.^[5]

정리(임버트의 첫 가속 정리). If the history ${\displaystyle H_{i}}$ of an inequality ${\displaystyle i}$ is minimal, then ${\displaystyle 1+ E_{i} \ \leq \ H_{i} \ \leq 1+\left E_{i}\cup (I_{i}\cap O_{k})\right }$.

이러한 한계를 만족시키지 못하는 불평등은 반드시 중복되며, 그 해결책 세트를 변경하지 않고 시스템에서 제거할 수 있다.

두 번째 가속 정리는 최소 이력 세트를 감지한다.

정리(임버트의 두 번째 가속 정리). $불평등{\displaystyle }$ i ${\displaystyle i}$이(가) $1{\displaystyle \mathrm{}}$+ E ${\displaystyle i_{}{}_{}}$= ${\displaystyle H_{}}$ i $displaystyle 1+ E_{i}$= $H_{i}}},$H i ${\${i}}} 등일 경우, ${\displaystyle {Hi}_{}}$ {\displaystystyle H_${i}}$는 최소값이다$$.

이 정리는 빠른 검출 기준을 제공하며, 매트릭스 등급에 기초한 점검과 같이 더 많은 비용이 드는 점검을 피하기 위해 실무에 사용된다. 구현에 대한 자세한 내용은 참조를 참조하십시오.^[5]

정보이론의 응용

정보-이론적 달성가능성 증명은 우수한 코딩 체계의 존재가 보장되는 조건을 낳는다. 이러한 조건들은 종종 불평등의 선형 시스템에 의해 설명된다. 시스템의 변수에는 (문제 제형의 일부인) 전송률과 제도 설계에 사용되는 추가 보조율이 모두 포함된다. 일반적으로, 의사소통의 근본적인 한계를 문제의 매개변수 측면에서만 기술하는 것을 목표로 한다. 이에 따라 앞서 언급한 보조 요율을 제거할 필요성이 대두되며, 이는 푸리에-모츠킨 제거를 통해 실행된다. 그러나, 제거 과정은 원본보다 더 많은 불평등을 포함할 수 있는 새로운 시스템으로 귀결된다. 그러나, 종종 감소된 시스템의 불평등 중 일부는 중복된다. 중복성은 다른 불평등이나 정보 이론의 불평등에 의해 암시될 수 있다. 섀넌형 불평등). 최근 개발된 MATLAB용^[6] 오픈 소스 소프트웨어는 중복 불평등을 식별하고 제거하는 동시에 제거를 수행한다. 따라서 소프트웨어의 출력은 통신 요금만 포함하는 단순화된 시스템(중복 없음)을 출력한다.

중복 제약조건은 다음과 같이 선형 프로그램을 풀어서 식별할 수 있다. 선형 제약 시스템을 고려할 때 다른 모든 불평등 해법에 대해 $i{\displaystyle }$ ${\displaystyle i}$ -th$$ 불평등이 충족되면 중복된다. 마찬가지로 STI는 정보 이론적 조치와 그들이 만족하는 기본 정체성의 비부정성에 의해 암시되는 불평등을 가리킨다. For instance, the STI ${\displaystyle I(X_{1};X_{2})\leq H(X_{1})}$ is a consequence of the identity ${\displaystyle I(X_{1};X_{2})=H(X_{1})-H(X_{1} X_{2})}$ and the non-negativity of conditional entropy, i.e., ${\displaystyle H(X_1}$${\displaystyle X_{}}$ ${\displaystyle {2\mathrm{}}_{}}$) ${\displaystyle \ge }$ ${\displaystyle 0}$ ${\displaystyle H(X_{1$} $X_{2})\geq$ 0$\}.$ 섀넌형 불평등은 $R{\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {\mathrm{2n}{}^{}}^{}}$- 1 ${\$에 원뿔을 정의하는데$,$ 여기서 $n{\displaystyle }$ ${\displaystystyle$ n$}$은 관련 정보 조치에 나타나는 임의 변수의 수입니다. 결과적으로, 어떤 STI도 기본 정체성과 비부정성 제약조건에 의해 암시되는지 확인함으로써 선형 프로그래밍을 통해 증명될 수 있다. 기술된 알고리즘은 먼저 푸리에-모츠킨 제거를 수행하여 보조 속도를 제거한다. 그리고 감소된 출력시스템에 정보이론적 비부정성 제약조건을 부과하고 중복되는 불평등을 제거한다.

참고 항목

• Farkas의 보조정리 – FM 제거를 사용하여 증명할 수 있다.
• 실제 폐쇄장 – 원통형 대수 분해 알고리즘은 단순히 선형적인 것이 아니라 다항식 불평등에 대한 정량자 제거를 수행한다.

참조

추가 읽기

• Schrijver, Alexander (1998). Theory of Linear and Integer Programming. John Wiley & sons. pp. 155–156. ISBN 978-0-471-98232-6.
• Keßler, Christoph W. "Parallel Fourier–Motzkin Elimination". Universität Trier. CiteSeerX 10.1.1.54.657. 누락 또는 비어 있음 url= (도움말)
• Williams, H. P. (1986). "Fourier's Method of Linear Programming and its Dual". American Mathematical Monthly. 93 (9): 681–695. doi:10.2307/2322281. JSTOR 2322281.

외부 링크

• 학부 볼록스의 제1장, 아후스 대학의 닐스 로리첸의 교과서.
• 정보이론을 위한 FME 소프트웨어, 이도 B. 갓테그노, 지브 골드펠트, 하임 H. 퍼머터(Haim H. Permuter)에 의한 MATLAB의 오픈 소스 코드.