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?

  • $\begingroup$ 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$? $\endgroup$
    – Neal Young
    Dec 16 '13 at 1:29
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 16 '13 at 1:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.