Tối ưu hóa lồi - Hull

Phần lồi của một tập hợp các điểm trong S là biên của vùng lồi nhỏ nhất chứa tất cả các điểm của S bên trong nó hoặc trên biên của nó.

HOẶC LÀ

Cho $ S \ subseteq \ mathbb {R} ^ n $ Phần lồi của S, ký hiệu là $ Co \ left (S \ right) $ by là tập hợp tất cả các tổ hợp lồi của S, tức là $ x \ trong Co \ left (S \ right) $ nếu và chỉ khi $ x \ in \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i $, trong đó $ \ displaystyle \ sum \ limit_ {1} ^ n \ lambda_i = 1 $ và $ \ lambda_i \ geq 0 \ forall x_i \ bằng S $

Remark - Tập hợp các điểm thuộc S trong mặt phẳng xác định một đa giác lồi và các điểm của S trên biên của đa giác xác định các đỉnh của đa giác.

Theorem $ Co \ left (S \ right) = \ left \ {x: x = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i, x_i \ in S, \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 \ right \} $ Chứng tỏ rằng một vỏ lồi là một tập lồi.

Bằng chứng

Đặt $ x_1, x_2 \ trong Co \ left (S \ right) $, sau đó $ x_1 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i $ và $ x_2 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ \ gamma x_i $ trong đó $ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ và $ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Đối với $ \ theta \ in \ left (0,1 \ right), \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ theta \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_ix_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i \ theta x_i + \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_i \ left (1- \ theta \ right) x_i $

$ \ theta x_1 + \ left (1- \ theta \ right) x_2 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ phải] x_i $

Xem xét các hệ số,

$ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ left [\ lambda_i \ theta + \ gamma_i \ left (1- \ theta \ right) \ right] = \ theta \ displaystyle \ sum \ limit_ {i = 1 } ^ n \ lambda_i + \ left (1- \ theta \ right) \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_i = \ theta + \ left (1- \ theta \ right) = 1 $

Do đó, $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

Do đó, một vỏ tàu lồi là một tập hợp lồi.