0

In Convex Optimization by Boyd and Vandenberghe, I don't understand how the formulation for Example 2.9 works.

Example 2.9: Polyhedron. The polyhedron $ \{ x | Ax \preceq b, Cx=d \}$ can be expressed as the inverse image of the Cartesian product of the nonnegative orthant and the origin under the affine function $f(x) = (b-Ax, d-Cx)$ $$ \{ x | Ax \preceq b, Cx=d \} = \{ x | f(x) \in \mathbb{R}^m_+ \times \{0\} \} $$

If I understand correctly, $\mathbb{R}^m \times \{ 0 \}$ looks something like $(x,y,0)$ if $m=2$.

I'm assuming that $Cx=d$ is reformatted to $d-Cx=0$, which can represented matrix-wise as $[d-Cx | 0]$, which kind of makes sense to me.

How then, does $b-Ax \succeq 0$ work? Since $b-Ax$ produces a vector, would this be vector based (component-wise inequality) comparison and not positive semidefinite? How do you represent that in the form of $f(x)=(z_1,...,z_m,0)$?

And how does the original equation represent both inequalities at the same time? I suspect that I'm missing some background/definitions with notation.

iquitgame
  • 1
  • The notation $x \preceq y$ is equivalent to $x_k \le y_k$ for all $k$. I prefer to write $x \le y$ for componentwise inequalities. The non negative orthant is $Q={ x \in \mathbb{R}^n \mid x_k \ge 0}$. $Ax \le b$ iff $b-Ax \ge 0$ iff $b-Ax \in Q$. $Cx=d$ iff $d=Cx$ iff $d-Cx\in {0}$. Hence $x$ satisfies $Ax \le b$ and $Cx=d$ iff $f(x) \in Q \times {0}$. – copper.hat Jan 13 '24 at 01:25
  • 1
    Oh I had forgotten that the nonnegative orphan can be written as $\mathbb{R}^m_+$, and I was misunderstanding the role of the affine function as a result. This clears everything up. Thank you! – iquitgame Jan 13 '24 at 01:51

0 Answers0