Consider the set
$$\{ x \in \mathbb{R}^n \mid x_1 = \cdots = x_{n-1}=0, 0 \le x_n \le 1 \}$$
Could this be the feasible set of a problem in standard form?
I'm leaning towards no, but I am unsure how to prove this.
$\endgroup$ 12 Answers
$\begingroup$I'm assuming that the standard form of a constraint set is a collection of inequalities $a_1^Tx \le c_1, ..., a_m^Tx \le c_m$. In this case, yes, this set can be written in standard form.
The constraint $x_i = 0$ can be written as the equation $e_i^Tx = 0$ where $e_i$ is the $i^{th}$ standard basis vector, $e_1 = (0, ..., 1, ..., 0)^T$ where the $1$ is in the $i^{th}$ position. An equation can always be written as two inequalities, $e_i^Tx \ge 0$, $e_i^Tx \le 0$, or equivalently $-e_i^Tx \le 0, e_i^Tx \le 0.$
For the last inequalities: they are $e_n^T \ge 0$ and $e_n^T \le 1$, or equivalently $-e_n^T \le 0$ and $e_n^T \le 1.$
$\endgroup$ $\begingroup$No.
Assume $Q$ can be represented in $\{x \mid Ax = b, x \geq 0\}$. We know $\boldsymbol{0} \in Q$, thus $b=\boldsymbol{0}$.
Let $A = [A_1, \dots, A_n]$, then $Q = \{x \mid x_1 A_1 + \dots + x_n A_n = \boldsymbol{0}, x \geq 0\}$. Since $[0, \dots, 1] \in Q$, $\;A_n = \boldsymbol{0}$ must hold.
However, in this situation, $[0, \dots, 2] \in Q$, which is a contradiction.
$\endgroup$
