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.



Algorithmic aspects of maximizing a convex function over a convex set
For one, the KKT conditions still apply. But in general even simple problems can be tough. For instance, maximizing a p-norm over a fairly nice type of convex polytope ("parallelotope") is NP hard -- see Bodlaender et al, "Computational Complexity of Norm Maximization." The general wisdom is: minimizing convex functions is easy; maximizing convex functions (equivalently, minimizing concave functions) is hard, though there are obviously exceptions.


