I have the following situation, as shown in the following diagram: enter image description here

  • $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!


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.