การเพิ่มประสิทธิภาพการนูน - ตัวถัง

ตัวถังนูนของชุดจุดใน S คือขอบเขตของส่วนนูนที่เล็กที่สุดซึ่งมีจุดทั้งหมดของ S อยู่ภายในหรือบนขอบเขตของมัน

หรือ

ให้ $ S \ subseteq \ mathbb {R} ^ n $ ตัวนูนของ S ซึ่งแสดงว่า $ Co \ left (S \ right) $ by คือชุดของชุดค่าผสมนูนทั้งหมดของ S นั่นคือ $ x \ in Co \ left (S \ right) $ if and only if $ x \ in \ displaystyle \ sum \ LIMIT_ {i = 1} ^ n \ lambda_ix_i $ โดยที่ $ \ displaystyle \ sum \ LIMIT_ {1} ^ n \ lambda_i = 1 $ และ $ \ lambda_i \ geq 0 \ forall x_i \ ใน S $

Remark - การสร้างฮัลล์ของชุดของจุดใน S ในระนาบกำหนดรูปหลายเหลี่ยมนูนและจุดของ S บนขอบเขตของรูปหลายเหลี่ยมจะกำหนดจุดยอดของรูปหลายเหลี่ยม

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 \} $ แสดงว่าตัวถังนูนเป็นชุดนูน

หลักฐาน

ให้ $ x_1, x_2 \ in Co \ left (S \ right) $ แล้ว $ x_1 = \ displaystyle \ sum \ LIMIT_ {i = 1} ^ n \ lambda_ix_i $ และ $ x_2 = \ displaystyle \ sum \ LIMIT_ {i = 1} ^ n \ lambda_ \ gamma x_i $ โดยที่ $ \ displaystyle \ sum \ LIMIT_ {i = 1} ^ n \ lambda_i = 1, \ lambda_i \ geq 0 $ และ $ \ displaystyle \ sum \ LIMIT_ {i = 1} ^ n \ gamma_i = 1, \ gamma_i \ geq0 $

สำหรับ $ \ 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 \ ซ้าย (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) \ ขวา] x_i $

พิจารณาค่าสัมประสิทธิ์

$ \ 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 $

ดังนั้น $ \ theta x_1 + \ left (1- \ theta \ right) x_2 \ in Co \ left (S \ right) $

ดังนั้นตัวถังนูนจึงเป็นชุดนูน