ĐẠI HỌC THÁI NGUYÊN
ĐẠI HỌC KHOA HỌC NGUYỄN VĂN HƯỞNG PHƯƠNG PHÁP ĐIỂM TRONG
GIẢI BÀI TOÁN QUY HOẠCH LỒI

LUẬN VĂN THẠC SĨ TOÁN HỌC
Chuyên ngành: Toán ứng dụng


x x
1
, x
2
, , x
k
x =
k

j=1
λ
j
x
j
, λ
j
> 0, ∀j = 1, , k,
k

j=1
λ
j
= 1.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
D D
x, y ∈ D
∀x, y ∈ D, ∀λ ∈ R =⇒ λx + (1 −λ)y ∈ D
C
C
∀x ∈ N, ∀λ

k

j=1
λ
j
x
j
, λ
j
> 0 ∀j = 1, , k,
k

j=1
λ
j
= 1.
ξ =
k−1

j=1
λ
j
.
0 < ξ < 1
x =
k−1

j=1
λ
j

> 0 j = 1, , k −1
y :=
k−1

j=1
λ
j
ξ
x
j
∈ C.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
x = ξy + λ
k
x
k
.
ξ > 0, λ
k
> 0
ξ + λ
k
=
k

j=1
λ
j
= 1,
y x

a = 0 α ∈ R
{x|a
T
x > α}
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
S ⊂ R
n
S
k + 1
S
k
:= {x ∈ R
k
|x ≥ 0,
k

j=1
x
j
≤ 1}
R
k
D := {x ∈ R
n
|a
j
, x ≤ b
j
, j = 1, , m}
A m a

