Chương 3. Bài toán tối ưu có điều kiện cho bởi phương trình và bất phương trình
3.3. Điều kiện tối ưu cấp hai
Cho x∗ ∈ X, nếu
dT∇f (x∗) > 0, ∀0̸= d ∈ SF D(x∗, X), (3.79) thì x∗ là cực tiểu địa phương chặt của Bài toán (3.1)-(3.3). Nếu
tồn tại d ∈ SF D(x∗, X) sao cho dT∇f (x∗) < 0, (3.80) thì theo Định lý 3.1 x∗ không thể là cực tiểu địa phương của Bài toán (3.1)- (3.3). Kết quả này nói với chúng ta rằng miễn là (3.79) hoặc (3.80) đúng thì những điều kiện tối ưu cấp một sẽ được sử dụng để xác định xem x∗ có phải là cực tiểu địa phương hay không. Tuy nhiên, chúng ta không thể biết x∗ là cực tiểu địa phương hay không nếu chỉ dùng đạo hàm cấp một khi cả (3.79) và (3.80) đều sai, nghĩa là khi
dT∇f (x∗) ≥ 0, ∀d ∈ SF D(x∗, X) ; (3.81)
dT∇f (x∗) = 0, ∃d ∈ SF D(x∗, X)d ̸= 0. (3.82) Trong những trường hợp này, thông tin về đạo hàm cấp hai là cần thiết. Giả sử rằng điều kiện ràng buôc CQ (3.35) đúng. Theo (3.81), (3.35) và Bổ đề Farkas (3.21) thì x∗ là một điểm KKT. Từ (3.82) và định nghĩa của nhân tử Lagrange, tồn tại ∃d ∈ SF D(x∗, X), d ̸= 0, sao cho
dT∇f (x∗) =
m
X
i=1
λ∗idT∇ci(x∗) = 0. (3.83) Vì SF D(x∗, X) ⊆ LF D(x∗, X), bằng cách sử dụng Định nghĩa 3.7, ta có (3.83) tương đương với
λ∗idT∇ci(x∗) = 0, ∀ i ∈ I(x∗). (3.84) Chúng ta đưa ra những định nghĩa sau. Cho x∗ là một điểm KKT của Bài toán (3.1)-(3.3) và λ∗ là vector nhân tử Lagrange tương ứng. Ta định nghĩa tập hợp các điều kiện hoạt động mạnh như sạu:
I+(x∗) =i|i ∈ I(x∗) với λ∗i > 0 . (3.85) Ta có I+(x∗) ⊆I (x∗).
Định nghĩa 3.11. Cho x∗ là một điểm KKT của Bài toán (3.1)-(3.3), và λ∗ là vector nhân tử Lagrange tương ứng. Nếu tồn tại dãy dk (k = 1,2, . . .) và dãy δk (k = 1,2, . . .) để cho
xk = x∗ + δkdk ∈ X (3.86) thỏa mãn
ci(xk) = 0, i ∈ E∪ I+(x∗), (3.87) ci(xk) ≥ 0, i ∈ I(x∗)\I+(x∗), (3.88) và dk → d, δk → 0, thì d được gọi là một hướng ràng buộc vô hiệu dãy tại x∗. Tập hợp tất cả các hướng ràng buộc vô hiệu dãy tại x∗ được kí hiệu là S(x∗, λ∗),
S(x∗, λ∗) =
d
xk = x∗ + δkdk ∈ X, δk > 0, δk →0, dk →d, ci(xk) = 0, i ∈ E∪ I+(x∗),
ci(xk) ≥ 0, i ∈ I(x∗)−I+(x∗).
(3.89) Bổ đề 3.3. Đặt H = {d|d ∈ SF D(x∗, X);Pmi=1λ∗ici(xk) = 0}. Khi đó, ta có S(x∗, λ∗) = H.
Chứng minh. Giả sử d ∈ S(x∗, λ∗) ⇒ xk = x∗ + δkdk ∈ X, δk > 0, δk → 0, dk → d ⇒d ∈ SF D(x∗, X). Ta thấy rằng (3.87)-(3.88) kéo theo rằng
m
X
i=1
λ∗ici(x∗ +δkdk) = 0. (3.90)
Thật vậy
m
X
i=1
λ∗ici(x∗ + δkdk)
=
m
X
i=1
λ∗ici(xk) = X
i∈E
λ∗ici(xk) +X
i∈I
λ∗ici(xk) =X
i∈I
λ∗ici(xk)
= X
i∈I(x∗)
λ∗ici(xk) + X
i∈I\I(x∗)
λ∗ici(xk) = X
i∈I(x∗)
λ∗ici(xk)
= X
i∈I+(x∗)
λ∗ici(xk) + X
i∈I(x∗)\I+(x∗)
λ∗ici(xk) = 0.
Vậy d∈ H.
Bây giờ giả sử d ∈ H ⇒d ∈ SF D(x∗, X) ⇒xk = x∗ +δkdk ∈ X, δk >
0, δk →0, dk → d.Hơn nữa,Pm
i=1λ∗ici(xk) = 0 ⇒λ∗ici(xk) = 0, i ∈ I.Với i ∈ I+(x∗)thì ta cóλ∗i > 0nênci(xk) = 0.Vậyci(xk) = 0, i ∈ E∪ I+(x∗). Ngoài ra ta có ci(xk) ≥ 0, i∈ I(x∗)−I+(x∗) (vì I(x∗)−I+(x∗) ⊆ I). Vì
vậy, ta có d ∈ S(x∗, λ∗). □
Từ Bổ đề 3.3, ta có:
S(x∗, λ∗) = (
d, d ∈ SF D(x∗, X);
m
X
i=1
λ∗ici(xk) = 0 )
. (3.91)
Từ đây suy ra: S(x∗, λ∗) ⊆ SF D(x∗, X).
Định nghĩa 3.12. Cho x∗ là một điểm KKT của Bài toán (3.1)-(3.3) và λ∗ là vector nhân tử Lagrange tương ứng. Nếu d là một hướng tuyến tính chấp nhận được tạix∗ và (3.84) đúng, thìd được gọi là một hướng ràng buộc vô hiệu tuyến tính tại x∗. Tập hợp tất cả các hướng ràng buộc vô hiệu tuyến tính hóa tại x∗ được kí hiệu là G(x∗, λ∗),
G(x∗, λ∗) =
d
d ̸= 0,
dT∇ci(x∗) = 0, i∈ E∪I+(x∗), dT∇ci(x∗) ≥ 0, i ∈ I(x∗)\I+(x∗)
. (3.92)
Nếu nhân tử Lagrange tại x∗ là duy nhất, G(x∗, λ∗) có thể viết là G(x∗). Bổ đề 3.4. Đặt F = d|d∈ LF D(x∗, X; dT∇ci(x∗) = 0, i ∈ I+(x∗) . Khi đó, ta có G(x∗, λ∗) = F.
Chứng minh. Giả sử d ∈ G(x∗, λ∗) ⇒ dT∇ci(x∗) = 0, i ∈ E. Ta chứng minh dT∇ci(x∗) ≥ 0, i∈ I(x∗). Thật vậy, ta có
I (x∗) = I+(x∗)∪ (I(x∗)\I+(x∗)).
Vì
dT∇ci(x∗) = 0 i ∈ I+(x∗) và
dT∇ci(x∗) ≥ 0, i∈ I (x∗)\I+(x∗)
nên dT∇ci(x∗) ≥ 0, i ∈ I (x∗). Vậy d ∈ LF D(x∗, X). Ngoài ra, vì d∈ G(x∗, λ∗) ta có
dT∇ci(x∗) = 0, i∈ I+(x∗)
. Vậy d ∈ LF D(x∗, X), dT∇ci(x∗) = 0, i∈ I+(x∗) nên d ∈ F.
Bây giờ giả sử d ∈ F ⇒ d ∈ LF D(x∗, X) ⇒ dT∇ci(x∗) = 0, i ∈ E.
Ta cũng có dT∇ci(x∗) = 0, i ∈ I+(x∗) nên dT∇ci(x∗) = 0, i ∈ E ∪ I+(x∗). Ngoài ra, ta có dT∇ci(x∗) ≥ 0, i ∈ I (x∗) nên dT∇ci(x∗) ≥ 0, i ∈ I(x∗)\I+(x∗). Vậy d ∈ G(x∗, λ∗). □
Từ Bổ đề 3.4, ta có:
G(x∗, λ∗) = (
d
d ∈ LF D(x∗, λ∗);
dT∇ci(x∗) = 0, i ∈ I+(x∗) )
. (3.93)
Từ các định nghĩa trên ta có
S(x∗, λ∗) ⊆SF D(x∗, X), (3.94) G(x∗, λ∗) ⊆LF D(x∗, X). (3.95) Tương tự như SF D(x∗, X) ⊆LF D(x∗, X), ta có
S(x∗, λ∗) ⊆ G(x∗, λ∗). (3.96) Bây giờ ta phát biểu những kết quả chính của phần này.
Định lí 3.11 ( Điều kiện cần cấp 2). Cho x∗ là cực tiểu địa phương của Bài toán (3.1)-(3.3). Nếu điều kiện ràng buộc CQ (3.35) đúng thì ta có
dT∇2xxL(x∗, λ∗)d ≥0, ∀ d ∈ S(x∗, λ∗), (3.97) với L(x, λ) là hàm Lagrange.
Hơn nữa, nếu
S(x∗, λ∗) = G(x∗, λ∗), (3.98) thì
dT∇2xxL(x∗, λ∗)d ≥0, ∀ d ∈ G(x∗, λ∗). (3.99) Chứng minh. Với mọi d ∈ S(x∗, λ∗), nếu d = 0 thì dT∇2xxL(x∗, λ∗)d = 0.
Ta xét d ̸= 0. Từ định nghĩa của S(x∗, λ∗) tồn tại {dk} và {δk} sao cho (3.86)-(3.90) đúng. Do đó, từ (3.90) và điều kiện KKT ta có
f(x∗ + δkdk) =L(x∗ + δkdk, λ∗)
= L(x∗, λ∗) + 1
2δk2dTk∇2xxL(x∗, λ∗)dk + 0(δk2)
= f (x∗) + 1
2δ2kdTk∇2xxL(x∗, λ∗)dk + 0 δk2. (3.100) Vì x∗ là cực tiểu địa phương nên với mọi k đủ lớn ta có
f(x∗ +δkdk) ≥f(x∗). (3.101) Sử dụng (3.100)-(3.101) và lấy giới hạn ta có
dT∇2xxL(x∗, λ∗)d ≥ 0.
Vì d ∈ S(x∗, λ∗) là tùy ý, ta có (3.97). Từ (3.98), ta nhận được (3.99) từ
(3.97). □
Định lí 3.12 ( Điều kiện đủ cấp hai). Cho x∗ là một điểm KKT của Bài toán (3.1)-(3.3). Nếu
dT∇2xxL(x∗, λ∗)d > 0, ∀d ∈ G(x∗, λ∗), (3.102) thì x∗ là cực tiểu địa phương chặt.
Chứng minh. Giả sử ngược lại rằng x∗ không phải là cực tiểu địa phương chặt thì tồn tại một dãy xk ∈ X (k = 1,2, . . .) sao cho
f(xk) ≤ f(x∗), (3.103)
và xk → x∗, xk ̸= x∗ (k = 1,2, . . .). Không mất tổng quát, ta giả sử rằng xk −x∗
∥xk−x∗∥2 →d.
Lập luận tương tự như (3.61)-(3.63), ta có
dT∇f (x∗) ≤0 (3.104)
và
d ∈ SF D(x∗, X) ⊆ LF D(x∗, X). (3.105) Từ điều kiện KKT và (3.19) ta có
dT∇f (x∗) =
m
X
i=1
λidT∇ci(x∗) ≥0. (3.106) Từ (3.104) và (3.106) ta suy ra
dT∇f (x∗) = 0. (3.107)
Từ (3.106) và Định nghĩa 3.7, ta có
λidT∇ci(x∗) = 0, ∀i ∈ I(x∗). (3.108) Vì thế, từ (3.105), (3.108) và Định nghĩa 3.12 ta có
d ∈ G(x∗, λ∗). (3.109)
Từ (3.103) ta có
L(x∗, λ∗) ≥ L(xk, λ∗) =L(xk, λ∗) + 1
2δk2dTk∇2xxL(x∗, λ∗)dk + 0 δk2. (3.110) Chia hai vế cho δk2 và lấy giới hạn ta có
dT∇2xxL(x∗, λ∗)d ≤ 0 (3.111) Điều này mâu thuẫn với (3.102). Vậy ta có điều phải chứng minh. □
Ta định nghĩa
A+(x∗, λ∗) =E ∪ {i | i ∈ I (x∗), λ∗i > 0}, (3.112) Tập hợp A+(x∗, λ∗) được gọi là tập chỉ số các điều kiện hoạt động mạnh.
Ta có hệ quả sau đây:
Hệ quả 3.3. Cho x∗ là một điểm KKT của Bài toán (3.1)-(3.3). Nếu dT∇2xxL(x∗, λ∗)d > 0 (3.113) với mọi d thỏa mãn
dT∇ci(x∗) = 0, ∀ i ∈ A+(x∗, λ∗), (3.114) thì x∗ là một cực tiểu địa phương chặt.
Chứng minh. Ta chứng minh rằng nếu d ∈ G(x∗, λ∗) thì dT∇ci(x∗) = 0, ∀i ∈ A+(x∗, λ∗). Thật vậy, giả sử d ∈ G(x∗, λ∗)thd ∈ LF D(x∗, X), ta có A+(x∗, λ∗) = E ∪ I+(x∗). Với i ∈ E thì dT∇ci(x∗) = 0 (do d ∈ LF D(x∗, X)). Với i ∈ I+(x∗) thì dT∇ci(x∗) = 0 (do d ∈ G(x∗, λ∗)). Vậy dT∇ci(x∗) = 0, ∀i ∈ A+(x∗, λ∗). Khi đó dT∇2xxL(x∗, λ∗)d > 0, ∀d ∈ G(x∗, λ∗). Vì vậy, x∗ là cực tiểu địa phương chặt. □