2
$\begingroup$

We work over $\mathbb{R}^K$. Let $V$ be the set of vectors whose coordinates take values $0$ or $1$, or equivalently the corners of the unit cube $[0,1]^K$.

Let $d:\{0, \ldots, K\} \to \mathbb{R}_+$ be a function such that $d(k)$ decreases with $k$ (and the function $kd(k)$ increases with $k$).

We define the subset $S = \{d(\| \mathbf{v} \|_1)\mathbf{v}: \mathbf{v} \in V\}$. Let $C$ be its convex hull.

Let $S_1 = \{e \mathbf{v}: \| \mathbf{v} \|_1 =1; (\mathbf{v}\in V) \}$, for some $e \in \mathbb{R}_+$. We denote by $C_1$ the convex hull of $S_1$.

I need to find the intersection between $C$ and $C_1$ (we suppose that this intersection always exists). An illustration of an example in 2D is given by the following figure:

enter image description here

How to find the coordinates of the extremal points of the intersection of $C$ and $C_1$ in the general case? There are 2 such points in the above example.

Any hint is welcome.

$\endgroup$
3
  • 1
    $\begingroup$ I asked this question on mathexchange, but it didn't attract any attention.. PS: I don't know if this is the proper way to link the questions $\endgroup$
    – tam
    May 20, 2015 at 18:29
  • $\begingroup$ It looks like the solution set is invariant under permutations of the indices. It looks like it may be enough to consider finding l such that d(lhat) <e < d((l+1)hat), where hat of a number l has the first l coordinates 1 and the rest 0. With l in hand, you can now consider linear combinations of the right number of vectors and do it up to permutation of coordinates. Gerhard "Use Symmetry To Your Advantage" Paseman, 2015.05.20 $\endgroup$ May 20, 2015 at 18:30
  • $\begingroup$ @GerhardPaseman I am not sure I have understood your idea (and the notation). Could you please detail your answer? $\endgroup$
    – tam
    May 21, 2015 at 6:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.