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