0

I am having difficulty with the following question. Let $P_n = \{x\in\mathbb{R}^n \; : \; |x_i| \leq 1, i\leq n, \sum_i |x_i| \leq 2 \}$. Build an explicit polyhedral representation of $P_n$ that is linear. That is, a representation of form $P_n = \{x\in\mathbb{R}^n : \exists u\in\mathbb{R}^m \text{ s.t. } Ax + Bu \leq c \}$, where $dim(u)$ and $dim(c)$ are linear in $n$ (also $A, B, c, m$ can depend on $n$).

I have a lot of difficulty with questions asking to building explicit polyhedral representations in general. I think I would see how to do these types of questions in general if I saw how specifically to build a polyhedral representation in this case.

RobPratt
  • 45,619
graphtheory123
  • 370
  • What kind(s) of objects are $A$ and $B$ supposed to be? $c$ is a real number? – Gerry Myerson Apr 09 '22 at 04:00
  • @GerryMyerson $A$ and $B$ are real matrices, and $c$ is a real vector. – RobPratt Apr 09 '22 at 13:00
  • @Rob, OK, then what's the meaning of $Ax+Bu\le c$? – Gerry Myerson Apr 09 '22 at 13:20
  • @GerryMyerson Let $d=\dim(c)$. Then we have matrix-vector multiplication $A_{d \times n} x_{n \times 1} + B_{d \times m} u_{m \times 1} \le c_{d \times 1}$. That is, $d$ linear inequality constraints with variables $x\in\mathbb{R}^n$ and $u\in \mathbb{R}^m$. – RobPratt Apr 09 '22 at 14:35
  • @Rob, OK, so it means each component of the vector on the left is no greater than the corresponding component of the vector on the right. – Gerry Myerson Apr 09 '22 at 22:44

1 Answers1

1

In other words, you want to linearize the absolute values. Introduce variable $u_i$ to represent $|x_i|$. The desired linear constraints in $x$ and $u$ are \begin{align} x_i - u_i &\le 0 \tag1 \\ -x_i - u_i &\le 0 \tag2 \\ u_i &\le 1 \tag3 \\ \sum_i u_i &\le 2 \tag4 \end{align} Constraints $(1)$ and $(2)$ enforce $|x_i| \le u_i$. Constraint $(3)$ enforces $|x_i| \le 1$. Constraint $(4)$ enforces $\sum_i |x_i| \le 2$.

RobPratt
  • 45,619
  • This makes a lot of sense, thank you. One question: When one is trying to create a polyhedral representation, does one usually make the "$u$" stand in for a "special function" (like the absolute value function)? – graphtheory123 Apr 09 '22 at 19:14
  • Yes, the additional variables often represent some nonlinear function of the original variables. Glad to help. Please mark my answer as accepted. – RobPratt Apr 09 '22 at 20:16