1274
/HPPD
/HW
E
EH D VWULFWO\ FRQYH[ DQG VPRRWK %DQDFK VSDFH 7KHQ IRU DOO
x, y
∈
E φ
(
x, y
) = 0
LI DQG
/HPPD
/HW
C
EH D QRQHPSW\ FORVHG FRQYH[ VXEVHW RI D VPRRWK %DQDFK VSDFH
E
DQG
x
∈
E
7KHQ
0
C
0
0
/HPPD
/HW
E
EH D UHIOH[LYH VWULFWO\ FRQYH[ DQG VPRRWK %DQDFK VSDFH
C
EH D QRQHPSW\ FORVHG FRQYH[
C
C
/HPPD
/HW
E
EH D VPRRWK DQG VWULFWO\ FRQYH[ %DQDFK VSDFH DQG
C
EH D QRQHPSW\ FORVHG FRQYH[ VXEVHW
RI
E
6XSSRVH
T
:
C
→
N
(
C
)
LV D UHODWLYHO\ QRQH[SDQVLYH PXOWL YDOXHG PDSSLQJ 7KHQ
F
(
T
)
LV D FORVHG
/HPPD
/HW
E
EH D XQLIRUPO\ FRQYH[ DQG VPRRWK %DQDFK VSDFH DQG
r >
0
7KHQ WKHUH H[LVWV D VWULFWO\
LQFUHDVLQJ FRQWLQXRXV DQG FRQYH[ IXQFWLRQ
g
: [0
,
∞
]
→
[0
,
∞
]
ZLWK
g
(0) = 0
VXFK WKDW
g
(
y
−
z
)
≤
φ
(
y, z
)
,
∀
y, z
∈
B
r
(0) =
{
x
≤
r
}
.
/HPPD
/HW
E
EH D XQLIRUPO\ FRQYH[ %DQDFK VSDFH DQG
r >
0
7KHQ WKHUH H[LVWV D VWULFWO\ LQFUHDVLQJ
FRQWLQXRXV DQG FRQYH[ IXQFWLRQ
h
: [0
,
∞
)
→
[0
,
∞
)
ZLWK
h
(0) = 0
VXFK WKDW
αx
+
βy
2
≤
α x
2
+
β y
2
−
αβh
(
x
−
y
)
IRU DOO
x, y
∈
B
r
:=
{
z
∈
X
:
z
≤
r
DQG DOO
α, β
∈
[0
,
1]
ZLWK
α
+
β
= 1
.
/HPPD
/HW
C
EH D QRQHPSW\ FORVHG FRQYH[ VXEVHW RI D XQLIRUPO\ VPRRWK VWULFWO\ FRQYH[ UHDO %DQDFK
VSDFH
E
DQG
A
:
C
→
E
∗
EH D FRQWLQXRXV PRQRWRQH PDSSLQJ )RU DQ\
r >
0
GHILQH D PDSSLQJ
F
r
:
E
→
C
DV IROORZV
F
r
x
=
{
z
∈
C
:
y
−
z, Az
+
1
r
y
−
z, Jz
−
Jx
≥
0
,
∀
y
∈
C
}
IRU DOO
x
∈
C
7KHQ WKH IROORZLQJ KROG
F
r
LV D VLQJOH YDOXHG PDSSLQJ
F
(
F
r
) =
V I
(
A, C
)
V I
(
A, C
)
LV D FORVHG DQG FRQYH[ VXEVHW RI
C
φ
(
q, F
r
x
) +
φ
(
F
r
x, x
)
≤
φ
(
q, x
)
IRU DOO
q
∈
F
(
F
r
)
GHWDLOV
,I
E
LV DQ DUELWUDU\ %DQDFK VSDFH WKHQ
J
LV PRQRWRQH DQG ERXQGHG
,I
E
LV D VWULFWO\ FRQYH[ WKHQ
J
LV VWULFWO\ PRQRWRQH
,I
E
LV D VPRRWK WKHQ
J
LV VLQJOH YDOXHG DQG VHPL FRQWLQXRXV
,I
E
LV XQLIRUPO\ VPRRWK WKHQ
J
LV XQLIRUPO\ QRUP WR QRUP FRQWLQXRXV RQ HDFK ERXQGHG VXEVHW
RI
E
,I
E
LV UHIOH[LYH VPRRWK DQG VWULFWO\ FRQYH[ WKHQ WKH QRUPDOL]HG GXDOLW\ PDSSLQJ
J
=
J
2
LV
VLQJOH YDOXHG RQH WR RQH DQG RQWR
,I
E
LV UHIOH[LYH VPRRWK DQG VWULFWO\ FRQYH[ WKHQ
J
−
1
LV DOVR VLQJOH YDOXHG RQH WR RQH RQWR DQG
LW LV WKH GXDOLW\ PDSSLQJ IURP
E
∗
LQWR
E
,I
E
LV XQLIRUPO\ VPRRWK WKHQ
E
LV VPRRWK DQG UHIOH[LYH
E
LV XQLIRUPO\ VPRRWK LI DQG RQO\ LI
E
∗
LV XQLIRUPO\ FRQYH[
RQO\ LI
x
=
y
> @
x
= Π
x
LI DQG RQO\ LI
x
−
y, Jx
−
Jx
≥
0
IRU DOO
y
∈
C
> @
VXEVHW RI
E
DQG
x
∈
E.
7KHQ
φ
(
y,
Π
x
) +
φ
(Π
x, x
)
≤
φ
(
y, x
)
IRU DOO
y
∈
C
> @
FRQYH[ VXEVHW RI
C
> @
6HH > @ IRU PRUH GHWDLO
6HH > @ IRU PRUH GHWDLO
6HH > @ IRU PRUH GHWDLO
5HPDUN
:H UHPDUN WKDW LI
E
LV D %DQDFK VSDFH 7KHQ WKH IROORZLQJ DUH ZHOO NQRZQ VHH > @ IRU PRUH
