고정점 계산

고정점 계산은 주어진 ^[1]함수의 정확하거나 근사적인 고정점을 계산하는 과정을 말합니다.가장 일반적인 형태에서, 우리는 브라우어 고정점 정리에 대한 조건을 만족시키는 함수 f가 주어집니다. 즉, f는 연속적이고 단위 d-큐브를 자신에게 매핑합니다.브라우어 고정점 정리는 f가 고정점을 갖는다는 것을 보장하지만, 증명은 건설적이지 않습니다.대략적인 고정점을 계산하기 위해 다양한 알고리즘이 고안되었습니다.이러한 알고리즘은 시장 균형을 계산하기 위한 경제학, 내쉬 균형을 계산하기 위한 게임 이론 및 동적 시스템 분석에 사용됩니다.

정의들

세 개의 고정점이 있는 예제 함수 그래프

단위 간격은 E $=$ [ $E:=[0,1]$ $]{displaystyle$ E:=[ $0,1$ 로 표시되며, 단위 d차원 큐브는 E로 표시됩니다^d.연속 함수 f는 (E에서^d 자체로) E에^d 정의됩니다.종종, f는 연속적일 뿐만 아니라 립시츠 연속적이라고 가정합니다. 즉, 어떤 상수 L에 $|f(x)-f(y)|\leq L\cdot |x-y|$ 는 f $x)$ - $|f(x)-f(y)|\leq L\cdot |x-y|$ ( $)$ $|f(x)-f(y)|\leq L\cdot |x-y|$ ≤ L $⋅$ $|f(x)-f(y)|\leq L\cdot |x-y|$ - $y$ \ $leq$ L $\cdot x-y$ }가 $|f(x)-f(y)|\leq L\cdot |x-y|$ E에^d 있는 모든 x에 대해서입니다.

고정점 off는 E에서^d f(x) = x인 점 x입니다. 브라우어 고정점 정리에 따르면, E에서^d 자체까지의 모든 연속 함수는 고정점을 가집니다.그러나 일반적인 함수의 경우, 임의의 실수가 될 수 있기 때문에 고정점을 정확하게 계산하는 것은 불가능합니다.고정점 계산 알고리즘은 대략적인 고정점을 찾습니다.대략적인 고정점에 대한 몇 가지 기준이 있습니다.몇 가지 일반적인 기준은 다음과 같습니다.^[2]

