# How to determine cuts for convex Hull

 0 Suppose I have two polyhedrons given as $$A_1 x \le b_1$$ And $$A_2 x \le b_2$$ Whereas ( A_1, A_2) are real matrices, (x \in \Bbb{R}^n ) and ( b_1,b_2 ) have the vertical dimension as(A_1,A_2 ) respectively. The question is how do I generate the matrix and vector ( A_3, b_3 ) such that $$A_3 x \le b_3$$ Is the minimal convex hull containing the two aforementioned polyhedrons? asked 20 Aug '15, 22:34 frogeyedpeas 15●4 accept rate: 0%

 3 There is an extended formulation for the convex hull of the union of (bounded) polytopes. You can look at the paper "Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems" by Egon Balas (1984). But it is actually straightforward: You create copies $$x_1, x_2$$ of your variables $$x$$ for each polytope and add the equation $$x = x_1 + x_2$$. You also add variables $$y_1, y_2 \in [0, 1]$$ with $$y_1 + y_2 = 1$$. Then you restrict your copies of variables: $$A_1 x_1 \le b_1 y_1, \quad A_2 x_2 \le b_2 y_2$$. The $$x$$ are now in effect a convex combination of points that live in the respective polytopes. There is also a version for unbounded polyhedra, but it will you give to the (topological) closure of the union, which might be open. If you don't want to add extra variables, you can try to eliminate them by Fourier-Motzkin. This has worked very well for me, when the dimension of $$x$$ is small. answered 21 Aug '15, 11:17 rschwarz 366●2●11 accept rate: 21%
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: