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

• 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. Aug 15, 2012 at 18:21
• 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). Aug 15, 2012 at 20:10
• Oh I see, the outer one is over M-dimensional vectors. Aug 15, 2012 at 20:16
• @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. Aug 16, 2012 at 2:17
• @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$. Aug 16, 2012 at 3:08