Timeline for How to prove this (corollary of) hyperplane separation theorem?
Current License: CC BY-SA 4.0
40 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 20, 2022 at 7:29 | comment | added | Fedor Petrov | @copper.hat I do not mind | |
| Aug 20, 2022 at 5:01 | comment | added | copper.hat | @FedorPetrov If you don't mind, I might add my elaborations as an answer to the corresponding question on MSE, with appropriate attribution, of course. | |
| Aug 20, 2022 at 4:18 | comment | added | copper.hat | @Ypbor dual cone. Unfortunately comments are not the best place for clarification. | |
| Aug 20, 2022 at 2:12 | comment | added | Ypbor | @copper.hat By "taking the dual", do you mean "dual space" (en.wikipedia.org/wiki/Dual_space) or "dual cone" (en.wikipedia.org/wiki/Dual_cone_and_polar_cone)? | |
| Aug 19, 2022 at 17:23 | comment | added | copper.hat | @Ypbor Please replace span by convex cone generated by... | |
| Aug 19, 2022 at 14:25 | comment | added | Ypbor | @copper.hat It seems that you suggested (1) $A \subset B$ implies $\mbox{dual} B \subset \mbox{dual} A$, and (2) $\mbox{dual}\left\{y \in Y | e_k(y) \geq 0\right\}=sp\left\{e_k\right\}$. Why are they true? | |
| Aug 17, 2022 at 5:32 | comment | added | copper.hat | @Ypbor If $y\ge 0$ (that is, component wise) and $y \in Y$ then $-y \in C$ and so $\eta(-y) \le 0$, hence $\eta(y) \ge 0$. | |
| Aug 17, 2022 at 5:28 | comment | added | copper.hat | @Ypbor The notations mean span and sum respectively. The dual of the intersections is the sum of the duals (see math.stackexchange.com/q/3356026/27978). | |
| Aug 15, 2022 at 11:50 | comment | added | Ypbor | @copper.hat Why is $\cap_K \left\{y \in Y | e_k(y) \geq 0\right\} \subset \left\{y \in Y|\eta(y) \geq 0\right\}$ true? (2) What does "taking the dual" mean? (3) What are the meanings of notation $sp$ and $+_k$? | |
| Aug 13, 2022 at 20:39 | comment | added | copper.hat | (Cont.) Now consider this as extending $\eta$ onto all of $\mathbb{R}^n$. In particular, we see that the extended $\eta$ is non positive on $(-\infty,0]^n$, non negative on $X$ and $\eta(x)>0$ for some $x \in X$. | |
| Aug 13, 2022 at 20:39 | comment | added | copper.hat | @Ypbor It took me a while to unravel. $Y$ is the span of $X$ so any functional that is zero on $X$ must be zero on $Y$. Since $\eta \ge 0$ on $X$, since it is non zero, it must be $>0$ somewhere on $X$. Note that $\cap_K \{ y \in Y | e_k (y) \ge 0 \} \subset \{ y \in Y | \eta(y) \ge 0 \}$ and taking the dual gives $\operatorname{sp} \{ \eta \} \subset +_k \operatorname{sp} \{ e_k \}$, so we can write $\eta = \sum_k \lambda_k e_k$ with $\lambda_k \ge 0$. | |
| Aug 13, 2022 at 14:30 | comment | added | Giorgio Metafune | @Ypbor If $\eta$ vanishes on $X$, then it vanishes on $Y$, while it is a non-zero functional. Then there is $x \in X$ such that $\eta(x)\neq 0$ and then $\eta (x)>0$ since $\eta \geq 0$ on $X$. | |
| Aug 13, 2022 at 11:12 | comment | added | Ypbor | @FedorPetrov Could you please elaborate on why $Y$ is the span of $X$ implies $\eta(x)>0$ for some $x$? I am sorry but it is nontrivial for me. | |
| Aug 13, 2022 at 7:56 | comment | added | Giorgio Metafune | @FedorPetrov Yes, true. I know also a proof by induction which is perhaps less evident, but closedness is crucial. By the way, I do not know an example in finite dimension where a positive functional defined on a subspace cannot be extended to the whole $R^d$ preserving positivity (positivity being defined with respect to a suitable cone $K$), do you? | |
| Aug 13, 2022 at 7:12 | comment | added | Fedor Petrov | @Ypbor $Y^*$ is a dual space of $Y$, so $\eta$ is a linear functional | |
| Aug 13, 2022 at 2:51 | comment | added | copper.hat | Took me a while. Simple, but rather subtle. | |
| Aug 12, 2022 at 23:43 | comment | added | Ypbor | @FedorPetrov What do you exactly mean by $\eta$ "$\in Y^*$" (is $Y^*$ a typo of $Y$)? I thought in my graph, $A \in Y$ but $l \notin Y$. | |
| Aug 12, 2022 at 18:20 | comment | added | Fedor Petrov | @Ypbor Ah, I want to separate by a linear hyperplane, not by affine. This is possible since one of two convex sets is a cone. | |
| Aug 12, 2022 at 16:19 | comment | added | Ypbor | @FedorPetrov If I understand your proof correctly, you apply the hyperplane separating theorem in $Y$. In my graph, $A$ (0-dimension) is a hyperplane in $Y$ (1-dimension), and it separates $C$ and $X$. But we eventually need a separating hyperplane in $\mathbb{R}^2$ (for example, the line $l$). I feel that the $\eta$ in your proof only specifies $A$ but not $l$? | |
| Aug 12, 2022 at 14:37 | comment | added | Fedor Petrov | any finitely generated cone is closed (it is a finite unit of cones generated by linearly independent subsets: if $g=c_1f_1+\ldots+c_kf_k\,(*)$ with all $c_1,\ldots,c_k$ positive, but $f_i$'s are linearly dependent, then adding this dependence with appropriate coefficient to $(*)$ you get a representation of $g$ with lesser number of f's.) | |
| Aug 12, 2022 at 14:21 | comment | added | Giorgio Metafune | @FedorPetrov I agree! Let me point out the fact that the cone generated by the $f_i$, $g=\sum_i c_i f_i, c_i \geq 0$ is closed. I would say that this is the main point (it is obviously closed if the vectors are independent on $Y$). | |
| Aug 12, 2022 at 13:23 | comment | added | Fedor Petrov | @GiorgioMetafune well, I use the fact: "Let linear functionals $f_1,\ldots,f_n, g$ on $Y$ be chosen so that whenever $x\in Y$ and $f_i(x)\geqslant 0$ for all $i$, then $g(x)\geqslant 0$. Then $g=\sum c_if_i$ for certain non-negative $c_i$'s." Proof: if not, $g$ does not belong to a cone generated by $f_i$'s, thus may be strictly separated from it by certain element $x\in Y^{**}=Y$. | |
| Aug 12, 2022 at 13:17 | comment | added | Fedor Petrov | @Ypbor on your graph $Y=l_1$ (a line), is not it? | |
| Aug 12, 2022 at 7:45 | comment | added | Giorgio Metafune | The argument is correct if you use the fact that any positive functional on $Y$ can be extended to the whole space preserving positivity, as in your first answer. I cannot fill the details in your last argument (which would give a simple proof of extendibility) | |
| Aug 12, 2022 at 7:45 | comment | added | Ypbor | @FedorPetrov Sorry but I still don't get the full dimension part. In my graph, for that $X$, $Y$ is actually $\mathbb{R}^2$. Take $l_1$ as your $\eta$, there is no $\eta(x)>0$. | |
| Aug 12, 2022 at 7:33 | comment | added | Fedor Petrov | @GiorgioMetafune is anything wrong with the argument in my answer? | |
| Aug 12, 2022 at 7:13 | comment | added | Giorgio Metafune | @copper.hat Saying that a positive functional on $Y$ is a linear combination of the coordinate functionals with positive coefficients, is equivalent to saying that it can be extended to a positive functional on $R^n$. This is true, see this old post mathoverflow.net/questions/370327/…. At the moment I do not see any convincing shortcut to the proof outlined above and I would be happy ho have a simpler one. | |
| Aug 12, 2022 at 4:55 | comment | added | Fedor Petrov | @copper.hat on $Y$ every functional may be represented as a non-negative linear combination of $x_1$ and $x_2$. | |
| Aug 12, 2022 at 4:17 | comment | added | Kroki | Wait in $Y$ you can not have both $x_1$ and $x_2$ non negative. The statement is always true. | |
| Aug 12, 2022 at 4:15 | comment | added | copper.hat | @Youem I understand that, but regardless of the representation of $\eta$, if $x_2>0$ then $\eta(x)<0$, so I do not follow the last paragraph in the answer. | |
| Aug 12, 2022 at 4:10 | comment | added | Kroki | @copper.hat On $Y$, $\eta(x) = x_1-x_2$ is the same as $2x_1$, since $x_1+x_2=0$ | |
| Aug 12, 2022 at 4:05 | comment | added | copper.hat | @FedorPetrov The last paragraph is a little glib for me. I wonder could you elaborate or point me somewhere please? If you take $n=2$, $X= \{ x\mid x_1+x_2 = 0, x_1>0 \}$ then $C=\{0\}$ and the functional $\eta:Y \to \mathbb{R}$ given by $\eta(x)= x_1-x_2$ separates $C$ and $X$. If the coordinate function $x \mapsto x_2$ is positive (on $Y$) then $\eta(x) < 0$. I presume I am missing something. | |
| Aug 11, 2022 at 9:40 | comment | added | Fedor Petrov | "Full dimension" here means that span of $X$ is $Y$, thus any non-zero functional on $Y$ can not vanish on $X$. | |
| Aug 11, 2022 at 9:29 | comment | added | Ypbor | Thanks for answering. Why is $X$ of full dimension in $Y$? Consider the case of $n=2$. Suppose $X$ is a line segment. Then $Y=\mathbb{R}^2$ but $X$ is not of full dimension in $Y$. | |
| Aug 10, 2022 at 14:48 | history | edited | Fedor Petrov | CC BY-SA 4.0 |
added 215 characters in body
|
| Aug 10, 2022 at 14:42 | comment | added | Fedor Petrov | oh, you are correct. Let's say differently: the coordinate functionals $x\to x_i$ and the functional $\eta$ on $Y$ satisfy the property "if $x_i$'s are non-negative, then $\eta$ is non-negative". It yields by duality that $\eta$ belongs to a cone generated by $x_i$'s. | |
| Aug 10, 2022 at 6:25 | comment | added | Wlod AA | It feels to me that you are right. (feelings as in a disco 80's song :) ). I'll still need to think a bit more about it. | |
| Aug 10, 2022 at 6:17 | comment | added | Fedor Petrov | @WlodAA $Y$ is used to find a point $x\in X$ in which $\eta(x)\ne 0$ | |
| Aug 10, 2022 at 6:15 | comment | added | Wlod AA | Fedor, what do you need $\ Y\ $ for? (It feels unnecessary to me to introduce it; right away, $\ \mathbb R^n\ $ instead of $\ Y\ $ would do fine)? | |
| Aug 10, 2022 at 4:15 | history | answered | Fedor Petrov | CC BY-SA 4.0 |