2
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – prubin
    Commented Mar 7 at 20:48
  • $\begingroup$ @prubin yes, this is what I meant $\endgroup$ Commented Mar 7 at 21:12

1 Answer 1

1
$\begingroup$

This is generally not true for general linear problems, nor for MILPs, although for the latter it often turns out to be the case (especially for BLPs) simply due to binary variables being present.

Do note that trivial solutions can exist where all binaries are equal to 1 (this is actually a very basic heuristic MIP solvers can use), so it's not guaranteed in the general case.

Also note that you can trivially show that this is not the case for LPs if you consider a linear feasibility problem subject to a square system of linearly independent equations, e.g.:

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.