Tối ưu hóa lồi - Polar Cone

Gọi S là một tập khác rỗng trong $ \ mathbb {R} ^ n $ Khi đó, hình nón cực của S ký hiệu là $ S ^ * $ được cho bởi $ S ^ * = \ left \ {p \ in \ mathbb {R } ^ n, p ^ Tx \ leq 0 \: \ forall x \ in S \ right \} $.

Nhận xét

• Hình nón có cực luôn lồi ngay cả khi S không lồi.

• Nếu S là tập trống, $ S ^ * = \ mathbb {R} ^ n $.

• Sự phân cực có thể được coi là sự tổng quát của tính trực giao.

Đặt $ C \ subseteq \ mathbb {R} ^ n $ sau đó là không gian trực giao của C, ký hiệu là $ C ^ \ perp = \ left \ {y \ in \ mathbb {R} ^ n: \ left \ langle x, y \ right \ rangle = 0 \ forall x \ in C \ right \} $.

Bổ đề

Đặt $ S, S_1 $ và $ S_2 $ là các tập không rỗng trong $ \ mathbb {R} ^ n $ thì các câu sau là đúng:

• $ S ^ * $ là một hình nón lồi kín.

• $ S \ subseteq S ^ {**} $ trong đó $ S ^ {**} $ là một hình nón cực của $ S ^ * $.

• $ S_1 \ subseteq S_2 \ Rightarrow S_ {2} ^ {*} \ subseteq S_ {1} ^ {*} $.

Bằng chứng

Step 1 - $ S ^ * = \ left \ {p \ in \ mathbb {R} ^ n, p ^ Tx \ leq 0 \: \ forall \: x \ in S \ right \} $

• Cho $ x_1, x_2 \ in S ^ * \ Rightarrow x_ {1} ^ {T} x \ leq 0 $ và $ x_ {2} ^ {T} x \ leq 0, \ forall x \ in S $

  Đối với $ \ lambda \ in \ left (0, 1 \ right), \ left [\ lambda x_1 + \ left (1- \ lambda \ right) x_2 \ right] ^ Tx = \ left [\ left (\ lambda x_1 \ right ) ^ T + \ left \ {\ left (1- \ lambda \ right) x_ {2} \ right \} ^ {T} \ right] x, \ forall x \ in S $

  $ = \ left [\ lambda x_ {1} ^ {T} + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ right] x = \ lambda x_ {1} ^ {T} x + \ left (1- \ lambda \ right) x_ {2} ^ {T} \ leq 0 $

  Do đó $ \ lambda x_1 + \ left (1- \ lambda \ right) x_ {2} \ trong S ^ * $

  Do đó $ S ^ * $ là một tập lồi.

• Đối với $ \ lambda \ geq 0, p ^ {T} x \ leq 0, \ forall \: x \ in S $

  Do đó, $ \ lambda p ^ T x \ leq 0, $

  $ \ Rightarrow \ left (\ lambda p \ right) ^ T x \ leq 0 $

  $ \ Rightarrow \ lambda p \ trong S ^ * $

  Do đó, $ S ^ * $ là một hình nón.

• Để hiển thị $ S ^ * $ đã đóng, tức là để hiển thị nếu $ p_n \ rightarrow p $ dưới dạng $ n \ rightarrow \ infty $, thì $ p \ trong S ^ * $

  $ \ forall x \ in S, p_ {n} ^ {T} xp ^ T x = \ left (p_n-p \ right) ^ T x $

  Như $ p_n \ rightarrow p $ bằng $ n \ rightarrow \ infty \ Rightarrow \ left (p_n \ rightarrow p \ right) \ rightarrow 0 $

  Do đó $ p_ {n} ^ {T} x \ rightarrow p ^ {T} x $. Nhưng $ p_ {n} ^ {T} x \ leq 0, \: \ forall x \ trong S $

  Do đó, $ p ^ Tx \ leq 0, \ forall x \ in S $

  $ \ Rightarrow p \ trong S ^ * $

  Do đó, $ S ^ * $ đã bị đóng.

Step 2 - $ S ^ {**} = \ left \ {q \ in \ mathbb {R} ^ n: q ^ T p \ leq 0, \ forall p \ in S ^ * \ right \} $

Đặt $ x \ in S $, sau đó $ \ forall p \ in S ^ *, p ^ T x \ leq 0 \ Rightarrow x ^ Tp \ leq 0 \ Rightarrow x \ in S ^ {**} $

Do đó, $ S \ subseteq S ^ {**} $

Step 3 - $ S_2 ^ * = \ left \ {p \ in \ mathbb {R} ^ n: p ^ Tx \ leq 0, \ forall x \ in S_2 \ right \} $

Vì $ S_1 \ subseteq S_2 \ Rightarrow \ forall x \ in S_2 \ Rightarrow \ forall x \ in S_1 $

Do đó, nếu $ \ hat {p} \ in S_2 ^ *, $ thì $ \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_2 $

$ \ Rightarrow \ hat {p} ^ Tx \ leq 0, \ forall x \ in S_1 $

$ \ Rightarrow \ hat {p} ^ T \ trong S_1 ^ * $

$ \ Rightarrow S_2 ^ * \ subseteq S_1 ^ * $

Định lý

Gọi C là một hình nón lồi không rỗng, khi đó $ C = C ^ ** $

Bằng chứng

$ C = C ^ {**} $ theo bổ đề trước.

Để chứng minh: $ x \ in C ^ {**} \ subseteq C $

Cho $ x \ trong C ^ {**} $ và cho $ x \ notin C $

Sau đó, theo định lý tách cơ bản, tồn tại một vectơ $ p \ neq 0 $ và một vô hướng $ \ alpha $ sao cho $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Do đó, $ p ^ Tx> \ alpha $

Nhưng vì $ \ left (y = 0 \ right) \ in C $ và $ p ^ Ty \ leq \ alpha, \ forall y \ in C \ Rightarrow \ alpha \ geq 0 $ và $ p ^ Tx> 0 $

Nếu $ p \ notin C ^ * $, thì tồn tại một số $ \ bar {y} \ trong C $ sao cho $ p ^ T \ bar {y}> 0 $ và $ p ^ T \ left (\ lambda \ bar {y} \ right) $ có thể lớn tùy ý bằng cách lấy $ \ lambda $ đủ lớn.

Điều này mâu thuẫn với thực tế là $ p ^ Ty \ leq \ alpha, \ forall y \ in C $

Do đó, $ p \ in C ^ * $

Vì $ x \ in C ^ * = \ left \ {q: q ^ Tp \ leq 0, \ forall p \ in C ^ * \ right \} $

Do đó, $ x ^ Tp \ leq 0 \ Rightarrow p ^ Tx \ leq 0 $

Nhưng $ p ^ Tx> \ alpha $

Như vậy là suy nghĩ.

Do đó, $ x \ trong C $

Do đó $ C = C ^ {**} $.