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.

  • $\begingroup$ If you just need a numerical answer and you use simulated annealing, it will converge quickly and almost surely by convexity. $\endgroup$ – Steve Huntsman Mar 5 '10 at 15:06
  • $\begingroup$ I am not very interested in numerical answers. I am more interested in general techniques for solving such problems (steepest ascent, etc...). As well as any computational complexity bounds. For example, what sufficient conditions are there (if there are any) for Netwon's method, for example, to be guaranteed to converge? $\endgroup$ – Travis Service Mar 5 '10 at 16:19
  • $\begingroup$ I'm assuming that you still want heuristics ? by the remark in your original problem, this problem is NP-hard. So do you want exact algorithms that run as quickly as possible, or are you willing to settle for approximations ? $\endgroup$ – Suresh Venkat Mar 8 '10 at 4:21

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.


If you're willing to tolerate an approximate answer, there are some options, but there's nothing direct. One idea would be to write the packing problem as an (exponential-sized) integer program and then relax it to the linear program. Then, you might (by studying the dual and using the ellipsoid algorithm) be able to get a close-enough solution to the linear program.

Following that, you could use any number of rounding techniques to solve the integer program. For example, look at Aravind Srinivasan's work: Improved Approximation Guarantees for Packing and Covering Integer Programs, SIAM Journal on Computing, Vol. 29, 648-670, 1999

But for this program to be successful, you still have to solve the LP, and given that you have both exponentially many variables and constraints (one var for each set), that's where things get complicated (as opposed to set packing, where there are $n$ sets by defn). There are cases when the ellipsoid method can be used to solve such problems, but it's case by case. At least in your case, you know that any feasible solution has at most $n$ nonzero set variables.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.