1
$\begingroup$

I have the following optimization problem: $$\min_{x} \sum a_i{x_i}^2 \\ s.t. x_i \ge 0 \\ \sum x_i=1 \\ \|x\|_0<T$$

Where $a_i > 0$.

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

Experimental Answer:

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 $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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Erwin Kalvelagen Jan 30 '17 at 12:06
  • $\begingroup$ 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". $\endgroup$ – Michael Grant Jan 30 '17 at 13:19
  • $\begingroup$ @MichaelGrant: Maybe i had a miss-interpretation about that comment! :-) $\endgroup$ – Bob Jan 30 '17 at 14:20
  • $\begingroup$ All good. Your rewrite is certainly a good one! $\endgroup$ – Michael Grant Jan 30 '17 at 14:21
4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ How can we be sure you don't need a Lagrange multiplier for the equality constraint? I'm not quite convinced here. $\endgroup$ – Michael Grant Jan 30 '17 at 13:23
  • 1
    $\begingroup$ @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. $\endgroup$ – LinAlg Jan 30 '17 at 13:25
  • $\begingroup$ That's what I get for commenting before coffee $\endgroup$ – Michael Grant Jan 30 '17 at 13:30
  • 1
    $\begingroup$ 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$. $\endgroup$ – Michael Grant Jan 30 '17 at 14:36
  • 1
    $\begingroup$ @MichaelGrant seems like you just enjoyed your coffee :) I think it's easier to change the constraint to $\sum x_i \geq 1$. $\endgroup$ – LinAlg Jan 30 '17 at 14:56
2
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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