دالة شبه محدبة

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 44 صور
الموسوعة الحرة
دالة شبه محدبة ليست محدبة
الدالة التي ليست شبه محدبة: مجموعة النقاط في مجال الدالة التي تكون قيم الدالة عندها أقل من الخط الأحمر المتقطع هي اتحاد الفترتين الحمراوين، وهي ليست مجموعة محدبة.
دالة كثافة الاحتمال للتوزيع الطبيعي شبه مقعرة ولكنها ليست مقعرة.
الكثافة المشتركة الطبيعية ثنائية المتغيرات شبه مقعرة.
مخطط كفافي لدالة شبه محدبة (أعلى) حيث تكون جميع مجموعات المستوى محدبة، ودالة غير شبه محدبة (أسفل) حيث تكون بعض مجموعات المستوى غير محدبة وقد تكون منفصلة.

في الرياضيات ، الدالة شبه المحدبة هي دالة حقيقية القيمة معرفة على مجموعة جزئية محدبة من فضاء متجهي حقيقي ، بحيث يكون لأي عدد حقيقي y ، مجموعة النقاط التي تكون فيها قيمة الدالة على الأكثر y مجموعة محدبة . بعبارة أخرى، الصورة العكسية لأي مجموعة من الشكل(-∞،y){\displaystyle (-\infty ,y)}هي مجموعة محدبة . التعريف المكافئ هو: على طول أي فترة في مجال الدالة، تصل الدالة إلى أعلى قيمة لها عند إحدى نقاط النهاية.

شبه التحدب خاصية أكثر عمومية من التحدب: جميع الدوال المحدبة هي أيضًا شبه محدبة، ولكن ليس كل الدوال شبه المحدبة محدبة.

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

الدالة شبه المقعرة هي معكوس الدالة شبه المحدبة. في الدالة شبه المقعرة، لأي عدد حقيقي y ، تكون مجموعة النقاط التي تكون عندها قيمة الدالة أكبر من أو تساوي y محدبة. وبالمثل، على امتداد أي فترة في مجال الدالة، تصل الدالة إلى أدنى قيمة لها عند إحدى نقطتي النهاية. في بُعد واحد، تحقق من أن أي خط أفقي يتقاطع مع المنطقة أسفل منحنى الدالة، يكون التقاطع فترة.

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

التعريف والخصائص

وظيفةو:S→R{\displaystyle f:S\to \mathbb {R} }معرفة على مجموعة فرعية محدبةS{\displaystyle S}يكون فضاء متجهي حقيقي شبه محدب إذا كان لكلx،y∈S{\displaystyle x,y\in S}وλ∈[0،1]{\displaystyle \lambda \in [0,1]}لدينا

و(λx+(1-λ)y)≤الأعلى{و(x)،و(y)}.{\displaystyle f(\lambda x+(1-\lambda )y)\leq \max {\big \{}f(x),f(y){\big \}}.}

بعبارة أخرى، الهدفو{\displaystyle f}تكون شبه محدبة إذا وفقط إذا كانت القيمة القصوى لـو{\displaystyle f}لا تتجاوز قيمة الخط المستقيم الواصل بين أي نقطتين طرفيتين القيمة عند النقطة الطرفية الأعلى. لاحظ أن النقاطx{\displaystyle x}وy{\displaystyle y}قد تكون نقاطًا في فضاء ذي أبعاد n . إذا كانت المتباينة صارمة، أي

و(λx+(1-λ)y)<الأعلى{و(x)،و(y)}{\displaystyle f(\lambda x+(1-\lambda )y)<\max {\big \{}f(x),f(y){\big \}}}

للجميعx≠y{\displaystyle x\neq y}وλ∈(0،1){\displaystyle \lambda \in (0,1)}، ثمو{\displaystyle f}هي شبه محدبة تمامًا . أي أن شبه التحدب التام يتطلب أن تعطي النقطة الواقعة مباشرة بين نقطتين أخريين قيمة أقل للدالة من قيمة إحدى النقاط الأخرى.

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

طريقة بديلة (انظر المقدمة) لتعريف دالة شبه محدبةو(x){\displaystyle f(x)}يتطلب ذلك أن كل مجموعة من المستويات الفرعية Sα(و)={x|و(x)≤α}{\displaystyle S_{\alpha }(f)=\{x\mid f(x)\leq \alpha \}} هي مجموعة محدبة. ويترتب على ذلك أنه لكل دالة شبه محدبة تمامًا، يوجد تحويل إحداثيات متزايد رتيب تمامًام:R→R{\displaystyle m:\mathbb {R} \to \mathbb {R} } بحيثم(و(x)){\displaystyle m(f(x))}محدب تمامًا.

