Mục từ này cần được bình duyệt
Phân loại các bài toán quy hoạch toán học

Có nhiều cách để phân loại các bài toán quy hoạch toán học:

  • Lồi đối lập với Không lồi
  • Trơn đối lập với Không trơn
  • Tuyến tính đối lập với Phi tuyến.

Lồi và không lồi

Tập lồi

Chúng ta nói rằng là một tập lồi nếu

.

Bao lồi

Tập lồi nhỏ nhất chứa được gọi là bao lồi của và được ký hiệu bởi .

Hàm lồi

Một hàm được gọi là lồi nếu tập trên đồ thị của nó,

 

 

 

 

(1)

là một tập lồi trong không gian tích .

Hàm chính thường

Hàm được gọi là chính thường nếu với ít nhất một phần tử với mọi . Hàm được gọi là lõm nếu hàm được xác định bởi công thức là lồi.

Theo các quy ước thường dùng (xem Rockafellar (1970), tr. 24),

.

Các tổ hợp là vô nghĩa và sẽ được tránh sử dụng.

Bất đẳng thức Jensen

Từ định nghĩa hàm lồi và công thức (1) ta suy ra rằng hàm số là lồi khi và chỉ khi

 

 

 

 

(2)

Tổng quát hơn, một hàm là lồi khi và chỉ khi

với mọi . (Xem Rockafellar (1970), Định lý 4.3.)

Hàm lồi chặt

Giả sử rằng là một tập lồi. Nếu bất đẳng thức trong (2) đúng với mọi và với mọi , thì ta nói là lồi trên . Nếu bất đẳng thức trong (2) nghiệm đúng như một bất đẳng thức chặt với mọi và với mọi , thì ta nói là lồi chặt trên .

Bài toán quy hoạch lồi

Ta nói rằng là bài toán quy hoạch lồi nếu là tập lồi và là hàm lồi. Nếu bài toán quy hoạch lồi, thì

 

 

 

 

(3)

Bài toán quy hoạch không lồi

Nếu là tập không lồi hoặc là hàm không lồi, thì ta nói bài toán quy hoạch không lồi.

Xét bài toán

 

 

 

 

(4)

ở đó . Nhận xét rằng là lồi, trong khi là không lồi. Rõ ràng rằng (4) là tương đương với bài toán sau đây:

 

 

 

 

(5)

Có thể thấy rằng tập nghiệm của (4) và (5) chỉ gồm một điểm , còn tập nghiệm địa phương gồm hai điểm: . Điều này chứng tỏ rằng đẳng thức (3) nói chung không đúng với các bài toán quy hoạch không lồi.

Đặt với mọi . Định nghĩa và chọn . Với hàm và tập đó, chúng ta có

tức là đẳng thức (3) không đúng cho bài toán trong ví dụ này. Ở đây, là hàm không lồi và là tập lồi.

Các hàm lồi có nhiều tính chất thú vị. Chẳng hạn, hàm lồi là liên tục tại mỗi điểm trong của miền hữu hiệu của nó và nó là khả vi theo hướng tại mỗi điểm thuộc miền đó.

Miền hữu hiệu

Đối với mỗi hàm số , tập hợp

được gọi là miền hữu hiệu của f.

Đạo hàm theo hướng

Đối với một điểm và một véctơ , nếu giới hạn

(có thể nhận các giá trị ) tồn tại, thì được gọi là khả vi theo hướng tại theo hướng và giá trị được gọi là đạo hàm theo hướng của tại theo hướng . Nếu tồn tại với mọi , thì được gọi là khả vi theo hướng tại .

Trong hai định lý tiếp theo đây, là một hàm lồi và chính thường.

Định lý 0.0.1. (Xem Rockafellar (1970), Định lý 10.1) Nếu là điểm và số thực sao cho hình cầu mở chứa trong , thì phần hạn chế của trên là một hàm số thực liên tục.

Định lý 0.0.2. (Xem Rockafellar (1970), Định lý 23.1) Nếu , thì với mỗi giới hạn

