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

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
📷 يحتوي على 43 صور
الموسوعة الحرة

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

التعريف الرسمي

لنفترض دالة قابلة للتفاضلو:X⊆Rن→R{\displaystyle f:X\subseteq \mathbb {R} ^{n}\rightarrow \mathbb {R} }، معرفة على مجموعة مفتوحة محدبة (غير فارغة)X{\displaystyle X}للفضاء الإقليدي ذي الأبعاد المحدودةRن{\displaystyle \mathbb {R} ^{n}}يُقال إن هذه الدالة محدبة زائفة إذا تحققت الخاصية التالية: [ 1 ]

للجميعx،y∈X:∇و(x)⋅(y-x)≥0⇒و(y)≥و(x).{\displaystyle x,y\in X:\quad \nabla f(x)\cdot (yx)\geq 0\Rightarrow f(y)\geq f(x).}

بمعنى آخر:

للجميعx،y∈X:و(y)<و(x)⇒∇و(x)⋅(y-x)<0.{\displaystyle x,y\in X:\quad f(y)<f(x)\Rightarrow \nabla f(x)\cdot (yx)<0.}

هنا∇و{\displaystyle \nabla f}هو تدرج​و{\displaystyle f}، كما هو محدد بـ:∇و=(∂و∂x1،...،∂و∂xن).{\displaystyle \nabla f=\left({\frac {\partial f}{\partial x_{1}}},\dots ,{\frac {\partial f}{\partial x_{n}}}\right).}

لاحظ أنه يمكن أيضًا صياغة التعريف بدلالة المشتق الاتجاهي لـو{\displaystyle f}، في الاتجاه المحدد بواسطة المتجهv=y-x{\displaystyle v=yx}وذلك لأن، كماو{\displaystyle f}إذا كانت الدالة قابلة للتفاضل، فإن المشتقة الاتجاهية تُعطى بالصيغة التالية:

∂و∂v(x)=∇و(x)⋅v=∇و(x)⋅(y-x).{\displaystyle {\frac {\partial f}{\partial v}}(x)=\nabla f(x)\cdot v=\nabla f(x)\cdot (yx).}

ملكيات

العلاقة بأنواع أخرى من "التحدب"

كل دالة محدبة هي دالة محدبة زائفة، لكن العكس ليس صحيحًا. على سبيل المثال، الدالةو(x)=x+x3{\displaystyle f(x)=x+x^{3}}هي دالة شبه محدبة وليست محدبة. وبالمثل، فإن أي دالة شبه محدبة هي دالة شبه محدبة ؛ ولكن العكس غير صحيح، لأن الدالةو(x)=x3{\displaystyle f(x)=x^{3}}هو شبه محدب ولكنه ليس محدبًا زائفًا. ويمكن تلخيص ذلك تخطيطيًا على النحو التالي:

محدب⇒{\displaystyle \Rightarrow }شبه محدب⇒{\displaystyle \Rightarrow }شبه محدب
الدالتان x^3 (شبه محدبة وليست محدبة زائفة) و x^3 + x (محدبة زائفة وبالتالي شبه محدبة). لا توجد أي منهما محدبة.
الدالتان x^3 (شبه محدبة وليست محدبة زائفة) و x^3 + x (محدبة زائفة وبالتالي شبه محدبة). لا توجد أي منهما محدبة.

لرؤية ذلكو(x)=x3{\displaystyle f(x)=x^{3}}ليست شبه محدبة، انظر إلى مشتقتها عندx=0{\displaystyle x=0}:و′(0)=0{\displaystyle f^{\prime }(0)=0}ثم، إذاو(x)=x3{\displaystyle f(x)=x^{3}}لو كان محدبًا زائفًا، لكان ينبغي أن يكون لدينا:

و′(0)(y-0)=0≥0⇒و(y)≥و(0)،∀y∈R.{\displaystyle f^{\prime }(0)(y-0)=0\geq 0\Rightarrow f(y)\geq f(0),\quad \forall \,y\in \mathbb {R} .}

وينطبق ذلك بشكل خاص علىy=-1{\displaystyle y=-1}لكن الأمر ليس كذلك، كما يلي:و(-1)=(-1)3=-1<و(0)=0{\displaystyle f(-1)=(-1)^{3}=-1<f(0)=0}.

شرط كافٍ للأمثلية

