مجموعة محدبة

المجموعات المحدبة من مجموعة الأعداد الحقيقية ( R ) هي الفترات ونقاط R. من أمثلة المجموعات المحدبة في المستوى الإقليدي : المضلعات المنتظمة المصمتة ، والمثلثات المصمتة، وتقاطعات المثلثات المصمتة. ومن أمثلة المجموعات المحدبة في الفضاء الإقليدي ثلاثي الأبعاد : المجسمات الأرخميدية والمجسمات الأفلاطونية . أما مجسمات كبلر-بوانسو فهي أمثلة على المجموعات غير المحدبة.

تُسمى المجموعة غير المحدبة مجموعة غير محدبة . ويُطلق أحيانًا على المضلع غير المحدب اسم مضلع مقعر ، ^{[ 5 ]} وتستخدم بعض المصادر مصطلح المجموعة المقعرة بشكل عام للدلالة على المجموعة غير المحدبة، ^{[ 6 ]} لكن معظم المراجع تمنع هذا الاستخدام. ^{[ 7 ] [ 8 ]}

يُطلق على مكمل المجموعة المحدبة، مثل الرسم البياني العلوي للدالة المقعرة ، أحيانًا اسم المجموعة المحدبة العكسية ، خاصة في سياق التحسين الرياضي . ^{[ 9 ]}

تتمتع مجموعة المجموعات الجزئية المحدبة لفضاء متجهي أو فضاء أفيني أو فضاء إقليدي بالخصائص التالية: ^{[ 10 ] [ 11 ]}

1. المجموعة الفارغة والفضاء بأكمله محدبان.
2. تقاطع أي مجموعة من المجموعات المحدبة يكون محدبًا.
3. يكون اتحاد مجموعة من المجموعات المحدبة محدبًا إذا شكلت هذه المجموعات سلسلة (مجموعة مرتبة كليًا) تحت الاحتواء. ولتحقيق هذه الخاصية، يُعدّ الاقتصار على السلاسل أمرًا مهمًا، إذ ليس بالضرورة أن يكون اتحاد مجموعتين محدبتين محدبًا.

المجموعات المحدبة المغلقة هي مجموعات محدبة تحتوي على جميع نقاطها الحدية . ويمكن وصفها بأنها تقاطعات أنصاف فضاءات مغلقة (مجموعات من النقاط في الفضاء تقع على مستوى فائق وعلى جانب واحد منه ).

مما سبق، يتضح أن هذه التقاطعات محدبة، وستكون أيضًا مجموعات مغلقة. ولإثبات العكس، أي أن كل مجموعة محدبة مغلقة يمكن تمثيلها كتقاطع من هذا النوع، نحتاج إلى نظرية المستوى الفائق الداعم ، والتي تنص على أنه لأي مجموعة محدبة مغلقة C ونقطة P خارجها، يوجد نصف فضاء مغلق H يحتوي على C ولا يحتوي على P. وتُعد نظرية المستوى الفائق الداعم حالة خاصة من نظرية هان-باناخ في التحليل الوظيفي .

وجه من مجموعة محدبة${\displaystyle C}$هي مجموعة جزئية محدبة${\displaystyle F}$ل${\displaystyle C}$بحيث كلما كانت النقطة${\displaystyle p}$في${\displaystyle F}$يقع تمامًا بين نقطتين${\displaystyle x}$و${\displaystyle y}$في${\displaystyle C}$، كلاهما${\displaystyle x}$و${\displaystyle y}$يجب أن يكون في${\displaystyle F}$[ ^{12 ] وبالمثل ،} لأي${\displaystyle x,y\in C}$وأي عدد حقيقي${\displaystyle 0<t<1}$بحيث${\displaystyle (1-t)x+ty}$هو في${\displaystyle F}$،${\displaystyle x}$و${\displaystyle y}$يجب أن يكون في${\displaystyle F}$وفقًا لهذا التعريف،${\displaystyle C}$نفسها والمجموعة الفارغة هما وجهان لـ${\displaystyle C}$وتسمى هذه أحيانًا بالوجوه التافهة لـ${\displaystyle C}$نقطة قصوى من${\displaystyle C}$هي نقطة تمثل وجهًا من أوجه${\displaystyle C}$.

