उत्तलता और लिप्सचित्ज़ निरंतरता

Oct 24 2020

यह शायद एक आसान सवाल है, लेकिन किसी तरह मैं फंस गया हूं।

प्रश्न निम्नलिखित कथन सत्य है? यदि हाँ, तो इसे कैसे प्रमाणित करें?

लगता है कि $f\in C^1(\mathbb{R}^n)$ उत्तल है और $$ \langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L|x-y|^2 $$ कुछ के लिए $L>0$ और सभी $x,y\in\mathbb{R}^n$। क्या यह उसका पालन करता है$$ |\nabla f(x)-\nabla f(y)|\leq L|x-y| $$ सभी के लिए $x,y\in\mathbb{R}^n$?

जवाब

11 Dirk Oct 24 2020 at 17:44

उत्तल अनुकूलन में यह एक मानक परिणाम है। उदाहरण के लिए, नेस्टरोव के "इंटेक्सटरी लेक्चर्स ऑन कॉनवेक्स ऑप्टिमाइज़ेशन" में प्रमेय 2.1.5 में कहा गया है कि निम्नलिखित हैं:

  • $f$ है $C^1$, उत्तल और ढाल $\nabla f$ है $L$-लिप्सिट्ज़
  • सभी के लिए $x,y$: $0\leq f(y) - f(x) - \langle\nabla f(x),y-x\rangle \leq \tfrac{L}2 \|x-y\|^2$
  • सभी के लिए $x,y$: $\tfrac1L\|\nabla f(x)-\nabla f(y)\|^2 \leq \langle\nabla f(x)-\nabla f(y),x-y\rangle$
  • सभी के लिए $x,y$: $\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$

(यदि आप रुचि रखते हैं: प्रमाण वहाँ के लिए सीधे है $C^1$ फ़ंक्शंस और कोई दूसरा डेरिवेटिव मध्यवर्ती चरणों में उपयोग नहीं किया जाता है।)

9 DenisSerre Oct 24 2020 at 15:13

हाँ

पहले मामले पर विचार करें जहां $f\in{\cal C}^2$। फिर$$\nabla f(y)-\nabla f(x)=\int_0^1{\rm D}^2f(x+t(y-x))\cdot(y-x)\,dt.$$ इस प्रकार है $$\|\nabla f(y)-\nabla f(x)\|\le\|y-x\|\int_0^1\|{\rm D}^2f(x+t(y-x))\|\,dt.$$ अब, धारणा आपको बताती है कि $\|{\rm D}^2f(x+t(y-x))\|\le L$, परिणाम

अब सामान्य मामला एक घनत्व तर्क द्वारा प्राप्त किया जा सकता है। एक उत्तल कार्य करते हैं$f$अपनी धारणा को पूरा करें। के लिये$\epsilon>0$, एट हमें एक चिकनी उत्तल फ़ंक्शन को परिभाषित करते हैं $f_\epsilon$ उल्लंघन से: $$f_\epsilon(x)=\inf_z(f(z)+\frac1\epsilon\,\|x-z\|^2).$$ के लिए परिणाम लागू करें $f_\epsilon$, तो के रूप में सीमा के पास $\epsilon\rightarrow0$।

4 PiotrHajlasz Oct 24 2020 at 23:31

यह उत्तर डेनिस सेरे के उत्तर का एक छोटा संशोधन है। मैंने पाठक की सुविधा के लिए जोड़ा: (1) परिणाम थोड़ा अधिक सामान्य है; (2) उत्तर में बहुत अधिक विवरण हैं; (३) मैं विभक्ति-दोष के बजाय मोलिफ़िकेशन सन्निकटन द्वारा एक कनवल्शन का उपयोग कर रहा हूँ।

चूंकि उत्तल कार्य संतुष्ट करते हैं $$ \langle \nabla f(x)-\nabla f(y),x-y\rangle\geq 0, $$ यह निम्नलिखित अधिक सामान्य परिणाम साबित करने के लिए पर्याप्त है।

