การเพิ่มประสิทธิภาพการนูน - ชุดรูปหลายเหลี่ยม

ชุดใน $ \ mathbb {R} ^ n $ ถูกกล่าวว่าเป็นรูปหลายเหลี่ยมถ้ามันเป็นจุดตัดของจำนวน จำกัด ของช่องว่างครึ่งปิดนั่นคือ

$ S = \ left \ {x \ in \ mathbb {R} ^ n: p_ {i} ^ {T} x \ leq \ alpha_i, i = 1,2, .... , n \ right \} $

ตัวอย่างเช่น,

  • $ \ left \ {x \ in \ mathbb {R} ^ n: AX = b \ right \} $

  • $ \ left \ {x \ in \ mathbb {R} ^ n: AX \ leq b \ right \} $

  • $ \ left \ {x \ in \ mathbb {R} ^ n: AX \ geq b \ right \} $

กรวยหลายเหลี่ยม

ชุดใน $ \ mathbb {R} ^ n $ จะกล่าวว่าเป็นรูปกรวยหลายเหลี่ยมถ้ามันเป็นจุดตัดของจำนวนช่องว่างครึ่งหนึ่งที่มีจุดกำเนิดเช่น $ S = \ left \ {x \ in \ mathbb { R} ^ n: p_ {i} ^ {T} x \ leq 0, i = 1, 2, ... \ right \} $

Polytope

polytope คือชุดรูปหลายเหลี่ยมซึ่งมีขอบเขต

หมายเหตุ

  • polytope คือเปลือกนูนของชุดจุดที่ จำกัด
  • กรวยรูปหลายเหลี่ยมถูกสร้างขึ้นโดยชุดเวกเตอร์ที่ จำกัด
  • ชุดรูปหลายเหลี่ยมเป็นชุดปิด
  • ชุดรูปหลายเหลี่ยมคือชุดนูน