हाइपरप्लेन पृथक्करण प्रमेय

ज्यामिति में, हाइपरप्लेन पृथक्करण प्रमेय, 'n'-आयामी यूक्लिडियन स्पेस में उत्तल समुच्चय पृथक्करण हेतु एक प्रमेय है। इसके कई संस्करण उपलब्ध है। प्रमेय के एक संस्करण में, यदि ये दोनों समुच्चय संकुचित समुच्चय हैं और उनमें से कम से कम एक सघन समुच्चय है, तो उनके मध्य में एक हाइपरप्लेन है और उनके मध्य दो समानांतर हाइपरप्लेन भी किसी अंतराल से भिन्न हो गए हैं। दूसरे संस्करण में, यदि दोनों असंयुक्त उत्तल समुच्चय विवृत हैं, तो उनके मध्य एक हाइपरप्लेन है, परन्तु जरूरी नहीं कि कोई अंतराल हो। कोई अक्ष जो किसी अलग करने वाले हाइपरप्लेन के लिए अष्टभुजीय है, पृथक करने वाला अक्ष है, क्योंकि अक्ष पर उत्तल पिंडों के अष्टभुजीय प्रक्षेप असंयुक्त हैं।

हाइपरप्लेन पृथक्करण प्रमेय हरमन मिन्कोव्स्की के कारण है। हन-बनाक पृथक्करण प्रमेय स्थलीय सदिश स्थानों के परिणाम का सामान्यीकरण करता है।

एक संबंधित परिणाम सहायक हाइपरप्लेन प्रमेय है।

समर्थन सदिश यंत्र के संदर्भ में, आदर्श पृथक्करण हाइपरप्लेन या अधिकतम-सीमा हाइपरप्लेन एक ऐसा हाइपरप्लेन होता है जो दो बिंदुगणित समूहों को पृथक्करण करता है और इन दोनों से समान दूरी पर स्थित होता है।

कथन और प्रमाण

सभी स्थितियों में, मान लीजिए $A,B$ असंयुक्त, अरिक्त और के उत्तल उपसमुच्चय $\mathbb {R} ^{n}$ है जिनके परिणामों का सारांश इस प्रकार है:

summary table

$A$	$B$	$\langle x,v\rangle$	$\langle y,v\rangle$
		$\geq c$	$\leq c$
संवृत तथा सघन	संवृत	$>c_{1}$	$<c_{2}$ के साथ $c_{2}<c_{1}$
संवृत	संवृत तथा सघन	$>c_{1}$	$<c_{2}$ के साथ $c_{2}<c_{1}$
विवृत		$>c$	$\leq c$
विवृत	विवृत	$>c$	$<c$

Hyperplane separation theorem — मान लीजिये की $A$ and $B$

$\mathbb {R} ^{n}$ का दो असम्बद्ध अरिक्त उत्तल उपसमुच्चय है तब एक ऐसा अशून्य सदिश $v$  तथा एक वास्तविक संख्या $c$ इस प्रकार उपलब्ध है की

$\langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c$

सभी $x$ में $A$ तथा $y$ में $B$ के लिए समर्थित है; उदहारण हेतु एक हाइपरप्लेन $\langle \cdot ,v\rangle =c$, $v$ में सदिश $A$ and $B$ को पृथक करता है

यदि दोनों समुच्चय बंद हैं, और उनमें से कम से कम एक सघन है, तो पृथक्करण कठिन हो सकता है, उदाहरण के लिए, $\langle x,v\rangle >c_{1}\,{\text{और}}\langle y,v\rangle <c_{2}$ $c_{1}>c_{2}$ के लिए सत्य है

आयामों की संख्या परिमित होनी चाहिए। अनंत-आयामी स्थानों में दो संवृत, उत्तल, असंयुक्त समुच्चय के उदाहरण हैं जिन्हें एक संवृत हाइपरप्लेन (एक हाइपरप्लेन जहां एक सतत रैखिक कार्यात्मक कुछ स्थिरांक के बराबर होता है) से अलग नहीं किया जा सकता है, यहां तक ​​कि कमजोर अर्थों में भी जहां असमानताएं सख्त नहीं हैं। यहाँ, परिकल्पना में सघनता को शिथिल नहीं किया जा सकता है; इसका उदहारण आगे के अनुभाग में प्रदर्शित किया गया है। पृथक्करण प्रमेय का यह संस्करण अनंत-आयाम का सामान्यीकरण करता है; सामान्यीकरण को सामान्यतः हाह्न-बनाक पृथक्करण प्रमेय के रूप में जाना जाता है।