لأي دالة قابلة للتفاضل، لدينا شرط فيرما الضروري للأمثلية، والذي ينص على ما يلي: إذاو{\displaystyle f}يوجد حد أدنى محلي عندx*{\displaystyle x^{*}}في مجال مفتوح ، إذنx*{\displaystyle x^{*}}يجب أن تكون نقطة ثابتة منو{\displaystyle f}(إنه:∇و(x*)=0{\displaystyle \nabla f(x^{*})=0}).

يُعدّ التحدب الزائف ذا أهمية بالغة في مجال التحسين ، لأن العكس صحيح أيضًا لأي دالة محدبة زائفة. أي: [ 2 ] إذاx*{\displaystyle x^{*}}هي نقطة ثابتة لدالة شبه محدبةو{\displaystyle f}، ثمو{\displaystyle f}يبلغ الحد الأدنى العالمي عندx*{\displaystyle x^{*}}لاحظ أيضًا أن النتيجة تضمن الحد الأدنى العالمي (وليس المحلي فقط).

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

و(x)=هـxx2+1+1هـx.{\displaystyle f(x)={\frac {e^{x}}{x^{2}+1}}+{\frac {1}{e^{x}}}.}

هذه الدالة ليست محدبة زائفة، ولكنها شبه محدبة. كذلك النقطةx=0{\displaystyle x=0}تُعد نقطة حاسمة منو{\displaystyle f}، مثلو′(0)=0{\displaystyle f^{\prime }(0)=0}. لكن،و{\displaystyle f}لا يوجد حد أدنى عالمي فيx=0{\displaystyle x=0}(ولا حتى الحد الأدنى المحلي).

مثال على دالة شبه محدبة ذات نقطة حرجة ليست نقطة دنيا.
مثال على دالة شبه محدبة ليست محدبة زائفة. للدالة نقطة حرجة عندx=0{\displaystyle x=0}لكن هذا ليس الحد الأدنى.

وأخيرًا، تجدر الإشارة إلى أن الدالة شبه المحدبة قد لا تحتوي على أي نقطة حرجة. خذ على سبيل المثال الدالة شبه المحدبة التالية:و(x)=x3+x{\displaystyle f(x)=x^{3}+x}، والتي تكون مشتقتها موجبة دائمًا:و′(x)=3x2+1>0،∀x∈R{\displaystyle f^{\prime }(x)=3x^{2}+1>0,\,\forall \,x\in \mathbb {R} }.

أمثلة

مثال على دالة شبه محدبة، ولكنها ليست محدبة، هو:و(x)=x2x2+ك،ك>0.{\displaystyle f(x)={\frac {x^{2}}{x^{2}+k}},\,k>0.}يوضح الشكل هذه الوظيفة في الحالة التيك=0.2{\displaystyle k=0.2}يمكن تعميم هذا المثال على متغيرين كما يلي:

و(x)=x2+y2x2+y2+ك،ك>0.{\displaystyle f(x)={\frac {x^{2}+y^{2}}{x^{2}+y^{2}+k}},\,k>0.}
دالة شبه محدبة ليست محدبة: x^2 / (x^2+0.2)
دالة شبه محدبة ليست محدبة.

يمكن تعديل المثال السابق للحصول على دالة ليست محدبة، ولا شبه محدبة، ولكنها شبه محدبة:

و(x)=|x|ص|x|ص+ك،ك>0،ص∈(0،1).{\displaystyle f(x)={\frac {|x|^{p}}{|x|^{p}+k}},\,k>0,\,p\in (0,1).}

يوضح الشكل هذه الوظيفة في الحالة التيك=0.5،ص=0.6{\displaystyle k=0.5,p=0.6}كما هو واضح، فإن هذه الدالة ليست محدبة بسبب التقعر، وليست شبه محدبة لأنها غير قابلة للتفاضل عند نقطة معينة.x=0{\displaystyle x=0}.

دالة شبه محدبة ليست محدبة ولا محدبة زائفة: {{!}}x{{!}}^0.6 / ( {{!}}x{{!}}^0.6 + 0.5 )
دالة شبه محدبة ليست محدبة، ولا محدبة زائفة.

التعميم على الدوال غير القابلة للتفاضل

يمكن تعميم مفهوم التحدب الزائف على الدوال غير القابلة للتفاضل كما يلي. [ 3 ] بالنظر إلى أي دالةو:X→R{\displaystyle f:X\rightarrow \mathbb {R} }، يمكننا تعريف مشتقة ديني العليا لـو{\displaystyle f}بواسطة:

و+(x،u)=ليم سوبح→0+و(x+حu)-و(x)ح؛{\displaystyle f^{+}(x,u)=\limsup _{h\to 0^{+}}{\frac {f(x+hu)-f(x)}{h}};}