tồn tại, và ta có

Nón pháp tuyến

Nón pháp tuyến của tập lồi tại một điểm được cho bởi công thức

Dưới vi phân

Dưới vi phân của một hàm lồi tại một điểm được định nghĩa bằng công thức

Phần trong tương đối

Tập con được gọi là một tập affine (a-phin) nếu với mọi . Đối với một , bao affine aff là tập affine nhỏ nhất chứa . Phần trong tương đối của được xác định bởi công thức

Định lý sau đây mô tả mối quan hệ giữa đạo hàm theo hướng và dưới vi phân của các hàm lồi.

Định lý 0.0.3. (Xem Rockafellar (1970), Định lý 23.4) Cho là một hàm lồi trên . Nếu , thì là rỗng. Nếu , thì là khác rỗng và

Ngoài ra, là tập khác rỗng và giới nội khi và chỉ khi

trong trường hợp đó, là hữu hạn với mỗi .

Kết quả sau đây được gọi là Định lý Moreau-Rockafellar.

Định lý 0.0.4. (Xem Rockafellar (1970), Định lý 23.8) Cho , ở đó là các hàm lồi, chính thường trên . Nếu

thì

Điều kiện cần và đủ tối ưu cho các bài toán quy hoạch lồi được phát biểu như sau.

Định lý 0.0.5. (Xem Rockafellar (1970), Định lý 27.4) Giả sử rằng là một hàm lồi, chính thường trên là một tập lồi. Nếu bao hàm thức

 

 

 

 

(6)

nghiệm đúng với , thì là nghiệm của . Ngược lại, nếu

 

 

 

 

(7)

thì (6) là điều kiện cần và đủ cho là nghiệm của . Nói riêng ra, nếu , thì là một nghiệm của khi và chỉ khi .

Bao hàm thức (6) có nghĩa là tồn tại sao cho 0 = x + u. Nhận xét rằng (7) là một điều kiện chính quy cho bài toán quy hạch lồi có dạng .

Định lý 0.0.5 là công cụ hiệu quả để giải nhiều bài toán quy hoạch lồi. Chúng ta có thể minh họa điều đó bằng cách xét ví dụ sau đây.

Điểm Fermat

Cho là ba điểm trong không gian hai chiều với các tọa độ tương ứng là

Giả sử rằng không tồn tại đường thẳng nào chứa tất cả ba điểm đó. Bài toán đặt ra là tìm một điểm trong với các tọa độ sao cho tổng khoảng cách từ tới là tối thiểu. Điều đó có nghĩa rằng là một nghiệm của bài toán quy hoạch lồi không có ràng buộc sau:

 

 

 

 

(8)

Sử dụng định lý Weierstrass và tính lồi chặt của trên , ta có thể chứng tỏ rằng (8) có duy nhất nghiệm; xem Lee, Tam, Yen (2005), tr. 11–13. Để ý rằng , ở đó . Theo Định lý 0.0.5, là nghiệm của (8) khi và chỉ khi . Vì , sử dụng Định lý 0.0.4 ta có thể viết bao hàm thức cuối dưới dạng

.

Tiếp theo, bằng cách tính toán các dưới vi phân (xem Lee, Tam, Yen (2005), tr. 10), ta có thể xác định được điểm là nghiệm duy nhất của bao hàm thức này. Trong ngôn ngữ của Hình học Euclide, ta có các kết luận sau:

  1. Nếu một trong ba góc của tam giác , ví dụ như góc , là lớn hơn hoặc bằng 120°, thì là nghiệm duy nhất của bài toán đang được xét.
  2. Nếu tất cả các góc của tam giác đều nhỏ hơn 120°, thì nghiệm duy nhất của bài toán là điểm nhìn các cạnh , của tam giác dưới cùng một góc 120°(Điểm đặc biệt này được gọi là điểm Fermat hay điểm Torricelli (xem Weisstein (1999)). Có thể chứng tỏ rằng điểm Fermat thuộc phần trong của tam giác .)