जिसका प्रमाण निम्नलिखित लेम्मा पर आधारित है:

Lemma — Let $A$ and $B$ be two disjoint closed subsets of $\mathbb {R} ^{n}$, and assume $A$ is compact. Then there exist points $a_{0}\in A$ and $b_{0}\in B$ minimizing the distance $\|a-b\|$ over $a\in A$ and $b\in B$.

Proof of lemma

Let $a\in A$ and $b\in B$ be any pair of points, and let $r_{1}=\|b-a\|$. Since $A$ is compact, it is contained in some ball centered on $a$; let the radius of this ball be $r_{2}$. Let $S=B\cap {\overline {B_{r_{1}+r_{2}}(a)}}$ be the intersection of $B$ with a closed ball of radius $r_{1}+r_{2}$ around $a$. Then $S$ is compact and nonempty because it contains $b$. Since the distance function is continuous, there exist points $a_{0}$ and $b_{0}$ whose distance $\|a_{0}-b_{0}\|$ is the minimum over all pairs of points in $A\times S$. It remains to show that $a_{0}$ and $b_{0}$ in fact have the minimum distance over all pairs of points in $A\times B$. Suppose for contradiction that there exist points $a'$ and $b'$ such that $\|a'-b'\|<\|a_{0}-b_{0}\|$. Then in particular, $\|a'-b'\|<r_{1}$, and by the triangle inequality, $\|a-b'\|\leq \|a'-b'\|+\|a-a'\|<r_{1}+r_{2}$. Therefore $b'$ is contained in $S$, which contradicts the fact that $a_{0}$ and $b_{0}$ had minimum distance over $A\times S$. $\square$

Proof of theorem

We first prove the second case. (See the diagram.)

WLOG, $A$ is compact. By the lemma, there exist points $a_{0}\in A$ and $b_{0}\in B$ of minimum distance to each other. Since $A$ and $B$ are disjoint, we have $a_{0}\neq b_{0}$. Now, construct two hyperplanes $L_{A},L_{B}$ perpendicular to line segment $[a_{0},b_{0}]$, with $L_{A}$ across $a_{0}$ and $L_{B}$ across $b_{0}$. We claim that neither $A$ nor $B$ enters the space between $L_{A},L_{B}$, and thus the perpendicular hyperplanes to $(a_{0},b_{0})$ satisfy the requirement of the theorem.

Algebraically, the hyperplanes $L_{A},L_{B}$ are defined by the vector $v:=b_{0}-a_{0}$, and two constants $c_{A}:=\langle v,a_{0}\rangle <c_{B}:=\langle v,b_{0}\rangle$, such that $L_{A}=\{x:\langle v,x\rangle =c_{A}\},L_{B}=\{x:\langle v,x\rangle =c_{B}\}$. Our claim is that $\forall a\in A,\langle a,v\rangle \leq c_{A}$ and $\forall b\in B,\langle b,v\rangle \leq c_{B}$.

Suppose there is some $a\in A$ such that $\langle a,v\rangle >c_{A}$, then let $a'$ be the foot of perpendicular from $b_{0}$ to the line segment $[a_{0},a]$. Since $A$ is convex, $a'$ is inside $A$, and by planar geometry, $a'$ is closer to $b_{0}$ than $a_{0}$, contradiction. Similar argument applies to $B$.

Now for the first case.

Approach both $A,B$ from the inside by $A_{1}\subseteq A_{2}\subseteq \cdots \subseteq A$ and $B_{1}\subseteq B_{2}\subseteq \cdots \subseteq B$, such that each $A_{k},B_{k}$ is closed and compact, and the unions are the relative interiors $\mathrm {relint} (A),\mathrm {relint} (B)$. (See relative interior page for details.)

Now by the second case, for each pair $A_{k},B_{k}$ there exists some unit vector $v_{k}$ and real number $c_{k}$, such that $\langle v_{k},A_{k}\rangle <c_{k}<\langle v_{k},B_{k}\rangle$.

