Skip to main content
rectified the decomposition (*) into a more meaningful one
Source Link
Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70

An obvious route to a proof of 6 would be showing that conv($P\otimes Q$) decomposes as $$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}(P_c\otimes Q_c)+\mathrm{conv}(P_\ell\otimes Q_\ell)\qquad (*)$$$$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}((P_p+P_c)\otimes Q_c+P_c\otimes (Q_p+Q_c))+\mathrm{conv}(P\otimes Q_\ell+P_\ell\otimes Q)\qquad (*)$$ where $P=P_p+P_c+P_\ell$, for $P_p$ a polytope, $P_c$ a pointed cone, and $P_\ell$ a linear subspace, and $Q=Q_p+Q_c+Q_\ell$ a similar decomposition for $Q$. You have mentioned that $\mathrm{conv}(P_p\otimes Q_p)$ is a polytope, and I think a proof of this should be easily adaptable to showing that the second $\mathrm{conv}(P_c\otimes Q_c)$$\mathrm{conv}(...)$ is a polyhedral cone. And the third $\mathrm{conv}(P_\ell\otimes Q_\ell)$$\mathrm{conv}(...)$ is linear subspace. Hence $(*)$ would imply that conv($P\otimes Q$)$\mathrm{conv}(P\otimes Q)$ is a polyhedron.

The hard part seems to be showing $(*)$. Any closed convex set $C$ in $\mathbb{R}^m$ has a decomposition into the sum of a convex set $C'$ which does not contain straight lines, and a subspace $C_\ell$, with $C'$ contained in the orthogonal complement of $C_\ell$, so this boils down to identifying $C'$ with $\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}(P_c\otimes Q_c)$the sum of the first two conv(...), and $C_\ell$ with $\mathrm{conv}(P_\ell\otimes Q_\ell)$the third conv(...).

An obvious route to a proof of 6 would be showing that conv($P\otimes Q$) decomposes as $$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}(P_c\otimes Q_c)+\mathrm{conv}(P_\ell\otimes Q_\ell)\qquad (*)$$ where $P=P_p+P_c+P_\ell$, for $P_p$ a polytope, $P_c$ a pointed cone, and $P_\ell$ a linear subspace, and $Q=Q_p+Q_c+Q_\ell$ a similar decomposition for $Q$. You have mentioned that $\mathrm{conv}(P_p\otimes Q_p)$ is a polytope, and I think a proof of this should be easily adaptable to showing that $\mathrm{conv}(P_c\otimes Q_c)$ is a polyhedral cone. And $\mathrm{conv}(P_\ell\otimes Q_\ell)$ is linear subspace. Hence $(*)$ would imply that conv($P\otimes Q$) is a polyhedron.

The hard part seems to be showing $(*)$. Any closed convex set $C$ in $\mathbb{R}^m$ has a decomposition into the sum of a convex set $C'$ which does not contain straight lines, and a subspace $C_\ell$, with $C'$ contained in the orthogonal complement of $C_\ell$, so this boils down to identifying $C'$ with $\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}(P_c\otimes Q_c)$ and $C_\ell$ with $\mathrm{conv}(P_\ell\otimes Q_\ell)$.

An obvious route to a proof of 6 would be showing that conv($P\otimes Q$) decomposes as $$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}((P_p+P_c)\otimes Q_c+P_c\otimes (Q_p+Q_c))+\mathrm{conv}(P\otimes Q_\ell+P_\ell\otimes Q)\qquad (*)$$ where $P=P_p+P_c+P_\ell$, for $P_p$ a polytope, $P_c$ a pointed cone, and $P_\ell$ a linear subspace, and $Q=Q_p+Q_c+Q_\ell$ a similar decomposition for $Q$. You have mentioned that $\mathrm{conv}(P_p\otimes Q_p)$ is a polytope, and I think a proof of this should be easily adaptable to showing that the second $\mathrm{conv}(...)$ is a polyhedral cone. And the third $\mathrm{conv}(...)$ is linear subspace. Hence $(*)$ would imply that $\mathrm{conv}(P\otimes Q)$ is a polyhedron.

The hard part seems to be showing $(*)$. Any closed convex set $C$ in $\mathbb{R}^m$ has a decomposition into the sum of a convex set $C'$ which does not contain straight lines, and a subspace $C_\ell$, with $C'$ contained in the orthogonal complement of $C_\ell$, so this boils down to identifying $C'$ with the sum of the first two conv(...), and $C_\ell$ with the third conv(...).

Source Link
Dima Pasechnik
  • 14k
  • 2
  • 34
  • 70

An obvious route to a proof of 6 would be showing that conv($P\otimes Q$) decomposes as $$\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}(P_c\otimes Q_c)+\mathrm{conv}(P_\ell\otimes Q_\ell)\qquad (*)$$ where $P=P_p+P_c+P_\ell$, for $P_p$ a polytope, $P_c$ a pointed cone, and $P_\ell$ a linear subspace, and $Q=Q_p+Q_c+Q_\ell$ a similar decomposition for $Q$. You have mentioned that $\mathrm{conv}(P_p\otimes Q_p)$ is a polytope, and I think a proof of this should be easily adaptable to showing that $\mathrm{conv}(P_c\otimes Q_c)$ is a polyhedral cone. And $\mathrm{conv}(P_\ell\otimes Q_\ell)$ is linear subspace. Hence $(*)$ would imply that conv($P\otimes Q$) is a polyhedron.

The hard part seems to be showing $(*)$. Any closed convex set $C$ in $\mathbb{R}^m$ has a decomposition into the sum of a convex set $C'$ which does not contain straight lines, and a subspace $C_\ell$, with $C'$ contained in the orthogonal complement of $C_\ell$, so this boils down to identifying $C'$ with $\mathrm{conv}(P_p\otimes Q_p)+\mathrm{conv}(P_c\otimes Q_c)$ and $C_\ell$ with $\mathrm{conv}(P_\ell\otimes Q_\ell)$.