الدالة شبه المقعرة هي دالة يكون معكوسها شبه محدب، والدالة شبه المقعرة تمامًا هي دالة يكون معكوسها شبه محدب تمامًا. بمعنى آخر، دالةو{\displaystyle f}يكون شبه مقعر إذا وفقط إذا

و(λx+(1-λ)y)≥مين{و(x)،و(y)}.{\displaystyle f(\lambda x+(1-\lambda )y)\geq \min {\big \{}f(x),f(y){\big \}}.}

الدالة شبه المحدبة (بشكل صارم) لها مجموعات محيطية سفلية محدبة (بشكل صارم) ، بينما الدالة شبه المقعرة (بشكل صارم) لها مجموعات محيطية علوية محدبة (بشكل صارم) . تُعدّ التوزيعات الاحتمالية أحادية النمط، مثل التوزيع الغاوسي، أمثلة شائعة على الدوال شبه المقعرة غير المقعرة.

الدالة التي تكون شبه محدبة وشبه مقعرة في آن واحد هي دالة شبه خطية ، وتحقق الشروط التالية:

مين{و(x)،و(y)}≤و(λx+(1-λ)y)≤الأعلى{و(x)،و(y)}{\displaystyle \min {\big \{}f(x),f(y){\big \}}\leq f(\lambda x+(1-\lambda )y)\leq \max {\big \{}f(x),f(y){\big \}}}

بالنسبة لدالة شبه خطية معرفة على مستوى، تكون مجموعات المستوى دائمًا خطوطًا. وبشكل أعم، فإن مجموعات المستوى لدالة شبه خطية علىRن{\displaystyle \mathbb {R} ^{n}}نكونن-1{\displaystyle n-1}المستويات ذات الأبعاد n.

التطبيقات

تُستخدم الدوال شبه المحدبة في التحليل الرياضي ، وفي التحسين الرياضي ، وفي نظرية الألعاب والاقتصاد .

التحسين الرياضي

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

الاقتصاد والمعادلات التفاضلية الجزئية: نظريات المينيماكس

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

الحفاظ على شبه التحدب

