co.combinatorics - Algorithmic aspects of maximizing a convex function over a convex set

Motivation

The problem I am facing can be considered a variant of the standard set packing problem. However; instead of being given a list of sets, I am given a function $nu : 2^N rightarrow {0,1}$ and want to find a partitioning $P$ of $N$ that maximizes $g(P) = sum_{S in P} nu(S)$. This can be shown to require somewhere between $O(2^{|N|})$ and $O(3^{|N|})$ operations.

The above problem can (almost) be reduced to the problem of finding a partition $P_3$ of $N$ into three sets that maximizes $g(P_3)$. However there are still $O(3^{|N|})$ partitionings of $N$ into three sets.

Lets say we construct such a 3 partition $(S_1,S_2,S_3)$ as follows: For each element $i in N$, we add $i$ to the first set with probability $x_i$, to the second set with probability $y_i$ and to the third with probability $z_i$, where $x_i+y_i+z_i = 1$ and $0 leq x_i, y_i, z_i$.

It can be shown that the expected value of such a probability distribution, $x,y,z$, over the 3 partitions of $N$ is $f(x,y,z) = E[g(P)] = sum_{c subset N} nu(C)left[Pi_{i in C} x_i Pi_{i not in C} (y_i+z_i) + Pi_{i in C} y_i Pi_{i not in C} (x_i+z_i) + Pi_{i in C} z_i Pi_{i not in C} (x_i+y_i)right]$.

I am considering the situation in which we relax the constraint $x_i+y_i+z_i = 1$ to $x_i+y_i+z_i leq 1$ and then using techniques akin to interior point methods for standard convex programming.

This relaxation clearly does not change maximum of $f(x,y,z)$ and with it in place $f(x,y,z)$ can be shown to be convex over our feasible set $0 leq x_i,y_i,z_i$ and $x_i +y_i+z_i leq 1$ for $i in N$.

---

Given the above, my question is: Is there any general theory for maximizing convex functions over convex compact sets? (Apart from that the maximum must appear on the boundary?)

First time poster, so my apologies if I have tagged this inappropriately.
I know of much work in convex programming (minimizing convex functions over convex sets) but haven't been able to find similar work for maximization.

• Next core - Could evaporating hot Jupiters have metallic hydrogen on their surfaces?
• Previous galaxy - How long until we cannot see any stars from other galaxies?