Return to Question

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

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