I previously posted this on MathSE and am now trying here.
I have the following situation, as shown in the following diagram:
$W=\{w_i\}_{i=1..|W|}$ is a set of vertices (show in diagram in blue) located within a regular simplex and having coordinates $\in \mathbb{R}^n$ . In the diagram, an example $W$ is depicted by three vertices $w_1$, $w_2$, and $w_3$. Some vertices of $w_i$ may be convex combinations of others.
$A=\{a_i\}_{i=1..|A|}$ (orange) and $B=\{b_i\}_{i=1..|B|}$ (green) are sets of vertices located within the convex hull of $W$. Examples are shown in the diagram, indicated by $a_1$, $a_2$, $a_3$ and $b_1$, $b_2$, $b_3$. The coordinates of the vertices $A$ and $B$ are held fixed in terms of the coefficients associated with $\{w_i\}$ (vertices of $W$), but naturally vary with $W$.
The convex hulls of $W$, $A$ and $B$ are all guaranteed to include the origin (indicated by the red $+$).
The intersection of the convex hulls of $A$ and $B$, called by $A \cap B$, is indicated in grey. Call this region, as a function of the vertices $W$, by $C(W)=Conv(A(W)) \cap Conv(B(W))$.
I need to maximize a convex function $f$ over the intersection region: $$\max_{W,x\in C(W)} f(x)$$
It is important to note again that some of the vertices of $w_i$ may be convex combinations of others. In fact, increasing the intersection between the convex hulls of $A$ and $B$ can involve projecting onto subspaces where they overlap (orthogonally to subspaces in which they differ).
Finding a global minimum does not seem possible using standard optimization techniques, since (at least in the way I've been able to state it), it involves a quadratic equality constraint. I'm wondering if there is some special structure, or some combination of optimization and enumeration, I can exploit to find the solution.
Some ideas:
1) Is it possible to prove something special about the optimal $W$ vertices, such as that they will map onto (a subset of) the vertices of underlying regular simplex? In this case, I could enumerate all possible such $W$ (I'm dealing with low dimensional objects).
2) Because $f$ is convex, for any given $W$ it will be maximized at one of the extreme points of $C(W)$. Is there any way to split the set of possible $W$s into a finite set of regions $\{\Omega_1, \dots, \Omega_m\}$, where in each case the set $\{Ep(C(W)) : W \in \Omega_i\}$ (where $Ep$ indicates the extreme points of a convex set) will be convex?
3) Perhaps the polar duality can be used here? For convex polytopes $P_1$ and $P_2$, I know that $P_1 \cap P_2 = ConvHull( P_1° \cup P_2°)°$, where $P°$ indicates the polar polytope of $P$. There is also duality between the vertices and faces of a polytope and its polar dual. Maybe the set of possible vertices of the intersections be associated with the faces of $(A° \cup B°)$ under linear transformation $T$ which represents remapping the vertices of $W$? One difficulty is that, IIRC, the polar of a polytope transformed by linear transformation $T$ (call this $PT$), is $P°T^{-1}$. As I suggested, the set of $W$ may not be linearly independent, leading to a singular $T$. (Actually, I'm not sure if this relationship even holds for non-convex polytopes -- such as $P_1° \cup P_2°$ -- or whether things get weird).
In any case, any other relevant literature / ideas here would be greatly appreciated!
