Điều kiện cần cho nghiệm của bài toán tối ưu

Chương 2. Lí thuyết cơ bản về bài toán tối ưu

2.2. Điều kiện cần cho nghiệm của bài toán tối ưu

Câu hỏi đầu tiên được đặt ra khi xét một bài toán tối ưu không phải là phương pháp giải là gì mà là khi nào thì bài toán có nghiệm. Một trong những kết quả chính được biết đến thời điểm này là Định lý Weierstreass 1.7 đã được nêu ở phần kiến thức cơ sở: nếu hàm số f liên tục trên Ω và Ω là một tập compact thì tồn tại cực tiểu. Đây là một định lý quan trọng trong quá trình phát triển các phương pháp khác. Tuy nhiên, khi xét một bài toán tối ưu, chúng ta thường quan tâm nhiều hơn đến các tính chất của nghiệm và việc đưa ra các phương pháp hiệu quả để tìm các nghiệm đó.

Trước khi nghiên cứu các điều kiện cần và đủ cho nghiệm của Bài toán (2.1), chúng ta giới thiệu hai khái niệm cơ bản: cực tiểu địa phương và cực tiểu toàn cục. Các khái niệm cực đại địa phương và cực đại toàn cục được định nghĩa hoàn toàn tương tự.

Định nghĩa 2.1. Một điểm x∗ ∈ Ω được gọi là cực tiểu địa phương của f trên Ω nếu tồn tại một số ε > 0 để cho f(x) ≥ f(x∗) với mọi x ∈ Ω nằm trong ε-lân cận của x∗ (tức là với mọi x ∈ Ω và ∥ x−x∗ ∥< ε). Hơn nữa, nếu f(x) > f(x∗) với mọi x ∈ Ω, x ̸= x∗ nằm trong lân cận của x∗ thì x∗ được gọi là cực tiểu địa phương chặt của f trên Ω.

Định nghĩa 2.2. Một điểm x∗ ∈ Ω được gọi là cực tiều toàn cục của f trên Ω nếu f(x) ≥f(x∗) với mọi x ∈ Ω. Hơn nữa, nếu f(x) > f(x∗) với mọi x ∈ Ω, x ̸= x∗ thì x∗ được gọi là cực tiểu toàn cục chặt của f trên Ω.

Hình 2.1: x1 là cực tiểu toàn cục chặt,x2 là cực tiểu địa phương chặt, x3 là cực tiểu địa phương.

Hình 2.1 minh họa các điểm cực tiểu địa phương và cực tiểu toàn tục.

Trong ví dụ này, hàm số f(x) đạt cực tiểu toàn cục tại x1 và đạt cực tiểu địa phương tại x1, x2, x3 và các điểm trong lân cận của x3.

Trong quá trình xây dựng giải thuật để giải Bài toán (2.1) chúng ta đề cập đến cực tiểu toàn cục của hàm f trên Ω. Tuy nhiên, trong thực tế, cả về lý thuyết lẫn tính toán, chúng ta thường chỉ đề cập đến cực tiểu địa phương.

Nghiệm toàn cục chỉ có thể tìm được nếu bài toán đã cho bài toán cực tiểu lồi: điều kiện để đảm bảo cho cực tiểu địa phương là cực tiểu toàn cục. Chính vì vậy, trong việc giải Bài toán (2.1), chúng ta sẽ đơn giản hóa bằng cách đề cập đến điểm cực tiểu địa phương. Nếu bài toán cực tiểu là lồi thì nó cũng sẽ cho ta điểm cực tiểu toàn cục.

2.2.1. Hướng chấp nhận được

Để bắt đầu tìm điểm cực tiểu địa phương x∗, ý tưởng ban đầu là xét sự thay đổi của hàm số tại một điểm và theo một hướng xác định nào đó. Dọc theo một hướng bất kỳ đã được xác định, hàm số theo biến x có thể được xem như hàm một biến với tham số được định nghĩa dọc theo sự thay đổi của hướng đó. Chính vì thế, việc tính toán được thực hiện đối với hàm một biến. Từ đó, người ta định nghĩa:

