<p>The problem statement is</p>

<blockquote>
  <p>Given convex functions $f_i$ over $X$, find  $$\arg\max_{x\in X} \sum_i f_i(x)$$</p>
</blockquote>

<p>Does this kind of problem structure allow one to use specific strategies to solve the problem?</p>

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

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

CC BY-SA 3.0
2012-10-05T03:40:58.380Z
A sum of convex functions is convex.
Yuval Filmus
CC BY-SA 3.0
2012-10-05T12:45:05.917Z
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
CC BY-SA 3.0
2012-10-06T06:33:02.910Z
@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
CC BY-SA 3.0
2012-10-07T18:40:58.807Z
The following paper is some what related. "An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope". http://www.optimization-online.org/DB_HTML/2011/09/3152.html. It appeared in Math. Programming Ser A.
Chandra Chekuri
CC BY-SA 3.0
2012-10-10T17:58:53.080Z
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
<ds.algorithms><approximation-algorithms><optimization><convex-optimization><approximation>
Maximizing a convex function where the objective function is separable but the search space is not
Rein
# Maximizing a convex function where the objective function is separable but the search space is not

(Asked by: username_0 on 2012-10-05)

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 ?

**Tags:** ds.algorithms, approximation-algorithms, optimization, convex-optimization, approximation
> **Comments:**
> **username_1**: A sum of convex functions is convex.  
> **username_2**: 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?  
> **username_3**: @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  
> **username_4**: The following paper is some what related. "An FPTAS for Optimizing a Class of Low-Rank Functions Over a Polytope". http://www.optimization-online.org/DB_HTML/2011/09/3152.html. It appeared in Math. Programming Ser A.  
> **username_2**: 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).  

---

## 0 answers

