# Tag Info

### Do convex quadratic problems always have sparse solutions?

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.
• 39.6k

### Do convex quadratic problems always have sparse solutions?

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 ...
• 2,806
Accepted

### Do convex quadratic problems always have sparse solutions?

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$.
• 1,196
Accepted

• 32.8k
Accepted

### How to model this constraint for a QP problem?

I assume that $x$ is binary. A more natural indexing would be $x_{ur}$, in which case you can introduce binary decision variables $y_r$ and impose linear constraints: \begin{align} x_{ur} &\le ...
• 32.8k
Accepted

### How to do the scaling to remove bias in QP problem?

If $x$ is binary vector, you have $x^T D x = d^T x$ for any diagonal matrix $D$ with diagonal $d$. This has two important consequences: You can assume Q to be convex without loss of generality. In ...
Let's assume that, per Rob Pratt's comment, your $Q$ is symmetric and positive definite. Your approximation is correctly derived, and you can certainly try it. Due to convexity, the linear ...