ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
HOÀNG THỊ KIM NGỌC
NGHIÊN CỨU HIỆU CHỈNH HÓA
TRONG BÀI TOÁN CÂN BẰNG LUẬN VĂN THẠC SĨ TOÁN HỌC
Mã số: 60. 46. 36
LUẬN VĂN THẠC SĨ TOÁN HỌC

Người hướng dẫn khoa học:
GS. TSKH LÊ DŨNG MƯU

THÁI NGUYÊN - 2009
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 3
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 5
[4]
R R
n
n
a, b n
R
n

, λ
2
≥ 0.
A ⊂ R
n
x
0
∈ clA
N
C
(x
0
) =

t ∈ R
n
:

t, x − x
0

≤ 0, ∀x ∈ A

A x
0
A ⊆ R
n
d = 0
A x ∈ A
{x + λd | λ ≥ 0} ⊂ A.

, λ
1
, λ
2
> 0
B A
A B A B
A
∀a, b ∈ A x = λa + (1 − λ)b ∈ B, 0 < λ < 1 ⇒ a, b ∈ B
0
1
A x
x =

i∈I
λ
i
v
i
+

j∈J
β
j
d
j

i∈I
λ
i


≤ λf(x) + (1 − λ)f(y),
x, y ∈ X λ ∈ [0, 1]
f X
f

λx + (1 − λ)y

< λf(x) + (1 − λ)f(y),
x, y ∈ X, x = y λ ∈ (0, 1)
f β > 0 X
f

λx + (1 − λ)y

≤ λf(x) + (1 − λ)f(y) −β(1 − λ)λ  x − y 
2
,
x, y ∈ X λ ∈ (0, 1)
f X ∀α ∈ R
L
α
(f) = {x ∈ X : f(x) ≤ α}
f A g
B A ∩ B
a, λf + βg, ∀λ, β ≥ 0,
b, max(f, g).
1.1.3
A
A

f A

∇f(x
∗
), y −x
∗

≥ 0, ∀y ∈ A.
1.1.5 1.1.6 f A
min
x∈A
f(x)
f A
y
∗
∈ R
n
f x
∗
∈ A
f(x) ≥ f(x
∗
) +

y
∗
, x − x
∗

, ∀x ∈ A.

∗
) ≤ f(x), ∀x ∈ D ∩U x
∗
f D f(x
∗
) ≤ f(x), ∀x ∈ D
a,
b, x
∗
f D x
∗
∈ intD
0 ∈ ∂f(x
∗
)
[2]
K
R
n
f : K × K → R f(x, x) =
0, ∀x ∈ K
x
∗
∈ K f(x
∗
, y) ≥ 0, ∀y ∈ K.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 11
f f(x, x) = 0, ∀x ∈ K
K
J : K → R K

∗
) ≥ 0, ∀y ∈ K
⇒ J(y) ≥ J(x
∗
), ∀y ∈ K.
x
∗
∈ K (1.2)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 12
T : K → 2
R
n
T (x) ∀x ∈ K
x
∗
∈ K, ξ
∗
∈ T (x
∗
)

ξ
∗
, y −x
∗

≥ 0, ∀y ∈ K
f(x, y) := max
ξ∈T (x)


∗

≥ 0, ∀y ∈ K.
x
∗
∈ K (1.1)
x
∗
∈ K (1.1)
f(x
∗
, y) ≥ 0, ∀y ∈ K.
f(x
∗
, y) = max
ξ
∗
∈T (x
∗
)

ξ
∗
, y −x
∗

≥ 0, ∀y ∈ K.
x
∗
∈ K (1.3)

T : K → R
n
x
∗
∈ K T (x
∗
) ∈ K

T (x
∗
), x
∗

= 0.
f(x, y) :=

T (x), y − x

, ∀x, y ∈ K
(1.5) (1.1)
x
∗
∈ K (1.5)
T (x
∗
) ∈ K

T (x
∗
), x


≥ 0, ∀y ∈ K.
x
∗
∈ K (1.1)
x
∗
∈ K (1.1)
f(x
∗
, y) ≥ 0 ∀y ∈ K.
f(x
∗
, y) =