يترك${\displaystyle C}$كن مجموعة محدبة في${\displaystyle \mathbb {R} ^{n}}$أي أنها متراصة (أو بصورة مكافئة، مغلقة ومحدودة ) . ثم${\displaystyle C}$^{[ 13 ]} بشكل عام، كل مجموعة محدبة مضغوطة في فضاء متجهي طوبولوجي محدب محليًا هي الغلاف المحدب المغلق لنقاطها القصوى ( نظرية كرين-ميلمان ).

على سبيل المثال:

• المثلث في المستوى (بما في ذلك المنطقة الداخلية) هو مجموعة محدبة متراصة. وجوهه غير التافهة هي رؤوسه الثلاثة وحوافه الثلاثة. (لذا فإن النقاط القصوى الوحيدة هي الرؤوس الثلاثة).
• الوجوه الوحيدة غير التافهة للقرص المغلق ذي الوحدة${\displaystyle \{(x,y)\in \mathbb {R} ^{2}:x^{2}+y^{2}\leq 1\}}$وهي نقاطها القصوى، أي النقاط الواقعة على دائرة الوحدة${\displaystyle S^{1}=\{(x,y)\in \mathbb {R} ^{2}:x^{2}+y^{2}=1\}}$.

ليكن C جسمًا محدبًا في المستوى (مجموعة محدبة لا يكون باطنها فارغًا). يمكننا رسم مستطيل r داخل C بحيث تكون نسخة متماثلة R من r محاطة بـ C. نسبة التماثل الموجبة لا تتجاوز 2، و: ^{[ 14 ]}$${\displaystyle {\tfrac {1}{2}}\cdot \operatorname {Area} (R)\leq \operatorname {Area} (C)\leq 2\cdot \operatorname {Area} (r)}$$

المجموعة ${\displaystyle {\mathcal {K}}^{2}}$ يمكن تحديد خصائص جميع الأجسام المحدبة المستوية بدلالة قطر الجسم المحدب D ، ونصف قطر دائرته الداخلية r (أكبر دائرة محصورة داخل الجسم المحدب)، ونصف قطر دائرته المحيطة R (أصغر دائرة تحوي الجسم المحدب). في الواقع، يمكن وصف هذه المجموعة بمجموعة المتباينات الواردة في المراجع ^{[ 15 ] و[ 16 ].}$${\displaystyle 2r\leq D\leq 2R}$$$${\displaystyle R\leq {\frac {\sqrt {3}}{3}}D}$$$${\displaystyle r+R\leq D}$$$${\displaystyle D^{2}{\sqrt {4R^{2}-D^{2}}}\leq 2R(2R+{\sqrt {4R^{2}-D^{2}}})}$$ ويمكن تصورها كصورة للدالة g التي ترسم جسمًا محدبًا إلى ^النقطة R² المعطاة بالعلاقة ( r / R , D /2R ) . تُعرف صورة هذه الدالة بمخطط بلاكه-سانتالو ( r , D , R ). ^{[ 16 ]}

أو بدلاً من ذلك، المجموعة ${\displaystyle {\mathcal {K}}^{2}}$ويمكن أيضًا تحديد خصائصها من خلال عرضها (أصغر مسافة بين أي مستويين متتاليين متوازيين مختلفين للدعم)، ومحيطها، ومساحتها. ^{[ 15 ] [ 16 ]}

ليكن X فضاءً متجهيًا طوبولوجيًا و${\displaystyle C\subseteq X}$يكون محدبًا.