잔류 기준: 근사 매개 변수 $\varepsilon >0$ $|f(x)-x|\leq \varepsilon$ > 0 ${displaystyle \varepsilon$ > $0}$ 이 주어지면, γ-잔여 고정점 off는 $|f(x)-x|\leq \varepsilon$ 에서 $|f(x)-x|\leq \varepsilon$ f( $x$ ) - x $≤$ {{ $displaystyle f(x)-x \leq$ \varepsilon $|f(x)-x|\leq \varepsilon$ 인 점^d x이며, 여기서 .는 최대 표준을 나타냅니다.즉, $f(x)-x$ f $f(x)-x$ - $({displaystyle$ f $(x)-x}$ 의 $f(x)-x$ 모든 d 좌표는 $최대$ ^[3]^{: 4}ε이어야 합니다.
절대 기준: 근사 매개 변수 $\delta >0$ $|x-x_{0}|\leq \delta$ > $\delta >0$ 0 ${\displaystyle$ \ $delta$ > $0$ 이 주어지면, γ-절대 고정점 f는 E의^d $|x-x_{0}|\leq \delta$ 점 x로 $|x-x_{0}|\leq \delta$ - $|x-x_{0}|\leq \delta$ $≤$ {{ $displaystyle$ $x_{0$ \ $leq \delta$ $|x-x_{0}|\leq \delta$ $x_{0}$ 서 $x_{0}$ 은 f의 임의의 고정점입니다.
상대적 기준: 근사 매개 $\delta >0$ δ > $\delta >0$ 0 {\ $displaystyle$ \ $delta$ 이 주어지면, A $|x-x_{0}|/|x_{0}|\leq \delta$ 상대적 고정점 f는 $|x-x_{0}|/|x_{0}|\leq \delta$ E의^d 점 $|x-x_{0}|/|x_{0}|\leq \delta$ 로 $|x-x_{0}|/|x_{0}|\leq \delta$ - $|x-x_{0}|/|x_{0}|\leq \delta$ 0 / $|x-x_{0}|/|x_{0}|\leq \delta$ 0 $≤$ {\ $displaystyle x_{0$ $}$ / $x_$ {0 $}$ \ $leq \delta$ }, $x_{0}$ 서 x $x_{0}$ 0은 f의 임의의 고정점입니다.

$립시츠$ 연속 함수의 경우, 절대 기준이 잔류 기준보다 더 강합니다. $|x-x_{0}|\leq \delta$ 가 상수 L을 갖는 립시츠 연속 함수인 경우 $|x-x_{0}|\leq \delta$ $|x-x_{0}|\leq \delta$ - $|x-x_{0}|\leq \delta$ $|x-x_{0}|\leq \delta$ $≤$ ≤ \ $delta$ 는 $|x-x_{0}|\leq \delta$ f $(x)$ - $f(x_{0)$ ≤ $≤$ $L$ $\delta$ 를 $|f(x)-f(x_{0})|\leq L\cdot \delta$ 합니다. $x_{0}$ 0({{ $displaystyle x_{$ $0}})$ 은 $x_{0}$ 고정점 off이므로, 이는 f $)$ - $x$ $|f(x)-x_{0}|\leq L\cdot \delta$ ≤ L $≤$ \ $leq$ $\delta$ $},$ $|f(x)-x|\leq (1+L)\cdot \delta$ ( $|f(x)-x|\leq (1+L)\cdot \delta$ - $|f(x)-x|\leq (1+L)\cdot \delta$ $|f(x)-x|\leq (1+L)\cdot \delta$ ( $|f(x)-x|\leq (1+L)\cdot \delta$ $|f(x)-x|\leq (1+L)\cdot \delta$ ) $|f(x)-x|\leq (1+L)\cdot \delta$ \ $|f(x)-x|\leq (1+L)\cdot \delta$ \ $displaystyle$ f $(x)$ - $x$ \ $leq ($ 1 $|f(x)-x|\leq (1+L)\cdot \delta$ + $L )$ \ $cdelta$ 를 $|f(x)-x_{0}|\leq L\cdot \delta$ 합니다 $|f(x)-x|\leq (1+L)\cdot \delta$ γ-절대 고정점은 또한 $\varepsilon =(1+L)\cdot \delta$ $\varepsilon =(1+L)\cdot \delta$ ( $\varepsilon =(1+L)\cdot \delta$ + $\varepsilon =(1+L)\cdot \delta$ ) $\varepsilon =(1+L)\cdot \delta$ = (1 $+L)\cdot \dot$ γ $}$ 인 $\varepsilon =(1+L)\cdot \delta$ γ-절대 고정점입니다.

고정점 계산 알고리즘의 가장 기본적인 단계는 값 쿼리입니다: E의^d 임의의 x가 주어지면^{[sentence fragment]},

함수 f는 평가 쿼리를 통해 액세스할 수 있습니다. 임의의 x에 대해 알고리즘이 f(x)를 평가할 수 있습니다.알고리즘의 런타임 복잡성은 일반적으로 필요한 평가 횟수에 따라 결정됩니다.

수축함수

L이 일정한 립시츠 연속 함수는 L < 1이면 수축 함수라고 하며, L ≤ 1이면 약하게 수축 함수라고 합니다.브라우어 조건을 만족하는 모든 수축 함수에는 고유한 고정점이 있습니다.게다가, 수축 함수에 대한 고정점 계산은 일반 함수에 대한 것보다 쉽습니다.

함수 반복을 사용하여 고정점 계산

고정점 계산을 위한 첫 번째 알고리즘은 바나흐의 고정점 반복 알고리즘이었습니다.바나흐의 고정점 정리는 고정점 반복이 수축 매핑에 적용될 때 반복 후의 오류가 $)({$ Lt})({ $displaystyle$ O $(L^{t$ 에 있음을 의미합니다.따라서 $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ 고정점에 필요한 평가 횟수는 $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ L $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ( $δ$ ) $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ( $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ) / $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ( $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ / l $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ) $=$ $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ( $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ / l ) / $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ( $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ / $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ ) \ $displaystyle \log _$ ${L}$ ( \ $delta$ ) $= log$ ( $1$ / log ( 1 / l ) $\$ log $($ 1 $\log _{L}(\delta )=\log(\delta )/\log(L)=\log(1/\delta )/\log(1/L)$ l $)$ Sikorski와 Wozniakowski는^[4] 치수가 클 때 Banach의 알고리즘이 최적임을 보여주었습니다.구체적으로, d $d\geq \log(1/\delta )/\log(1/L)$ $d\geq \log(1/\delta )/\log(1/L)$ $d\geq \log(1/\delta )/\log(1/L)$ ( $d\geq \log(1/\delta )/\log(1/L)$ / $d\geq \log(1/\delta )/\log(1/L)$ $d\geq \log(1/\delta )/\log(1/L)$ / $d\geq \log(1/\delta )/\log(1/L)$ $d\geq \log(1/\delta )/\log(1/L)$ ( $d\geq \log(1/\delta )/\log(1/L)$ $d\geq \log(1/\delta )/\log(1/L)$ ) {\ $displaystyle$ d $\geq \log(1/\delta )/\log(1/L$ 일 때, δ 상대적 고정점에 대한 알고리즘의 필요한 평가 횟수는 반복 알고리즘에 필요한 평가 횟수의 50%보다 큽니다.L이 1에 가까워지면 평가 횟수는 무한대에 가까워집니다.실제로 L=1인 모든 함수에 대해 ^[5]γ-절대 고정점을 계산할 수 있는 유한 알고리즘은 없습니다.

L < 1 그리고 d = 1일 때, 최적의 알고리즘은 시코르스키와 워즈니악스키의 ^[4]고정점 외피(FPE) 알고리즘입니다.O $O(\log(1/\delta )+\log \log(1/(1-L)))$ $O(\log(1/\delta ))$ ( $O(\log(1/\delta )+\log \log(1/(1-L)))$ / $O(\log(1/\delta )+\log \log(1/(1-L)))$ $O(\log(1/\delta ))$ $O(\log(1/\delta )+\log \log(1/(1-L)))$ ) + $O(\log(1/\delta )+\log \log(1/(1-L)))$ $O(\log(1/\delta )+\log \log(1/(1-L)))$ $O(\log(1/\delta )+\log \log(1/(1-L)))$ $O(\log(1/\delta )+\log \log(1/(1-L)))$ ( $O(\log(1/\delta )+\log \log(1/(1-L)))$ / - L $O(\log(1/\delta )+\log \log(1/(1-L)))$ ) $O(\log(1/\delta )+\log \log(1/(1-L)))$ \ $displaystyle$ O $(\log($ / ( 1 - $O(\log(1/\delta )+\log \log(1/(1-L)))$ ) $O(\log(1/\delta )+\log \log(1/(1-L)))$ ) $O(\log(1/\delta )+\log \log(1/(1-L)))$ \ displaystyle O(\ $log(1$ $/\delta$ ) $O(\log(1/\delta ))$ +\ $log$ \ log \ log $(1/(1-L))}$ 쿼리를 $O(\log(1/\delta )+\log \log(1/(1-L)))$ $O(\log(1/\delta ))$ $O(\log(1/\delta )+\log \log(1/(1-L)))$ 하여 δ 상대적 고정점을 찾고 $O(\log(1/\delta ))$ O $(log$ ( $O(\log(1/\delta ))$ / $delta))$ 쿼리를 $O(\log(1/\delta ))$ 하여 절대 고정점을 찾습니다.이것은 고정점 반복 ^[6]알고리즘보다 훨씬 빠릅니다.

d>1이지만 너무 크지 않고 L≤1일 때 최적의 알고리즘은 내부 타원체 알고리즘입니다(타원체 ^[7]방법에 기초함).ε-잔류 고정점이 O $O(d\cdot \log(1/\varepsilon ))$ ⋅ $O(d\cdot \log(1/\varepsilon ))$ $O(d\cdot \log(1/\varepsilon ))$ ( 1 / $O(d\cdot \log(1/\varepsilon ))$ ) $O(d\cdot \log(1/\varepsilon ))$ \ $displaystyle$ O $(d\cdot \log(1/\varepsilon))$ 평가를 $O(d\cdot \log(1/\varepsilon ))$ $O(d\cdot \log(1/\varepsilon ))$ 하고 있음을 발견합니다.L<1일 때 $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ O ( $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ [ $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ ( $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ / $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ ) $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ + $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ ( $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ 1 $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ / ( $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ - $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ ) $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ ] $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ ) \\ $displaystyle$ O $(d\cdot [\log(1/\delta$ ) +\ $log(1/(1-L))}$ 평가를 $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ $O(d\cdot [\log(1/\delta )+\log(1/(1-L))])$ 하여 δ-절대 고정점을 찾습니다.

셸먼과 시코르스키는^[8] $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ 2µlog $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ ) $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ + ${displaystyle$ 2 $\lceilon \log$ _ ${2}(1/\varepsilon )\rceil +1}$ 쿼리만을 $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ $2\lceil \log _{2}(1/\varepsilon )\rceil +1$ 하여 L ≤ 1인 2차원 함수의 µ-잔존 고정점을 계산하기 위한 BEFix(이등분 엔벨로프 고정점)라는 알고리듬을 제시했습니다.그들은^[9] 나중에 BEDFix(Bisection Envelope Deep-cut Fix)라는 개선 사항을 제시했는데, 이는 동일한 최악의 경우 보증이지만 더 나은 경험적 성능입니다.L<1일 때, BEDFix는 O $O(\log(1/\varepsilon )+\log(1/(1-L)))$ $O(\log(1/\varepsilon )+\log(1/(1-L)))$ ( $O(\log(1/\varepsilon )+\log(1/(1-L)))$ / $O(\log(1/\varepsilon )+\log(1/(1-L)))$ $O(\log(1/\varepsilon )+\log(1/(1-L)))$ + $O(\log(1/\varepsilon )+\log(1/(1-L)))$ $O(\log(1/\varepsilon )+\log(1/(1-L)))$ ( $O(\log(1/\varepsilon )+\log(1/(1-L)))$ / ( $O(\log(1/\varepsilon )+\log(1/(1-L)))$ - $O(\log(1/\varepsilon )+\log(1/(1-L)))$ ) $O(\log(1/\varepsilon )+\log(1/(1-L)))$ ) \ $displaystyle$ O $(\log(1/\varepsilon$ ) +\ $log(1/(1-L))}$ 쿼리를 $O(\log(1/\varepsilon )+\log(1/(1-L)))$ $O(\log(1/\varepsilon )+\log(1/(1-L)))$ 하여 δ-절대 고정점을 계산할 수도 있습니다.

셸먼과 시코르스키는^[2] O $O(\log ^{d}(1/\varepsilon ))$ d $⁡$ ( $O(\log ^{d}(1/\varepsilon ))$ / $O(\log ^{d}(1/\varepsilon ))$ ) \ $displaystyle$ O $(\log ^{d}(1/\varepsilon))}$ 쿼리를 $O(\log ^{d}(1/\varepsilon ))$ $O(\log ^{d}(1/\varepsilon ))$ 하여 L ≤ 1로 d차원 함수의 γ-잔존 고정점을 계산하기 위한 PFix라는 알고리듬을 제시했습니다.L < 1, PFix가 $O(\log ^{d}(1/[(1-L)\delta ]))$ $=$ ( $\varepsilon =(1-L)\cdot \delta$ $\varepsilon =(1-L)\cdot \delta$ ) $O(\log ^{d}(1/[(1-L)\delta ]))$ \ $displaystyle \varepsilon$ =( $1-L)\cdot$ \delt $\varepsilon =(1-L)\cdot \delta$ 쿼리로 실행될 수 있는 경우, 이 경우 O $O(\log ^{d}(1/[(1-L)\delta ]))$ d $O(\log ^{d}(1/[(1-L)\delta ]))$ ( $O(\log ^{d}(1/[(1-L)\delta ]))$ / [ $O(\log ^{d}(1/[(1-L)\delta ]))$ ( 1 $O(\log ^{d}(1/[(1-L)\delta ]))$ - $O(\log ^{d}(1/[(1-L)\delta ]))$ ) $O(\log ^{d}(1/[(1-L)\delta ]))$ $δ$ $O(\log ^{d}(1/[(1-L)\delta ]))$ $\$ $displaystyle$ O $(\log$ ^{ $d}(1/(1-L))$ 를 $O(\log ^{d}(1/[(1-L)\delta ]))$ 하여 ^-(1-(\ $delt$ ))deltelt) delt $)$ 를 계산합니다.L이 1에 가까울 때 반복 알고리즘보다 효율적입니다.알고리즘은 재귀적입니다. (d-1)차원 함수에 대한 재귀적 호출을 통해 d차원 함수를 처리합니다.

미분 가능한 함수에 대한 알고리즘

함수 f가 미분 가능하고 알고리즘이 그 도함수를 평가할 수 있을 때(f 그 자체뿐만 아니라) 뉴턴 방법을 사용할 수 있고 훨씬 ^[10]^[11]더 빠릅니다.

일반 함수

립시츠 상수 L > 1을 갖는 함수의 경우, 고정점을 계산하는 것이 훨씬 어렵습니다.

일차원

1차원 함수(d $E:=[0,1]$ 1)의 경우, O $O(\log(1/\delta ))$ $O(\log(1/\delta ))$ ( $O(\log(1/\delta ))$ / $O(\log(1/\delta ))$ ) $O(\log(1/\delta ))$ \displaystyle O $(\log(1/\delta))$ 쿼리를 $O(\log(1/\delta ))$ $O(\log(1/\delta ))$ 하여 γ-절대 고정점을 찾을 수 있습니다. 간격 $E:=[0,1]$ : $=$ [ $E:=[0,1]$ ] {\ $displaystyle$ E : [ $0, 1$ 각 반복 시 x를 현재 간격의 중심으로 합니다.그리고 f(x)를 계산합니다. f(x) > x가 x의 오른쪽 부분 구간에서 반복됩니다. 그렇지 않으면 x의 왼쪽 구간에서 반복됩니다. 현재 구간에는 항상 고정점이 포함되므로 O $O(\log(1/\delta ))$ $O(\log(1/\delta ))$ ( $O(\log(1/\delta ))$ / $O(\log(1/\delta ))$ ) $O(\log(1/\delta ))$ \ $displaystyle$ O $(\log(1/\delta))$ $O(\log(1/\delta ))$ 이후에는나머지 구간의 임의의 점은 π-절대 고정점 off입니다. $\delta :=\varepsilon /(L+1)$ $\delta :=\varepsilon /(L+1)$ : $\delta :=\varepsilon /(L+1)$ $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ $\delta :=\varepsilon /(L+1)$ $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ / $\delta :=\varepsilon /(L+1)$ ( $\delta :=\varepsilon /(L+1)$ + 1 $\delta :=\varepsilon /(L+1)$ ) $\delta :=\varepsilon /(L+1)$ \ $displaystyle \displaystyle$ \displaystyle \ $displaystyle$ : = \ $varepsilon$ / ( $L$ + 1 $\delta :=\varepsilon /(L+1)$ ) 여기서 L은 O $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ ( $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ / $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ ) = $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ ( $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ / $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ 디스플레이 $스타일$ O $(\log (L$ / $varepsilon$ ) \ $log = log$ / log / log $}$ ^[3] ( log / log / log / log / log )\lon $O(\log(L/\varepsilon )=\log(L)+\log(1/\varepsilon ))$ ( $log$ / log / l ) \ $log$ / log / l

2차원 이상

2차원 이상의 기능의 경우 문제가 훨씬 더 어렵습니다.셸먼과 시코르스키는^[2] 모든 정수 d≥ 2와 L > 1에 대해 d차원 L-립시츠 함수의 γ-절대 고정점을 찾는 것은 무한히 많은 평가를 필요로 할 수 있다는 것을 증명했습니다.그 증명 아이디어는 다음과 같습니다.모든 정수 T > 1 및 평가 쿼리의 T 시퀀스(적응 가능성 있음)에 대해, 하나는 상수 L로 Lipschitz 연속적인 두 개의 함수를 구성할 수 있으며, 이러한 모든 쿼리에 대해 동일한 대답을 산출할 수 있지만, 하나는 (x, 0)에서 고유한 고정점을 가지며 다른 하나는 (x, 1)에서 고유한 고정점을 갖습니다.T 평가를 사용하는 알고리즘은 이러한 함수를 구별할 수 없으므로 π-절대 고정점을 찾을 수 없습니다.이것은 모든 유한 정수 T에 해당합니다.

함수 평가에 기반한 여러 알고리즘이 π-잔차 고정점을 찾기 위해 개발되었습니다.

일반 함수의 고정점을 근사화한 최초의 알고리즘은 1967년 ^[12]^[13]허버트 스카프에 의해 개발되었습니다.스카프의 알고리즘은 스퍼너의 부제와 유사한 구조에서 완전한 레이블이 지정된 "원시 집합"을 찾아 π-잔차 고정점을 찾습니다.
해롤드^[14] 쿤의 이후 알고리즘은 원시 집합 대신 단순과 단순 분할을 사용했습니다.
오린 해리슨 메릴은^[15] 단순한 접근법을 더욱 발전시키면서 재시작 알고리즘을 제시했습니다.
커티스^[16] 처마는 호모토피 알고리즘을 제시했습니다.이 알고리즘은 f에 가까운 아핀 함수로 시작하여 고정점을 따르면서 f 쪽으로 변형함으로써 작동합니다.마이클^[1] 토드의 책은 1976년까지 개발된 다양한 알고리즘을 조사합니다.
David^[17] Gale은 n차원 함수의 고정점을 계산하는 것은 Hex(d 플레이어가 있는 게임으로 각각 두 개의 반대 면을 연결해야 함)의 d차원 게임에서 누가 승자인지 결정하는 것과 같다는 것을 보여주었습니다.원하는 $정확도$ 가 주어지면 »
- 크기 kd의 Hex 보드를 구성합니다. $k>1/\varepsilon$ 서 $k>1/\varepsilon$ k > $k>1/\varepsilon$ / $k>1/\varepsilon$ {\ $displaystyle$ k> $1/\varepsilon$ 각 정점 z는 단위 n-큐브의 점 z/k에 해당합니다.
- 차이 f(z/k) - z/k를 계산합니다. 차이는 n-벡터입니다.
- 차이 벡터에서 가장 큰 좌표를 나타내는 1, ..., d의 레이블로 정점 z에 레이블을 지정합니다.
- 결과 레이블링은 d 플레이어에서 d차원 Hex 게임의 가능한 플레이에 해당합니다.이 게임은 반드시 승자가 있어야 하며, 게일은 승리 경로를 구성하는 알고리즘을 제시합니다.
- 승리 경로에는 f(z/k) - z/k가 양수인_i 점과 f(z/k) - z/k가_i 음수인 인접한 점이 있어야 합니다.이는 이 두 점 사이에 고정 점 꺼짐이 있음을 의미합니다.

최악의 경우, 이 모든 알고리즘에 필요한 함수 평가의 수는 정확도의 이진 표현, 즉 $\Omega (1/\varepsilon )$ ( $\Omega (1/\varepsilon )$ $)$ \ $displaystyle \Omega (1/\varepsilon$ 에서 기하급수적입니다.

쿼리 복잡도

Hirsch, Papadimitriu 및 Vavasis는 γ-잔차 고정점 off를 찾는 함수 평가에 기반한 알고리즘은 $\Omega (L'/\varepsilon )$ / $)$ \ $displaystyle \Omega(L'/\varepsilon)}$ 함수 $\Omega (L'/\varepsilon )$ 평가를 필요로 한다는 것을 증명했습니다^[3]. $L'$ 서 L $'{\$ L $'$ 은 $L'$ $f(x)-x$ f $f(x)-x$ - $({displaystyle f(x)-x$ } $f(x)-x$ 의 립시츠 상수입니다( $L-1\leq L'\leq L+1$ - $L-1\leq L'\leq L+1$ ≤ $L-1\leq L'\leq L+1$ $L-1\leq L'\leq L+1$ + $L-1\leq L'\leq L+1$ {\ $displaystyle$ L $'\leq$ L $+1}).$ 더 정확하게는:

2차원 함수(d=2)의 경우, 그들은 $\Theta (L'/\varepsilon )$ / $)$ \ $displaystyle \Theta(L'/\varepsilon)$ 를 증명합니다 $\Theta (L'/\varepsilon )$
임의의 d≥ 3에 대해, d차원 함수의 $\Omega ((L'/\varepsilon )^{d-2})$ 고정점을 찾으려면 $\Omega ((L'/\varepsilon )^{d-2})$ / $O((L'/\varepsilon )^{d})$ $\Omega ((L'/\varepsilon )^{d-2})$ d - $\Omega ((L'/\varepsilon )^{d-2})$ ) $\Omega ((L'/\varepsilon )^{d-2})$ \ $displaystyle$ $\Omega((L'/\varepsilon)^{d-2})$ 쿼리와 $\Omega ((L'/\varepsilon )^{d-2})$ O $($ d $d}$ 쿼리가 $O((L'/\varepsilon )^{d})$ 필요합니다.

후자의 결과는 지수에 공백을 남깁니다.첸과^[18] 덩은 격차를 좁혔습니다.그들은 모든 ≥ $1/\varepsilon >4d$ 및 $1/\varepsilon >4d$ 1 / $1/\varepsilon >4d$ $L'/\varepsilon >192d^{3}$ $1/\varepsilon >4d$ d \ $displaystyle$ 1 $/\varepsilon$ > 4 $d$ 및 $L'/\varepsilon >192d^{3}$ / $L'/\varepsilon >192d^{3}$ $\Theta ((L'/\varepsilon )^{d-1})$ $L'/\varepsilon >192d^{3}$ d $L'/\varepsilon >192d^{3}$ \ $displaystyle$ L $'/\varepsilon$ > $\Theta ((L'/\varepsilon )^{d-1})$ d $^{3$ 에 대해 $\Theta ((L'/\varepsilon )^{d-1})$ 잔류 고정점 계산에 필요한 쿼리 수가 θ $\Theta ((L'/\varepsilon )^{d-1})$ ( $\Theta ((L'/\varepsilon )^{d-1})$ ε / $\Theta ((L'/\varepsilon )^{d-1})$ ) $\Theta ((L'/\varepsilon )^{d-1})$ - $\Theta ((L'/\varepsilon )^{d-1})$ 1 $\Theta ((L'/\varepsilon )^{d-1})$ \ $Ta (L'$ ) { $v$ -dilon에 있음을 증명했습니다.

이산 고정점 계산

이산 함수는 $(d차원$ 정수 격자)의 $\mathbb {Z} ^{d}$ 집합에 정의된 함수입니다 $.$ 이산 함수가 고정점을 갖는 조건을 나타내는 여러 개의 이산 고정점 정리가 있습니다.예를 들어, Iimura-Murota-Tamura 정리에 따르면, 만약 f가 $\mathbb {Z} ^{d}$ 의 $\mathbb {Z} ^{d}$ $\mathbb {Z} ^{d}$ 부분 집합에서 $자신$ 으로 가는 함수이고, f가 초입방 방향 보존이라면, f는 고정점을 갖는다고 합니다.

f가 정수 $\{1,\dots ,n\}^{d}$ 큐브 { $\{1,\dots ,n\}^{d}$ $\{1,\dots ,n\}^{d}$ $\{1,\dots ,n\}^{d}$ ${$ \{ $1,\dots,n\}^{d}}$ 에서 $\{1,\dots ,n\}^{d}$ 그 자체로의 방향 보존 함수라고 하자.Chen과^[18] Deng은 모든 d≥2 및 n > 48d에 대해 그러한 고정점을 계산하려면 θ $\Theta (n^{d-1})$ ( $\Theta (n^{d-1})$ - $\Theta (n^{d-1})$ 1 $\Theta (n^{d-1})$ ) \ $displaystyle \Theta (n^{d-1})$ 함수 $\Theta (n^{d-1})$ 평가가 필요하다는 것을 증명합니다.

Chen과^[19] Deng은 2D-BROWER라고 하는 다른 이산 고정점 문제를 정의합니다.그리드의 모든 x에 대해 f(x) - x가 (0 $,$ 1, 0) 또는 (1, 0) 또는 (-1, -1)이 $\{0,\dots ,n\}^{2}$ {0, $\{0,\dots ,n\}^{2}$ …, $}$ $\{0,\dots ,n\}^{2}$ {\ $dots, n\}^{2}}$ 의 $\{0,\dots ,n\}^{2}$ 이산 함수 f를 고려합니다.목표는 세 개의 레이블이 모두 발생하는 그리드에서 사각형을 찾는 것입니다.함수 f는 정사각형 $\{0,\dots ,n\}^{2}$ { $\{0,\dots ,n\}^{2}$ $\{0,\dots ,n\}^{2}$ n $\{0,\dots ,n\}^{2}$ } $({$ displaystyle \{0 $,\displaystyle,n\}^{$ 2})를 $\{0,\dots ,n\}^{2}$ 자신에게 매핑해야 하므로, x = 0 및 y = 0을 (0, 1) 또는 (1, 0)에 매핑해야 합니다.문제는 2D-SPERNER(스페너의 부제에 대한 조건을 충족하는 삼각 측량에서 완전한 레이블이 있는 삼각형 계산)로 축소될 수 있으며, 따라서 PAD-완전입니다.이것은 대략적인 고정점을 계산하는 것이 매우 간단한 기능에 대해서도 PAD-완전하다는 것을 의미합니다.

고정점 연산과 루트 찾기 알고리즘 간의 관계

E에서^d R까지의 함수 g가 주어지면, g의 근은 E에서^d g(x)=0인 점 x입니다.g의 γ-루트는 E에서^d g $g(x)\leq \varepsilon$ {{ $displaystyle$ g( $x)\leq \varepsilon$ 인 점 x입니다.

고정점 계산은 루트 찾기의 특별한 경우입니다. E에 함수^d f가 주어지면 $g(x):=|f(x)-x|$ g ( $g(x):=|f(x)-x|$ : $=$ $g(x):=|f(x)-x|$ ( $g(x):=|f(x)-x|$ - $g(x):=|f(x)-x|$ {\ $displaystyle$ g $(x$ ):= $f(x)-x$ 를 $g(x):=|f(x)-x|$ 합니다. 분명히 x는 g의 루트인 경우에만 고정점 off이고, x는 g가 g의 루트인 경우에만 π-π 고정점 f입니다.따라서 루트 찾기 알고리즘(함수의 대략적인 루트를 계산하는 알고리즘)을 사용하여 대략적인 고정점을 찾을 수 있습니다.

그 반대는 사실이 아닙니다. 일반 함수의 대략적인 근을 찾는 것이 대략적인 고정점을 찾는 것보다 어려울 수 있습니다.특히, 시코르스키는^[20] γ-루트를 찾는 데는 $\Omega (1/\varepsilon ^{d})$ ( $\Omega (1/\varepsilon ^{d})$ $\Omega (1/\varepsilon ^{d})$ $\Omega (1/\varepsilon ^{d})$ d $\Omega (1/\varepsilon ^{d})$ ) \ $displaystyle \Omega (1/\varepsilon$ ^{ $d})$ 함수 $\Omega (1/\varepsilon ^{d})$ 평가가 필요하다는 것을 증명했습니다.이는 1차원 함수에 대해서도 지수 하한을 제공합니다(반대로, 1차원 함수의 γ-잔여 고정점은 2분할 방법을 사용한 O $O(\log(1/\varepsilon ))$ $O(\log(1/\varepsilon ))$ ( $O(\log(1/\varepsilon ))$ / $O(\log(1/\varepsilon ))$ ) $O(\log(1/\varepsilon ))$ \ $displaystyle$ O $(\log (1/\varepsilon))$ 쿼리를 $O(\log(1/\varepsilon ))$ $O(\log(1/\varepsilon ))$ 하여 찾을 수 있습니다).여기에 증명 ^[3]^{: 35}스케치가 있습니다.점 x 주변의₀ 일부 작은 입방체를 제외한 E의 모든^d 곳에서 $π$ 보다 약간 큰 함수 g를 구성합니다. 여기서₀ x는 g의 고유한 루트입니다.만약 g가 상수 L을 갖는 Lipschitz라면, x 주위의₀ 큐브는 $\varepsilon /L$ / $L의 측면$ 길이를 가질 수 있습니다. g의 π-루트를 찾는 모든 알고리즘은 E 전체를^d 포함하는 큐브 집합을 확인해야 합니다. 이러한 큐브의 수는 적어도 $(L/\varepsilon )^{d}$ ( $L$ / $π$ ) $(L/\varepsilon )^{d}$ {\varepsilon $\varepsilon /L$ $)^{d$ 입니다.

그러나 근사 근을 찾는 것이 근사 고정점을 찾는 것과 동일한 함수 클래스가 있습니다.한^[18] 예로 g $g(x)+x$ + $(\displaystyle$ g $(x)$ + $x($ $g(x)+x$ ) + $({displaystyle$ g( $x)$ + $x}$ 가 $g(x)+x$ $g(x)+x$ E에^d 있는^d 모든 x에 대해 E에 있음^d)를 매핑하는 $g(x)+x$ g의 클래스가 있습니다.이는 이러한 모든 함수에 대해 f $=$ + ${displaystyle$ f $(x$ ):= $g(x)+x$ $f(x):=g(x)+x$ 가 브라우어의 고정점 정리에 대한 조건을 만족시키기 때문입니다.분명히, x는 x가 g의 루트인 경우에만 고정점 off이고, x는 x가 g의 γ-루트인 경우에만 γ-잔류 고정점 off입니다.Chen과^[18] Deng은 이러한 문제의 이산 변형이 계산적으로 동일하다는 것을 보여줍니다. 두 문제 모두 $\Theta (n^{d-1})$ Δ ( $\Theta (n^{d-1})$ - $\Theta (n^{d-1})$ ) {\ $displaystyle \Theta (n^{d-1})}$ 함수 $\Theta (n^{d-1})$ 평가가 필요합니다.

의사소통의 복잡성

러프가든과 와인스타인은^[21] 대략적인 고정점 계산의 통신 복잡성을 연구했습니다.모형에는 두 개의 에이전트가 있습니다. 하나는 함수 f를 알고 다른 하나는 함수 g를 알고 있습니다.두 기능 모두 립시츠 연속이며 브라우어의 조건을 만족시킵니다.목표는 복합 $g\circ f$ g $g\circ f$ {\ $displaystyle$ g $\circf$ 의 대략적인 고정점을 계산하는 것입니다.그들은 결정론적 통신 복잡성이 $\Omega (2^{d})$ ( $)$ \ $displaystyle \Omega (2^{d$ 에 있음을 보여줍니다.

레퍼런스

^ ^a ^b The Computation of Fixed Points and Applications. Lecture Notes in Economics and Mathematical Systems. Vol. 124. 1976. doi:10.1007/978-3-642-50327-6. ISBN 978-3-540-07685-8.^{[페이지 필요]}
^ ^a ^b ^c Shellman, Spencer; Sikorski, K. (December 2003). "A recursive algorithm for the infinity-norm fixed point problem". Journal of Complexity. 19 (6): 799–834. doi:10.1016/j.jco.2003.06.001.
^ ^a ^b ^c ^d Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "Exponential lower bounds for finding Brouwer fix points". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254.
^ ^a ^b Sikorski, K; Woźniakowski, H (December 1987). "Complexity of fixed points, I". Journal of Complexity. 3 (4): 388–405. doi:10.1016/0885-064X(87)90008-2.
^ Sikorski, Krzysztof A. (2001). Optimal Solution of Nonlinear Equations. Oxford University Press. ISBN 978-0-19-510690-9.^{[페이지 필요]}
^ Sikorski, K. (1989). "Fast Algorithms for the Computation of Fixed Points". Robustness in Identification and Control. pp. 49–58. doi:10.1007/978-1-4615-9552-6_4. ISBN 978-1-4615-9554-0.
^ Huang, Z; Khachiyan, L; Sikorski, K (June 1999). "Approximating Fixed Points of Weakly Contracting Mappings". Journal of Complexity. 15 (2): 200–213. doi:10.1006/jcom.1999.0504.
^ Shellman, Spencer; Sikorski, K. (June 2002). "A Two-Dimensional Bisection Envelope Algorithm for Fixed Points". Journal of Complexity. 18 (2): 641–659. doi:10.1006/jcom.2001.0625.
^ Shellman, Spencer; Sikorski, K. (September 2003). "Algorithm 825: A deep-cut bisection envelope algorithm for fixed points". ACM Transactions on Mathematical Software. 29 (3): 309–325. doi:10.1145/838250.838255. S2CID 7786886.
^ Kellogg, R. B.; Li, T. Y.; Yorke, J. (September 1976). "A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational Results". SIAM Journal on Numerical Analysis. 13 (4): 473–483. doi:10.1137/0713041.
^ Smale, Steve (July 1976). "A convergent process of price adjustment and global newton methods". Journal of Mathematical Economics. 3 (2): 107–120. doi:10.1016/0304-4068(76)90019-7.
^ Scarf, Herbert (September 1967). "The Approximation of Fixed Points of a Continuous Mapping". SIAM Journal on Applied Mathematics. 15 (5): 1328–1343. doi:10.1137/0115116.
^ H. 스카프는 첫 번째 알고리즘 증명을 발견했습니다.
^ Kuhn, Harold W. (1968). "Simplicial Approximation of Fixed Points". Proceedings of the National Academy of Sciences of the United States of America. 61 (4): 1238–1242. doi:10.1073/pnas.61.4.1238. JSTOR 58762. PMC 225246. PMID 16591723.
^ Merrill, Orin Harrison (1972). Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-continuous Point to Set Mappings (Thesis). OCLC 570461463. NAID 10006142329.
^ Eaves, B. Curtis (December 1972). "Homotopies for computation of fixed points". Mathematical Programming. 3–3 (1): 1–22. doi:10.1007/BF01584975. S2CID 39504380.
^ Gale, David (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly. 86 (10): 818–827. doi:10.2307/2320146. JSTOR 2320146.
^ ^a ^b ^c ^d Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881.
^ Chen, Xi; Deng, Xiaotie (October 2009). "On the complexity of 2D discrete fixed point problem". Theoretical Computer Science. 410 (44): 4448–4456. doi:10.1016/j.tcs.2009.07.052. S2CID 2831759.
^ Sikorski, K. (June 1984). "Optimal solution of nonlinear equations satisfying a Lipschitz condition". Numerische Mathematik. 43 (2): 225–240. doi:10.1007/BF01390124. S2CID 120937024.
^ Roughgarden, Tim; Weinstein, Omri (2016). "On the Communication Complexity of Approximate Fixed Points". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 229–238. doi:10.1109/FOCS.2016.32. ISBN 978-1-5090-3933-3. S2CID 87553.

진일보한 내용

Yannakakis, Mihalis (May 2009). "Equilibria, fixed points, and complexity classes". Computer Science Review. 3 (2): 71–85. doi:10.1016/j.cosrev.2009.03.004.

[:1-1] The Computation of Fixed Points and Applications. Lecture Notes in Economics and Mathematical Systems. Vol. 124. 1976. doi:10.1007/978-3-642-50327-6. ISBN 978-3-540-07685-8.^{[페이지 필요]}

[:3-2] Shellman, Spencer; Sikorski, K. (December 2003). "A recursive algorithm for the infinity-norm fixed point problem". Journal of Complexity. 19 (6): 799–834. doi:10.1016/j.jco.2003.06.001.

[:0-3] Hirsch, Michael D; Papadimitriou, Christos H; Vavasis, Stephen A (December 1989). "Exponential lower bounds for finding Brouwer fix points". Journal of Complexity. 5 (4): 379–416. doi:10.1016/0885-064X(89)90017-4. S2CID 1727254.

[:5-4] Sikorski, K; Woźniakowski, H (December 1987). "Complexity of fixed points, I". Journal of Complexity. 3 (4): 388–405. doi:10.1016/0885-064X(87)90008-2.

[:4-5] Sikorski, Krzysztof A. (2001). Optimal Solution of Nonlinear Equations. Oxford University Press. ISBN 978-0-19-510690-9.^{[페이지 필요]}

[6] Sikorski, K. (1989). "Fast Algorithms for the Computation of Fixed Points". Robustness in Identification and Control. pp. 49–58. doi:10.1007/978-1-4615-9552-6_4. ISBN 978-1-4615-9554-0.

[7] Huang, Z; Khachiyan, L; Sikorski, K (June 1999). "Approximating Fixed Points of Weakly Contracting Mappings". Journal of Complexity. 15 (2): 200–213. doi:10.1006/jcom.1999.0504.

[8] Shellman, Spencer; Sikorski, K. (June 2002). "A Two-Dimensional Bisection Envelope Algorithm for Fixed Points". Journal of Complexity. 18 (2): 641–659. doi:10.1006/jcom.2001.0625.

[9] Shellman, Spencer; Sikorski, K. (September 2003). "Algorithm 825: A deep-cut bisection envelope algorithm for fixed points". ACM Transactions on Mathematical Software. 29 (3): 309–325. doi:10.1145/838250.838255. S2CID 7786886.

[10] Kellogg, R. B.; Li, T. Y.; Yorke, J. (September 1976). "A Constructive Proof of the Brouwer Fixed-Point Theorem and Computational Results". SIAM Journal on Numerical Analysis. 13 (4): 473–483. doi:10.1137/0713041.

[11] Smale, Steve (July 1976). "A convergent process of price adjustment and global newton methods". Journal of Mathematical Economics. 3 (2): 107–120. doi:10.1016/0304-4068(76)90019-7.

[12] Scarf, Herbert (September 1967). "The Approximation of Fixed Points of a Continuous Mapping". SIAM Journal on Applied Mathematics. 15 (5): 1328–1343. doi:10.1137/0115116.

[13] H. 스카프는 첫 번째 알고리즘 증명을 발견했습니다.

[14] Kuhn, Harold W. (1968). "Simplicial Approximation of Fixed Points". Proceedings of the National Academy of Sciences of the United States of America. 61 (4): 1238–1242. doi:10.1073/pnas.61.4.1238. JSTOR 58762. PMC 225246. PMID 16591723.

[15] Merrill, Orin Harrison (1972). Applications and Extensions of an Algorithm that Computes Fixed Points of Certain Upper Semi-continuous Point to Set Mappings (Thesis). OCLC 570461463. NAID 10006142329.

[16] Eaves, B. Curtis (December 1972). "Homotopies for computation of fixed points". Mathematical Programming. 3–3 (1): 1–22. doi:10.1007/BF01584975. S2CID 39504380.

[17] Gale, David (1979). "The Game of Hex and Brouwer Fixed-Point Theorem". The American Mathematical Monthly. 86 (10): 818–827. doi:10.2307/2320146. JSTOR 2320146.

[:2-18] Chen, Xi; Deng, Xiaotie (2005). "On algorithms for discrete and approximate brouwer fixed points". Proceedings of the thirty-seventh annual ACM symposium on Theory of computing. pp. 323–330. doi:10.1145/1060590.1060638. ISBN 1581139608. S2CID 16942881.

[19] Chen, Xi; Deng, Xiaotie (October 2009). "On the complexity of 2D discrete fixed point problem". Theoretical Computer Science. 410 (44): 4448–4456. doi:10.1016/j.tcs.2009.07.052. S2CID 2831759.

[20] Sikorski, K. (June 1984). "Optimal solution of nonlinear equations satisfying a Lipschitz condition". Numerische Mathematik. 43 (2): 225–240. doi:10.1007/BF01390124. S2CID 120937024.

[21] Roughgarden, Tim; Weinstein, Omri (2016). "On the Communication Complexity of Approximate Fixed Points". 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). pp. 229–238. doi:10.1109/FOCS.2016.32. ISBN 978-1-5090-3933-3. S2CID 87553.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

Search