Định nghĩa 2.3. Cho điểm x∗ ∈ Ω, một véctơ d được gọi là một hướng chấp nhận được tạixnếu tồn tạiα > 0sao chox+αd ∈ Ω với mọiα ∈ [0;α].

Hình 2.2:d1 là hướng chấp nhận được,d2 không phải là hướng chấp nhận được.

Hình 2.2 minh họa hướng chấp nhận được d1 và hướng không chấp nhận được d2 tại điểm x.

Với khái niệm đơn giản này, chúng ta có thể xây dựng các điều kiện cần về điểm cực tiểu địa phương của hàm số f.

2.2.2. Điều kiện cần bậc nhất

Định lí 2.1. (Điều kiện cần bậc nhất) Cho Ω là một tập con của Rn và f ∈ C1 là một hàm xác định trên Ω. Nếu x∗ là điểm cực tiểu địa phương của hàm số f trên Ω thì với mọi hướng chấp nhận được d ∈ Rn tại x∗, ta đều có ∇f(x∗)Td ≥0.

Chứng minh. Định lý này có thể được chứng minh bằng một trong hai cách sau đây.

Cách 1. Vì d là một hướng chấp nhận được tại x∗ nên tồn tại α > 0 sao cho x(α) = x∗ + αd ∈ Ω với mọi α ∈ [0;α]. Với mọi α ∈ [0;α], ta định nghĩa hàm số g(α) = f(x(α)). Vì x∗ là cực tiểu địa phương của f nên α = 0 là cực tiểu địa phương của g (đồ thi hàm số g được mô tả ở Hình 2.3). Khi đó,

Hình 2.3: Đồ thị hàm số g(α).

khai triển Taylor của hàm số g ta được:

g(α) =g(0) +αg′(0) +o(α),

trong đó o(α) là vô cùng bé bậc cao hơn α. Chuyển vế ta được g(α)−g(0) = αg′(0) +o(α).

Nếu g′(0) < 0 thì với giá trị α > 0 đủ bé vế phải của biểu thức trên nhận giá trị âm nên ta suy ra g(α) < g(0). Điều này trái với giải thiết α = 0 là cực tiểu địa phương của hàm số f. Vậy g′(0) = ∇f(x∗)Td ≥ 0.

Cách 2. Theo Định lý 1.8 ta có:

∇f(x∗)Td = f′(x∗, d) = lim

α→0+

f(x∗ +αd)−f(x∗)

α .

Vì x∗ là điểm cực tiểu địa phương của f nên f(x∗+αd)−f(x∗) ≥ 0. Từ đó, ta suy ra ∇f(x∗)Td ≥ 0.

□ Một trong những trường hợp đặc biệt là khi x∗ là một điểm trong của Ω (ví dụ như Ω = Rn). Trong trường hợp này, hướng chấp nhận được có thể chọn một cách tùy ý. Do đó, ∇f(x∗)Td ≥ 0, với mọi d ∈ Rn. Điều này đưa đến kết quả ∇f(x∗) = 0. Ta nhận được hệ quả sau:

Hệ quả 2.1. (Điều kiện cần bậc nhất cho bài toán tối ưu tự do) Cho Ω là một tập con của Rn và f ∈ C1 là hàm số xác định trên Ω. Nếu x∗ là điểm cực tiểu địa phương của f trên Ω và x∗ là điểm trong của Ω thì

∇f(x∗) = 0.

Chứng minh. Giả sử f có điểm cực tiểu địa phương trên Ω là x∗, đồng thời

đó cũng là điểm trong của Ω. Vì x∗ là điểm trong của Ω nên tập hợp các hướng chấp nhận được tại x∗ là toàn không gian Rn. Do đó, với mọi d ∈ Rn, theo Định lý 2.1 ta có:

∇f(x∗)Td≥ 0 và −∇f(x∗)Td ≥0.

Từ hai bất đẳng thức trên đúng khi và chỉ khi ∇f(x∗)Td = 0, ∀d∈ Rn. Vậy

