# Are there classes of non-linear programs that always have sparse solutions?

It is well-known that linear programs always have sparse solutions -- solutions in which only at most $$m$$ variables are nonzero, where $$m$$ is the number of constraints.

In the answers to this question, it is shown that the same does not hold for quadratic convex programs, as there may be quadratic programs in which all solutions are dense.

QUESTION: are there other classes of mathematical programs (besides linear programs) in which all problems are guaranteed to have sparse solutions?

• Just to be clear, LPs do not always have sparse solutions out of the box. If an LP has nontrivial lower bounds for the variables, you can convert it to one with a sparse solution by replacing $x \ge \ell$ with $x'=x-\ell \ge 0.$ So I guess you would be looking for other model classes easily convertible to equivalent models with sparse solutions.
– prubin
Commented Mar 7 at 20:48
• @prubin yes, this is what I meant Commented Mar 7 at 21:12

$$\min_{x\in{X}} 0, s.t. x=1, x\in\mathbb{R}.$$
The only class of problems I can think of from the top of my head that must have zeros in their solutions are problems with single-term complementarity constraints, i.e., $$x_1x_2=0$$, or problems where binary variables enforce it through the constraints, e.g., $$b_1+b_2+b_3=1$$, or $$b_1b_2+b_3=1$$. If you play around with the math and variable types and bounds you can come up with virtually infinite nonlinear formulations that demand that some set of variables is a set of zeros.
Maybe someone else can contribute a more insightful use case - in general such formulations are ubiquitous and we use them all the time, but I can't really single out a specific class of problems where we have to use such constraints $$100\%$$ of the time.