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)$.

$\endgroup$
  • 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 Aug 15 '12 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$ – John Moeller Aug 15 '12 at 20:10
  • $\begingroup$ Oh I see, the outer one is over M-dimensional vectors. $\endgroup$ – John Moeller Aug 15 '12 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$ – John Moeller Aug 16 '12 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$ – John Moeller Aug 16 '12 at 3:08
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.

$\endgroup$
  • $\begingroup$ @harish You should probably select this as the correct answer. $\endgroup$ – John Moeller Aug 17 '12 at 19:17

Your Answer

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

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