Optimasi Cembung - Hull

Lambung cembung dari sekumpulan titik di S adalah batas dari wilayah cembung terkecil yang berisi semua titik S di dalamnya atau di batasnya.

ATAU

Misal $ S \ subseteq \ mathbb {R} ^ n $ Convex hull dari S, dinotasikan $ Co \ left (S \ right) $ by adalah kumpulan dari semua kombinasi cembung S, yaitu $ x \ in Co \ left (S \ kanan) $ jika dan hanya jika $ x \ in \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i $, dengan $ \ displaystyle \ sum \ limit_ {1} ^ n \ lambda_i = 1 $ dan $ \ lambda_i \ geq 0 \ untuk semua x_i \ dalam S $

Remark - Conves hull dari sekumpulan titik di S pada bidang mendefinisikan poligon cembung dan titik S pada batas poligon mendefinisikan simpul dari poligon.

Theorem $ Co \ kiri (S \ kanan) = \ kiri \ {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 \} $ Tunjukkan bahwa convex hull adalah himpunan cembung.

Bukti

Misalkan $ x_1, x_2 \ di Co \ kiri (S \ kanan) $, lalu $ x_1 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ix_i $ dan $ x_2 = \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_ \ gamma x_i $ dengan $ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ dan $ \ displaystyle \ sum \ limit_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

Untuk $ \ 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 \ kanan) \ displaystyle \ sum \ batas_ {i = 1} ^ n \ gamma_ix_i $

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

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

Mempertimbangkan koefisien,

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

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

Jadi, lambung cembung adalah himpunan cembung.