3
$\begingroup$

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 ?

$\endgroup$
  • 3
    $\begingroup$ A sum of convex functions is convex. $\endgroup$ – Yuval Filmus Oct 5 '12 at 3:40
  • 1
    $\begingroup$ 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? $\endgroup$ – Tsuyoshi Ito Oct 5 '12 at 12:45
  • $\begingroup$ @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 $\endgroup$ – Suresh Venkat Oct 6 '12 at 6:33
  • $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Oct 7 '12 at 18:40
  • $\begingroup$ 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). $\endgroup$ – Tsuyoshi Ito Oct 10 '12 at 17:58

Your Answer

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

Browse other questions tagged or ask your own question.