<p>The problem as presented is NP-hard. </p>

<p>Suppose we have $f(y)=0, y\leq 1$ and $f(y) = y, y &gt; 1$. Now if we have the constraints $y_1 + y_2 \geq 2.01$ and $y_i \geq 0$, and we want to minimize $\sum_i f(y_i)$, clearly we should choose one of these $y_i$ to be $1$ and one to be $1.01$. </p>

<p>Now, suppose we have a graph $G$, and we put a constraint like this for every edge. Replace $2.01$ by $2 + \epsilon$ for a sufficiently small $\epsilon$. (You don't even need to do this, because vertex cover has an inapproximability result.) To minimize the objective function, we want to find the minimum number of vertices that hit every edge. This is the minimum vertex cover problem, and it is NP-complete. </p>

<p>The only reason that this isn't exactly your problem is that the matrix $A$ is not square, because the number of variables is the number of vertices in $G$, and the number of equations is the number of edges in $G$. But you can always add dummy vertices that don't participate in the equations to make $A$ square.</p>

<p>Possibly your real problem has more structure so that this NP-completeness proof doesn't apply. Maybe if you told us more about the real problem, it might be solvable in polynomial time.</p>

<p>For convex $f$, this should be solvable in polynomial time ... see Chandra's comment. </p>

CC BY-SA 3.0
2013-06-22T08:02:59.017Z
Nice result. Indeed my problem has more structure, so I will see another way. I am still looking for references on approximation results though.
Gopi
CC BY-SA 3.0
2013-06-20T23:56:33.513Z
2013-06-21T10:27:49.760Z
2013-06-21T10:27:49.760Z
Peter Shor 
<p>I am looking for references whether this problem can be doable in polynomial time (or other known approximation results):</p>

<p>Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$),
$$
\min \sum_{i=1}^n f(y_i)
$$
under the constraints
$$
Ay \geq b
$$</p>

<p>To answer to Peter Shor's comment, we are trying to find the vector $y=(y_1,\cdots,y_n)$, $A$ is a $n\times n$ matrix. We suppose that $k$ is a constant.</p>

<p>I am particularly interested in the case where $f$ is a piecewise linear function, not continuous ($\exists (a_1,\cdots,a_k),0&lt;\alpha_1&lt;\cdots&lt;\alpha_k) $, such that $\forall x\in ]a_i,a_{i+1}], f(x) = \alpha_{i+1}x$).</p>

<p>It seems to me that the ellipsoid algorithm could work for those special functions, but I have not been able to find any references, maybe because either this is a sub problem of a known problem? Note that I am trying to solve this for any rational values.</p>

<p>(Note that this is a sub-question of <a href="https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in">What classes of mathematical programs can be solved exactly or approximately, in polynomial time?</a>)</p>

