Mục đích của luận văn là giới thiệu lại kiến thức cơ bản về giải tích lồi, bài toán về quy hoạch lồi. Đặc biệt đi sâu vào các bài chấp nhận lồi tách và một phương pháp giải. Mời các bạn tham khảo!
Tập lồi, hàm lồi
Tập lồi trong R n được định nghĩa là một tập C ⊆ R n mà chứa mọi đoạn thẳng nối giữa hai điểm bất kỳ trong tập đó Điều này có nghĩa là tập C lồi khi và chỉ khi mọi đoạn thẳng đi qua hai điểm thuộc C đều hoàn toàn nằm trong C.
Ta nóixlàtổ hợp lồicủa các điểm (véctơ)x 1 , x 2 , , x k nếu x k
Tương tự,xlàtổ hợp affinecủa các điểm (véctơ)x 1 , , x k nếu x k
Tập hợp của các tổ hợp affine của x 1 , , x k thường được gọi là bao affinecủa các điểm này.
Hình 1.1: (a), (b), (e) - Tập lồi; (c), (d) - Tập không lồi
Mệnh đề 1.1 Tập hợp C là lồi khi và chỉ khi nó chứa mọi tổ hợp lồi của các điểm của nó Tức là:C lồi khi và chỉ khi
Chúng ta sẽ chứng minh điều kiện cần bằng phương pháp quy nạp theo số điểm Đối với trường hợp k = 2, điều này có thể được suy ra trực tiếp từ định nghĩa của tập lồi và tổ hợp lồi Giả sử mệnh đề đúng với k - 1 điểm, nhiệm vụ của chúng ta là chứng minh nó cũng đúng với k điểm.
Giả sửxlà tổ hợp lồi củakđiểmx 1 , , x k ∈C Tức là x k
X j=1 λ j ζ = 1 và λ j ζ >0với mọij = 1, , k−1nên theo giả thiết quy nạp, điểm y : k−1
X j=1 λ j = 1, nênxlà một tổ hợp lồi của hai điểmy vàx k đều thuộcC Vậyx∈ C.
Lớp các tập lồi là đóng với các phép giao, phép cộng đại số và phép nhân tích Descartes Cụ thể, ta có mệnh đề sau:
Mệnh đề 1.2 NếuA, B là các tập lồi trongR n , C là lồi trong R m , thì các tập sau là lồi :
A×C := {x ∈R n+m | x= (a, c) : a ∈A, c ∈C}. Định nghĩa 1.2 Một điểma∈C được gọi làđiểm trong tương đốicủaCnếu nó là điểm trong củaC theo tô-pô cảm sinh bởi affC (tập affine nhỏ nhất chứaC).
Tập hợp các điểm trong tương đối của C được ký hiệu là riC, được định nghĩa như sau: riC := {a ∈ C | ∃B: (a+B)∩affC ⊂ C}, trong đó B là một lân cận mở của gốc Rõ ràng, riC cũng có thể được mô tả là {a ∈ affC | ∃B: (a+B)∩affC ⊂ C}.
Tiếp theo ta nhắc khái niệm hàm lồi và một số khái niệm liên quan.
ChoC ⊆ R n là tập lồi vàf: C → R Ta sẽ ký hiệu domf :={x∈C | f(x) 0khi và chỉ khi hàm h(.) := f(.)− η
Bằng qui nạp, dễ dàng chứng minh được rằng, nếuf nhận giá trị hữu hạn trên tập lồiC, thì với mọi số tự nhiênmvà mọix 1 , , x m ∈ Cthoả mãnλ 1 ≥ 0, , λ m ≥0, m
Hàmf được gọi là mộthàm lõmtrênC, nếu−f lồi trênC.
Ví dụ 1.1 Cho S := {x ∈ R n | kxk = 1}là một mặt cầu và h: S → R+ là một hàm bất kỳ Định nghĩa hàmf như sau: f(x) :
Hàm này được gọi là hàm mặt cầu Dễ thấy rằngf là một hàm lồi trênR n , mặc dùh là một hàm không âm bất kỳ trên mặt cầuS.
Ví dụ 1.2 Ví dụ về hàm lồi, hàm lõm
Hình 1.2: (a) - Hàm lồi; (b) - Hàm lõm
Dưới đây là một điều kiện cần và đủ về hàm lồi, rất tiện ích trong nhiều trường hợp.
Mệnh đề 1.3 Một hàm f: C → Rlà lồi trênC khi và chỉ khi
Chứng minh Chứng minh điều kiện cần Giả sử f lồi Chọnx, y, α, β như đã nêu trong mệnh đề Chọn α 0 ∈ (f(x), α) vàβ 0 ∈ (f(y), β) Vậy (x, α 0 )và(y, β 0 )thuộc epif Do epif lồi, nên
Chứng minh điều kiện đủ Chọn(x, à) và (y, ν) thuộc epif và λ ∈ (0,1) Thế thì với mọi > 0, ta có f(x)< à+, f(y) < ν+.
Do đó f [(1−λ)α 0 +λβ 0 ]< (1−λ)(à+) +λ(ν +) = (1−λ)à+λν +. Điều này đúng với mọi >0, nên cho→ 0, ta được f [(1−λ)α 0 +λβ 0 ] ≤(1−λ)à+λν.
Hàm lồi được định nghĩa thông qua hệ số lồi Cụ thể, cho hàm f: R n → R∪ {+∞} (không nhất thiết phải lồi) và tập lồi C ⊆ R n không rỗng, một số thực η được gọi là hệ số lồi của f trên C nếu với mọi λ ∈(0,1) và mọi x, y thuộc C, điều kiện f [(1−λ)x+λy] ≤ (1−λ)f(x) +λf(y) - 1 được thỏa mãn.
Hiển nhiên nếuη = 0 thìf lồi trênC Nếuf có hệ số lồi trên C làη > 0, thìf lồi mạnh trênCvới hệ số η.
Một hàmf được gọi làchính thường nếu domf 6= ∅vàf(x) > −∞với mọix. Hàmf được gọi làđóng, nếu epif là một tập đóng trongR n+1
Như đã nói ở trên, nếuf là một hàm lồi trên một tập lồi C, thì có thể thác triển f lên toàn không gian bằng cách đặt f e (x) :
Hàm f e (x) = f(x) với mọi x ∈ C và f e là hàm lồi trên R n Hơn nữa, f e là chính thường khi và chỉ khi f là chính thường Tương tự, f e đóng khi và chỉ khi f đóng Lưu ý rằng, nếu f là một hàm lồi trên R n, thì tập xác định domf cũng là một tập lồi, vì domf chính là hình chiếu trên R n của epif, tức là: domf = {x | ∃a ∈ R: (x, a) ∈ epif}.
Hàm lồi được xác định bởi đồ thị của nó, và điều này giải thích lý do tại sao trong thực tế, người ta thường chỉ tập trung vào các hàm lồi chính.
Mệnh đề 1.4 Giả sửf là một hàm lồi không chính thường trênR n vàf 6≡+∞ Khi đóf(x) =−∞với mọix ∈ri(domf).
Chứng minh rằng theo định nghĩa hàm chính thường, nếu miền xác định của hàm f không rỗng, thì tồn tại một điểm x0 sao cho f(x0) = −∞ Giả sử x thuộc miền nội của miền xác định của f Theo định nghĩa về điểm trong tập hợp tương đối, tồn tại y thuộc miền xác định của f sao cho x = λy + (1−λ)x0 với λ nằm trong khoảng (0,1) Do hàm f là hàm lồi và f(y) < +∞, nên ta có f(x) ≤ λf(y) + (1−λ)f(x0) = −∞.
Để tránh làm việc với các hàm lồi đồng nhất với −∞ trong miền hữu dụng, từ nay khi đề cập đến hàm lồi trên R n, chúng ta hiểu đó là hàm chính thường, không đồng nhất với +∞ và không nhận giá trị −∞.
Mệnh đề 1.5 Nếuf là một hàm lồi trênR n , thì các tập mức
Chứng minh Trường hợp α = +∞ hoặc−∞ là hiển nhiên (nhớ rằng tập rỗng là lồi) Lấyx, y ∈ l f (α) Tức làf(x) < α, f(y) < α Dof lồi, nên theo Mệnh đề 1.3, với mọiλ ∈(0,1)ta có: f(λx+ (1−λ)y) < λα+ (1−λ)α= α.
TậpL f (α) = \ à>α l f (à), nờn nú cũng là tập lồi.
Một lớp hàm lồi rất quan trọng là hàm lồi thuần nhất dương Nhắc lại rằng một hàmf được gọi làthuần nhất dương(bậc 1) trênR n nếu f(λx) =λf(x)∀x ∈R n , ∀λ >0.
Một hàm thuần nhất dương không nhất thiết là hàm lồi, tuy nhiên ta dễ dàng chứng minh mệnh đề sau:
Mệnh đề 1.6 Cho f là một hàm thuần nhất dương trênR n Khi đóf lồi khi và chỉ khi nó là dưới cộng tính, theo nghĩa f(x+y) ≤f(x) +f(y)∀x, y.
Một hàm thuần nhất dương và dưới cộng tính được gọi làdưới tuyến tính Một ví dụ điển hình về hàm dưới tuyến tính là hàm chuẩnf(x) =kxk.
Toán tử chiếu lên tập lồi đóng
Trong phần này, chúng ta sẽ chứng minh sự tồn tại và tính duy nhất của hình chiếu xuống một tập lồi đóng, đồng thời khảo sát một số tính chất cơ bản của toán tử chiếu Định nghĩa 1.5 nêu rõ rằng, với ∅ 6= C ⊆ R n (không nhất thiết phải lồi) và y là một véctơ bất kỳ, khoảng cách từ y đến C được xác định bởi d C (y) := inf x∈C kx−yk Nếu tồn tại một điểm π ∈ C sao cho d C (y) = kπ−yk, thì π được gọi là hình chiếu của y trên C.
Theo định nghĩa, ta thấy rằng hình chiếu p C (y) của y trên C sẽ là nghiệm của bài toán tối ưumin x
Nói cách khác việc tìm hình chiếu của y trênC có thể đưa về việc tìm cực tiểu của hàm toàn phươngkx−yk 2 trênC.
Ta ký hiệu π = p C (y) hoặc đơn giản là p(y) nếu không cần nhấn mạnh đến tập chiếu C Lưu ý rằng, khi C khác rỗng, thì d C (y) sẽ hữu hạn, với điều kiện 0 ≤ d C (y) ≤ k y - x k cho mọi x thuộc C Xét C ⊆ R n và x 0 thuộc C, nón pháp tuyến (ngoài) của tập C tại x 0 được định nghĩa là tập hợp các điểm liên quan.
Hình 1.3: Hình chiếu vuông góc
Mệnh đề 1.7 Cho Clà một tập lồi đóng khác rỗng Khi đó:
(i) Với mọiy ∈R n ,π ∈C hai tính chất sau là tương đương: a) π =p C (y), b) y−π ∈ N C (π).
(ii) Với mọiy ∈R n , hình chiếup C (y)củay trênC luôn tồn tại và duy nhất.
(iii) Nếuy 6∈ C, thìhp C (y)−y, x−p C (y)i= 0là siêu phẳng tựa củaC tạip C (y) và tách hẳny khỏi C, tức là hp C (y)−y, x−p C (y)i ≥ 0, ∀x∈ C, và hp C (y)−y, y−p C (y)i 0, ta nhận được λkx−πk 2 + 2hx−π, π−yi ≥ 0 Điều này áp dụng cho mọi x thuộc C và λ trong khoảng (0,1) Khi cho λ tiến đến 0, ta rút ra hπ−y, x−πi ≥ 0 với mọi x thuộc C.
Bây giờ giả sử cób) Với mọix∈ C, có
Từ đây vàb), dùng bất đẳng thức Cauchy-Schwarz ta có: ky−πk 2 ≤ (y−π) T (y−x) ≤ ky −πkky−xk.
Suy raky−πk ≤ ky −xk ∀x∈C, và do đóπ =p(y).
(ii) Dod C (y) = inf x∈Ckx−yk, nên theo định nghĩa của cận dưới đúng, tồn tại một dãy{x k } ∈ C sao cho lim k kx k −yk=d C (y) 0vàζ >0 Nếu tậpΩbị chặn, khi đó ta có
(i) ∇p(x) liên tục Lipschitz vớiL = α+ 2L 1 β là hằng số Lipschitz, trong đó L 1 được định nghĩa trong (2.14).
(ii) Nếup(x) lồi thì∇p(x)tự bức với hệ số ν = 1
Chứng minh DoP C không giãn nên k(I −P C )(x−y)k ≤ kx−yk ∀x, y ∈R n
Vì vậy ta có k(I −P C )(x)−(I −P C )(y)k ≤ kx−yk ∀x, y ∈R n Mặt khác, vìF và∇F đều liên tục Lipschitz nên ta có k∇F(x) T (I −P D )(F(x))− ∇F(y) T (I −P D )(F(y))k
Bất đẳng thức ≤ 2L 1 kx−yk thể hiện mối quan hệ giữa các giá trị, trong đó bất đẳng thức đầu tiên và thứ hai dựa trên bất đẳng thức tam giác Bất đẳng thức thứ ba được thiết lập dựa trên tính chất của chuẩn L 1 trong bất đẳng thức cuối cùng đóng vai trò quan trọng trong việc xác định các giá trị này.
2ã[kF(y)k+kP D (F(z))k], (2.14) do tính bị chặn củaΩvà tính liên tục củaF,∇F Do đó k∇p(x)− ∇p(y)k ≤αk(I −P C )(x)−(I −P C )(y)k
Khẳng định đầu tiên đã được chứng minh, trong đó p(x) là hàm lồi và ∇p(x) liên tục Lipschitz với hằng số L Từ đó, khẳng định thứ hai cũng được suy ra từ một kết quả đã được biết đến trong tài liệu [8].
Chú ý 2.3 Tính liên tục Lipschitz của ánh xạ∇p(x) là quan trọng cho sự phân tích sự hội tụ thuật toán được đề nghị dưới đây.
Giả thiết 2.1 khẳng định rằng ánh xạ F và ∇F đều liên tục Lipschitz, đồng thời tập lồi Ω bị chặn và C thuộc Ω Dưới giả thiết 1.1 đã được thỏa mãn, chúng ta có thể trình bày bổ đề sau đây.
Bổ đề 2.4 khẳng định rằng, cho Ω là một tập lồi không rỗng trong R n và hàm p(x) là hàm lồi khả vi trên một tập mở chứa Ω, thì vectơ x ∗ sẽ là cực tiểu của bài toán (2.12)-(2.13) nếu và chỉ nếu nó thỏa mãn bất đẳng thức biến phân tương ứng.
Chứng minh Từ p(x) lồi và khả vi trên một tập mở chứa Ωvà bất đẳng thức (2.15) thỏa mãn ta có p(x) ≥ p(x ∗ ) +∇p(x ∗ ) T (x−x ∗ ) ≥ p(x ∗ ) ∀x∈Ω, suy rax ∗ là cực tiểu củap(x)trênΩ.
Ngược lạix ∗ là cực tiểu thỏa mãn bài toán (2.12)–(2.13) và bất đẳng thức (2.15) không thỏa mãn, tức là tồn tạix¯∈Ωthỏa mãn
Bằng cách lấy đạo hàm ta có limα↓0 p(x ∗ +α(¯x−x ∗ ))−p(x ∗ ) α =∇p(x ∗ ) T (¯x−x ∗ )< 0.
Vậy p(x ∗ +α(¯x−x ∗ ))giảm chặt khiα > 0đủ nhỏ và điều này mâu thuẫn với giả thiết tối ưu củax ∗
Bài toán (2.12)-(2.13) có thể được chuyển đổi về bài toán bất đẳng thức biến phân (2.15) Đối với tập đơn giản Ω, việc tính toán hình chiếu trở nên dễ dàng Để tổng quát hóa, chúng ta có thuật toán chiếu nhằm giải quyết bài toán (2.15), trong đó x k+1 được xác định theo công thức: x k+1 = P Ω (x k − β k+1 ∇p(x k )).
, trong đóβ k+1 >0là độ dài bước.
Dựa trên các kết quả đã trình bày, chúng ta có thể áp dụng thuật toán đạo hàm cho quy hoạch lồi để giải bài toán chấp nhận tách Ngoài ra, có thể sử dụng thuật toán chiếu đạo hàm như một phương pháp thay thế để giải quyết vấn đề này.
Thuật toán 2.2 Thuật toán chiếu được trình bày như sau:
•Bước 1: Cho dãy không âm {τ k }với
•Bước 2: Tỡm số nguyờn khụng õm nhỏ nhấtl k sao choβ k+1 =à l k γ k và x k+1 =P Ω x k −β k+1 ∇p(x k )
•Bước 3: Nếu β k+1 k∇p(x k )− ∇p(x k+1 )k 2 ≤0.5(x k −x k+1 ) T (∇p(x k )− ∇p(x k+1 )), thì lấyγ k+1 = (1 +τ k+1 )β k+1 ; trái lại thì lấyγ k+1 =β k+1
•Bước 4: Nếuke(x k , β k )k ≤ εthì STOP, trái lạik := k+ 1chuyển đến Bước 2.
Nhận xét 2.1 Từ tham sốδ ∈(0,1)và∇p(x)tự bức từ Bổ đề 2.3, vế phải của (2.17) luôn luôn không âm Do đó ta tìmβ k+1 không âm đủ bé để thỏa mãn (2.17).
Ta có kết quả sau về cách chọnβ k
Bổ đề 2.5 khẳng định rằng trong mỗi bước lặp của Thuật toán 2.2, quá trình tìm độ dài bước β k+1 sẽ kết thúc sau một số hữu hạn bước lặp Hơn nữa, tồn tại một số thực dương β min, đảm bảo rằng β k+1 luôn lớn hơn hoặc bằng β min và β min lớn hơn 0 cho mọi k lớn hơn 0.
Chứng minh Từ ∇p(x) tự bức vớiν = 1
L > 0, trong đó L được định nghĩa trong
Bổ đề 2.3, ta có β k+1 k∇p(x k )− ∇p(x k+1 )k 2 hx k −x k+1 ,∇p(x k )− ∇p(x k+1 )i ≤ β k+1 k∇p(x k )− ∇p(x k+1 )k 2
, điều kiện (2.17) được thỏa mãn Mặt khác, theo Bước 2 và Bước 3 trong Thuật toán 2.2, ta được β k+1 ≤ γ k ≤(1 +τ k )β k ≤ ã ã ã ≤
X k=0 τ k < ∞, τ k ≥ 0 ∀k ≥ 0, thì trong Bước 1 ta có
Dãy {γ k} bị chặn với điều kiện β k+1 ≤ γ k ≤ C 0 β 0 Với a ∈ (0,1) và lim n→∞ a n = 0, quá trình tìm β k+1 thỏa mãn (2.17) sẽ hoàn thành sau một số bước lặp hữu hạn, tức là tồn tại l k sao cho β k+1 = a l k γ k ≤ β max Hơn nữa, β k+1 cũng thỏa mãn điều kiện β k+1 ≥ β min := β max với mọi k ≥ 0.
Nếux k+1 =x k vớik nào đó, theo (2.16) và [8, Bổ đề 2.1] ta có
