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.2. Điều kiện tối ưu bậc nhất
Trong phần này chúng ta sẽ nghiên cứu các điều kiện tối ưu bậc nhất.
Vì các hướng chấp nhận được đóng một vai trò rất quan trọng trong việc hình thành các điều kiện tối ưu, nên chúng ta đưa ra định nghĩa của một số hướng chấp nhận được.
Định nghĩa 3.6. Cho x∗ ∈ X,0 ̸= d ∈ Rn. Nếu tồn tại δ > 0 sao cho x∗+td ∈ X, ∀t ∈ [0, δ], thì d được gọi là một hướng chấp nhận được của X tại x∗. Tập hợp tất cả các hướng chấp nhận được của X tại x∗ dược kí hiệu bởi
F D(x∗, X) = {d|x∗ +td ∈ X, ∀t∈ [0, δ]}. (3.16) Định nghĩa 3.7. Cho x∗ ∈ X và d ∈ Rn. Nếu
(dT∇ci(x∗) = 0, i ∈ E, dT∇ci(x∗) ≥ 0, i ∈ I(x∗),
thì d được gọi là hướng tuyến tính chấp nhận được của X tại x∗. Tập hợp tất cả các hướng tuyến tính chấp nhận được của X tại x∗ được kí hiệu bởi
LF D(x∗, X) = d|dT∇ci(x∗) = 0, i ∈ E, dT∇ci(x∗) ≥0, i ∈ I(x∗) . (3.17) Định nghĩa 3.8. Cho x∗ ∈ X và d ∈ Rn. Nếu tồn tại các dãy dk (k =
1,2, . . .) và δk > 0 (k = 1,2, . . .) sao cho x∗ + δkdk ∈ X, ∀k và dk → d, δk → 0, thì giới hạn d được gọi là hướng dãy chấp nhận được của X tại x∗. Tập hợp tất cả các hướng dãy chấp nhận được của X tại x∗ được kí hiệu bởi
SF D(x∗, X) = {d|x∗ +δkdk ∈ X, ∀k, dk →d, δk →0}. (3.18) Trong định nghĩa ở trên, nếu ta đặt xk = x∗ +δkdk, thì {xk} là một dãy điểm chấp nhận được thỏa mãn:
(1) xk ̸= x∗, ∀ k;
(2) limk→∞xk = x∗; (3) xk ∈ X với mọi k.
Nếu đặt δk = ||xk −x∗| |, thì ta có
dk = xk −x∗
||xk −x∗| | →d,
nghĩa làxk = x∗+δkdk là một dãy điểm chấp nhận được với hướng dãy chấp nhận được là d. Chú ý rằng nếu SF D(x∗, X) chứa vector không thì nó trở thành nón tiếp tuyến của X tại x∗, nghĩa là:
TX (x∗) =SF D(x∗, X)∪ {0}.
Từ những định nghĩa trên ta có bổ đề sau nói về mối quan hệ giữa các tập hợp F D(x∗, X), LF D(x∗, X) và SF D(x∗, X).
Bổ đề 3.1. Cho x∗ ∈ X. Nếu tất cả các hàm điều kiện đều khả vi tại x∗ thì
F D(x∗, X) ⊆ SF D(x∗, X) ⊆LF D(x∗, X). (3.19) Chứng minh. Với mọi d ∈ F D(x∗, X), theo Định nghĩa 3.6 tồn tại δ > 0 để (3.16) đúng. Đặt dk = d và δk = δ/2k thì (3.18) đúng và rõ ràng dk → d, δk → 0. Vậy d ∈ SF D(x∗, X). Vì d là tùy ý nên
F D(x∗, X) ⊆SF D(x∗, X). (3.20) Tiếp theo, với mọi d ∈ SF D(x∗, X), nếu d = 0 thì d ∈ LF D(x∗, X).
Giả sử rằng d ̸= 0. Từ Định nghĩa 3.8 tồn tại hai dãy dk (k = 1,2, . . .) và δk > 0 (k = 1,2, . . .) để (3.18) đúng, và dk → d ̸= 0, δk → 0. Từ (3.18) ta thấy x∗ +δkdk ∈ X, nghĩa là:
0 = ci(x∗ +δkdk) =δkdTk∇ci(x∗) + 0(∥δkdk∥), i∈ E; (3.21) 0 ≤ ci(x∗ +δkdk) =δkdTk∇ci(x∗) + 0 (∥δkdk∥), i ∈ I (x∗). (3.22)
Chia hai vế của hai (bất) đẳng thức trên choδk > 0 và cho k → ∞, ta nhận được (3.17). Vậy ta có
SF D(x∗, X) ⊆LF D(x∗, X). (3.23)
Từ (3.20) và (3.23) ta có (3.19). □
Để mô tả một cách rõ ràng những điều kiện cần cho cực tiểu địa phương, chúng ta giới thiệu tập hợp:
D(x′) =D′ = ddT∇f (x′) < 0 . (3.24) Tập hợp trên được gọi là tập hợp các hướng giảm tại x′. Bây giờ chúng ta mô tả điều kiện tối ưu hình học cơ bản nhất như sau:
Định lí 3.1 (Điều kiện tối ưu hình học). Cho x∗ ∈ X là cực tiểu địa phương của Bài toán (3.1)-(3.3). Nếu f(x) và ci(x) (i = 1, . . . , m) khả vi tại x∗, thì
dT∇ f (x∗) ≥ 0, ∀d ∈ SF D(x∗, X). (3.25) Nghĩa là
SF D(x∗, X)∩ D(x∗) = ∅. (3.26) Chứng minh. Với mọid ∈ SF D(x∗, X),tồn tại hai dãy dk (k = 1,2, . . .)và δk > 0 (k = 1,2, . . .)đểx∗+δkdk ∈ X vớidk → d, δk → 0.Vìx∗+δkdk → x∗ và x∗ là cực tiểu địa phương nên với k đủ lớn, ta có:
f (x∗) ≤f (x∗ +δkdk) (3.27)
= f (x∗) +δkdTk∇f (x∗) + 0(δk). (3.28) Điều này suy ra
dT∇f(x∗) ≥ 0. (3.29)
Vì d là tùy ý, ta nhận được (3.25). Hơn nữa, ta có SF D(x∗, X)∩ D(x∗) =∅.
□ Nếu ta sử dụng thuật ngữ của nón tiếp tuyến để phát biểu (3.25), ta có
dT∇f (x∗) ≥0, ∀d ∈ TX (x∗), nghĩa là
− {∇f (x∗)}T d ≤ 0, ∀d ∈ TX (x∗). (3.30) Điều này kéo theo
−∇ f (x∗) ∈ NX (x∗), (3.31) với NX (x∗) là nón pháp tuyến của X tại x∗.
Bổ đề 3.2 (Bổ đề Farkas). Tập hợp
S = d| dT∇f(x∗) < 0, dT∇ci(x∗) = 0, i∈ E, dT∇ci(x∗) ≥ 0, i ∈ I (3.32) là rỗng nếu và chỉ nếu tồn tại các số thực λi, i ∈ E và các số thực không âm λi ≥ 0, i ∈ I sao cho
∇f (x∗) =X
i∈E
λi∇ci(x∗) + X
i∈I
λi∇ci(x∗). (3.33) Để đưa ra các điều kiện tối ưu một cách dễ dàng, ta giới thiệu hàm Lagrange:
L(x, λ) =f (x)−
m
X
i=1
λici(x), (3.34)
với λ = (λ1, . . . , λm)T ∈ Rm là một vector nhân tử Lagrange.
Bây giờ ta sẽ phát biểu điều kiện tối ưu cấp 1 của một điểm cực tiểu địa phương bằng cách sử dụng Bổ đề Farkas và Định lý 3.1.
Định lí 3.2 (Karush – Kuhn – Tucker). 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 hạn chế
SF D(x∗, X) = LF D(x∗, X) (3.35) đúng, thì tồn tại các nhân tử Lagrange λ∗i để những điều kiện sau thỏa mãn tại (x∗, λ∗) :
∇f (x∗)−
m
X
i=1
λ∗i∇ci(x∗) = 0, (3.36) ci(x∗) = 0, ∀i ∈ E, (3.37) ci(x∗) ≥0, ∀i ∈ I, (3.38) λ∗i ≥0, ∀i ∈ I, (3.39) λ∗ici(x∗) = 0, ∀i ∈ I. (3.40) Chứng minh. Vì x∗ là cực tiểu địa phương nên x∗ là điểm chấp nhận được.
Do đó (3.37) và (3.38) thỏa mãn. Nếu d ∈ SF D(x∗, X) thì vì x∗ là cực tiểu địa phương nên theo Định lý 3.1 ta có dT∇f (x∗) ≥ 0. Vậy hệ:
dT∇ci(x∗) = 0, i ∈ E, (3.41) dT∇ci(x∗) ≥0, i∈ I(x∗), (3.42)
dT∇f (x∗) < 0 (3.43)
vô nghiệm. Vậy trong mọi trường hợp, hệ (3.41)-(3.43) vô nghiệm.
Nếu d /∈ SF D(x∗, X) thì theo điều kiện hạn chế (3.35) ta có d /∈ LF D(x∗, X) (nên hệ gồm dT∇ci(x∗) = 0, i ∈ E và dT∇ci(x∗) ≥ 0, i ∈
I(x∗) vô nghiệm).
Theo Bổ đề Farkas, ta có
∇f (x∗) = X
i∈E
λ∗i∇ci(x∗) + X
i∈I(x∗)
λ∗i∇ci(x∗), (3.44) với λ∗i ∈ R (i ∈ E) và λ∗i ≥ 0 (i ∈ I (x∗)). Đặt λ∗i = 0(i ∈ I\I(x∗)), ta có
∇f (x∗) =
m
X
i=1
λ∗i∇ci(x∗), tức là (3.36), và ta có λ∗i ≥ 0, ∀i ∈ I.
Cuối cùng, chú ý rằng: khi i ∈ I(x∗), ci(x∗) = 0 và λ∗i ≥ 0. Do đó λ∗ici(x∗) = 0; khi i ∈ I\I (x∗), ci(x∗) > 0nhưng λ∗i = 0. Do đó λ∗ici(x∗) =
0. Vậy ta có λ∗ici(x∗) = 0, ∀ i ∈ I. □
Điều kiện (3.36)-(3.40) thường được gọi là điều kiện Karush – Kuhn – Tucker, hay viết tắt là điều kiện KKT, (3.36) được gọi là điều kiện điểm dừng, bởi vì nó có thể viết:
∇xL(x∗, λ∗) =∇f (x∗)−
m
X
i=1
λ∗i∇ci(x∗) = 0. (3.45) Điều kiện (3.37) và (3.38) được gọi là điều kiện chấp nhận được, (3.39) là điều kiện không âm cho các nhân tử, và (3.40) được gọi là điều kiện bổ sung, tức là λ∗i và ci(x∗) không thể cùng khác không, hay nói một cách tương đương các nhân tử Lagrange tương ứng với những ràng buộc không hoạt động đều bằng không.
Ta nói rằng điều kiện bù là chặt nếu có chính xác một trong hai số λ∗i và ci(x∗) bằng không với mỗi i ∈ I,nghĩa là ta có λ∗i > 0với mỗi i ∈ I∩A(x∗). Một điều kiện bất đẳng thứcci được gọi là hoạt động mạnh nếui ∈ I∩A(x∗) và λ∗i > 0, nghĩa là λ∗i > 0 và ci(x∗) = 0. Một điều kiện bất đẳng thức ci được gọi là hoạt động yếu nếu i ∈ I ∩ A(x∗) và λ∗i = 0, nghĩa là λ∗i = 0 và ci(x∗) = 0.
Điều kiện (3.35) được gọi là điều kiện hạn chế (CQ). Điều kiện hạn chế là quan trọng cho điều kiện KKT. Như một ví dụ được đưa ra bởi Fletcher chỉ ra rằng nếu điều kiện CQ không đúng, thì cực tiểu địa phương của Bài toán (3.1)-(3.3) có thể không phải là một điểm KKT.
Ví dụ 3.1.
min
(x1,x2)∈R2
x1 (3.46)
với điều kiện x31 −x2 ≥ 0, (3.47)
x2 ≥ 0. (3.48) Ta thấy rằng x∗ = (0,0) là cực tiểu toàn cục của bài toán. Tại x∗, ta có
SF D(x∗, X) = (
d|d = α 0
!
, α ≥ 0 )
(3.49) và
LF D(x∗, X) = (
d|d= α 0
!
, α ∈ R )
. (3.50)
Do đó CQ không đúng. Bằng tính toán trực tiếp ta có
∇f (x∗) = 1 0
!
, ∇c1(x∗) = 0
−1
!
, ∇c2(x∗) = 0 1
!
. (3.51)
Điều này cho thấy không tồn tại λ∗1 và λ∗2 để cho
∇f (x∗) = λ∗1∇c1(x∗) + λ∗2∇c2(x∗). (3.52) Ví dụ đơn giản này cho ta thấy tầm quan trọng của điều kiện CQ. Tuy nhiên không dễ để biết điều kiện CQ đúng hay không. Sau đây, ta sẽ đưa ra một số ràng buộc cụ thể dễ kiểm tra và được sử dụng thường xuyên. Điều kiện ràng buộc đơn giản và rõ ràng nhất là điều kiện ràng buộc hàm tuyến tính.
Định nghĩa 3.9. Nếu tất cả các hàm điều kiện ci(x) (i ∈ A(x∗) = E∪ I(x∗)) đều là tuyến tính, thì ta nói rằng điều kiện ràng buộc hàm tuyến tính (LFCQ) là đúng.
Từ định nghĩa, nếu ci(x) (i ∈ A(x∗)) là những hàm tuyến tính, thì điều kiện CQ (3.35) đúng và ta có hệ quả sau đây:
Hệ quả 3.1. 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 hàm tuyến tính (LFCQ) đúng tại x∗, thì x∗ là một điểm KKT.
Điều kiện ràng buộc quan trọng nhất và thường xuyên được sử dụng là điều kiện ràng buộc độc lập tuyến tính (LICQ) sau đây.
Định nghĩa 3.10. Nếu các gradient của các ràng buộc hoạt động
∇ci(x∗), i∈ A(x∗)
là độc lập tuyến tính thì ta nóiđiều kiện ràng buộc độc lập tuyến tính (LICQ) đúng.
Định lí 3.3. Cho x∗ là một điểm chấp nhận được và A(x∗) là tập hợp chỉ số của các điều kiện hoạt động tại x∗. Nếu các ∇ci(x∗), i ∈ A(x∗) là độc lập tuyến tính thì điều kiện hạn chế (3.35) (CQ) đúng.
Chứng minh. Vì SF D(x∗, X) ⊆ LF D(x∗, X), ta chỉ cần chứng minh LF D(x∗, X) ⊆SF D(x∗, X).
Cho d ∈ LF D(x∗, X) tùy ý, đặt
A(x∗) = E ∪ I(x∗) = {1, . . . , l}, me ≤ l ≤ n.
Vì ∇c1(x∗), . . . , ∇cl(x∗) là độc lập tuyến tính nên ta có thể bổ sung bl+1, . . . , bn để ∇c1(x∗), . . . ,∇cl(x∗), bl+1, . . . , bn là độc lập tuyến tính.
Xét hệ phi tuyến
r(x, θ) = 0, (3.53)
với các thành phần được định nghĩa bởi
ri(x, θ) =ci(x)−θdT∇ci(x∗), i = 1, . . . , l, (3.54) ri(x, θ) = (x−x∗)Tbi −θ dTbi, i= l+ 1, . . . , n. (3.55) Khi θ = 0 hệ (3.53) được giải bởi x∗, khi θ ≥ 0 đủ nhỏ, bất cứ nghiệm x cũng là điểm chấp nhận được của Bài toán (3.1)-(3.3).
Ta viết
A= [∇c1(x), . . . , ∇cl (x)], B = [bl+1, . . . , bn].
Thì ma trận Jacobian J(x, θ) = ∇xrT(x, θ) = [A : B]. Ta có J(x∗) = [A(x∗) : B] là ma trận không suy biến. Cho nên theo định lý của hàm ẩn tồn tại một lân cận mở Ωx của x∗ và Ωθ của θ = 0 sao cho với mọi θ ∈ Ωθ, tồn tại duy nhất nghiệm x(θ) ∈ Ωx, và x(θ) là điểm chấp nhận được và khả vi liên tục theo θ. Từ (3.53) và sử dụng đạo hàm hàm số hợp ta có:
0 = dri dθ
= X
j
∂ri
∂xi
dxj
dθ + ∂ri
∂θ, ;i = 1, . . . , n, hay
∇ci(x)Tdx
dθ − ∇ci(x∗)T d = 0, i = 1, . . . , l, (3.56) bTi dx
dθ −bTi d = 0, i= l+ 1, . . . , n. (3.57) Hệ trên là
JTdx
dθ −J (x∗)T d = 0.
Vì x = x∗ tại θ = 0. Vậy hệ trên trở thành J(x∗)
dx
dθ|θ=0 −d
= 0.
Vì ma trận hệ số không suy biến, ta nhận được dx
dθ = d tại θ = 0.
Vậy nếu θk ↓ 0 thì x(θk) là một dãy điểm chấp nhận được với hướng chấp nhận được d, nghĩa là
x(θk)−x∗
θk →d.
Điều này cho thấy rằng d ∈ SF D(x∗, X). Vì d ∈ LF D(x∗, X) tùy ý, ta có LF D(x∗, X) ⊆SF D(x∗, X).
□ Từ định lý trên và Định lý 3.2 ta có định lý sau đây
Định lí 3.4. Cho x∗ là cực tiểu địa phương của Bài toán (3.1)-(3.3).
Nếu LICQ đúng, nghĩa là ∇ci(x∗), i ∈ A(x∗) là độc lập tuyến tính, thì tồn tại các nhân tử Lagrange λ∗i (i = 1, . . . , m) để (3.36)-(3.40) đúng.
Thỉnh thoảng chúng ta sử dụng giả thiết
SF D(x∗, X)∩ D(x∗) =LF D(x∗, X)∩ D(x∗). (3.58) Giả thiết này có thể suy ra trực tiếp từ điều kiện CQ (3.35). Tuy nhiên, điều ngược lại không đúng.
Với giả thiết (3.58), điều kiện cần của Định lý 3.1 (SF D(x∗, X)∩D(x∗) =
∅) trở thành LF D(x∗, X)∩ D(x∗) =∅, nghĩa là không có hướng tuyến tính giảm tại x∗. Hơn nữa, như là một hệ quả của định lý KKT, ta có
Định lí 3.5. Cho x∗ ∈ X là cực tiểu địa phương của Bài toán (3.1) - (3.3). Nếu SF D(x∗, X) ∩ D(x∗) = LF D(x∗, X) ∩ D(x∗), thì x∗ là một điểm KKT.
Tiếp theo, ta bàn về điều kiện đủ của điều kiện tối ưu cấp một.
Định lí 3.6. Cho x∗ ∈ X. Cho f(x) và ci(x), (i = 1, . . . , m) khả vi tại x∗. Nếu
dT∇f (x∗) > 0, ∀0̸= d ∈ SF D(x∗, X), (3.59) thì x∗ là một cực tiểu địa phương chặt của Bài toán (3.1) - (3.3).
Chứng minh. Giả sử ngược lại rằng x∗ không 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.60)
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. (3.61)
Đặt dk = ∥xxk−x∗
k−x∗∥2, δk = ∥xk −x∗∥2. Từ Định nghĩa 3.8 ta có
d∈ SF D(x∗, X). (3.62)
Từ (3.60) và (3.61) và f(xk) = f(x∗) + (xk −x∗)T∇f (x∗) + 0(∥xk−x∗∥2, bằng cách chia hai vế cho ∥xk −x∗∥2 sau đó lấy giới hạn khi k → ∞, ta nhận được
dT∇f (x∗) ≤ 0, (3.63)
Điều này cùng (3.62) mâu thuẫn với (3.59). Vậy định lý đã được chứng
minh. □
Vì SF D(x∗, X) ⊆ LF D(x∗, X), ta có hệ quả sau đây.
Hệ quả 3.2. Cho x∗ ∈ X. Cho f(x) và ci(x), (i = 1, . . . , m) khả vi tại x∗. Nếu
dT∇f (x∗) > 0, ∀0̸= d ∈ LF D(x∗, X), (3.64) thì x∗ là một cực tiểu địa phương chặt của Bài toán (3.1) - (3.3).
Một điều kiện tối ưu quan trọng khác, được ghi nhận bởi Fritz John, là điều kiện tối ưu của Fritz John.
Định lí 3.7. Cho f(x) và ci(x) (i = 1, . . . , m) khả vi liên tục trên một tập mở khác rỗng chứa tập chấp nhận được X. Nếu x∗ là một cực tiểu địa phương chặt của Bài toán (3.1) - (3.3), thì tồn tại một số λ∗0 ≥ 0 và một vector λ∗ để
λ∗0∇ f (x∗)−
m
X
i=1
λi∇ci(x∗) = 0 (3.65)
ci(x∗) = 0, i ∈ E, (3.66)
ci(x∗) > 0, i ∈ I, (3.67)
λ∗i ≥0, i ∈ I, (3.68)
λ∗ici(x∗) = 0, ∀i, (3.69)
m
X
i=1
(λ∗i)2 > 0. (3.70)
Chứng minh. Nếu các ∇ci(x∗) (i ∈ A(x∗)) là phụ thuộc tuyến tính, thì tồn tại các λ∗i (i ∈ A(x∗)) không đồng thời bằng không sao cho
X
i∈A(x∗)
λ∗i∇ci(x∗) = 0. (3.71) Cho λ∗0 = 0 và λ∗i = 0, (i ∈ I\I(x∗)), ta nhận được (3.65)-(3.70). Nếu các
∇ci(x∗) (i ∈ A(x∗)) là độc lập tuyến tính thì ta nhận được (3.65)-(3.70) với
λ∗0 = 1, theo Định lý 3.4 □
Điểm thỏa mãn (3.65)-(3.70) được gọi là điểm Fritz John và hàm Lagrange có trọng
Le(x, λ0, λ) = λ0f (x)−
m
X
i=1
λici(x) (3.72) được gọi là hàm Fritz John.
Chúng ta kết thúc phần này với một điều kiện tối ưu của bài toán tối ưu lồi. Như chúng ta đã biết, bài toán cực tiểu của một hàm lồi trên tập lồi Ω được gọi là bài toán quy hoạch lồi. Vậy một bài toán quy hoạch lồi có dạng
min f(x)
với điều kiện x ∈ Ω (3.73)
với f(x) là một hàm lồi trên tập lồi Ω. Thông thường, trong bài toán quy hoạch phi tuyến
min f(x)
với điều kiện ci(x) = 0, i∈ E,
ci(x) ≥ 0, i∈ I, (3.74)
nếuf(x) lồi, ci(x), (i ∈ E) là các hàm tuyến tính, vàci(x), (i ∈ I) là những hàm lõm, thì tập hợp điều kiệnΩ = {x| ci(x) = 0, i ∈ E; ci(x) ≥ 0, i ∈ I} là một tập lồi, cho nên (3.74) là một bài toán quy hoạch lồi. Định lý sau đây chỉ ra rằng cực tiểu địa phương của bài toán quy hoạch lồi cũng là cực tiểu toàn cục của nó.
Định lí 3.8. Mỗi cực tiểu địa phương của bài toán quy hoạch lồi cũng là cực tiểu toàn cục của nó, và tập S gồm các cực tiểu toàn cục là một tập lồi.
Chứng minh. Giả sử ngược lại rằngx∗ là cực tiểu địa phương mà không phải là cực tiểu toàn cục. Khi đó, tồn tại x1 ∈ Ω sao cho f(x1) < f(x∗). Xét
xθ = (1−θ)x∗ +θx1, θ ∈ [0,1]. Từ tính lồi của Ω và f, ta có xθ ∈ Ω và
f (xθ) ≤(1−θ)f (x∗) +θ f(x1)
= f (x∗) +θ(f (x1)−f (x∗)) < f (x∗).
Với θ đủ nhỏ xθ ∈ B(x∗, ε)∩Ω. Vì x∗ là cực tiểu địa phương nên ta có với θ đủ nhỏ thìf (xθ) ≥f (x∗).Ta gặp mâu thuẫn. Vậy cực tiểu địa phương cũng là cực tiểu toàn cục. Cho x0, x1 ∈ S. Đặt xθ = (1−θ)x0 +θ x1, θ ∈ [0,1]. Vì x0, x1 là cực tiểu toàn cục nên f (xθ) ≥ f (x0) = f(x1). Vì f lồi nên ta có f (xθ) ≤ (1−θ)f (x0) + θ f(x1) = f (x0) = f(x1). Do đó, f (xθ) = f (x0) = f(x1). Vậy xθ ∈ S, tức là S lồi. □
Định lí 3.9. Điểm KKT của bài toán quy hoạch lồi là cực tiểu của nó.
Chứng minh. Cho (x∗, λ∗) là điểm KKT bất kỳ của bài toán quy hoạch lồi.
Ta có hàm Lagrange
L(x, λ∗) =f (x)−X
i∈E
λ∗ici(x)−X
i∈I
λ∗ici(x) (3.75) là lồi đối với x. Bằng cách sử dụng tính lồi của hàm số và những điều kiện KKT, ta có với bấy kì điểm chấp nhận được x,
L(x, λ∗) ≥ L(x∗, λ∗) + (x−x∗)T ∇xL(x∗, λ∗)
= L(x∗, λ∗)
= f (x∗)−
m
X
i=1
λ∗ici(x∗)
= f (x∗). (3.76)
Chú ý rằng x là một điểm chấp nhận được và λ∗i ≥0, ∀ i ∈ I nên ta có λ∗ici(x) = 0, i∈ E; λ∗ici(x) ≥ 0, i ∈ I.
Vì vậy
L(x, λ∗) ≤ f (x). (3.77) Từ (3.76) và (3.77) ta nhận được
f (x) ≥ f (x∗). (3.78)
Vậy điểm KKT x∗ là một cực tiểu. □
Định lí 3.10. Một bài toán quy hoạch lồi với hàm mục tiêu lồi chặt có duy nhất một cực tiểu.