Since the unit sphere is compact, we can take a convergent subsequence, so that $v_{k}\to v$. Let $c_{A}:=\sup _{a\in A}\langle v,a\rangle ,c_{B}:=\inf _{b\in B}\langle v,b\rangle$. We claim that $c_{A}\leq c_{B}$, thus separating $A,B$.

Assume not, then there exists some $a\in A,b\in B$ such that $\langle v,a\rangle >\langle v,b\rangle$, then since $v_{k}\to v$, for large enough $k$, we have $\langle v_{k},a\rangle >\langle v_{k},b\rangle$, contradiction.

चूँकि एक पृथक्करण हाइपरप्लेन विवृत उत्तल समुच्चयों के आतंरिक भागों को नहीं काट सकता है, हमारे पास एक परिणाम है:

Separation theorem I — Let $A$ and $B$ be two disjoint nonempty convex sets. If $A$ is open, then there exist a nonzero vector $v$ and real number $c$ such that

$\langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle \leq c$

for all $x$ in $A$ and $y$ in $B$. If both sets are open, then there exist a nonzero vector $v$ and real number $c$ such that

$\langle x,v\rangle >c\,{\text{ and }}\langle y,v\rangle <c$

for all $x$ in $A$ and $y$ in $B$.

संभावित प्रतिच्छेदन की स्थिति

अगर समुच्चय करता है यदि समूह $A,B$ में संभावित प्रतिच्छेदन होता है, परन्तु उनके सांदर्भिक आंतरिकों में पृथक्करण होता है, तो पहली स्थिति के प्रमाण, परिवर्तन के बिना ही लागू हो जाते है, जिससे निम्न परिणाम मिलता है:

Separation theorem II — Let $A$ and $B$ be two nonempty convex subsets of $\mathbb {R} ^{n}$ with disjoint relative interiors. Then there exist a nonzero vector $v$ and a real number $c$ such that

$\langle x,v\rangle \geq c\,{\text{ and }}\langle y,v\rangle \leq c$

विशेष रूप से, हमारे पास सहायक हाइपरप्लेन प्रमेय है।

Supporting hyperplane theorem — if $A$ is a convex set in $\mathbb {R} ^{n},$ and $a_{0}$ is a point on the boundary of $A$, then there exists a supporting hyperplane of $A$ containing $a_{0}$.

Proof

If the affine span of $A$ is not all of $\mathbb {R} ^{n}$, then extend the affine span to a supporting hyperplane. Else, $\mathrm {relint} (A)=\mathrm {int} (A)$ is disjoint from $\mathrm {relint} (\{a_{0}\})=\{a_{0}\}$, so apply the above theorem.

प्रमेय का विलोम

ध्यान दें कि एक हाइपरप्लेन का अस्तित्व जो केवल दो उत्तल समुच्चयों को अलग करता है, दोनों असमानताओं के कमजोर अर्थों में गैर-सख्त होने का स्पष्ट रूप से यह अर्थ नहीं है कि दो समुच्चय अलग हैं। दोनों समुच्चयों में हाइपरप्लेन पर स्थित बिंदु भिन्न हो सकते हैं।

प्रति उदाहरण और विशिष्टता

यदि A और B में से एक उत्तल नहीं है, तो कई संभावित प्रति उदाहरण हैं। उदाहरण के लिए, A और B संकेंद्रित वृत्त हो सकते हैं। एक अधिक सूक्ष्म प्रति उदाहरण वह है जिसमें ए और बी दोनों संवृत हैं परन्तु कोई भी सघन नहीं है। उदाहरण के लिए, यदि ए एक संवृत अर्ध समुच्चय है और बी हाइपरबोला के एक हाथ से घिरा हुआ है, तो कोई सख्ती से अलग करने वाला हाइपरप्लेन नहीं है:

$A=\{(x,y):x\leq 0\}$

$B=\{(x,y):x>0,y\geq 1/x\}.\$

यद्यपि, दूसरे प्रमेय के एक उदाहरण से, एक हाइपरप्लेन है जो उनके आंतरिक भाग को अलग करता है। एक अन्य प्रकार के प्रति उदाहरण में A सघन और B विवृत है। उदाहरण के लिए, A एक संवृत वर्ग हो सकता है और B एक विवृत वर्ग हो सकता है जो A को स्पर्श करता है।

