Maximizing a convex function with linear constraints 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)$.
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.