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

-
If you just need a numerical answer and you use simulated annealing, it will converge quickly and almost surely by convexity. – Steve Huntsman Mar 5 '10 at 15:06
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? – Travis Service Mar 5 '10 at 16:19
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 ? – Suresh Venkat Mar 8 '10 at 4:21

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.