<p>I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a_i \cdot x \le c_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers.  In other words,</p>

<p>$$\mathcal{P} = \{x \in \mathbb{R}^d : \forall i . a_i \cdot x \le c_i, \forall j . x_j \ge 0\},$$</p>

<p>where $a_1,\dots,a_n \in \mathbb{R}^d$ and $c_1,\dots,c_n$ are given.</p>

<p>I'm given $m$, where $m &lt; n$.  I want to find a new convex polyhedron $\mathcal{Q}$ defined by $m$ linear inequalities, so that $\mathcal{Q}$ is contained within $\mathcal{P}$.  In other words, I want to find $b_1,\dots,b_m \in \mathbb{R}^d$ and $d_1,\dots,d_n$ such that the convex polyhedron</p>

<p>$$\mathcal{Q} = \{x \in \mathbb{R}^d : \forall i . b_i \cdot x \le d_i, \forall j . x_j \ge 0\}$$</p>

<p>is wholly contained within $\mathcal{P}$ ($\mathcal{Q} \subseteq \mathcal{P}$).</p>

<p>So far, this is easy, but there is an objective function I am trying to minimize.  Fix vectors $\mu,\sigma \in \mathbb{R}^d$.  Let $X$ be a random variable over $\mathbb{R}^d$, where the $i$th component $X_i$ of $X$ has a $\mathcal{N}(\mu_i,\sigma_i^2)$ distribution, and where the $X_i$'s are mutually independent.  The "badness" of $\mathcal{Q}$ is given by $\Pr[X \in \mathcal{Q} \setminus \mathcal{P}]$.</p>

<p>My goal: given $\mathcal{P}$ and $m,\mu,\sigma$, find a convex polyedron $\mathcal{Q}$ defined by $m$ linear inequalities that is contained within $\mathcal{P}$ and whose "badness" is as small as possible.</p>

<p>If there is no efficient solution to this optimization problem, I would be happy with an approximation algorithm or a heuristic.  In my application, I would expect to have $m,n \le 50$ or so (perhaps even smaller), but $d$ is large (say $d \approx 10^4$ or so).  Also, if a solution for the general problem is too hard, I would be satisfied with a solution for the special case where we are guaranteed that $a_i,c_i$ are all $\ge 0$.</p>

<p>Can you suggest any methods that might be effective for this problem?</p>

CC BY-SA 3.0
2013-12-16T01:29:33.563Z
do you want to stipulate that $a_i, c_i\ge 0$?  If not, then $\cal Q$ might not exist.  E.g. using $n=2k$, take ${\cal P} = {\mathbb R}_+^d \cap \{x : \forall i\in \{1,\ldots,k\}.  x_i = 1\}$.  If $m<n$, then maybe no such (non-empty) $\cal Q$ is contained in $\cal P$?
Neal Young
CC BY-SA 3.0
2013-12-16T01:35:19.263Z
Thanks, @NealYoung, those are excellent points.  I appreciate your careful review.  I would be fine with a stipulation that $a_i,c_i \ge 0$; in the application I have in mind, that is usually the case.  I've updated the question accordingly.
D.W.
<cg.comp-geom><approximation-algorithms><linear-programming><convex-geometry><high-dimensional-geometry>
Approximating a convex polyhedron, with fewer inequalities
D.W.
# Approximating a convex polyhedron, with fewer inequalities

(Asked by: username_0 on 2013-12-15)

I have a convex polyhedron $\mathcal{P}$, given by $n$ linear inequalities $a\_i \cdot x \le c\_i$ where $x$ is a $d$-dimensional vector over the non-negative real numbers. In other words,

$$\mathcal{P} = \{x \in \mathbb{R}^d : \forall i . a\_i \cdot x \le c\_i, \forall j . x\_j \ge 0\},$$

where $a\_1,\dots,a\_n \in \mathbb{R}^d$ and $c\_1,\dots,c\_n$ are given.

I'm given $m$, where $m < n$. I want to find a new convex polyhedron $\mathcal{Q}$ defined by $m$ linear inequalities, so that $\mathcal{Q}$ is contained within $\mathcal{P}$. In other words, I want to find $b\_1,\dots,b\_m \in \mathbb{R}^d$ and $d\_1,\dots,d\_n$ such that the convex polyhedron

$$\mathcal{Q} = \{x \in \mathbb{R}^d : \forall i . b\_i \cdot x \le d\_i, \forall j . x\_j \ge 0\}$$

is wholly contained within $\mathcal{P}$ ($\mathcal{Q} \subseteq \mathcal{P}$).

So far, this is easy, but there is an objective function I am trying to minimize. Fix vectors $\mu,\sigma \in \mathbb{R}^d$. Let $X$ be a random variable over $\mathbb{R}^d$, where the $i$th component $X\_i$ of $X$ has a $\mathcal{N}(\mu\_i,\sigma\_i^2)$ distribution, and where the $X\_i$'s are mutually independent. The "badness" of $\mathcal{Q}$ is given by $\Pr[X \in \mathcal{Q} \setminus \mathcal{P}]$.

My goal: given $\mathcal{P}$ and $m,\mu,\sigma$, find a convex polyedron $\mathcal{Q}$ defined by $m$ linear inequalities that is contained within $\mathcal{P}$ and whose "badness" is as small as possible.

If there is no efficient solution to this optimization problem, I would be happy with an approximation algorithm or a heuristic. In my application, I would expect to have $m,n \le 50$ or so (perhaps even smaller), but $d$ is large (say $d \approx 10^4$ or so). Also, if a solution for the general problem is too hard, I would be satisfied with a solution for the special case where we are guaranteed that $a\_i,c\_i$ are all $\ge 0$.

Can you suggest any methods that might be effective for this problem?

**Tags:** cg.comp-geom, approximation-algorithms, linear-programming, convex-geometry, high-dimensional-geometry
> **Comments:**
> **username_1**: do you want to stipulate that $a_i, c_i\ge 0$?  If not, then $\cal Q$ might not exist.  E.g. using $n=2k$, take ${\cal P} = {\mathbb R}_+^d \cap \{x : \forall i\in \{1,\ldots,k\}.  x_i = 1\}$.  If $m<n$, then maybe no such (non-empty) $\cal Q$ is contained in $\cal P$?  
> **username_0**: Thanks, @NealYoung, those are excellent points.  I appreciate your careful review.  I would be fine with a stipulation that $a_i,c_i \ge 0$; in the application I have in mind, that is usually the case.  I've updated the question accordingly.  

---

## 0 answers

