0

I need some help with convex polyhedrons. First of all, I will write my definition of "convex polyhedrons", since Im not sure about translating this term into English (you can edit the name if you find out what it is).

Convex polyhedron: $X = \{ x \in R^n | a_i^Tx \geq b_i, i = 1, \dots, m \} = \{ x \in R^n | Ax \geq b \}$ / hence its intersection of finite number halfspaces...

Now back to mz question? Are these sets convex polyhedrons? Can you write them as $\{ x \in R^n | Ax \geq b \}$?

a) $X = \{2y_1 + 3y_2 | -1 \leq y_1 \leq 1, 1 \leq y_1 \leq 1\}$

It obvisously IS a convex polyhedron (Its a 2D hyperspace in 3D limited by 4 halspaces). Im not sure, however, how to formulate it as $\{ x \in R^n | Ax \geq b \}$.

a) $X = \{x \in R^n | x \geq 0, 1^Tx = 1, \sum a_ix_i = b_1, \sum a_i^2x_i = b_2 \}$, where $b_1, b_2, a_i \in R$.

I think, that this is not a convex polyhedron because of the quadratic condition but Im not sure....

Thanks for any help!

Smajl
  • 686

1 Answers1

1

a. Do you mean collection of all $(y_1,y_2,y_3)$ such that $y_3 = 2y_1 + 3y_2$? Then you can write your polyhedron in $Ax \leq b$ form by breaking that equality into two inequalities. $$ y_3 \leq y_1 + y_2 $$ $$ y_3 \geq y_1+y_2 $$ $$ -1 \leq y_1 \leq 1 $$ $$ -1 \leq y_2 \leq 1 $$

b. Conditions are still linear in terms of the variables $x_i$. The quadratic factors $a_i^2$ are just some constants. It can again be put in $Ax \leq b$ form by replacing equalities by pairs of inequalities.

polkjh
  • 1,432