العمليات التي تحافظ على شبه التحدب

  • الحد الأقصى للدوال شبه المحدبة (أيو=الأعلى{و1،...،ون}{\displaystyle f=\max \left\lbrace f_{1},\ldots ,f_{n}\right\rbrace }الدالة شبه محدبة. وبالمثل، فإن القيمة العظمى للدوال شبه المحدبة تمامًا هي دالة شبه محدبة تمامًا. [ 4 ] وبالمثل، فإن القيمة الصغرى للدوال شبه المقعرة هي دالة شبه مقعرة، والقيمة الصغرى للدوال شبه المقعرة تمامًا هي دالة شبه مقعرة تمامًا.
  • التركيب ذو الدالة غير المتناقصة  :ز:Rن→R{\displaystyle g:\mathbb {R} ^{n}\rightarrow \mathbb {R} }شبه محدب،ح:R→R{\displaystyle h:\mathbb {R} \rightarrow \mathbb {R} }غير متناقصة، إذنو=ح∘ز{\displaystyle f=h\circ g}هو شبه محدب. وبالمثل، إذاز:Rن→R{\displaystyle g:\mathbb {R} ^{n}\rightarrow \mathbb {R} }شبه مقعر،ح:R→R{\displaystyle h:\mathbb {R} \rightarrow \mathbb {R} }غير متناقصة، إذنو=ح∘ز{\displaystyle f=h\circ g}شبه مقعر.
  • التقليل (أيو(x،y){\displaystyle f(x,y)}شبه محدب،ج{\displaystyle C}مجموعة محدبة، ثمح(x)=معلوماتy∈جو(x،y){\displaystyle h(x)=\inf _{y\in C}f(x,y)}(شبه محدب)

العمليات التي لا تحافظ على شبه التحدب

  • لا يشترط أن يكون مجموع الدوال شبه المحدبة المعرفة على نفس المجال شبه محدب: بعبارة أخرى، إذاو(x)،ز(x){\displaystyle f(x),g(x)}إذا كانت شبه محدبة،(و+ز)(x)=و(x)+ز(x){\displaystyle (f+g)(x)=f(x)+g(x)}ليس بالضرورة أن يكون شبه محدب. على سبيل المثال،±لافتة⁡(x±1){\displaystyle \pm \operatorname {sign} (x\pm 1)}هي دوال شبه محدبة (في الواقع، شبه خطية) مجموعها ليس شبه محدب.
  • مجموع الدوال شبه المحدبة المعرفة على مجالات مختلفة (أي إذاو(x)،ز(y){\displaystyle f(x),g(y)}هي شبه محدبة،ح(x،y)=و(x)+ز(y){\displaystyle h(x,y)=f(x)+g(y)}لا يشترط أن تكون الدوال شبه محدبة. تُسمى هذه الدوال "دوالًا قابلة للتحليل الجمعي" في علم الاقتصاد، و"دوالًا قابلة للفصل" في التحسين الرياضي . على سبيل المثال،و(x)=-x2{\displaystyle f(x)=-x^{2}}محدد للإيجابيةx>0{\displaystyle x>0}هو شبه محدب، لكنح(x،y)=و(x)+و(y){\displaystyle h(x,y)=f(x)+f(y)}ليس شبه محدب في الربع الموجب.

أمثلة

  • كل دالة محدبة هي دالة شبه محدبة.
  • يمكن أن تكون الدالة المقعرة شبه محدبة. على سبيل المثال،x↦سجل⁡(x){\displaystyle x\mapsto \log(x)}هو مقعر وشبه محدب في نفس الوقت.
  • أي دالة رتيبة تكون شبه محدبة وشبه مقعرة في آن واحد. وبشكل أعم، فإن الدالة التي تتناقص حتى نقطة معينة ثم تتزايد من تلك النقطة فصاعدًا تكون شبه محدبة (قارن بخاصية أحادية النمط ).
  • وظيفة الأرضيةx↦⌊x⌋{\displaystyle x\mapsto \lfloor x\rfloor }هذا مثال على دالة شبه محدبة ليست محدبة ولا متصلة.

انظر أيضاً

مراجع

  1. ↑ دي  غولييلمو (1977 ، ص 287-288) : دي غولييلمو، ف. (1977). "الازدواجية غير المحدبة في التحسين متعدد الأهداف". رياضيات بحوث العمليات . 2 (3): 285-291 . doi : 10.1287/moor.2.3.285 . JSTOR 3689518. MR 0484418 .    
  2. ↑ دي غولييلمو، ف. (1981). "تقديرات فجوة الازدواجية لمسائل التحسين المنفصلة وشبه المحدبة ". في: شايبل، سيغفريد؛ زيمبا، ويليام ت. (محرران). التقعر المعمم في التحسين والاقتصاد: وقائع معهد الدراسات المتقدمة التابع لحلف الناتو، المنعقد في جامعة كولومبيا البريطانية، فانكوفر، كولومبيا البريطانية، 4-15 أغسطس 1980. نيويورك : أكاديميك برس، إنك. [هاركورت بريس جوفانوفيتش، ناشرون]. ص 281-298 . ISBN               0-12-621120-5MR 0652702 .​ 
  3. ↑ كيوييل، كريستوف سي. (2001). "تقارب وكفاءة طرق التدرج الفرعي للتصغير شبه المحدب". البرمجة الرياضية، السلسلة أ . 90 (1). برلين، هايدلبرغ: سبرينغر: 1-25 . doi : 10.1007 /PL00011414 . ISSN 0025-5610 . MR 1819784. S2CID 10043417 .   يقر كيوييل بأن يوري نيستيروف هو أول من أثبت إمكانية حل مشاكل التصغير شبه المحدبة بكفاءة.
  4. ↑ يوهانسون، إدوارد؛ بيترسون، ديفيد (2016). تحسين المعلمات لحلول التوازن لأنظمة فعل الكتلة (رسالة ماجستير). ص 13-14 . تم الاطلاع عليه بتاريخ 26 أكتوبر 2016 . 
  • Avriel, M., Diewert, WE, Schaible, S. and Zang, I., Generalized Concavity , Plenum Press, 1988.
  • كروزيكس، جيه-بي. (2008). "شبه التقعر". في: دورلاف، ستيفن  ن.؛ بلوم، لورانس  إي (محرران). قاموس بالغراف الجديد  للاقتصاد (الطبعة الثانية  ). بالغراف ماكميلان. ص 815-816 . doi : 10.1057/9780230226203.1375 . ISBN  978-0-333-78676-5.
  • سينغر، إيفان. التحليل المحدب المجرد . سلسلة الدراسات والنصوص المتقدمة للجمعية الرياضية الكندية. منشور وايلي-إنترساينس. جون وايلي وأولاده، نيويورك، 1997. 491 صفحة + 22 صفحة تمهيدية. ISBN  0-471-16015-6