<p>Your problem in revision 3 of the question is NP-hard by a reduction from the vertex cover problem.  Slightly more precisely, even if <i>a</i><sub><i>ip</i></sub>’s are restricted to 0 or 1, it is NP-complete to decide whether the maximum value in the question is equal to <i>N</i> or less than <i>N</i>.  (Note that the maximum value cannot be greater than <i>N</i> if <i>a</i><sub><i>ip</i></sub>’s are 0 or 1.)  The detail is left as an exercise.</p>

CC BY-SA 3.0
2012-08-17T19:17:27.710Z
@harish You should probably select this as the correct answer.
Josephine Moeller
CC BY-SA 3.0
2012-08-16T13:38:43.693Z
2012-08-16T13:38:43.693Z
Tsuyoshi Ito
<p>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\}$.</p>

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

<hr>

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

CC BY-SA 3.0
2012-08-15T18:21:08.993Z
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
CC BY-SA 3.0
2012-08-15T20:10:59.670Z
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).
Josephine Moeller
CC BY-SA 3.0
2012-08-15T20:16:37.727Z
Oh I see, the outer one is over M-dimensional vectors.
Josephine Moeller
CC BY-SA 3.0
2012-08-16T02:17:52.723Z
@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.
Josephine Moeller
CC BY-SA 3.0
2012-08-16T03:08:59.790Z
@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$.
Josephine Moeller
<ds.algorithms><approximation-algorithms><optimization><convex-optimization>
Maximizing a convex function with linear constraints
harish
# Maximizing a convex function with linear constraints

(Asked by: username_0 on 2012-08-15)

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

**Tags:** ds.algorithms, approximation-algorithms, optimization, convex-optimization

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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).  
> **username_2**: Oh I see, the outer one is over M-dimensional vectors.  
> **username_2**: @username_0 (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.  
> **username_2**: @username_0 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$.  

---

## 1 answers

### Answer by username_1 on 2012-08-16. Score: 4 | Accepted answer

Your problem in revision 3 of the question is NP-hard by a reduction from the vertex cover problem. Slightly more precisely, even if *a**ip*’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 *a**ip*’s are 0 or 1.) The detail is left as an exercise.

> **Comments:**
> **username_2**: @username_0 You should probably select this as the correct answer.  

---