∇f(x∗) = 0. □

Như vậy, điều kiện cần bậc nhất cho bài toán tối ưu không ràng buộc dẫn đến việc giải n phương trình (theo Hệ quả 2.1). Trong một số trường hợp, chúng ta có thể dễ dàng tìm được các nghiệm của những phương trình này.

Tuy nhiên, trong nhiều trường hợp, việc giải hệ phương trình này rất phức tạp và gặp nhiều khó khăn. Trong thực tế, việc giải các bài toán tối ưu sẽ được thực hiện dễ dàng hơn với phương pháp lặp được giới thiệu ở chương sau.

Sau đây chúng ta sẽ xem một số ví dụ về việc áp dụng điều kiện cần bậc nhất để tìm cực tiểu cho một bài toán tối ưu.

Ví dụ 2.1. Tìm điểm cực tiểu của hàm số sau trên R2: f(x1, x2) =x21 −x1x2 +x22 −3x2.

Hình 2.4: Đồ thị hàm sốf(x1, x2).

Giải: Ta có:

∇f(x1, x2)T = (2x1 −x2,−x1 + 2x2 −3) = (0,0).

Do đó, ta có hệ phương trình:

( 2x1 −x2 = 0

−x1 + 2x2 −3 = 0 ⇔

( x1 = 1 x2 = 2

Vậy xT = (1,2) là nghiệm cực tiểu toàn cục của f (vì f là hàm lồi). Hình 2.4 minh họa đồ thị của hàm số f trong ví dụ này.

Ví dụ sau sẽ cho ta thấy việc áp dụng điều kiện cần để tìm cực tiểu địa phương cũng gây không ít khó khăn, việc đưa ra các phương pháp giải cho bài toán này sẽ được đề cập trong các chương sau. Ở ví dụ này chúng ta sẽ xét một lời giải sơ cấp cho bài toán.

Ví dụ 2.2. Xét hàm số f xác định bởi:

f(x1, x2) = x21 −x1 +x2 + x1x2, với x1, x2 ≥ 0.

Bằng việc thực hiện biến đổi sơ cấp đã học, ta có thể biến đổi hàm số f thành

f(x1, x2) =

x1 − 1 2

2

+x2 +x1x2 − 1

4 ≥ −1 4. Vậy cực tiểu toàn cục của f là xT = 12,0.

Rõ ràng nghiệm này thỏa điều kiện cần của bài toàn tối ưu (Định lý 2.1) vì

∇f(x)T = (2x1 −1 +x2,1 +x1) =

0,3 2

.

Rõ ràng với mọi hướng chấp nhận được d = (d1, d2)T ∈ R2 tại điểm 12,0 phải thỏa mãn d2 ≥ 0. Do đó, ta có: ∇f(x)Td ≥ 0.

2.2.3. Điều kiện cần bậc hai

Chứng minh Định lý 2.1 ở phần trên dựa vào xấp xỉ bậc nhất của hàm số f trong lân cận của điểm cực tiểu địa phương. Điều kiện cần bậc hai thu được bằng cách xét xấp xỉ bậc hai của hàm số f sử dụng ma trận Hessian

∇2f và là một lý thuyết quan trọng trong việc giải Bài toán (2.1).

Định lí 2.2. (Điều kiện cần bậc hai) Cho Ω là một tập con của Rn và f ∈ C2 xác định trên Ω. Nếu x∗ là một điểm cực tiểu địa phương của f trên Ω thì với mọi hướng chấp nhận được d ∈ Rn tại x∗, ta có:

(i) ∇f(x∗)Td ≥ 0.

(ii) Nếu ∇f(x∗)Td = 0 thì dT∇2f(x∗)d ≥0.

Chứng minh. Điều kiện (i) trong định lý chính là nội dung của Định lý 2.1.

Ta chỉ cần chứng minh điều kiện (ii). Vì d là một hướng chấp nhận được tại x∗ nên tồn tại α > 0 sao cho x(α) =x+αd ∈ Ω với mọi α ∈ [0;α].

Xét hàm số g xác định bởi g(α) = f (x(α)). Vì ∇f(x∗)Td = 0 nên g′(α) = 0. Khi đó, dùng khai triển Taylor của hàm số g tại 0, ta được:

g(α)−g(0) = 1

2g′′(0)α2 + o(α2),

trong đó o(α2) là vô cùng bé bậc cao hơn α2.

Nếu g′′(0) < 0 thì vế phải của đẳng thức trên âm nếu α > 0 đủ bé.

Điều này kéo theo g(α) < g(0) vớiα > 0 đủ bé, trái với giả thiết 0 là cực tiểu địa phương của g (do x∗ là cực tiểu địa phương của f). Do vậy,

g′′(0) = dT∇2f(x∗)d ≥0. □

Ví dụ 2.3. Xét Ví dụ 2.2 ở phần trước, ta có dT = (d1, d2) và với cực tiểu địa phương (x∗)T = (12,0) ta có

∇f(x∗)Td = 3 2d2.

Điều kiện (ii) của Định lý 2.2 xảy ra nếu d2 = 0. Trong trường hợp này, ta có:

dT∇2f(x)d= 2d21 ≥0.

Do đó, điều kiện (ii) được thỏa mãn.

Tương tự như điều kiện cần bậc nhất, đối với trường hợp x∗ là điểm trong ta cũng có hệ quả của Định lý 2.2 được phát biểu như sau:

Hệ quả 2.2. Giải sử x∗ là điểm trong của tập Ω và x∗ là điểm cực tiểu địa phương của hàm số f ∈ C2 trên Ω. Khi đó, ta có

(i) ∇f(x∗) = 0.

(ii) Với mọi d, dT∇2f(x∗)d ≥ 0.

Chứng minh. Điều kiện (i) của hệ quả trên chính là Hệ quả 2.1 nên ta chỉ cần chứng minh (ii). Ta để ý rằng vì ∇f(x∗) = 0 nên ∇f(x∗)Td = 0 với mọi d. Vậy theo (ii) của Định lý 2.2, với mọi d ta có: dT∇2f(x∗)d≥ 0. □ Trong phần kiến thức cơ sở, để đơn giản ta kí hiệu ma trận Hessian

∇2f(x) bởi F(x) và điều kiện (ii) của Định lý 2.2 tương đương với ma trận Hessian F(x) là nửa xác định dương.

Ma trận Hessian F(x∗) trong điều kiện cần bậc hai đóng một vai trò quan trọng trong phương pháp lặp để giải bài toán tối ưu không điều kiện rằng buộc. Hơn nữa, cấu trúc của ma trận Hessian cũng đóng một vai trò quan trọng trong việc xác định tốc độ hội tụ của giải thuật cho bài toán tối ưu.

Ví dụ 2.4. Xét hàm số f xác định bởi:

f(x1, x2) = x31 −x21x2 + 2x22, với x1, x2 ≥ 0.

Giả sử nghiệm của bài toán là điểm trong của tập các rằng buộc, tức là

nếu x1 > 0 và x2 > 0 thì theo điều kiện cần bậc nhất, ta có :

∇f(x∗)T = 3x21 −2x1x2,−x21 + 4x2 = (0,0).

Giải hệ phương trình này, ta được 2 nghiệm là x1 = x2 = 0 (trên biên của tập xác định) và nghiệm x1 = 6, x2 = 9. Để ý rằng, nếu ta cố định x1 = 6 thì hàm số đạt cực tiểu tại x2 = 9 và ngược lại nếu cố định x2 = 9 thì hàm số đạt cực tiểu tại x1 = 6. Tuy nhiên, x1 = 6, x2 = 9 không phải là cực tiểu địa phương của hàm số f. Thật vậy, ta có ma trận Hessian của f là

F = 6x1 −2x2 −2x1

−2x1 4

! . Với x1 = 6, x2 = 9, ta có:

F = 18 −12

−12 4

! .

Vì F không phải là ma trận nửa xác định dương nên xT = (6,9) không phải cực tiểu địa phương của f.