CC BY-SA 3.0
2013-06-19T12:46:33.660Z
Are you trying to find the $n$ values of $y_i$ that minimize this? What are the relative sizes of $n$, $k$, and $\dim A$?
Peter Shor 
CC BY-SA 3.0
2013-06-19T13:47:12.630Z
@PeterShor, thank you, I have corrected my text accordingly.
Gopi
CC BY-SA 3.0
2013-06-19T15:45:51.823Z
The first thought that comes to mind here is to use the technique of [column generation](http://en.wikipedia.org/wiki/Column_generation). The idea is to start with just a few possible values of $y_i$, set up the resulting problem as a linear program, and solve it. Then find more values of $y_i$ to add to the permissible set that will lower the minimum, and repeat. It would require some work to fill in the details (if this technique does indeed work), and I don't have the time to work this out.
Peter Shor 
CC BY-SA 3.0
2013-06-19T15:55:23.390Z
Are you trying to solve this problem in practice, or are you trying to prove that it can be solved in polynomial time?
Peter Shor 
CC BY-SA 3.0
2013-06-19T16:18:47.873Z
@PeterShor, I am trying to solve it in practice (for another problem), I did not know the column generation technique, I will try to look into it, thanks.
Gopi
CC BY-SA 3.0
2013-06-19T17:39:16.480Z
In cases where column generation works in practice, the ellipsoidal algorithm can often give an algorithm that is polynomial in theory. I haven't thought about your question long enough to have a good idea of whether column generation should work, but it has the feel of a problem where it should.
Peter Shor 
CC BY-SA 3.0
2013-06-20T03:38:48.703Z
I don't see the connection with column generation. It's usually used only when there are exponentially many variables.
Austin Buchanan
CC BY-SA 3.0
2013-06-20T17:51:06.780Z
I did not understand what you meant by "not continuous" when you consider the piece-wise linear case. If you do have continuity then isn't your function convex in this case? In that case you are doing convex function minimization subject to convex constraints and the problem should be solvable in polynomial time.
Chandra Chekuri
CC BY-SA 3.0
2013-06-20T17:54:21.970Z
@Austin: there are uncountably many variables; one for each possible value of $y_i$.
Peter Shor 
CC BY-SA 3.0
2013-06-20T19:02:29.037Z
@ChandraChekuri, yes, in the case where I have continuity, then, yes, it is a convex function. However I do not have continuity for each $a_i$ since $f(a_i^-)=\alpha_i a_i$ and $f(a_i^+)=\alpha_{i+1} a_i$. The function is therefore not convex, but it is star-shaped.
Gopi
CC BY-SA 3.0
2013-06-20T19:03:31.167Z
@PeterShor, here I have a polynomial number of variable (I consider the unary version of $n$). So there are only $n$ variables?
Gopi
CC BY-SA 3.0
2013-06-20T19:06:54.590Z
@Gopi: I think you need a variable for every possible value of $y_i$. Since $y_i$ can take on any possible positive real value, you get an infinite number of variables.
Peter Shor 
CC BY-SA 3.0
2013-06-20T19:09:13.577Z
@PeterShor, maybe I am mistaken, but isn't the point of optimization to find those solutions without needing an infinite number of variables? I was seeing this as some special sort of LP, am I missing something? (or is this linked to the special function I am minimizing?)
Gopi
CC BY-SA 3.0
2013-06-20T23:30:25.530Z
I just realized that I have been thinking about $f$ as being convex. I am not sure that my idea works if $f$ is merely superadditive.
Peter Shor 
<reference-request><optimization>
Minimize in polynomial time a super-additive increasing function under linear constraints?
Gopi
# Minimize in polynomial time a super-additive increasing function under linear constraints?

(Asked by: username_0 on 2013-06-19)

I am looking for references whether this problem can be doable in polynomial time (or other known approximation results):

Let $f$ a super-additive function ($\forall x,y, f(x+y) \geq f(y)+f(y)$),
$$
\min \sum\_{i=1}^n f(y\_i)
$$
under the constraints
$$
Ay \geq b
$$

To answer to Peter Shor's comment, we are trying to find the vector $y=(y\_1,\cdots,y\_n)$, $A$ is a $n\times n$ matrix. We suppose that $k$ is a constant.

I am particularly interested in the case where $f$ is a piecewise linear function, not continuous ($\exists (a\_1,\cdots,a\_k),0<\alpha\_1<\cdots<\alpha\_k) $, such that $\forall x\in ]a\_i,a\_{i+1}], f(x) = \alpha\_{i+1}x$).

It seems to me that the ellipsoid algorithm could work for those special functions, but I have not been able to find any references, maybe because either this is a sub problem of a known problem? Note that I am trying to solve this for any rational values.

