Minimize in polynomial time a super-additive increasing function under linear constraints?

Question

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?)

Answer 1

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.