دالة محدبة

في الرياضيات ، تُسمى الدالة الحقيقية محدبة إذا كانت القطعة المستقيمة الواصلة بين أي نقطتين مختلفتين على منحنى الدالة تقع فوق أو على منحنى الدالة بين هاتين النقطتين. وبعبارة أخرى، تكون الدالة محدبة إذا كان منحنى الدالة (مجموعة النقاط الواقعة على أو فوق منحنى الدالة) مجموعة محدبة . وبعبارة أبسط، يكون منحنى الدالة المحدبة على شكل كوب.${\displaystyle \cup }$(أو خط مستقيم مثل الدالة الخطية)، بينما يكون شكل الرسم البياني للدالة المقعرة مثل غطاء${\displaystyle \cap }$.

تكون الدالة القابلة للتفاضل مرتين لمتغير واحد محدبة إذا وفقط إذا كانت مشتقتها الثانية غير سالبة على كامل مجالها . ^{[ 1 ]} ومن الأمثلة المعروفة للدوال المحدبة لمتغير واحد الدالة الخطية${\displaystyle f(x)=cx}$(أين${\displaystyle c}$( عدد حقيقي )، دالة تربيعية${\displaystyle cx^{2}}$(${\displaystyle c}$(كعدد حقيقي غير سالب) ودالة أسية${\displaystyle ce^{x}}$(${\displaystyle c}$(كعدد حقيقي غير سالب).

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

يترك${\displaystyle X}$ليكن مجموعة جزئية محدبة من فضاء متجهي حقيقي، وليكن${\displaystyle f:X\to \mathbb {R} }$أن تكون دالة.

ثم${\displaystyle f}$يُطلق عليه اسم محدب إذا وفقط إذا تحققت أي من الشروط المتكافئة التالية:

1. للجميع${\displaystyle 0\leq t\leq 1}$وكل شيء${\displaystyle x_{1},x_{2}\in X}$: $${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)\leq tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$ يمثل الجانب الأيمن الخط المستقيم بين${\displaystyle \left(x_{1},f\left(x_{1}\right)\right)}$و${\displaystyle \left(x_{2},f\left(x_{2}\right)\right)}$في الرسم البياني لـ${\displaystyle f}$كدالة لـ${\displaystyle t;}$زيادة${\displaystyle t}$من${\displaystyle 0}$ل${\displaystyle 1}$أو تتناقص${\displaystyle t}$من${\displaystyle 1}$ل${\displaystyle 0}$يمسح هذا الخط. وبالمثل، وسيط الدالة${\displaystyle f}$يمثل الجانب الأيسر الخط المستقيم بين${\displaystyle x_{1}}$و${\displaystyle x_{2}}$في${\displaystyle X}$أو${\displaystyle x}$المحور السيني للرسم البياني لـ${\displaystyle f.}$لذا، يتطلب هذا الشرط أن يكون الخط المستقيم بين أي زوج من النقاط على منحنى${\displaystyle f}$أن يكون أعلى من الرسم البياني أو على وشك الوصول إليه. ^{[ 2 ]}
2. للجميع${\displaystyle 0<t<1}$وكل شيء${\displaystyle x_{1},x_{2}\in X}$بحيث${\displaystyle x_{1}\neq x_{2}}$: $${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)\leq tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$ يتمثل الفرق بين هذا الشرط الثاني والشرط الأول المذكور أعلاه في أن هذا الشرط لا يشمل نقاط التقاطع (على سبيل المثال،${\displaystyle \left(x_{1},f\left(x_{1}\right)\right)}$و${\displaystyle \left(x_{2},f\left(x_{2}\right)\right)}$) بين الخط المستقيم المار بنقطتين على منحنى${\displaystyle f}$(يمثل الجانب الأيمن من هذه المعادلة الخط المستقيم) ومنحنى${\displaystyle f;}$يتضمن الشرط الأول نقاط التقاطع عندما يصبح${\displaystyle f\left(x_{1}\right)\leq f\left(x_{1}\right)}$أو${\displaystyle f\left(x_{2}\right)\leq f\left(x_{2}\right)}$في${\displaystyle t=0}$أو${\displaystyle 1,}$أو${\displaystyle x_{1}=x_{2}.}$في الواقع، لا يلزم مراعاة نقاط التقاطع في حالة التحدب باستخدام$${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)\leq tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$لأن${\displaystyle f\left(x_{1}\right)\leq f\left(x_{1}\right)}$و${\displaystyle f\left(x_{2}\right)\leq f\left(x_{2}\right)}$تكون صحيحة دائمًا (لذا ليس من المفيد أن تكون جزءًا من شرط).

العبارة الثانية التي تصف الدوال المحدبة التي لها قيم في خط الأعداد الحقيقية${\displaystyle \mathbb {R} }$يُستخدم هذا المصطلح أيضًا لتعريف الدوال المحدبة التي تُقاس قيمها على خط الأعداد الحقيقية الممتد.${\displaystyle [-\infty ,\infty ]=\mathbb {R} \cup \{\pm \infty \},}$حيثما توجد مثل هذه الوظيفة${\displaystyle f}$يُسمح له بأخذ${\displaystyle \pm \infty }$كقيمة. لم يتم استخدام العبارة الأولى لأنها تسمح${\displaystyle t}$لأخذ${\displaystyle 0}$أو${\displaystyle 1}$كقيمة، وفي هذه الحالة، إذا${\displaystyle f\left(x_{1}\right)=\pm \infty }$أو${\displaystyle f\left(x_{2}\right)=\pm \infty ,}$على التوالي، ثم${\displaystyle tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$ستكون غير مُعرَّفة (لأن عمليات الضرب${\displaystyle 0\cdot \infty }$و${\displaystyle 0\cdot (-\infty )}$(غير مُعرّفة). المجموع${\displaystyle -\infty +\infty }$كما أنها غير معرفة، لذا يُسمح عادةً للدالة المحدبة الممتدة ذات القيم الحقيقية بأخذ قيمة واحدة فقط من القيم التالية:${\displaystyle -\infty }$و${\displaystyle +\infty }$كقيمة.

يمكن أيضًا تعديل العبارة الثانية للحصول على تعريف التحدب الصارم ، حيث يتم الحصول على الأخير عن طريق استبدال${\displaystyle \,\leq \,}$مع عدم المساواة الصارمة${\displaystyle \,<.}$ بشكل صريح، الخريطة${\displaystyle f}$يُطلق عليها اسم محدبة تمامًا إذا وفقط إذا كان لكل عدد حقيقي${\displaystyle 0<t<1}$وكل شيء${\displaystyle x_{1},x_{2}\in X}$بحيث${\displaystyle x_{1}\neq x_{2}}$: $${\displaystyle f\left(tx_{1}+(1-t)x_{2}\right)<tf\left(x_{1}\right)+(1-t)f\left(x_{2}\right)}$$

دالة محدبة تمامًا${\displaystyle f}$هي دالة بحيث يكون الخط المستقيم بين أي زوج من النقاط على المنحنى${\displaystyle f}$يقع فوق المنحنى${\displaystyle f}$باستثناء نقاط التقاطع بين الخط المستقيم والمنحنى. مثال على دالة محدبة ولكنها ليست محدبة تمامًا هو${\displaystyle f(x,y)=x^{2}+y}$هذه الدالة ليست محدبة تمامًا لأن أي نقطتين تشتركان في إحداثي x سيكون بينهما خط مستقيم، بينما أي نقطتين لا تشتركان في إحداثي x سيكون لهما قيمة أكبر للدالة من النقاط الواقعة بينهما.

الوظيفة${\displaystyle f}$يُقال إن السطح مقعر (أو مقعر تمامًا ) إذا${\displaystyle -f}$(${\displaystyle f}$(مضروبًا في -1) يكون محدبًا (على التوالي محدبًا تمامًا).

يُشار غالبًا إلى مصطلح "محدب" بمصطلح "محدب لأسفل" أو "مقعر لأعلى" ، ويُشار غالبًا إلى مصطلح "مقعر " بمصطلح "مقعر لأسفل " أو "محدب لأعلى " . ^{[ 3 ] [ 4 ] [ 5 ]} إذا استُخدم مصطلح "محدب" دون كلمة "لأعلى" أو "لأسفل"، فإنه يشير تحديدًا إلى رسم بياني على شكل كوب.${\displaystyle \cup }$على سبيل المثال، تشير متباينة جنسن إلى متباينة تتضمن دالة محدبة أو محدبة (لأسفل). ^{[ 6 ]}

تتشابه العديد من خصائص الدوال المحدبة في صياغتها البسيطة سواءً للدوال ذات المتغيرات المتعددة أو الدوال ذات المتغير الواحد. انظر أدناه خصائص الدوال ذات المتغيرات المتعددة، حيث لم تُذكر بعض خصائص الدوال ذات المتغير الواحد.

• ${\displaystyle -f}$يكون السطح مقعرًا إذا وفقط إذا${\displaystyle f}$محدب.
• لو${\displaystyle r}$هل أي عدد حقيقي إذن${\displaystyle r+f}$تكون محدبة إذا وفقط إذا${\displaystyle f}$محدب.
• المجاميع المرجحة غير السالبة:
  • لو${\displaystyle w_{1},\ldots ,w_{n}\geq 0}$و${\displaystyle f_{1},\ldots ,f_{n}}$إذا كانت جميعها محدبة، فإن كذلك${\displaystyle w_{1}f_{1}+\cdots +w_{n}f_{n}.}$على وجه الخصوص، فإن مجموع دالتين محدبتين يكون محدباً.
  • تمتد هذه الخاصية إلى المجاميع اللانهائية والتكاملات والقيم المتوقعة أيضًا (بشرط وجودها).
• الحد الأقصى للعناصر: ليكن${\displaystyle \{f_{i}\}_{i\in I}}$لتكن مجموعة من الدوال المحدبة. إذن${\displaystyle g(x)=\sup \nolimits _{i\in I}f_{i}(x)}$محدبة. مجال${\displaystyle g(x)}$هي مجموعة النقاط التي يكون عندها التعبير منتهيًا. حالات خاصة مهمة:
  • لو${\displaystyle f_{1},\ldots ,f_{n}}$إذا كانت الدوال محدبة، فإن الدوال كذلك${\displaystyle g(x)=\max \left\{f_{1}(x),\ldots ,f_{n}(x)\right\}.}$
  • نظرية دانسكين : إذا${\displaystyle f(x,y)}$محدبة في${\displaystyle x}$ثم${\displaystyle g(x)=\sup \nolimits _{y\in C}f(x,y)}$محدبة في${\displaystyle x}$حتى لو${\displaystyle C}$ليست مجموعة محدبة.
• تعبير:
  • لو${\displaystyle f}$و${\displaystyle g}$هي دوال محدبة و${\displaystyle g}$إذا كانت الدالة غير متناقصة على مجال أحادي المتغير،${\displaystyle h(x)=g(f(x))}$محدب. على سبيل المثال إذا${\displaystyle f}$إذا كان محدبًا، فإن كذلك${\displaystyle e^{f(x)}}$لأن${\displaystyle e^{x}}$محدبة ومتزايدة بشكل رتيب.
  • لو${\displaystyle f}$مقعر و${\displaystyle g}$إذا كانت الدالة محدبة وغير متزايدة على مجال أحادي المتغير،${\displaystyle h(x)=g(f(x))}$محدب.
  • التحدب ثابت تحت التحويلات الأفينية: أي، إذا${\displaystyle f}$محدبة ذات مجال${\displaystyle D_{f}\subseteq \mathbf {R} ^{m}}$إذن كذلك${\displaystyle g(x)=f(Ax+b)}$، أين${\displaystyle A\in \mathbf {R} ^{m\times n},b\in \mathbf {R} ^{m}}$مع النطاق${\displaystyle D_{g}\subseteq \mathbf {R} ^{n}.}$
• التقليل: إذا${\displaystyle f(x,y)}$محدبة في${\displaystyle (x,y)}$ثم${\displaystyle g(x)=\inf \nolimits _{y\in C}f(x,y)}$محدبة في${\displaystyle x,}$بشرط أن${\displaystyle C}$هي مجموعة محدبة، و${\displaystyle g(x)\neq -\infty .}$
• لو${\displaystyle f}$إذا كان محدبًا، فإن منظوره${\displaystyle g(x,t)=tf\left({\tfrac {x}{t}}\right)}$مع النطاق${\displaystyle \left\{(x,t):{\tfrac {x}{t}}\in \operatorname {Dom} (f),t>0\right\}}$محدب.
• يترك${\displaystyle X}$ليكن فضاءً متجهيًا.${\displaystyle f:X\to \mathbf {R} }$محدبة وتحقق الشرط التالي:${\displaystyle f(0)\leq 0}$إذا وفقط إذا${\displaystyle f(ax+by)\leq af(x)+bf(y)}$لأي${\displaystyle x,y\in X}$وأي أعداد حقيقية غير سالبة${\displaystyle a,b}$ذلك يرضي${\displaystyle a+b\leq 1.}$

يُوسّع مفهوم التحدب القوي مفهوم التحدب الصارم ويُحدّد معالمه. وبشكلٍ بديهي، فإن الدالة المحدبة بقوة هي دالة تنمو بنفس سرعة الدالة التربيعية. ^{[ 11 ]} الدالة المحدبة بقوة تكون أيضًا محدبة تمامًا، ولكن ليس العكس. إذا كانت دالة أحادية البعد${\displaystyle f}$إذا كانت الدالة قابلة للتفاضل مرتين بشكل مستمر وكان مجالها هو خط الأعداد الحقيقية، فيمكننا وصفها على النحو التالي:

• ${\displaystyle f}$محدبة إذا وفقط إذا${\displaystyle f''(x)\geq 0}$للجميع${\displaystyle x.}$
• ${\displaystyle f}$محدب تمامًا إذا${\displaystyle f''(x)>0}$للجميع${\displaystyle x}$(ملاحظة: هذا كافٍ، ولكنه ليس ضرورياً).
• ${\displaystyle f}$محدبة بقوة إذا وفقط إذا${\displaystyle f''(x)\geq m>0}$للجميع${\displaystyle x.}$

على سبيل المثال، لنفترض${\displaystyle f}$لنفترض أن يكون محدبًا تمامًا، ولنفترض وجود سلسلة من النقاط${\displaystyle (x_{n})}$بحيث${\displaystyle f''(x_{n})={\tfrac {1}{n}}}$. بالرغم من${\displaystyle f''(x_{n})>0}$الدالة ليست محدبة بقوة لأن${\displaystyle f''(x)}$سيصبح صغيراً بشكل تعسفي.

وبشكل أعم، دالة قابلة للتفاضل${\displaystyle f}$يُطلق عليه اسم محدب بقوة مع المعامل${\displaystyle m>0}$إذا تحققت المتباينة التالية لجميع النقاط${\displaystyle x,y}$في نطاقها: ^{[ 12 ]}$${\displaystyle (\nabla f(x)-\nabla f(y))^{T}(x-y)\geq m\|x-y\|_{2}^{2}}$$ أو بشكل أعم، $${\displaystyle \langle \nabla f(x)-\nabla f(y),x-y\rangle \geq m\|x-y\|^{2}}$$ أين${\displaystyle \langle \cdot ,\cdot \rangle }$أي منتج داخلي ، و${\displaystyle \|\cdot \|}$هو المعيار المقابل . يشير بعض المؤلفين، مثل ^{[ 13 ]،} إلى الدوال التي تحقق هذه المتباينة باسم الدوال الإهليلجية .

الشرط المكافئ هو التالي: ^{[ 14 ]}$${\displaystyle f(y)\geq f(x)+\nabla f(x)^{T}(y-x)+{\frac {m}{2}}\|y-x\|_{2}^{2}}$$

ليس من الضروري أن تكون الدالة قابلة للتفاضل لكي تكون محدبة بقوة. تعريف ثالث ^{[ 14 ]} للدالة المحدبة بقوة، مع المعامل${\displaystyle m,}$هذا هو، بالنسبة للجميع${\displaystyle x,y}$في المجال و${\displaystyle t\in [0,1],}$$${\displaystyle f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)-{\frac {1}{2}}mt(1-t)\|x-y\|_{2}^{2}}$$

لاحظ أن هذا التعريف يقترب من تعريف التحدب الصارم عندما${\displaystyle m\to 0,}$وهو مطابق لتعريف الدالة المحدبة عندما${\displaystyle m=0.}$على الرغم من ذلك، توجد دوال محدبة تمامًا ولكنها ليست محدبة بقوة لأي${\displaystyle m>0}$(انظر المثال أدناه).

إذا كانت الدالة${\displaystyle f}$إذا كانت الدالة قابلة للتفاضل مرتين بشكل مستمر، فإنها تكون محدبة بقوة ذات معامل${\displaystyle m}$إذا وفقط إذا${\displaystyle \nabla ^{2}f(x)\succeq mI}$للجميع${\displaystyle x}$في المجال، حيث${\displaystyle I}$هي الهوية و${\displaystyle \nabla ^{2}f}$هي مصفوفة هيسيان ، والمتباينة${\displaystyle \succeq }$هذا يعني أن${\displaystyle \nabla ^{2}f(x)-mI}$هي شبه موجبة . وهذا يكافئ اشتراط أن تكون القيمة الذاتية الدنيا لـ${\displaystyle \nabla ^{2}f(x)}$كن على الأقل${\displaystyle m}$للجميع${\displaystyle x.}$إذا كان المجال هو خط الأعداد الحقيقية فقط، فإن${\displaystyle \nabla ^{2}f(x)}$هي مجرد المشتقة الثانية${\displaystyle f''(x),}$وهكذا يصبح الشرط${\displaystyle f''(x)\geq m}$. لو${\displaystyle m=0}$وهذا يعني أن مصفوفة هيسيان موجبة شبه محددة (أو إذا كان المجال هو خط الأعداد الحقيقية، فهذا يعني أن${\displaystyle f''(x)\geq 0}$)، مما يعني أن الدالة محدبة، وربما محدبة تمامًا، ولكنها ليست محدبة بقوة.

بافتراض أن الدالة قابلة للتفاضل مرتين بشكل مستمر، يمكن إثبات أن الحد الأدنى لـ${\displaystyle \nabla ^{2}f(x)}$وهذا يعني أنها محدبة بشدة. باستخدام نظرية تايلور، يوجد $${\displaystyle z\in \{tx+(1-t)y:t\in [0,1]\}}$$ بحيث $${\displaystyle f(y)=f(x)+\nabla f(x)^{T}(y-x)+{\frac {1}{2}}(y-x)^{T}\nabla ^{2}f(z)(y-x)}$$ ثم $${\displaystyle (y-x)^{T}\nabla ^{2}f(z)(y-x)\geq m(y-x)^{T}(y-x)}$$ بناءً على الافتراض المتعلق بالقيم الذاتية، وبالتالي نستعيد معادلة التحدب القوي الثانية المذكورة أعلاه.

وظيفة${\displaystyle f}$تكون الدالة محدبة بقوة ذات المعامل m إذا وفقط إذا كانت الدالة $${\displaystyle x\mapsto f(x)-{\frac {m}{2}}\|x\|^{2}}$$ محدب.

دالة قابلة للتفاضل مرتين بشكل مستمر${\displaystyle f}$في نطاق مضغوط${\displaystyle X}$ذلك يرضي${\displaystyle f''(x)>0}$للجميع${\displaystyle x\in X}$هي دالة محدبة بقوة. ويستند برهان هذه العبارة إلى نظرية القيمة القصوى ، التي تنص على أن الدالة المتصلة على مجموعة مضغوطة لها قيمة عظمى وقيمة صغرى.

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

دالة محدبة بانتظام، ^{[ 16 ] [ 17 ]} ذات معامل${\displaystyle \phi }$، هي دالة${\displaystyle f}$ذلك، للجميع${\displaystyle x,y}$في المجال و${\displaystyle t\in [0,1],}$يرضي $${\displaystyle f(tx+(1-t)y)\leq tf(x)+(1-t)f(y)-t(1-t)\phi (\|x-y\|)}$$ أين${\displaystyle \phi }$هي دالة غير سالبة ولا تنعدم إلا عند  الصفر. وهذا تعميم لمفهوم الدالة المحدبة بقوة؛ وذلك بأخذ${\displaystyle \phi (\alpha )={\tfrac {m}{2}}\alpha ^{2}}$نستعيد تعريف التحدب القوي.

تجدر الإشارة إلى أن بعض المؤلفين يشترطون استخدام المعامل.${\displaystyle \phi }$أن تكون دالة متزايدة، ^{[ 17 ]} ولكن هذا الشرط ليس مطلوبًا من جميع المؤلفين. ^{[ 16 ]}

• بيرتسيكاس، ديمتري (2003). التحليل المحدب والتحسين . أثينا ساينتيفيك.
• بورواين، جوناثان ، ولويس، أدريان. (2000). التحليل المحدب والتحسين غير الخطي. سبرينغر.
• دونوهيو، ويليام ف. (1969). التوزيعات وتحويلات فورييه . دار النشر الأكاديمية.
• هيريارت أوروتي، جان بابتيست، ولومارشال، كلود . (2004). أساسيات التحليل المحدب. برلين: سبرينغر.
• Krasnosel'skii MA ، Rutickii Ya.B. (1961). الدوال المحدبة وفضاءات أورليتش . جرونينجن: بي نوردهوف المحدودة.
• لوريتزن، نيلز (2013). التحدب الجامعي . دار النشر العالمية العلمية.
• لوينبرغر، ديفيد (1984). البرمجة الخطية وغير الخطية . أديسون-ويسلي.
• لوينبرغر، ديفيد (1969). التحسين باستخدام طرق الفضاء المتجهي . وايلي وأولاده.
• روكافيلر، آر تي (1970). التحليل المحدب . برينستون: مطبعة جامعة برينستون.
• تومسون، برايان (1994). الخصائص المتناظرة للدوال الحقيقية . مطبعة سي آر سي.
• زالينسكو، سي. (2002). التحليل المحدب في الفضاءات المتجهة العامة . ريفر إيدج، نيوجيرسي: دار  النشر العالمية العلمية . الصفحات: xx+367. ISBN    981-238-067-1MR 1921556 .​ 

• "الدالة المحدبة (لمتغير حقيقي)" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• "الدالة المحدبة (لمتغير مركب)" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]