3
$\begingroup$

I have the following optimization problem: $$ \arg\max_{\{\phi_p\}_{p=1}^M}\sum_{i=1}^N \max_{p=1,\ldots,M}\{\phi_p a_{ip}\} \mbox{ such that }\sum_{p}\phi_p\leq 1\mbox{ and }0\leq \phi_p\leq 1,\forall p=1,\ldots,M, $$ where $a_{ij} \geq 0,\forall i,j$. The objective function is clearly convex since $\max_{p}\{\phi_p a_{ip}\}$ is convex in $\{\phi_p\}$.

I realize that, in general, convex maximization problems can be NP-hard but I was wondering whether there are any known efficient solutions for this specific problem structure.

I apologize but there was a typo in my question. The constraint is supposed to be $\sum_{p}\phi_p\leq K$. Hence, I need to search over ${M\choose K}$ vertices, which may be an exponential number of vertices if $K=O(M)$.

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ It is easy to compute the maximum value and one point which attains the maximum because a convex function is maximized at an extreme point of the domain, and in your case you have only M extreme points. If you want to compute the set of points which attain the maximum value, I am not sure. $\endgroup$
    – Tsuyoshi Ito
    Commented Aug 15, 2012 at 18:21
  • $\begingroup$ Wait a minute, maybe I'm missing something, but why is there a max inside the sum? That would make the max outside the sum redundant (they're both maximized over the same variable). $\endgroup$
    – Josephine Moeller
    Commented Aug 15, 2012 at 20:10
  • $\begingroup$ Oh I see, the outer one is over M-dimensional vectors. $\endgroup$
    – Josephine Moeller
    Commented Aug 15, 2012 at 20:16
  • $\begingroup$ @harish (after your edit) The trick here is to realize that max doesn't really introduce anything nonlinear into your optimization (it just adds more facets to your constraint polytope). I'm trying to remember exactly how you convert these types of problems, and I'll post an answer when I figure it out. $\endgroup$
    – Josephine Moeller
    Commented Aug 16, 2012 at 2:17
  • $\begingroup$ @harish Ah. I realize the problem with that approach now. The number of constraints will also explode exponentially if you convert it to a linear program. If my guess is correct, the number of constraints can grow as $N2^M$. $\endgroup$
    – Josephine Moeller
    Commented Aug 16, 2012 at 3:08

1 Answer 1

Reset to default
4
$\begingroup$

Your problem in revision 3 of the question is NP-hard by a reduction from the vertex cover problem. Slightly more precisely, even if aip’s are restricted to 0 or 1, it is NP-complete to decide whether the maximum value in the question is equal to N or less than N. (Note that the maximum value cannot be greater than N if aip’s are 0 or 1.) The detail is left as an exercise.

Improve this answer
$\endgroup$
1
  • $\begingroup$ @harish You should probably select this as the correct answer. $\endgroup$
    – Josephine Moeller
    Commented Aug 17, 2012 at 19:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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