3
$\begingroup$

It is known that a feasible bounded linear program with $m$ constraints always has a solution with at most $m$ non-zero variables (a basic feasible solution). Since the number of constraints might be much smaller than the number of variables, this solution may be very sparse, which is useful in some applications.

My question is whether an analogous result holds for convex quadratic programming? I.e., does there always exist a solution in which the number of non-zero variables is bounded by some function of $m$, independently of the number of variables?

$\endgroup$

3 Answers 3

6
$\begingroup$

Consider the unconstrained convex QP $$ \min \|x - x_0\|_2^2. $$

The solution is $$ x = x_0 $$ which is also fully dense for dense $x_0$.

$\endgroup$
14
$\begingroup$

Consider the convex QP $$\min \lbrace \sum_{i=1}^n x_i^2 : x\in \mathbb{R}^n, \sum_{i=1}^n x_i = 1\rbrace.$$ The solution is $$x = (\frac{1}{n},\dots,\frac{1}{n}),$$which is fully dense.

$\endgroup$
7
$\begingroup$

Not in general. In quadratic programming (and in nonlinear programming, more general), we have basic, non-basic and super-basic variables. These superbasics can be interpreted as non-basic but between the bounds. We can end up with a solution with few non-basics (at bound) and many super-basics.

Actually, that happens a lot in practice. QP-based portfolio models often have almost all instruments in the portfolio (many with small values). Creating sparse solutions requires binary variables (or something related), to implement a cardinality constrained model.

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