T (x
∗
), y −x
∗

, ∀y ∈ K.
K 0 ∈ K 2x
∗
∈ K
y = 0 ∈ K

T (x
∗
), −x
∗

∗
), x
∗

= 0
0 ≤

T (x
∗
), y −x
∗

=

T (x
∗
), y

−

t(x
∗
), x
∗

=

T (x
∗
), y

ξ∈T (x)

x −ξ, y −x

, ∀x, y ∈ K
(1.1) (1.6)
x
∗
∈ K (1.6)
T (x
∗
) = x
∗
.
f(x
∗
, y) =

x
∗
− T (x
∗
), y −x
∗

, ∀y ∈ K.
x
∗
∈ K (1.1)
x

) − x
∗

≥ 0, ∀y ∈ K
⇒ −  x
∗
− T (x
∗
) ≥ 0, ∀y ∈ K
⇒ x
∗
− T (x
∗
) ≤ 0, ∀y ∈ K
⇒ x
∗
= T (x
∗
), ∀y ∈ K.
x
∗
∈ K (1.6)
• T
x
∗
∈ K x
∗
= T (x
∗
).

y = (y
1
, . . . , y
p
) ∈ K
1
× . . . K
p
x[y
i
] ∈ K
1
× . . . × K
p
x[y
i
]
j
=



x
j
, ∀j = i
y
i
, ∀j = i
K = K
1

∗
∈ K (1.8)
f
i
(x
∗
) ≤ f
i
(x
∗
[y
i
]), ∀i ∈ I, ∀y
i
∈ K
i
⇒ f
i
(x
∗
[y
i
]) − f
i
(x
∗
) ≥ 0, ∀i ∈ I, ∀y
i
∈ K
i

∈ K (1.1)
f(x
∗
, y) ≥ 0, ∀y ∈ K.
p

i=1
{f
i
(x
∗
[y
i
]) − f
i
(x
∗
)} ≥ 0, ∀i ∈ K, ∀y ∈ K.
x
∗
∈ K (1.8) ∃i
0
∈ K
f
i
(x
∗
) > f
i
(x


i=1

f
i
(x
∗
[y
i
]) − f
i
(x
∗
)

< 0,
x
∗
∈ K (1.8)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 17
[2], [5]
x
∗
∈ K : f(y, x
∗
) ≤ 0, ∀y ∈ K.
f : K × K → R
a, f(x, x) = 0, ∀x ∈ K
b, f(x, .) : K → R ∀x ∈ K
x ∈ K L

λ
) = f(z
λ
, λy +(1 −λ)x
∗
)
(b)
≤λf(z
λ
, y)+ (1 −λ)f(z
λ
, x
∗
).
x
∗
x
∗
∈

y∈K
L
f
(y) =