Trong bài toán , nếu là tập nhiệm của một hệ các phương trình và bất phương trình, thì điều kiện tối ưu bậc nhất có thể viết được ở dạng có sử dụng các nhân tử Lagrange.

Chúng ta hãy xét bài toán dưới các giả thiết là một hàm lồi,

 

 

 

 

(9)

ở đó , là các hàm lồi, là các hàm affine, nghĩa là tồn tại sao cho với mọi . Chúng ta chấp nhận rằng các ràng buộc bất đẳng thức (tương ứng, các ràng buộc bất đẳng thức) có thể không có mặt trong (9). Để cho gọn, chúng ta sử dụng cách viết hình thức (tương ứng, ) để chỉ rằng các ràng buộc bất đẳng thức (tương ứng, các ràng buộc bất đẳng thức) không có mặt trong (9).

Định lý 0.0.6. (Định lý Kuhn-Tucker cho các bài toán quy hoạch lồi; xem Rockafellar (1970), tr. 283) Giả sử rằng là bài toán quy hoạch lồi với được cho bởi (9). Giả sử rằng các giả thiết đặt lên như đã nói ở trên được thỏa mãn. Giả sử rằng tồn tại véctơ sao cho

 

 

 

 

(10)

Khi đó, là một nghiệm của khi và chỉ khi tồn tại số thực được gọi là các nhân tử Langrange tương ứng với , sao cho các điều skiện Kuhn-Tucker sau đây được thỏa mãn:

Nhận xét rằng (10) là một điều kiện chuẩn hóa ràng buộc (còn được gọi là điều kiện chính quy ràng buộc, hay đơn giản là điều kiện chính quy) cho các bài toán hoạch lồi. Nếu thì nó trở thành

Nếu thì (10) tương đương với đòi hỏi rằng là khác rỗng. Trên thực tế, trong trường hợp đó, có thể bỏ qua điều kiện (10) trong phát biểu của Định lý 0.0.6.

Trơn và không trơn

Định nghĩa

Để cho gọn, nếu là hàm khả vi Fréchet liên tục, thì ta nói rằng là một (tức là hàm thuộc lớp ).

Ta gọi là bài toán quy hoạch toán học trơn nếu là hàm biểu diễn được dưới dạng (9), ở đó là các hàm . Ngược lại, được gọi là bài toán quy hoạch toán học không trơn.

Hàm Lipschitz địa phương

Một hàm được gọi là Lipschitz địa phương tại nếu tồn tại hằng số và lân cận của sao cho

 

 

 

 

(11)

Nếu là Lipschitz địa phương tại mỗi điểm thuộc , thì được gọi là hàm số Lipschitz địa phương trên .

Nếu bất đẳng thức trong (11) đúng với mọi , ở đó là một tập con của , thì ta nói là Lipschitz trên với hệ số Lipschitz .

Đạo hàm theo hướng suy rộng theo nghĩa Clarke

Nếu là Lipschitz địa phương tại , thì đạo hàm theo hướng suy rộng theo nghĩa Clarke của tại theo hướng được định nghĩa bằng công thức

Dưới vi phân Clarke

Dưới vi phân Clarke của tại được cho bởi công thức

Định lý 0.0.7. ( Xem Clarke (1983), các Mệnh đề 2.1.2, 2.2.4, 2.2.6 và 2.2.7)

Cho là một hàm số thực. Khi đó, các khẳng định sau đây nghiệm đúng:

(a) Nếu là Lipschitz địa phương tại , thì

với mọi v ∈ Rn.

(b) Nếu là hàm , thì là hàm số Lipschitz địa phương và

(c) Nếu là lồi, thì là hàm số Lipschitz địa phương và, với mỗi , dưới vi phân Clarke trùng với dưới vi phân của tại theo nghĩa Giải tích lồi, tức là dưới vi phân được định nghĩa bởi . Ngoài ra,

Liên quan đến khẳng định (c) ở trên, chúng ta lưu ý rằng, đạo hàm theo hướng tồn tại (xem Định lý 0.0.2).

