Timeline for Confining a polytope to one side of an affine hyperplane
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 12, 2021 at 11:18 | comment | added | Dima Pasechnik | Please see my other answer, which gives a full answer to your question (yes, the inequality holds, but it's not easy to prove). | |
| Mar 10, 2021 at 1:28 | vote | accept | Hans | ||
| Mar 10, 2021 at 3:31 | |||||
| Mar 9, 2021 at 20:16 | comment | added | Hans | Like I said before, I do very much appreciate your illuminating as evidenced by my upvoting of your answer. However, due to my obtuseness, from the very beginning I am blind to the route leading from your result to the desired relations in the question. The $b′\ge \lambda^Tb$ vs $b′=\lambda^Tb$ is not my worry. I have detailed the current status of the solution in an answer box and stated where I have gotten stuck. Please review and I would very much appreciate it if you would let me know exactly what I have missed. | |
| Mar 9, 2021 at 9:57 | comment | added | Dima Pasechnik | perhaps you wonder why there is $\geq$ in $b'\geq\lambda^\top b$, and not $=$. That's because increasing $b'$ for a fixed $a'$ makes the inequality weaker, and indeed there is minimal $b'$ so that the inequality is still valid (and that's exactly where $b'=\lambda^\top b$ would hold). | |
| Mar 9, 2021 at 9:45 | comment | added | Dima Pasechnik | Proved, naturally, and please note I am not oblidged to provide you more details - it's a research maths forum, not undergraduate maths forum. The whole question ought to be closed as being out of scope. | |
| Mar 9, 2021 at 1:28 | comment | added | Hans | I do not understand what you are claiming. Are you claiming you have proved or disproved the original proposition? It appears that the above answer, which I have upvoted for its illuminating idea, has achieved neither. If you do not agree, could you please present the detailed proof or a counterexample? | |
| Mar 8, 2021 at 20:24 | comment | added | Dima Pasechnik | Other than dealing with non-full-dimensional case (just restrict to the affine span of $P$) it looks as if we're done. | |
| Mar 6, 2021 at 23:12 | comment | added | Hans | +1 for the great idea! But is it fair to say we have not proved or disproved the original proposition? | |
| Mar 6, 2021 at 20:49 | comment | added | Hans | Let us continue this discussion in chat. | |
| Mar 6, 2021 at 20:28 | comment | added | Dima Pasechnik | there is no $b$ any more. All the b's are now 1. | |
| Mar 6, 2021 at 20:22 | comment | added | Hans | You misunderstood my question. I knew how to prove your claim that $\frac{a'}{b'}\in P^*$ as I have stated in my first comment. I am asking how you would prove $b'>\lambda b$ for some $\lambda>0$ as posited in the original question. I do not see yet how that is derived from $\frac{a'}{b'}\in P^*$ | |
| Mar 6, 2021 at 10:17 | comment | added | Dima Pasechnik | P* is a polytope, and so each point $a$ (ie an inequality $<a,x>\leq 1$ ) in P* can be expressed as $\lambda A$ for $\lambda \geq 0$, $\sum \lambda_k=1$. For each point $a$ outside, there will be a separating hyperplane, which, in case of P*, is just $z \in P$ s.t. $<a,z> >1$. | |
| Mar 6, 2021 at 0:38 | comment | added | Hans | Let us say $b'$ or $\beta>0$ so that $b'^{-1}a'^Tx\le1$. How do we argue for the desired relation? | |
| Mar 6, 2021 at 0:28 | comment | added | Dima Pasechnik | if your a'x<b' cannot be normalised so that b'=1 then it is not valid (check for x=0). | |
| Mar 5, 2021 at 22:05 | comment | added | Hans | Cool! I see that when the origin is in the interior of the convex hull $P*$ of the rows of the $A$ scaled as you described, called $A'$, $\beta^-1a' = u^T A'$ where $u\ge0$ and $u^T\mathbf 1=1$. But how does one proceed to show the two desired relations from here, especially the second one? | |
| Mar 5, 2021 at 10:58 | history | answered | Dima Pasechnik | CC BY-SA 4.0 |