y∈K
{x ∈ K | f(y, x) ≤ 0}
y = z
λ
∀λ ∈ [0, 1] f(z

= ∅, S
2
= [0, 2] ⇒ S
1
 S
2
b, f(x, y) = max{0, | x −y | −1} ⇒ S
1
= {1}, S
2
= [0, 2] ⇒ S
1
 S
2
 f ∀x, y ∈ K : f(x, y) ≥ 0 ⇒ f(y, x) ≤ 0
2.1.1
2.1
2.1
k = 0, x
0
∈ K r
0
=  x
0

x
k
r
k
(i)

= 0
(iii) x
k+1
x
k+1
= x
k
+ t
k

P
L
f
(y
k
)
(x
k
) − x
k

, (2.1c)
P
L
f
(y
k
)
(x
k

K
k
⊂ K
k+1
, ∀k ∈ N.
x
0
∈ K  x
0
≤ r
0
+ 1 x
0
∈ K
0
⇒ x
0
∈ K
k
, ∀k ∈ N
K
k
f f(., y
k
) K
k
y
k
∈ K
k

P
L
f
(y
k
)
(x
k
) − x
k


+∞

k=0
L
f
(y
k
) = ∅,
a, ∀x
∗
∈
+∞

k=0
L
f
(y
k

= x
k
+ t
k

P
L
f
(y
k
)
(x
k
) − x
k

 x
k+1
− x
∗

2
=  x
k
+ t
k
[P
L
f
(y

2
+ 2 t
k

x
k
− x
∗
, P
L
f
(y
k
)
(x
k
) − x
k

.
2 t
k

x
k
− x
∗
, P
L
f

) − x
∗
, P
L
f
(y
k
)
(x
k
) − x
k

= −2 t
k
 x
k
− P
L
f
(y
k
)
(x
k
) 
2
+2 t
k


k
− x
∗

2
+ t
k
2
 P
L
f
(y
k
)
(x
k
) − x
k

2
−
− 2 t
k
 x
k
− P
L
f
(y
k

.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 21
x
∗
∈ L
f
(y
k
)
(2.6)
2 t
k

P
L
f
(y
k
)
(x
k
) − x
∗
, P
L
f
(y
k
)
(x

k

2
−
− 2 t
k
 x
k
− P
L
f
(y
k
)
(x
k
) 
2
=  x
k
− x
∗

2
−t
k
(2 − t
k
)  x
k

k
=  x
k
− x
∗
+ x
∗
≤ x
k
− x
∗
 +  x
∗

⇒ {x
k
}
k≥0
c, (2.8)
t
k
(2 − t
k
)  x
k
− P
L
f
(y
k

f
(y
k
)
(x
k
) 
2
≤ x
k
− x
∗

2
−  x
k+1
− x
∗

2
.
(2.10) 0 < α(2 − α ) { x
k
− x
∗
}
k≥0
lim
k→+∞
{x

k→+∞
 x
k+1
− x
k
= 0.
{x
k
}
k≥0
x
∗
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 22
• x
k+1
= x
k
+ t
k

P
L
f(y
k
)
(x
k
) −x
k


k
)} = 0.
• {y
k
}
k≥0
{x
k
}
k≥0
∃
r > 0
 x
k
≤ r, ∀k ∈ N
(2.1d) 2.1 r
k+1
= max{r
k
,  x
k+1
}
r
k
= max{ x
0
, . . . ,  x
k
}.
r

}
k≥0
• x {x
k
}
k≥0
⊂ K K x ∈ K
{x
k
n
}
k
n
≥0
{x
k
}
k≥0
lim
k
n
→+∞
x
k
n
= x.
{y
k
n
}

y
k
n
p
≡ y
k
n
x
k
n
p
x
k
n
p
≡ x
k
n
• f(y, x) = 0?
lim
k→+∞
{x
k
−P
L
f(y
k
)
(x
k

)
(x
k
n
)

= lim
k
n
→+∞
f

y
k
n
, P
L
f(y
k
n
)
(x
k
n
)

≤ 0.
P
L
f(y

) ≤ f(y
k
, x
k
) + 
k
.
lim
k→+∞

k
= 0 f (2.12)
0 ≤ lim
k
n
→+∞
{f(y
k
n
, x
k
n
) + 
k
n
}
= f( lim
k
n
→+∞

r
k
?
r
k
r
∗
= sup
k∈N
r
k
0 < δ < 1 B(0, r
∗
+ 1 − δ) ≡ B(δ)
(2.1d)  x
k
≤ r
k
≤ r
∗
< r
∗
+1−δ, ∀k ∈ N
x ∈ intB(δ).
x ∈

intB(0, r
∗
+ 1 − δ)


k
}
k∈N
r
k
≤ r
k+1
k
0
∈ N
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 24
r
k
0
≥ r
∗
− δ
r
∗
+ 1 − δ ≤ r
k
+ 1, ∀k ≥ k
0
.

B(δ) ⊂ K
k
, ∀k ≥ k
0
.

)
= lim
k
n
→+∞
f(z, x
k
n
)
(2.16)
≤ lim
k
n
→+∞
{f(y
k
n
, x
k
n
) + 
k
n
}
= f(y, x) = 0.
f(z, x) ≤ 0, ∀z ∈

B(δ).
(2.18) x ∈ K 0 < δ < 1
x ∈

g(y) =



f(x, y) y ∈ K,
+∞ y ∈ K.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên 25