Nón tiếp tuyến Clarke

Cho C ⊂ Rn là tập con khác rỗng. Nón tiếp tuyến Clarke TC(x) của C tại x ∈ C là tập hợp tất cả các véctơ v ∈ Rn thỏa mãn d0 C(x; v) = 0, ở đó d0 C(x; v) ký hiệu đạo hàm theo hướng suy rộng theo nghĩa Clarke của hàm số Lipschitz

dC(z) := inf{ky − zk : y ∈ C}

tại x theo hướng v.

Nón pháp tuyến Clarke

Nón pháp tuyến Clarke NC(x) của C tại x được định nghĩa là nón đối ngẫu của TC(x), tức là

NC(x) = {x∗ ∈ Rn: hx∗, vi ≤ 0 với mọi v ∈ TC(x)}.

Định lý 0.0.8. (Xem Clarke (1983), các Mệnh đề 2.4.3, 2.4.4 và 2.4.5) Với mỗi tập con khác rỗng C ⊂ Rn và với mỗi điểm x ∈ C, các khẳng định sau nghiệm đúng:

(a) NC(x) = n∪t≥0 t∂dC(x)o.

(b) Nếu C là lồi, thì NC(x) trùng với nón pháp tuyến của C tại x được định nghĩa bởi công thức , và TC(x) trùng với bao đóng tôpô của hình nón

cone(C − x) := {tz : t ≥ 0, z ∈ C − x}.

(c) Bao hàm thức v ∈ TC(x) nghiệm đúng khi và chỉ khi với mỗi dãy điểm xk trong C hội tụ đến x và dãy số tk trong (0, +∞) hội tụ đến 0, tồn tại dãy véctơ vk trong Rn hội tụ đến v sao cho xk + tkvk ∈ C với mọi k.

Xét bài toán (P) dưới các giả thiết f : Rn → R là hàm Lipschitz địa phương,

D = {x ∈ C : g1(x) ≤ 0, . . . , gm(x) ≤ 0, h1(x) = 0, . . . , hs(x) = 0}, (12)

với C ⊂ Rn là tập khác rỗng, gi: Rn → R (i = 1, . . . , m) và hj: Rn → R(j = 1, . . . , s) là các hàm Lipschitz địa phương.

Định lý 0.0.9. (Xem Clarke (1983), Định lý 6.1.1 và Nhận xét 6.1.2) Nếu x¯ là nghiệm địa phương của (P), thì tồn tại m + s + 1 số thực λ0 ≥ 0, λ1 ≥ 0, . . . , λm ≥ 0, µ1, . . . , µs, không đồng thời bằng 0, sao cho

0 ∈ λ0∂f(¯x) +Xm i=1 λi∂gi(¯x) +Xs j=1 µj∂hj (¯x) + NC(¯x) (13)

λigi(¯x) = 0 với mọi i = 1, 2, . . . , m. (14)

Điều kiện cần tối ưu bậc nhất ở dạng Fritz-John

Định lý trên phát biểu điều kiện cần tối ưu bậc nhất ở dạng Fritz-John cho một lớp bài toán không trơn. Dưới những điều kiện chính quy ràng buộc thích hợp, nhân tử λ0 tương ứng với hàm mục tiêu f là dương. Trong trường hợp đó, bằng cách chia cả hai vế của bao hàm thức trong (13) và các đẳng thức trong (14) cho λ0, và đặt λei = λi/λ0 cho mỗi i = 1, . . . , m, µej = µj/λ0 cho mỗi j = 1, . . . , s, chúng ta thu được

0 ∈ ∂f(¯x) +Xmi=1λei∂gi(¯x) +X s j=1 µej∂hj (¯x) + NC(¯x) (15)

λeigi(¯x) = 0 với mọi i = 1, 2, . . . , m. (16)

Tương tự như trong trường hợp các bài toán quy hoạch lồi (Định lý 1.6), nếu x¯ ∈ D và (15), (16) nhiệm đúng, thì các số λe1 ≥ 0, . . . , λem ≥ 0, µe1 ∈ R, . . . , µes ∈ R được gọi là các nhân tử Lagrange tương ứng với x¯.

