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