• ${\displaystyle \operatorname {Cl} C}$و${\displaystyle \operatorname {Int} C}$كلاهما محدب (أي أن إغلاق وداخل المجموعات المحدبة محدب).
• لو${\displaystyle a\in \operatorname {Int} C}$و${\displaystyle b\in \operatorname {Cl} C}$ثم${\displaystyle [a,b[\,\subseteq \operatorname {Int} C}$(أين${\displaystyle [a,b[\,:=\left\{(1-r)a+rb:0\leq r<1\right\}}$).
• لو${\displaystyle \operatorname {Int} C\neq \emptyset }$ثم:
  • ${\displaystyle \operatorname {cl} \left(\operatorname {Int} C\right)=\operatorname {Cl} C}$، و
  • ${\displaystyle \operatorname {Int} C=\operatorname {Int} \left(\operatorname {Cl} C\right)=C^{i}}$، أين${\displaystyle C^{i}}$هو الجزء الجبري الداخلي لـ C.

تحتوي كل مجموعة جزئية A من الفضاء المتجهي على أصغر مجموعة محدبة (تسمى الغلاف المحدب لـ A )، وهي تقاطع جميع المجموعات المحدبة التي تحتوي على A. يتمتع عامل الغلاف المحدب Conv() بالخصائص المميزة لعامل الإغلاق .

• موسع : S  ⊆  Conv( S ) ،
• غير متناقصة : S  ⊆ T  تعني أن Conv( S )  ⊆  Conv( T ) ، و
• idempotent : Conv(Conv( S )) = Conv( S ) .

تُعد عملية الغلاف المحدب ضرورية لتشكيل شبكة من المجموعات المحدبة ، حيث تكون عملية " الضم " هي الغلاف المحدب لاتحاد مجموعتين محدبتين. $${\displaystyle \operatorname {Conv} (S)\vee \operatorname {Conv} (T)=\operatorname {Conv} (S\cup T)=\operatorname {Conv} {\bigl (}\operatorname {Conv} (S)\cup \operatorname {Conv} (T){\bigr )}.}$$ إن تقاطع أي مجموعة من المجموعات المحدبة هو نفسه محدب، لذا فإن المجموعات الفرعية المحدبة لفضاء متجه (حقيقي أو مركب) تشكل شبكة كاملة .

في فضاء متجهي حقيقي، يُعرَّف مجموع مينكوفسكي لمجموعتين (غير فارغتين)، _{S1 و} S2 ، بأنه _{المجموعة} S1 + S2 التي تتكون   من جمع المتجهات عنصرًا بعنصر من مجموعات المجموع _.$${\displaystyle S_{1}+S_{2}=\{x_{1}+x_{2}:x_{1}\in S_{1},x_{2}\in S_{2}\}.}$$ وبشكل أعم، فإن مجموع مينكوفسكي لعائلة منتهية من المجموعات (غير الفارغة) S _n هو المجموعة المتكونة من خلال الجمع العنصري للمتجهات $${\displaystyle \sum _{n}S_{n}=\left\{\sum _{n}x_{n}:x_{n}\in S_{n}\right\}.}$$

بالنسبة لعملية جمع مينكوفسكي  ، فإن المجموعة الصفرية {0} التي تحتوي فقط على المتجه الصفري 0 لها أهمية خاصة : لكل مجموعة جزئية غير فارغة S من فضاء متجهي     $${\displaystyle S+\{0\}=S;}$$ في المصطلحات الجبرية، {0} هو العنصر المحايد لعملية جمع مينكوفسكي (على مجموعة المجموعات غير الفارغة). ^{[ 17 ]}

تتصرف عملية جمع مينكوفسكي بشكل جيد فيما يتعلق بعملية أخذ الأغلفة المحدبة، كما هو موضح في الاقتراح التالي:

إذا كانت S1 _و S2 مجموعتين جزئيتين من فضاء متجهي حقيقي، فإن _الغلاف المحدب لمجموع مينكوفسكي الخاص بهما هو مجموع مينكوفسكي لأغلفةهما المحدبة .$${\displaystyle \operatorname {Conv} (S_{1}+S_{2})=\operatorname {Conv} (S_{1})+\operatorname {Conv} (S_{2}).}$$

تنطبق هذه النتيجة بشكل عام على كل مجموعة منتهية من المجموعات غير الفارغة: $${\displaystyle {\text{Conv}}\left(\sum _{n}S_{n}\right)=\sum _{n}{\text{Conv}}\left(S_{n}\right).}$$

في المصطلحات الرياضية، تُعتبر عمليات جمع مينكوفسكي وتكوين الأغلفة المحدبة عمليات تبادلية . ^{[ 18 ] [ 19 ]}

مجموع مينكوفسكي لمجموعتين محدبتين متراصتين هو مجموعة متراصة. مجموع مجموعة محدبة متراصة ومجموعة محدبة مغلقة هو مجموعة مغلقة. ^{[ 20 ]}

تُقدّم النظرية الشهيرة التالية، التي أثبتها ديودونيه عام 1966، شرطًا كافيًا لكي يكون الفرق بين مجموعتين جزئيتين محدبتين مغلقتين مجموعةً جزئية مغلقة. ^{[ 21 ]} وهي تستخدم مفهوم مخروط التراجع لمجموعة جزئية محدبة غير فارغة S ، والذي يُعرّف على النحو التالي: $${\displaystyle \operatorname {rec} S=\left\{x\in X\,:\,x+S\subseteq S\right\},}$$ حيث تكون هذه المجموعة عبارة عن مخروط محدب يحتوي${\displaystyle 0\in X}$ومُرضٍ${\displaystyle S+\operatorname {rec} S=S}$لاحظ أنه إذا كانت S مغلقة ومحدبة، فإن${\displaystyle \operatorname {rec} S}$مغلق للجميع${\displaystyle s_{0}\in S}$، $${\displaystyle \operatorname {rec} S=\bigcap _{t>0}t(S-s_{0}).}$$

نظرية (ديودونيه). ليكن A و B مجموعتين جزئيتين غير فارغتين ومغلقتين ومحدبتين من فضاء متجهي طوبولوجي محدب محليًا بحيث${\displaystyle \operatorname {rec} A\cap \operatorname {rec} B}$هي فضاء جزئي خطي. إذا كانت A أو B متراصة محليًا، فإن A  − B تكون مغلقة. 

ليكن C مجموعة في فضاء متجهي حقيقي أو مركب. تُسمى C مجموعة محدبة نجمية (على شكل نجمة) إذا وُجدت نقطة x₀ في C بحيث تكون القطعة المستقيمة من _x₀ إلى أي نقطة y في C محصورة داخل C. لذا _{، فإن المجموعة المحدبة غير الفارغة تكون دائمًا محدبة نجمية} ، ولكن المجموعة المحدبة نجمية ليست دائمًا محدبة.

ومن الأمثلة على التحدب المعمم التحدب المتعامد . ^{[ 22 ]}

تُسمى المجموعة S في الفضاء الإقليدي محدبة متعامدة، أو محدبة عمودياً ، إذا كان أي قطعة مستقيمة موازية لأي من محاور الإحداثيات، والتي تربط نقطتين من S، تقع كلياً داخل S. من السهل إثبات أن تقاطع أي مجموعة من المجموعات المحدبة عمودياً هو مجموعة محدبة عمودياً. كما تنطبق بعض الخصائص الأخرى للمجموعات المحدبة.

يمتد تعريف المجموعة المحدبة والغلاف المحدب بشكل طبيعي إلى الأشكال الهندسية غير الإقليدية من خلال تعريف المجموعة المحدبة جيوديسيًا بأنها تلك التي تحتوي على الخطوط الجيوديسية التي تربط أي نقطتين في المجموعة.

يمكن تعميم التحدب على مجموعة مرتبة كليًا X مزودة بطوبولوجيا الترتيب . ^{[ 23 ]}

ليكن Y ⊆ X. يُقال عن الفضاء الجزئي Y أنه مجموعة محدبة إذا كان لكل زوج من النقاط a و b في Y بحيث a ≤ b ، فإن الفترة [ a , b ] = { x ∈ X | a ≤ x ≤ b } تقع ضمن Y. أي أن Y محدبة إذا وفقط إذا كان لكل a و b في Y ، فإن a ≤ b يستلزم [ a , b ] ⊆ Y.

المجموعة المحدبة ليست متصلة بشكل عام: يتم تقديم مثال مضاد بواسطة الفضاء الجزئي {1,2,3} في Z ، وهو محدب وغير متصل.

يمكن تعميم مفهوم التحدب على أشياء أخرى، إذا تم اختيار خصائص معينة للتحدب كمسلمات .

بالنظر إلى مجموعة X ، فإن التحدب على X هو مجموعة 𝒞 من المجموعات الجزئية من X التي تحقق البديهيات التالية: ^{[ 10 ] [ 11 ] [ 24 ]}

1. المجموعة الفارغة و X موجودتان في 𝒞 .
2. تقاطع أي مجموعة من 𝒞 يقع في 𝒞 .
3. اتحاد سلسلة ( بالنسبة لعلاقة الاحتواء ) من عناصر 𝒞 موجود في 𝒞 .

تُسمى عناصر المجموعة 𝒞 بالمجموعات المحدبة، ويُسمى الزوج ( X , 𝒞 ) بفضاء التحدب . بالنسبة للتحدب العادي، تتحقق البديهيتان الأوليان، أما الثالثة فهي بديهية.

للحصول على تعريف بديل للتحدب المجرد، وهو أكثر ملاءمة للهندسة المنفصلة ، ​​انظر إلى الهندسات المحدبة المرتبطة بالأجسام المضادة .

يمكن تعميم التحدب كبنية جبرية مجردة: يكون الفضاء محدبًا إذا كان من الممكن أخذ تركيبات محدبة من النقاط.