Hai quy tắc nhân tử Lagrange sau đây suy ra từ Định lý 0.0.9 (xem Clarke(1983), tr. 234–236).

Hệ quả 0.0.1. Nếu x¯ là một nghiệm địa phương của (P) và nếu điều kiện chuẩn hóa ràng buộc


h0 ∈Xmi=1λi∂gi(¯x) +Xsj=1µj∂hj (¯x) + NC(¯x),

λ1 ≥ 0, . . . , λm ≥ 0, µ1 ∈ R, . . . , µs ∈ R;

λigi(¯x) = 0 với i = 1, . . . , mi

=⇒[λ1 = · · · = λm = 0, µ1 = · · · = µs = 0i]

được thỏa mãn, thì tồn tại các nhân tử Lagrange λ1 ≥ 0, . . . , λm ≥ 0, µ1 ∈ R, . . . , µs ∈ R sao cho λigi(¯x) = 0 với i = 1, 2, . . . , m, và

0 ∈ ∂f(¯x) +X m i=1 λi∂gi(¯x) +X s j=1 µj∂hj (¯x) + NC(¯x).

Hệ quả 0.0.2. Giả sử rằng x¯ là một nghiệm địa phương của bài toán quy hoạch trơn (P), ở đó D được cho bởi công thức (9). Nếu điều kiện chuẩn hóa ràng buộc Mangasarian-Fromovitz (viết tắt: (MFCQ))

Các véctơ {∇hj (¯x) : j = 1, . . . , s} là độc lập tuyến tính,

và tồn tại v ∈ Rn sao cho h∇hj (¯x), vi = 0

với mỗi j = 1, . . . , s, và h∇gi(¯x), vi < 0

với mỗi i = 1, . . . , m thỏa mãn gi(¯x) = 0

được thỏa mãn, thì tồn tại các nhân tử Lagrange λ1 ≥ 0, . . . , λm ≥ 0, µ1 ∈ R, . . . , µs ∈ R sao cho λigi(¯x) = 0 với i = 1, 2, . . . , m, và

0 = ∇f(¯x) +X m i=1 λi∇gi(¯x) +X s j=1 µj∇hj (¯x).

Sử dụng Định lý 0.0.9 ta dễ dàng chứng minh được quy tắc nhân tử Lagrange cho các bài toán quy hoạch lồi đã được phát biểu trong Định lý 0.0.6 (xem Lee, Tam, Yen (2005), tr. 18–19).

Tuyến tính và phi tuyến

Tập lồi đa diện

Tập hợp D ⊂ Rn được gọi là tập lồi đa diện nếu như ta có thể biểu diễn D dưới dạng giao của một số hữu hạn các nửa không gian đóng của R n; nghĩa là tồn tại các véctơ khác không a1, . . . , am ∈ Rn và các số thực β1, . . . , βm sao cho

D = {x ∈ Rn : hai , xi ≥ βi với i = 1, . . . , m}. (17)

Nói một cách khác, D là tập nghiệm của một hệ gồm hữu hạn các bất đẳng thức tuyến tính. (Chúng ta quy ước rằng giao của một họ rỗng của các nửa không gian đóng của Rn là Rn. Vì thế, D = Rn cũng là một tập lồi đa diện.)

Điểm cực biên

Một điểm x ∈ D được gọi là điểm cực biên của D nếu như không thể nào biểu diễn x dưới dạng x = (1 − t)y + tz, ở đó y ∈ D, z ∈ D, y 6= z, và t ∈ (0, 1). Tập hợp tất cả các điểm cực biên của D được ký hiệu bởi extrD. Ký hiệu bởi A ma trận cấp m × n với các phần tử aij (i = 1, . . . , m, j = 1, . . . , n), ở đó aij là thành phần thứ j của véctơ ai. Đặt b = (β1, . . . , βm) ∈ Rm. Khi đó, ta có thể viết lại (17) như sau:

