What optimization problems have solutions with few nonzeros?

Question

Consider the following optimization problem, with $n$ variables and $m$ linear constraints: \begin{align} \text{maximize} && c_1 x_1 + \cdots + c_n x_n & \\ \text{subject to} && a_{11} x_1 + \cdots + a_{1n} x_n &= b_1 \\ && a_{21} x_1 + \cdots + a_{2n} x_n &= b_2 \\ &&... \\ && a_{m1} x_1 + \cdots + a_{mn} x_n &= b_m \\ && x_1 \ldots,x_n &\geq 0 \end{align} It is known that, if the problem has an optimal solution, then it has an optimal solution in which at most $m$ variables are non-zero; it is called an optimal basic feasible solution.

This can be easily visualized in two dimensions ($n=2$). For example here:

the solid black segment represents the single constraint ($m=1$), and the two dotted lines represent two different objectives; it is clearly visible that each objective is both maximized and minimized at one of the endpoints of the segments, which has at most one nonzero.

This nice property holds, in some cases, even if the constraints are not linear. For example, in the above case, if we raise the variables in the constraint to a power smaller than 1, then the linear objectives are still maximized (but not minimized) at the endpoints:

MY QUESTION IS: is this true in general? I.e., is it true that, if we replace each term $a_{ij}x_i$ in the above program with a term $f_{ij}(x_i)$, where $f_{ij}$ is a concave function (such as $f_{ij}(x_i) = (x_i)^{0.7}$), then there is still an optimal solution with at most $m$ nonzeros?

_{Note: posted previously on math.SE with no replies.}

Answer 1

Geometrically speaking, one gets basic solutions due to the usual linear programming (LP) dual of the problem in the question being linear minimisation on a convex polyhedron $P$, specified by linear inequalities $$ \sum_{j=1}^m a_{ji} y_j\leq c_i, \text{ for $1\leq i\leq n$,}\qquad\qquad (1) $$ applying the complementary slackness. For our purposes it suffices to consider the case of $P$ bounded, i.e. the convex closure of finitely many points, the vertices $v_k$ of $P$. If you replace the linear functions in $(1)$ by functions that result in $P$ being transformed into $P'\subset P$, that still contains all the $v_k$, and do not change its face structure (e.g. think of changes being "small", such as you "pump out a bit of air" from $P$), then the combinatorics of dual and primal optimal solutions does not change, and you still have the property you ask about. The transformation in question might perturb $P$ more, it can move vertices, but as long as the face structure remains the same, it will still work.

To summarise - if the transformation you propose is as described, the answer is yes. In particular it is important that the faces of $P$ get deformed so that the convex closure of images of $v_k$ contains the image of $P$.