# Maximizing a convex function where the objective function is separable but the search space is not

The problem statement is

Given convex functions $f_i$ over $X$, find $$\arg\max_{x\in X} \sum_i f_i(x)$$

Does this kind of problem structure allow one to use specific strategies to solve the problem?

Does it help if I also know the lower bound and upper bound of each $\max_x f_i(x)$ and the corresponding $x$?

For example, is there any algorithm like the objective function analogy of branch and bound method ?

• A sum of convex functions is convex. – Yuval Filmus Oct 5 '12 at 3:40
• What does it even mean for an objective function to be separable if this condition has nothing to do with the feasible set? Is a linear function separable? – Tsuyoshi Ito Oct 5 '12 at 12:45
• @YuvalFilmus not sure why that's relevant. Maximizing a convex function is still a hard problem in general, and the OP is asking for heuristics that exploit the special structure of the problem. Tsuyoshi, by the OP's reasoning, a linear function would be separable, but the function (x+y)^2 wouldn't, because of the term xy that isn't convex – Suresh Venkat Oct 6 '12 at 6:33
• The following paper is some what related. "An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope". optimization-online.org/DB_HTML/2011/09/3152.html. It appeared in Math. Programming Ser A. – Chandra Chekuri Oct 7 '12 at 18:40
• I do not know if you count a linear function as “separable,” but if you do, then the mere fact that the objective function is separable is not useful by itself, because maximizing f(x) subject to x∈X is the same as maximizing t subject to x∈X and t≤f(x). – Tsuyoshi Ito Oct 10 '12 at 17:58