I am faced with this problem:
$P=\{x\in R^n| x\ge 0, x^Ty\le 1$for all $y$ with $||y||_2=1\}$
Is $P$ a polyhedron?
I said yes, for the following reasoning:
Since the definition of a polyhedron is $P=\{x\in R^n|A^Tx\le b, Fx=g\}$, I can put it into that form above like this:
- First of all, by squaring both sides of $||y||_2=1$ we can get $||y||_2^2=1$ so that $\Sigma y_i^2=1$
- Then I can form matrices for all of the restrictions like so:
$A=[diag(-1);y^T]$
(this is the concatenation of a diagonal matrix of -1's and then the vector $y$ on the bottom. Multiplying this with the $x$ vector seems to satisfy the inequality from what i can tel $Ax \le b$
And for the equality constraint we can write $y^Ty=1$
This seems to make it a polyhedron...but apparently the TA says that this is incorrect because it requires an intersection between infinitely many halfspaces.
But, seemsto me like I formulated it correctly above. Can someone please correct me?
EDIT $P$ is the intersection of the unit ball and the nonnegative orthant $R_+^n$.
"Then I can form matrices for all of the restrictions ..."
You then proceed to show how you can enforce the restriction $x^Ty \leq 1$ for one particular value of $y$ such that $\lVert y \rVert_2 = 1.$ But there are infinitely many values of $y$ such that $\lVert y \rVert_2 = 1.$ To form matrices for all of the restrictions, do you intend to form infinitely many matrices? (Not just infinitely many, by the way; there are an uncountable number of solutions to $\lVert y \rVert_2 = 1.$)
The edit to the question makes this even clearer: you are aware that the unit sphere in $R^n$ provides part of the boundary of the set you are trying to delimit. For example, for $n = 2$ you are looking at a right-angled pie-slice of the unit disk, bounded by two segments and a $\frac\pi2$-radian arc. Intuitively, you should know that this is not a polygon.
Postscript: The derivation actually goes off the rails sooner than I indicated above. The formula for a polyhedron that you are attempting to invoke is specified by one matrix. A different matrix gives you a different polyhedron. As soon as you wrote "matrices" while still trying to show that the single figure in the exercise is a polyhedron, you were no longer using that formula for a polyhedron.