## 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.