حيث u أي متجه وحدة . يُقال إن الدالة شبه محدبة إذا كانت متزايدة في أي اتجاه تكون فيه مشتقة ديني العليا موجبة. وبشكل أدق، يتم تحديد ذلك بدلالة التفاضل الجزئي.∂و{\displaystyle \partial f}على النحو التالي:

للجميعx،y∈X{\displaystyle x,y\in X}: لوx*∈∂و(x){\displaystyle x^{*}\in \partial f(x)}بحيث⟨x*،y-x⟩≥0{\displaystyle \langle x^{*},y-x\rangle \geq 0}، ثمو(x)≤و(z){\displaystyle f(x)\leq f(z)}للجميعz∈[x،y]{\displaystyle z\in [x,y]}؛

أين[x،y]{\displaystyle [x,y]}يشير إلى القطعة المستقيمة المجاورة لـ x و y .

أالدالة شبه المقعرة هي دالة يكون معكوسها شبه محدب.الدالة شبه الخطية هي دالة شبه محدبة وشبه مقعرة في آن واحد. [ 4 ] على سبيل المثال،تحتويالبرامج الخطية الكسريةدوال هدفوقيودخطية متباينة. تسمح هذه الخصائص بحل المسائل الخطية الكسرية باستخدام صيغة معدلة منخوارزمية سيمبلكس(لجورج ب. دانتزيج). [ 5 ] [ 6 ] [ 7 ]

بفرض دالة ذات قيم متجهةη{\displaystyle \eta }، وهناك مفهوم أكثر عمومية لـη{\displaystyle \eta }- شبه التحدب [ 8 ] [ 9 ] وη{\displaystyle \eta }- شبه الخطية؛ حيث يتعلق كل من التحدب الزائف الكلاسيكي وشبه الخطية بالحالة التيη(x،y)=y-x{\displaystyle \eta (x,y)=y-x}.

انظر أيضاً

ملحوظات

  1. ↑ مانغاساريان 1965
  2. ↑ مانغاساريان 1965
  3. ↑ فلوداس وباردالوس 2001
  4. ↑ رابساك 1991
  5. ↑ الفصل الخامس: كرافن، ب. د. (1988). البرمجة الكسرية . سلسلة سيجما في الرياضيات التطبيقية. المجلد  4. برلين: دار نشر هيلدرمان. ص  145. ISBN 3-88538-404-3MR 0949209 .​ 
  6. ↑ كروك، سيرج؛ وولكوفيتش، هنري (1999). "البرمجة شبه الخطية". مجلة SIAM . 41 (4): 795-805 . Bibcode : 1999SIAMR..41..795K . doi : 10.1137/S0036144598335259 . JSTOR 2653207. MR 1723002 .  
  7. ↑ ماثيس، فرانك هـ.؛ ماثيس، لينورا جين (1995). " خوارزمية برمجة غير خطية لإدارة المستشفيات". مجلة SIAM Review . 37 (2): 230-234 . doi : 10.1137/1037046 . JSTOR 2132826. MR 1343214. S2CID 120626738 .   
  8. ↑ أنصاري، قمر الحسن؛ لاليثا، سي إس؛ ميهتا، مونيكا (2013). التحدب المعمم، والمتباينات التباينية غير الملساء، والتحسين غير الأملس . مطبعة سي آر سي. ص 107. ISBN  9781439868218تم الاطلاع عليه بتاريخ 15 يوليو 2019 .
  9. ↑ ميشرا، شاشي ك.؛ جيورجي، جورجيو (2008). التحدب والتحسين . سبرينغر ساينس آند بيزنس ميديا. ص 39. ISBN  9783540785613تم الاطلاع عليه بتاريخ 15 يوليو 2019 .

مراجع

  • فلوداس، كريستودولوس أ .؛ باردالوس، بانوس م. (2001)، "الخرائط الرتيبة المعممة متعددة القيم"، موسوعة التحسين ، سبرينغر، ص  227، ISBN 978-0-7923-6932-5.
  • مانغاساريان، أو إل (يناير 1965). "الدوال شبه المحدبة". مجلة جمعية الرياضيات الصناعية والتطبيقية، السلسلة أ: التحكم . 3 (2): 281-290 . doi : 10.1137/0303020 . ISSN 0363-0129 . .
  • رابساك، ت. (15 فبراير 1991). "حول الدوال شبه الخطية". المجلة الأوروبية لبحوث العمليات . 50 (3): 353-360 . doi : 10.1016/0377-2217(91)90267-Y . ISSN 0377-2217 .