(x
0
) := {ω ∈ R
n
: ω, x − x
0
 ≤ 0, ∀x ∈ D.
D x
0
−N
D
(x
0
)
D x
0
N
ε
D
(x
0
) := {ω ∈ R
n
: ω, x − x
0
 ≤ ε, ∀x ∈ D.
ε D x
0
0 ∈ N
D

n
A m ×n
a, x ≥ 0, x Ax ≥ 0 y > 0
R
m
a = A
T
y
a, x = 0, Ax ≥ 0
a A
D = ∅ y
d
D
(y) := inf
x∈D
x − y.
d
D
(y) y D π ∈ D
d
D
(y) = y − π π y D
π = P
D
(y)
P
D
(y) y D
min
x∈D

(y) y D
P
D
(x) − P
D
(y) ≤ x − y, ∀x, y ∈ R
n
P
D
(x) − P
D
(y)
2
≤ P
D
(x) − P
D
(y), x − y, ∀x, y ∈ R
n
3x
1
+ 2x
2
+ x
3
= 1
x
1
− 4x
2

f : R
n
−→ R ∪{+∞}
f(λx + (1 −λ)y) ≤ λf(x) + (1 − λ)f(y), ∀x, y ∈ C, ∀λ ∈ (0; 1)
f : R
n
−→ R ∪{+∞} C
f(λx + (1 −λ)y) < λf(x) + (1 −λ)f(y), ∀x, y ∈ C, ∀λ ∈ (0; 1)
f domf = ∅
f(x) > −∞ x f epif
R
n+1
f(x) := a
T
x + α a ∈ R
n
α ∈ R
f
α = 0
C = ∅
δ
C
(x) :=



0 x ∈ C
+∞ x ∈ C
δ
C

∈ (f(x), α) β

∈ (f(y), β). (x, α

) (y, β

) epif
epif
((1 − λ)x + λy, (1 − λ)α

+ λβ

) ∈ epif.
f((1 −λ)x + λy) ≤ (1 − λ)α

+ λβ

≤ (1 − λ)α + λβ
(x, µ) (y, v) epif λ ∈ (0; 1)
∀ > 0
f(x) < µ + , f(y) < v + 
f((1 −λ)α

+ λβ

) < (1 − λ)(µ + ) + λ(v + ) = (1 − λ)µ + λv + 
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
 > 0  −→ 0
f((1 −λ)α


l
f
(α) f(x) < α, f(y) < α f
α ∈ (0; 1)
f(λx + (1 −λ)y) < λα + (1 − λ)α = α.
λx + (1 − λ)y ∈ l
f
(α)
L
f
(α) = ∩
µ>α
l
f
(µ),
f : R
n
−→ R
E x {x
k
} ⊂ E x
k
−→ x
lim inf f(x
k
) ≥ f(x).
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
f E x −f
E x x
k

j
, α) ∈ epif
epif (x, α) ∈ epif x ∈ L
f
(α)
→ x
j
→ x lim inf f(x
j
) < f(x)
α < f(x) f(x
j
) ≤ α j x
j
∈ L
f
(α) j
x
j
→ x L
f
(α) x ∈ L
f
(α) f(x) < α
α < f(x)
→ (x
j
, µ
j
) ∈ epif (x

, λ
j
≥ 0,
n+1

j=1
λ
j
= 1.
f
f(x) ≤ max{f(ν
j
)|j = 1, , n + 1}.
S f
x
0
∈ intS f
int(domf).
f R
n
D ⊆ domf
f D
D
x ∈ D
x = 0 {x
k
} ∈ D x = 0 G 2
n
−
n− n

1
x
k
= (1 −

ν∈V
1
λ
k
(ν))0 +

ν∈V
1
λ
k
(ν)ν,
λ
k
(ν) ≥ 0

ν∈V
1
λ
k
(ν) ≤ 1 x
k
→ 0 λ
k
(ν) → 0
ν ∈ V

f

(a) f(a) f a
f : D −→ R D
f D
f(x) + f(x), y − x ≤ f(y), ∀x, y ∈ D.
f f D ∀x ∈ A
H(x) f x
y
T
H(x)y ≥ 0, ∀x ∈ D, y ∈ R
n
.
f(x) =
1
2
x
T
Qx, Q
f : R
n
−→ R ∪{+∞} x
∗
∈ R
n
f x
x
∗
, z −x+ f(x) ≤ f(z), ∀z.
f x ∂f(x)

(x, y) = sup
x
∗
∈∂f (x)
x
∗
, y, ∀y.
f R
n
x ∈ dom(∂f),
f(x) = f(x) ∂f(x) = ∂f(x).
x
∗
∈ ∂f(x) ⇐⇒ x
∗
, z −x+ f(x) ≤ f(z), ∀z.
y z = x + λy, λ > 0
x
∗
, λy + f(x) ≤ f(x + λy).
x
∗
, y ≤
f(x + λy) − f(x)
λ
, ∀λ > 0.
f

(x, y)
x

p ∈ ∂f(x) f

(x, .)
f

(x, y) = sup
p∈∂f (x)
p, y.
x ∈ dom(∂f) x
∗
∈ ∂f(x) f
x
∗
∈ ∂f(x)
f(x) ≥ f(x) = f
∗∗
(x) ≥ x
∗
, x − f
∗
(x
∗
) = f(x).
f(x) = f(x)
y
∗
∈ ∂f(x) z
f(z) ≥ f(z) ≥ f(x) + y
∗
, z −x = f(x) + y

x ∈ domf ∂f(x) = ∅.
x ∈ int(domf) ∂f(x) = ∅ ∂f(x) =
∅ x ∈ ri(domf)
z ∈ domf f(z) < +∞ x ∈ domf
f(x) = +∞ x
∗
x
∗
, z −x+ f(x) ≤ f(z) < +∞.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
∂f(x) = ∅.
x ∈ int(domf) (x, f(x))
epif f
epif (x, f(x)) p ∈ R
n
, t ∈ R
p, x + tf(x) ≤ p, y + tµ, ∀(y, µ) ∈ epif. (1.2)
t = 0 t = 0
p, x ≤ p, y, ∀y ∈ domf.
x ∈ int(domf) p = 0 t = 0
t > 0 t < 0 µ → +∞
t > 0 µ = f(y) x
∗
= −
p
t
x
∗
, x + f(x) ≤ x
∗

f

(x, d) ≥ x
∗
, d, ∀d. (1.3)
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
e
i
i(i = 1, , n) R
n
e
i
d = e
i
i = 1, , n x
∗
i
≤ f

(x, e
i
). d = −e
i
i = 1, , k −x
∗
i
≤ f

(x, −e
i

i
) i = 1, , n ∂f(x)
∂f(x) x ∈
ri(domf) ∂f(x) x ∈ domf x ∈ ri(domf)
x domf domf
domf x p ∈ R
n
, p = 0
p
T
x ≥ p
T
z, ∀z ∈ domf.
x
∗
∈ ∂f(x)
f(z) − f(x) ≥ x
∗
, z −x ≥ x
∗
+ λp, z −x, ∀λ ≥ 0, ∀z.
x
∗
+ λp ∈ ∂f(x) λ ≥ 0
∂f(x) x ∈ ri (domf)
f R
n
C ⊂ ri(domf) ∪
x∈C
∂f(x)

D f
(P )
D f D
D
D := {x ∈ X : g
j
(x) ≤ 0, h
i
(x) = 0, j = 1, , m, i = 1, , p}, (2.1)
∅ = X ⊆ R
n
g
j
, h
i
: R
n
−→ R(j = 1, , m, i = 1, , p)
D
x x
j
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
j f(x)
x
D
x
∗
∈ D
U x
∗

F
+
= [f(x
∗
), +∞]
F
+
(D) t
∗
= inf F
+
(D) t > −∞
F
+
(D) t
∗
∈ F
+
(D) x
∗
∈ D f(x
∗
) = t
∗
x
∗
f D
D f
D
α := inf

D f
D x
∗
0 ∈ ∂f(x
∗
) + N
D
(x
∗
), (2.2)
N
D
(x
∗
) D x
∗
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên

Trích đoạn Trường hợp khả vi

---