cvxbook-solutions exercise page-5 exercise 2.8(a)
2.8(a)
$S = \{y_1a_1 + y_2a_2 | − 1 ≤ y_1 ≤ 1, − 1 ≤ y_2 ≤ 1\}, \text{where }a_1, a_2 ∈ R^n$.
The following is the solution mixed with my question.
S is a polyhedron. It is the parallelogram with corners $a_1 + a_2, a_1 − a_2, −a_1 + a_2, −a_1 − a_2$, as shown below for an example in $R^2$.
For simplicity we assume that $a_1$ and $a_2$ are independent. We can express S as the intersection of three sets:
• $S_1$: the plane defined by $a_1$ and $a_2$
• $S_2 = \{z+y_1a_1 + y_2a_2 \,|\, a^T_1 z = a^T_2 z=0,-1≤ y_1 ≤1\}$. This is a slab parallel to $a_2$ and orthogonal to $S_1$
here,my first question is that what z is,one vector? but as we know that there are total n-2 independent vectors ($v_1$,...,$v_{n-2}$ )that are orthogonal to $a_1$ and $a_2$ (which form a basis for the nullspace of the matrix $[a_1 \, a_2]^T$)
here,my second question what's the value of $y_2$, is a constant or a variable ? If there are total two variable $y_1$ and $y_2$ at most, how could it represent a slab, I think it should have three variable in $R^3$
• $S_3 = \{z+y_1a_1 + y_2a_2 \,|\, a^T_1 z = a^T_2 z=0,-1≤ y_2 ≤1\}$. This is a slab parallel to $a_1$ and orthogonal to $S_1$
Each of these sets can be described with linear inequalities.
• $S_1$ can be described as
$$v^T_kx=0,\;k=1,...,n-2$$
where $v_k$ are n−2 independent vectors that are orthogonal to $a_1$ and $a_2$ (which form a basis for the nullspace of the matrix $[a_1 \, a_2]^T$)
• Let $c_1$ be a vector in the plane defined by $a_1$ and $a_2$, and orthogonal to $a_2$. For example, we can take
$$c_1=a_1 - \frac{a^T_1 a_2}{||a_2||^2_2}a_2$$
Then $x \in S_2$ if and only if
$$-|c^T_1 a_1| \le c^T_1 x \le |c^T_1 a_1|$$
• Similarly, let c2 be a vector in the plane defined by a1 and a2, and orthogonal to a1, e.g.,
$$c_2=a_2 - \frac{a^T_2 a_1}{||a_1||^2_2}a_1$$
Then $x \in S_3$ if and only if $$-|c^T_2 a_2| \le c^T_2 x \le |c^T_2 a_2|$$
Putting it all together, we can describe S as the solution set of $2n$ linear inequalities
$$\;v^T_kx \le 0, \; k=1,...,n-2$$ $$-v^T_kx \le 0, \; k=1,...,n-2$$ $$\;c^T_1 x \le |c^T_1 a_1|$$ $$-c^T_1 x \le |c^T_1 a_1|$$ $$\;c^T_2 x \le |c^T_2 a_2|$$ $$-c^T_2 x \le |c^T_2 a_2|$$
my third question what if $S = \{y_1a_1 + y_2a_2 + y_3a_3 \;|\; − 1 ≤ y_1 ≤ 1, − 1 ≤ y_2 ≤ 1, − 1 ≤ y_3 ≤ 1\}$,where $a_1, a_2, a_3 \in R^n$. How to express it in the form S = {x | Ax<=b, Fx = g} ,I could find the all $v_k$ that are n−3 independent vectors that are orthogonal to $a_1$, $a_2$ and $a_3$ (which form a basis for the nullspace of the matrix $[a_1 \, a_2\, a_3]^T$), how to get the counterparts of $c_1$, $c_2$, $c_3$, if you give the final solution I will be grateful.
This is my second time to try to read convex optimization book, the first four chapter still confuses me a lot, I always feel there are key points I could not get. Is there any a more introductory reading material?