(Note that this is a sub-question of [What classes of mathematical programs can be solved exactly or approximately, in polynomial time?](https://cstheory.stackexchange.com/questions/6833/what-classes-of-mathematical-programs-can-be-solved-exactly-or-approximately-in))

**Tags:** reference-request, optimization
> **Comments:**
> **username_1**: Are you trying to find the $n$ values of $y_i$ that minimize this? What are the relative sizes of $n$, $k$, and $\dim A$?  
> **username_0**: @PeterShor, thank you, I have corrected my text accordingly.  
> **username_1**: The first thought that comes to mind here is to use the technique of [column generation](http://en.wikipedia.org/wiki/Column_generation). The idea is to start with just a few possible values of $y_i$, set up the resulting problem as a linear program, and solve it. Then find more values of $y_i$ to add to the permissible set that will lower the minimum, and repeat. It would require some work to fill in the details (if this technique does indeed work), and I don't have the time to work this out.  
> **username_1**: Are you trying to solve this problem in practice, or are you trying to prove that it can be solved in polynomial time?  
> **username_0**: @PeterShor, I am trying to solve it in practice (for another problem), I did not know the column generation technique, I will try to look into it, thanks.  
> **username_1**: In cases where column generation works in practice, the ellipsoidal algorithm can often give an algorithm that is polynomial in theory. I haven't thought about your question long enough to have a good idea of whether column generation should work, but it has the feel of a problem where it should.  
> **username_2**: I don't see the connection with column generation. It's usually used only when there are exponentially many variables.  
> **username_3**: I did not understand what you meant by "not continuous" when you consider the piece-wise linear case. If you do have continuity then isn't your function convex in this case? In that case you are doing convex function minimization subject to convex constraints and the problem should be solvable in polynomial time.  
> **username_1**: @Austin: there are uncountably many variables; one for each possible value of $y_i$.  
> **username_0**: @ChandraChekuri, yes, in the case where I have continuity, then, yes, it is a convex function. However I do not have continuity for each $a_i$ since $f(a_i^-)=\alpha_i a_i$ and $f(a_i^+)=\alpha_{i+1} a_i$. The function is therefore not convex, but it is star-shaped.  
> **username_0**: @PeterShor, here I have a polynomial number of variable (I consider the unary version of $n$). So there are only $n$ variables?  
> **username_1**: @Gopi: I think you need a variable for every possible value of $y_i$. Since $y_i$ can take on any possible positive real value, you get an infinite number of variables.  
> **username_0**: @PeterShor, maybe I am mistaken, but isn't the point of optimization to find those solutions without needing an infinite number of variables? I was seeing this as some special sort of LP, am I missing something? (or is this linked to the special function I am minimizing?)  
> **username_1**: I just realized that I have been thinking about $f$ as being convex. I am not sure that my idea works if $f$ is merely superadditive.  

---

## 1 answers

### Answer by username_1 on 2013-06-20. Score: 7

The problem as presented is NP-hard.

Suppose we have $f(y)=0, y\leq 1$ and $f(y) = y, y > 1$. Now if we have the constraints $y\_1 + y\_2 \geq 2.01$ and $y\_i \geq 0$, and we want to minimize $\sum\_i f(y\_i)$, clearly we should choose one of these $y\_i$ to be $1$ and one to be $1.01$.

Now, suppose we have a graph $G$, and we put a constraint like this for every edge. Replace $2.01$ by $2 + \epsilon$ for a sufficiently small $\epsilon$. (You don't even need to do this, because vertex cover has an inapproximability result.) To minimize the objective function, we want to find the minimum number of vertices that hit every edge. This is the minimum vertex cover problem, and it is NP-complete.

The only reason that this isn't exactly your problem is that the matrix $A$ is not square, because the number of variables is the number of vertices in $G$, and the number of equations is the number of edges in $G$. But you can always add dummy vertices that don't participate in the equations to make $A$ square.

Possibly your real problem has more structure so that this NP-completeness proof doesn't apply. Maybe if you told us more about the real problem, it might be solvable in polynomial time.

For convex $f$, this should be solvable in polynomial time ... see Chandra's comment.

> **Comments:**
> **username_0**: Nice result. Indeed my problem has more structure, so I will see another way. I am still looking for references on approximation results though.  

---