D = {x ∈ Rn: Ax ≥ b}.

Từ đây về sau, đối với hai véctơ tùy ý y = (y1, . . . , ym) ∈ Rm và z = (z1, . . . , zm) ∈ R m, ta viết y ≥ z nếu yi ≥ zi với i = 1, . . . , m. Ta sẽ viết y > z nếu yi > zi với mọi i = 1, . . . , m. Vì

{x ∈ Rn: Ax = b} = {x ∈ Rn: Ax ≥ b, (−A)x ≥ −b},

ta suy ra rằng {x ∈ Rn: Ax = b} là một tập lồi đa diện.

Bài toán quy hoạch tuyến tính

Bài toán (P) được gọi là bài toán quy hoạch tuyến tính nếu D là tập lồi đa diện và f(x) là phiếm hàm tuyến tính. Ngược lại, (P) được gọi là bài toán quy hoạch phi tuyến.

Có ba dạng điển hình của bài toán quy hoạch tuyến:

min{f(x) = hc, xi : x ∈ Rn, Ax ≥ b},

min{f(x) = hc, xi : x ∈ Rn, Ax = b, x ≥ 0},

min{f(x) = hc, xi : x ∈ Rn, Ax ≥ b, Cx = d};

chúng được gọi tương ứng là dạng chuẩn, dạng chính tắc, và dạng tổng quát. Ở đây, A ∈ Rm×n, C ∈ Rs×n là các ma trận cho trước, c ∈ Rn, b ∈ Rm và d ∈ Rs là các véctơ cho trước.

Xét bài toán quy hoạch tuyến tính dạng chuẩn:

min nx1 +12x2 : x = (x1, x2), x1 + x2 ≥ 1, x1 ≥ 0, x2 ≥ 0o.

Dễ kiểm tra rằng Sol(P) = {(0, 1)}. Nhận xét rằng tập ràng buộc

D = {x ∈ R2: x1 + x2 ≥ 1, x1 ≥ 0, x2 ≥ 0}

có hai điểm cực biên, cụ thể là extr = {(1, 0), (0, 1)}. Một trong hai điểm đó là nghiệm của bài toán được xét.

Bài toán đối ngẫu

Bài toán đối ngẫu của các bài toán quy hoạch tuyến tính dạng chuẩn, dạng chính tắc, và dạng tổng quát, tương ứng là:

max{hb, yi : y ∈ Rm, ATy = c, y ≥ 0},

max{hb, yi : y ∈ Rm, ATy ≤ c},

max{hb, yi + hd, zi : (y, z) ∈ Rm × Rs, ATy + CTz = c, y ≥ 0}.

Vì bài toán quy hoạch tuyến tính cũng là một bài toán quy hoạch lồi, nên nó có tất cả các tính chất của bài toán quy hạch lồi. Ngoài ra, bài toán quy hoạch tuyến tính còn có những tính chất đặc biệt khác.

Định lý 0.0.10. (Xem Dantzig (1963)) Cho (P) là bài toán quy hoạch tuyến tính ở một trong các dạng điển hình. Các tính chất sau đây nghiệm đúng:

(i) Nếu tập ràng buộc là khác rỗng và nếu v(P) > −∞, thì Sol(P) là tập lồi đa diện khác rỗng.

(ii) Nếu cả hai tập extrD và Sol(P) đều khác rỗng, thì giao extrD ∩ Sol(P) cũng là khác rỗng.

(iii) Nếu rankA = n và tập D := {x ∈ Rn: Ax = b, x ≥ 0} là khác rỗng, thì D phải có ít nhất một điểm cực biên.

(iv) Giá trị tối ưu v(P) của (P) và giá trị tối ưu v(P0) of của bài toán đối ngẫu(P0) của (P) là bằng nhau, nếu như tập ràng buộc của ít nhất là một trong hai bài toán là khác rỗng.

Tham khảo

  • Lee, Tam, Yen (2005), Chương 1.