प्रमेय। लश्कर$f\in C^1(\mathbb{R}^n)$ और जाने $L>0$जब निम्नलिखित स्थितियाँ समतुल्य हो जाती हैं: \ start {समीकरण} (1) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ lab \ nabla f (x) - \ nabla f (y), xy \ | rangle | \ leq L | xy | ^ 2 \ quad \ text {सभी के लिए$x,y\in\mathbb{R}^n$।} \ _ {समीकरण} \ _ {समीकरण {शुरू} (2) \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ _ \ n नाबला च | (x) - \ nabla f (y) | \ leq L | xy | सभी के लिए \ quad \ text {$x,y\in\mathbb{R}^n$।} \ n अंत {समीकरण}

सबूत। जबकि निहितार्थ (2) से (1) स्पष्ट है कि दूसरा नहीं है इसलिए हम अब (2) से (1) तक निहितार्थ को सिद्ध करेंगे। पहले मान लें कि$f\in C^\infty(\mathbb{R}^n)$। के लिये$|u|=1$, (1) पैदावार, $$ \left|\left\langle\frac{\nabla f(x+tu)-\nabla f(x)}{t},u\right\rangle\right|\leq L, $$ इसलिए सीमा के रूप में गुजर रहा है $t\to 0$ देता है $$ |\langle D^2f(x)u,u\rangle|\leq L. $$ जबसे $D^2 f(x)$ एक सममित मैट्रिक्स है, वर्णक्रमीय प्रमेय का अर्थ है कि मैट्रिक्स का ऑपरेटर मान $D^2f(x)$ संतुष्ट $$ \Vert D^2f(x)\Vert = \sup_{|u|=1}|\langle D^2f(x)u,u\rangle|\leq L. $$यह अनुमान हालांकि, आसानी से परिणाम \ start {समीकरण {\ _ {विभाजन} & | \ nabla f (x) - \ nabla f (y) | = \ left | \ int_0 ^ 1 \ frac {d} {tt} को परिणामित करता है। \ nabla f (y + t (xy)) \, dt \ right | \\ & \ le | xy | \ int_0 ^ 1 \ Vert D ^ 2f (y + t (xy)) \ Vert \, dt \ leq L | xy | \ end {विभाजित} \ end {समीकरण} यह जब सबूत पूरा करता है$f\in C^\infty$। अब मान लें कि$f\in C^1$ और जाने $f_\epsilon=f*\varphi_\epsilon$दृढ़ संकल्प द्वारा एक मानक सन्निकटन हो। याद करें कि$f_\epsilon\in C^\infty$ तथा $\nabla f_\epsilon=(\nabla f)*\varphi_\epsilon$। हमारे पास \ समीकरण {\} शुरू / विभाजित {शुरू} और | \ langle \ nabla f_ \ epsilon (x) - \ nabla f_ \ epsilon (y), xy \ rangle | = \ बिग / \ Big \ langle \ int \ {\ _ mathbb {R} ^ n} (\ nabla f (xz) - \ nabla f (yz)) \ varphi_ \ epsilon (z) \, dz, xy \ Big \ rangle का बिग। \\ & \ leq \ int _ {| mathbb {R} ^ n} \ big | \ big \ langle \ nabla f (xz) - \ nabla f (yz)), (xz) - (yz) \ big \ rangle \ big। \ _, \ varphi_ \ epsilon ( z) \ _, dz \ leq L | xy | ^ 2, \ end {विभाजित} \ end {समीकरण} जहां अंतिम असमानता का परिणाम है (1) और$\int_{\mathbb{R}^n}\varphi_\epsilon=1$। जबसे$f_\epsilon\in C^\infty$सबूत पैदावार का पहला हिस्सा $$ |\nabla f_\epsilon(x)-\nabla f_\epsilon(y)|\leq L|x-y| $$ और परिणाम निम्नानुसार सीमा से गुजर रहा है $\epsilon\to 0$।

3 Borbei Oct 24 2020 at 14:23

एक आंशिक उत्तर: यदि आप अपनी धारणा को मजबूत करने और मान लेने के लिए तैयार हैं $f\in C^2(\mathbb{R}^n)$, तो ठीक। अन्यथा, मुझे यकीन नहीं है।


कार्य जो संतुष्ट करते हैं - $$\langle\nabla f(x)-\nabla f(y),x-y\rangle \leq L\|x-y\|^2$$ "एल-अर्ध-अवतल" कहा जाता है, और कार्य जो संतुष्ट करते हैं - $$\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$$ "एल-चिकनी" कहा जाता है।

अगर $f\in C^2(\mathbb{R}^n)$ दोनों कम से कम एल-सेमी-उत्तल है (विशेष रूप से, उत्तल) और कम से कम एल-अर्ध-संधि - तो यह वास्तव में एल-चिकनी है।

एक हेस्सियन पर विचार करके इसे साबित कर सकता है $\nabla^2f$ का $f$: उत्तलता का तात्पर्य है सकारात्मक सकारात्मक, और अर्ध-समरूपता का तात्पर्य है $\nabla^2f-\frac{1}{2}\mathrm{Id}$ऋणात्मक अर्धचालक है। इसलिए, के ऑपरेटर-आदर्श$\nabla^2f$ बाध्य होना चाहिए, जिसका अर्थ है कि $\nabla f$ लिप्सचित्ज़ है (यानी $f$ L- चिकनी है)।

मुझे यकीन नहीं है कि यह अभी भी कमजोर धारणा के तहत है $f\in C^1(\mathbb{R}^n)$।