प्रमेय के पहले संस्करण में, स्पष्ट रूप से अलग करने वाला हाइपरप्लेन कभी भी अद्वितीय नहीं होता है। दूसरे संस्करण में, यह अद्वितीय हो भी सकता है और नहीं भी। तकनीकी रूप से एक पृथक्करण धुरी कभी भी अद्वितीय नहीं होती क्योंकि इसका अनुवाद किया जा सकता है; प्रमेय के दूसरे संस्करण में, एक अलग अक्ष अनुवाद तक अद्वितीय हो सकता है।

हॉर्न कोण कई हाइपरप्लेन पृथक्करणों के लिए एक अच्छा प्रति उदाहरण प्रदान करता है। उदाहरण के लिए, में $\mathbb {R} ^{2}$, यूनिट डिस्क विवृत अंतराल से अलग है $((1,0),(1,1))$, परन्तु उन्हें अलग करने वाली एकमात्र रेखा में संपूर्णता शामिल है $((1,0),(1,1))$. इससे पता चलता है कि अगर $A$ संवृत है और $B$ अपेक्षाकृत विवृत है, तो जरूरी नहीं कि एक पृथक्करण उपलब्ध हो जो सख्त हो $B$. हालांकि, यदि $A$ संवृत पालीटॉप है तो ऐसा पृथक्करण उपलब्ध है।

अन्य प्रकार

फ़ार्कस लेम्मा और संबंधित परिणामों को हाइपरप्लेन पृथक्करण प्रमेय के रूप में समझा जा सकता है, जब उत्तल पिंडों को सूक्ष्म रूप से कई रेखीय असमानताओं द्वारा परिभाषित किया जाता है तो और भी परिणाम मिल सकते हैं।

संघटन का पता लगाने में प्रयोग

संघटन का पता लगाने में, हाइपरप्लेन पृथक्करण प्रमेय सामान्यतः निम्न रूप में प्रयोग किया जाता है:

अक्ष पृथक्करण प्रमेय — यदि एक रेखा ("पृथक्करण धारक ध्रुव") उपलब्ध होती है जिस पर दो सम्पूर्ण घनों के प्रक्षेपण अलगावपूर्ण होते हैं, तो दो बंद घन अलग होते हैं।

आयाम के अतिरिक्त, पृथक्करण धुरी सदैव एक रेखा होती है।

उदाहरण के लिए, 3डी में, समष्टि को प्लेन द्वारा अलग किया जाता है, परन्तु अलग करने वाला अक्ष अलग करने वाले प्लेन के लंबवत होता है।

बहुभुज धुरी के मध्य तेजी से संघटन का पता लगाने के लिए पृथक अक्ष प्रमेय लागू किया जा सकता है। प्रत्येक फलक की सतह सामान्य या अन्य विशेषता दिशा का उपयोग पृथक करने वाले अक्ष के रूप में किया जाता है। ध्यान दें कि यह भिन्न-भिन्न अक्षों को अलग करता है तथा रेखा/प्लेन को अलग नहीं करता है।

3डी में, फेस नॉर्म्स का उपयोग अकेले कुछ एज-ऑन-एज गैर-संघटन वाले स्थितियों को अलग करने में विफल होता है। अतिरिक्त अक्षों की आवश्यकता होती है, जिसमें शीर्षों के युग्म के गुणन-उत्पाद सम्मिलित होते हैं।

प्रवर्धित दक्षता के लिए, समानांतर अक्षों की गणना एकल अक्ष के रूप में की जा सकती है।

यह भी देखें

• दोहरी शंकु
• फ़र्कस की लेम्मा
• किर्चबर्गर प्रमेय
• इष्टतम नियंत्रण

संदर्भ

• Boyd, Stephen P.; Vandenberghe, Lieven (2004). Convex Optimization (PDF). Cambridge University Press. ISBN 978-0-521-83378-3.
• Golshtein, E. G.; Tretyakov, N.V. (1996). Modified Lagrangians and monotone maps in optimization. New York: Wiley. p. 6. ISBN 0-471-54821-9.
• Shimizu, Kiyotaka; Ishizuka, Yo; Bard, Jonathan F. (1997). Nondifferentiable and two-level mathematical programming. Boston: Kluwer Academic Publishers. p. 19. ISBN 0-7923-9821-1.

• Soltan, V. (2021). Support and separation properties of convex sets in finite dimension. Extracta Math. Vol. 36, no. 2, 241-278.

बाहरी संबंध

• Collision detection and response