0
$\begingroup$

I am trying to solve the following problem: Consider the polyhedron $P = \{x\in \mathbb{R}^3 \mid x_1 + x_2 + x_3 \geq 1, x_j \geq 0 \; j \in [3] \}$. The polar of a set $S$ is defined as $S^* := \{y\mid y^T x \leq 1 \; \forall x\in S\}$. Construct $(P^*)^*$.

What I did was to first find the extreme points and extreme rays of $P$, which are $\{e_i, \; i=1, 2, 3 \}$ for both the extreme points and extreme rays. Then I used the resolution theorem with the set of extreme points/rays I found to conclude that $P^*$ is the negative orthant of $\mathbb{R}^3$. Namely, that $P^* = \{y\in\mathbb{R}^3 \mid y_1 \leq 0, y_2 \leq 0, y_3 \leq 0 \}$. Then I realized that the only extreme point of $P^*$ is just the origin $(0, 0, 0)$, and the extreme rays are $(-1, 0, 0), (0, -1, 0), (0, 0, -1)$. Then I used the resolution theorem again to conclude that $(P^*)^* = \{z\in\mathbb{R}^3 \mid z_1 \geq -1, z_2 \geq -1, z_3 \geq -1 \}$.

Was there a better way to do this (assuming my answer is even correct)?

$\endgroup$

1 Answer 1

0
$\begingroup$

Well, but what is had for $(P^*)^*$ in the OP is incorrect though. [You may want to precisely state both the conditions and the conclusions of the resolution theorem.] You did conclude correctly that $P^*$ is indeed the set defined $$P^* = \{y \in \mathbb{R}^3; y = (y_1,y_2,y_3), {\text{ with }} y_1,y_2,y_3 \le 0\}.$$ The mistake was in calculating $(P^*)^*$.

In particular: You can check directly that, on the one hand, for any $x \in \mathbb{R}^3$ that has a negative coordinate, that there is a $y \in P^*$ such that $x^Ty>1$. Indeed, suppose $x= (a_1,a_2,a_3)$ is such that $x$ has a negative coordinate, or equivalently, there is an $i \in \{1,2,3\}$ such that $a_i$ is negative. Then let $y$ be any vector in $P^*$ such that the $i$-th coordinate of $y$ is $\frac{2}{a_i}$ [also a negative number], and every other coordinate of $y$ is $0$. Then $x^Ty= \frac{2}{a_i} \times a_i = 2$. So indeed, for any $x \in \mathbb{R}^3$ that has a negative coordinate, that there is a $y \in P^*$ such that $x^Ty>1$. Thus, if an $x \in \mathbb{R}^3$ that has a negative coordinate, then $x$ cannot be in $(P^*)^*$. So on the one hand, $(P^*)^*$ must be a subset of $\{x \in \mathbb{R}^3$; $x = (x_1,x_2,x_3)$, with $x_1,x_2,x_3 \ge 0\}$.

On the other hand, if every coordinate of $x \in \mathbb{R}^3$ is nonegative, then $x^Ty \le 0$ for all $y \in P^*$, so $x$ must be in $(P^*)^*$. So on the other hand, $(P^*)^*$ must contain $\{x \in \mathbb{R}^3$; $x = (x_1,x_2,x_3)$ with $x_1,x_2,x_3 \ge 0\}$.

From these two paragraphs you can conclude that

$$(P^*)^* = \{x \in \mathbb{R}^3; x = (x_1,x_2,x_3), {\text{ with }} x_1,x_2,x_3 \ge 0\}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .