1273
$ PDSSLQJ
T
:
C
→
C
LV VDLG WR EH
QRQH[SDQVLYH
LI
Tx
−
T y
≤
x
−
y
IRU DOO
x, y
∈
C
$Q HOHPHQW
p
∈
C
LV FDOOHG D
IL[HG SRLQW
RI
T
LI
T p
=
p
'HQRWH E\
F
(
T
)
WKH VHW RI IL[HG SRLQWV RI
T
WKDW
D VHTXHQFH
{
x
n
}
ZKLFK FRQYHUJHV ZHDNO\ WR
p
VXFK WKDW OLP
n
→∞
x
n
−
Tx
n
= 0
7KH DV\PSWRWLF IL[HG
SRLQW VHW RI
T
LV GHQRWHG E\
F
(
T
)
5
F
(
T
)
LV QRQHPSW\
5
φ
(
p, Tx
)
≤
φ
(
p, x
)
IRU DOO
x
∈
C
DQG
p
∈
F
(
T
)
5
F
(
T
) =
F
(
T
)
$ PDSSLQJ
T
:
C
→
C
LV FDOOHG
UHODWLYHO\ TXDVL QRQH[SDQVLYH
RU
TXDVL
φ
QRQH[SDQVLYH
LI WKH
FRQGLWLRQV 5 DQG 5 KROG
2Q WKH DXWKRU KDQG WKH
JHQHUDOL]HG SURMHFWLRQ
Π
C
:
E
→
C
LV D PDSSLQJ WKDW DVVLJQV WR DQ DUELWUDU\
SRLQW
x
∈
E
WKH PLQLPXP SRLQW RI WKH IXQFWLRQDO
φ
(
x, y
)
WKDW LV
Π
C
x
= ¯
x
ZKHUH
¯
x
LV WKH VROXWLRQ WR WKH
PLQLPL]DWLRQ SUREOHP
φ
(¯
x, x
) =
LQI
y
∈
C
φ
(
y, x
)
.
7KH H[LVWHQFH DQG XQLTXHQHVV RI WKH RSHUDWRU
Π
C
IROORZV IURP WKH SURSHUWLHV RI WKH IXQFWLRQDO
φ
(
y, x
)
DQG UHIOH[LYH %DQDFK VSDFH WKHQ
Π
C
LV D FORVHG UHODWLYHO\ TXDVL QRQH[SDQVLYH PDSSLQJ IURP
E
RQWR
C
ZLWK
C
/HW
N
(
C
)
DQG
CB
(
C
)
GHQRWHG WKH IDPLO\ RI QRQHPSW\ VXEVHWV DQG QRQHPSW\ FORVHG ERXQGHG VXEVHWV
RI
C
UHVSHFWLYHO\ 7KH
+DXVGRUII PHWULF
RQ
CB
(
C
)
LV GHILQHG E\
H
(
A
1
, A
2
) =
PD[
{
VXS
x
∈
A
2
d
(
x, A
1
)
,
VXS
y
∈
A
1
d
(
y, A
2
)
}
IRU DOO
A
1
, A
2
∈
CB
(
C
)
ZKHUH
d
(
x, A
1
) =
LQI
{
x
−
y
;
y
∈
A
1
}
$Q HOHPHQW
p
∈
C
LV FDOOHG D
IL[HG SRLQW
RI
T
:
C
→
N
(
C
)
LI
p
∈
F
(
T
)
ZKHUH
F
(
T
) :=
{
p
∈
C
:
p
∈
T
(
p
)
}
$ SRLQW
p
∈
C
LV FDOO DQ
DV\PSWRWLF IL[HG SRLQW
RI D PXOWL YDOXHG PDSSLQJ
T
:
C
→
N
(
C
)
LI
WKHUH H[LVWV D VHTXHQFH
{
x
n
}
LQ
C
ZKLFK FRQYHUJHV ZHDNO\ WR
p
DQG OLP
n
→∞
d
(
x
n
, T
(
x
n
)) = 0
7KH DV\PSWRWLF
IL[HG SRLQW VHW RI
T
LV GHQRWHG E\
F
(
T
)
$ PXOWL YDOXHG PDSSLQJ
T
:
C
→
N
(
C
)
LV VDLG WR EH
UHODWLYHO\ QRQH[SDQVLYH
LI
´
R F
(
T
)
LV QRQHPSW\
´
R φ
(
p, z
)
≤
φ
(
p, x
)
IRU DOO
x
∈
C z
∈
T
(
x
)
DQG
p
∈
F
(
T
)
´
R F
(
T
) =
F
(
T
)
WKHRUHPV IRU WKH ,VKLNDZD LWHUDWLRQ VFKHPH LQYROYLQJ TXDVL QRQH[SDQVLYH PXOWL YDOXHG PDSSLQJV LQ XQLIRUPO\
FRQYH[ %DQDFK VSDFHV ,WHUDWLYH PHWKRGV IRU DSSUR[LPDWLQJ IL[HG SRLQWV RI PXOWL YDOXHG PDSSLQJV LQ %DQDFK
SUREOHP DQG WKH VHW RI FRPPRQ IL[HG SRLQWV RI UHODWLYHO\ QRQH[SDQVLYH PXOWL YDOXHG PDSSLQJV 0RWLYDWHG E\
RWKHU UHFHQW ZRUNV LQ WKLV SDSHU ZH LQWURGXFH DQ LWHUDWLYH SURFHVV IRU WKH DSSUR[LPDWLRQ RI D FRPPRQ HOHPHQW
RI WKH VHW RI IL[HG SRLQW RI UHODWLYHO\ QRQH[SDQVLYH PXOWL YDOXHG PDSSLQJ DQG WKH VROXWLRQ VHW RI YDULDWLRQDO
LQHTXDOLW\ SUREOHP :H SURYH WKDW DQ LWHUDWLYH VHTXHQFH FRQYHUJHV VWURQJO\ WR D FRPPRQ HOHPHQW RI WKH VHW
RI IL[HG SRLQW RI UHODWLYHO\ QRQH[SDQVLYH PXOWL YDOXHG PDSSLQJ DQG WKH VROXWLRQ VHW RI YDULDWLRQDO LQHTXDOLW\
SUREOHP LQ %DQDFK VSDFHV
:H DOVR QHHG WKH IROORZLQJ OHPPDV IRU WKH SURRI RI RXU PDLQ UHVXOWV
LV
F
(
T
) =
{
x
∈
C
:
Tx
=
x
}
$ SRLQW
p
LQ
C
LV FDOOHG DQ
DV\PSWRWLF IL[HG SRLQW
RI
T
> @ LI
C
FRQWDLQV
$ PDSSLQJ
T
:
C
→
C
LV FDOOHG
UHODWLYHO\ QRQH[SDQVLYH
> y @ LI
DQG WKH VWULFW PRQRWRQLFLW\ RI WKH PDSSLQJ
J
VHH IRU H[DPSOH > y
@ ,I
E
LV D VPRRWK VWULFWO\ FRQYH[
F
(Π ) =
C
> @
6DVWU\ DQG %DEX > @ SURYH WKDW WKH 0DQQ DQG ,VKLNDZD LWHUDWLRQ VFKHPHV IRU D PXOWL YDOXHG PDSSLQJ
T
ZLWK D IL[HG SRLQW
p
FRQYHUJH WR D IL[HG SRLQW
q
RI
T
3DQ\DQDN > @ H[WHQGHG WKH UHVXOW RI 6DVWU\ DQG
%DEX WR XQLIRUPO\ FRQYH[ %DQDFK VSDFHV ,Q
6KDK]DG DQG =HJH\H > @ SURYHG VWURQJ FRQYHUJHQFH
VSDFHV KDYH EHHQ VWXGLHG E\ PDQ\ DXWKRUV VHH > y @ IRU PRUH GHWDLO 5HFHQWO\ +RPDHLSRXU DQG 5D]DQL
> @ LQWURGXFHG DQ LWHUDWLYH VHTXHQFH IRU ILQGLQJ D FRPPRQ HOHPHQW RI WKH VHW RI VROXWLRQV RI DQ HTXLOLEULXP
