ما معنى مجموعة محدبة؟

مثال 17.12 (المناطق الواقعة فوق المنحنيات مجموعات محدبة)

المنطقة $C = \{(x, y) : y \geq x^2\}$ الواقعة فوق القطع المكافئ محدبة: فمن أجل $(x_1, y_1), (x_2, y_2) \in C$ ومن أجل $t \in \intcc01$، تعطي متراجحة تحدب دالة المربع

ومنه يبقى مركز الثقل فوق القطع المكافئ. والحساب عام: فالمجموعة $\{y \geq f(x)\}$ محدبة إذا وفقط إذا كانت $f$ دالة محدبة — فالمجموعات المحدبة والدوال المحدبة (الفصل 8) وجهان لمفهوم واحد، والمناطق الواقعة فوق المنحنيات هي المعجم بينهما. وهذا هو السبب الهندسي في وجود مستقيمات مساندة للدوال المحدبة، وهي الحقيقة التي ستبرهن على متراجحة جنسن في الفصل 22.

مثال 17.13 (مولّدات زائدة لغلاف محدب)

لنأخذ $S = \{(0,0), (2,0), (2,2), (0,2), (1,1)\}$. النقطة الخامسة هي مركز الثقل

ومنه فهي تقع أصلا في غلاف النقط الأربع الأخرى: فالمجموعة $\operatorname{conv}(S)$ هي المربع ذو الرؤوس الأربعة. وبوجه عام، يمكن حذف أي نقطة من $S$ تكون مركز ثقل بأوزان موجبة للنقط الأخرى من $S$ دون تغيير الغلاف؛ والنقط التي لا يمكن حذفها أبدا (وهي هنا الرؤوس الأربعة) هي النقط المتطرفة للغلاف. وتحديدها حساب مراكز ثقل خالص: فالنقطة $(2,0)$ مثلا لا يمكن كتابتها $\operatorname{bar}$ بالنقط الباقية بأوزان موجبة، لأن الإحداثية الأولى ستفرض تركيز كل الوزن على النقط ذات $x = 2$، ثم تسقط الإحداثية الثانية. فأسئلة التحدب تختزل، مرة بعد مرة، إلى حل جمل موزونة صغيرة.