# Sparse $\ell_0$ solution to constrained quadratic program

Given $$a_i > 0$$,

$$\begin{array}{ll} \underset{x}{\text{minimize}} & \sum\limits_i a_i x_i^2 \\ \text{subject to} & \sum\limits_i x_i = 1 \\ & x_i \ge 0 \\ & \|x\|_0 < T \end{array}$$

Obviously, if i remove the constraints, the minimum to the above would be at $$x=0$$. Also, it it possible to solve the above using constrained quadratic programming. By $$\|x\|_0 < T$$, I mean that the cardinality $$\operatorname{card} (x)$$ to be lower than $$T$$ and I like to choose $$x_i$$ so that it leads to smallest $$f(x)$$ which satisfies the above constraints.

A: I noticed if i sort $$x$$ according to the values $$a_i$$ in the ascending order, then the first $$T$$ choice of $$x$$ would be the optimal choice when we want to have $$\operatorname{card} (x)=T$$. For example, imagine $$f(x) = 2x_1^2+x_2^2+3x_3^2+0.5x_4^2$$ and we want to choose only 2 elements of $$x$$, then the optimal set is $$\{x_4,x_2\}$$ and we can solve the constrained optimization for $$g(x)=x_2^2+0.5x_4^2$$ and having rest of $$x$$ equal to zero.

B: Also, I noticed the optimal answer is in reverse relation to the ratio of $$a_i$$ elements, meaning that $$x_i/x_j=a_j/a_i$$ which will lead to a closed form solution.

Question: Do you have any mathematical way to support A and B in the above?

• Such a constraint is sometimes called a cardinality constraint. Usually we handle this by adding binary variables (indicating whether a variable is active or nonzero). Cardinality constrained portfolio optimization problems form a well known application. Jan 30, 2017 at 12:06
• Regarding my comment in the previous thread, @LinAlg adequately addressed it. If you require the cardinality to be 1, then picking the smallest $a_i$, as I claimed, is correct. Your supposed counterexample had a cardinality of 2, so of course it would be "better". Jan 30, 2017 at 13:19
– Bob
Jan 30, 2017 at 14:20
• All good. Your rewrite is certainly a good one! Jan 30, 2017 at 14:21

As for A, I think the statement is trivial.

Given the answer to $A$, the answer to $B$ is found with the KKT conditions for the problem. Consider $$\min_x \{ \sum a_i x_i^2 : \sum x_i \geq 1, x_i \geq 0 \}$$ where the index $i$ is restricted to the $T$ elements from A. I replaced the equality with an inequality since that simplifies the solution ($\lambda \geq 0$) but clearly does not change the optimal solution. The Lagrangian is: $$L(x) = \sum a_i x_i^2 - \lambda(\sum x_i - 1) - \sum \mu_i x_i$$ The KKT conditions are therefore: $$2a_i x_i - \lambda - \mu_i = 0 \; \forall i, \mu_i x_i = 0 \; \forall i, x \geq 0, \lambda \geq 0, \mu \geq 0, \sum x_i = 1$$ Suppose that for some $i$, $x_i=0$, then $\lambda+\mu_i = 0$, so $\lambda=0$. Then, for all other $i$, $2a_i x_i = \mu_i$, and since $x_i \mu_i = 0$, $x_i = 0$ for all $I$, contradicting $\sum x_i - 1$. So, $x_i > 0$ for all $i$, and $\mu_i = 0$.

The first condition now states that $2a_i x_i$ is constant for all $i$, so $2a_i x_i = 2a_j x_j$, leading to $x_i / x_j = a_j / a_i$.

• How can we be sure you don't need a Lagrange multiplier for the equality constraint? I'm not quite convinced here. Jan 30, 2017 at 13:23
• @MichaelGrant the equality constraint has multiplier $\lambda$, so I don't get your comment. Let me add a multiplier for the nonnegativity constraint though, I must have been confused by thinking about dualization. Jan 30, 2017 at 13:25
• That's what I get for commenting before coffee Jan 30, 2017 at 13:30
• I think it's possible to prove, however, that the values of $x_i$ must be nonnegative, so the inequalities can be dropped. For instance, suppose one or more $x_i$ is negative; then setting $x_i = |x_i|/\sum_j |x_j|$ will yield a smaller objective, since $\sum_j |x_j| > 1$. Jan 30, 2017 at 14:36
• @MichaelGrant seems like you just enjoyed your coffee :) I think it's easier to change the constraint to $\sum x_i \geq 1$. Jan 30, 2017 at 14:56

I'm going to offer my comment as an answer because, frankly, I'm proud to have thought of it this early in the morning ;-)

It turns out that the nonnegativity constraints on $x$ are unnecessary. Suppose that we have an $x$ with one or more negative values, but $\sum_j x_j=1$. Then, since $|x_i|>x_i$ when $x_i<0$, we have $$\sum_j |x_j| > \sum_j x_j = 1.$$ Now consider the vector $y_i = |x_i| / \sum_j |x_j|$. By construction, $\sum_i y_i = 1$, so it too is a feasible solution to the problem. And $$\sum_i a_i y_i^2 = \sum_i a_i \frac{x_i^2}{(\sum_j |x_j|)^2} = \frac{\sum_i a_i x_i^2}{(\sum_j |x_j|)^2} < \sum_i a_i x_i^2.$$ So $y$ has a smaller objective value that $x$, which means $x$ cannot be optimal. That doesn't mean $y$ is optimal, mind you; it just means that $x$ cannot be.

So now we have established that the problem is equivalent to \begin{array}{ll} \text{minimize} & \sum_i a_i x_i^2 \\ \text{subject to} & \sum_i x_i = 1 \end{array} and you can proceed with LinAlg's answer by setting all $\mu_i$ to zero.

• I wish i could accept both as the answers, such a dilemma! But anyway, i really liked it!
– Bob
Jan 30, 2017 at 17:37
• You are kind but it is just fine! Jan 30, 2017 at 17:37