I am following along Stephen Boyd's lectures on convex optimization and am having trouble understanding the diagram in this screenshot.

I have read through a few answers such as this one and this one.

My question is I am having trouble understanding why $$a^Tx = b$$ implies that a and x are perpendicular.

One way I understood it, following this post's answer is $$a^Tx = b \implies a^T x - a^T x_b = 0 $$ for some $x_b$ and so $a^T (x - x_b) = 0$. I understand why $a$ will be perpendicular to $x - x_b$ but am having trouble seeing why $a$ will be perpendicular to $x$.

One way I think about it is $x_b$ is a particular solution to the equation $a^Tx = b$ and since this is a linear program, any $a' = ka$ and $x' = x_b/k$ for non-zero $k$ will solve for $a'^T x' = b$. Hence, $x_b$ is just one of the solutions, and the other solutions are of the form $x_b/ k$, for non-zero $k$. Note, the other solutions are all parallel to $x_b$ and I think the linear combination of parallel lines is parallel to any of of them.

Hence, since $x$ and $x_b$ are parallel, $x - x_b$ is parallel to $x$ and so $a^T$ which is perpendicular to $x - x_b$ is perpendicular to $x$.

However, I'm having trouble seeing this for fixed $a$. In particular, is $a$ fixed?


The diagram in the screenshot is not showing that $a$ and $x$ are perpendicular. Indeed, by definition two vectors are perpendicular (aka orthogonal) iff their dot product is zero. Rather, it is showing that if $x_0$ satisfies $a^\top x_0 =b$, then every element $y$ in the hyperplane $H = \{y: a^\top y = b\}$ may be written in the form $y = x_0 + x$, where $a^\top x = 0$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.