11
$\begingroup$

The linear program \begin{align} \min &\sum_{i=1}^nc_{i}x_{i}\\\ \mbox{s.t.:}&\sum_{i=1}^nx_{i}=1,\\\ &x_{i}\geq 0,&&\forall i=1,\dots,n \end{align} has a trivial optimal solution which is to simply: find an $i^*\in\arg\min_{i=1,...,n}\{c_{i}\}$ and then set $x_{i^*}=1$ - the rest of the $x$'s should be zero. However, the quadratic program \begin{align} \min &\sum_{i=1}^nc_{i}x_{i} + \sum_{i=1}^n \beta_{i}x_{i}^2\\\ \mbox{s.t.:}&\sum_{i=1}^nx_{i}=1,\\\ &x_{i}\geq 0,&&\forall i=1,\dots,n, \end{align} doesn't exhibit this nice "single assignment" property. Albeit, the structure is rather simple, and one could expect that there is a simple way to solve the program anyway. So the questions are

  1. Does the quadratic program have a closed form solution, that I just haven't thought of?
  2. If the answer to 1. is "No", what would be your approach to solving (to optimality) this problem fast, given the simple structure?

For my purpose, we can assume that both $c_{i}$ and $\beta_{i}$ are non-negative.

$\endgroup$
1

1 Answer 1

8
$\begingroup$

Fast resolution

Let's start with speeding up the solution process. For the optimal solutions, all variables will be either inactive ($x_i = 0$) or, due to $\sum x_i = 1$, contribute equally to the gradient. So, for some $\gamma$, either:

  • $x_i = 0$ and $c_i \geq \gamma$
  • or $c_i + 2\beta_i x_i = \gamma$

In particular, the active variables will be the ones with smallest $c_i$.

To solve the problem, we sort the variables by $c_i$, and solve the unconstrained problem with $1 \leq k \leq n$ active variables. The solution that satisfies the above equations and the non-negativity constraints is the optimal solution.

Closed form solution

Thankfully, there is a closed form solution for this problem.

Since $x_i = \frac{\gamma - c_i}{2\beta_i}$, $\sum \frac{\gamma - c_i}{2\beta_i} = 1$, you get $\gamma \sum_i \frac{1}{\beta_i} - \sum_i \frac{c_i}{\beta_i} = 2$.

And finally $\gamma = \frac{2 + \sum_i \frac{c_i}{\beta_i}}{\sum_i \frac{1}{\beta_i}}$.

Algorithm

So, now our algorithm is to sort the variables by $c_i$, then compute $\gamma$ for $k$ first variables active, $1 \leq k \leq n$.

Then we find $k$ for which, with some tolerance:

  • the inactive variables satisfy $c_i \geq \gamma$
  • the active variables satisfy $\frac{\gamma - c_i}{2\beta_i} \geq 0$ i.e. $c_i \leq \gamma$

Please check my calculations before using ;)

$\endgroup$
3
  • $\begingroup$ Thanks @prubin for the fixes $\endgroup$
    – Ggouvine
    Jun 24, 2021 at 7:06
  • $\begingroup$ this is very nice indeed. I am not completely sure I can follow everything you're writing. I need to calculate $\gamma$ which is found in your solution, by utilizing that $x_i=\frac{\gamma-c_i}{2\beta_i}$. But that is only true for the active variables, right? And then we use the value of $\gamma$ to figure out which variables should be active. It is most likely a brain-fart from my side, but isn't that kind of circular? Simplifying, I believe the expression for $\gamma$ can be written as \begin{align} \gamma=\frac{2+\sum_{i=1}^n\frac{c_i}{\beta_i}}{\sum_{i=1}^n \frac{1}{\beta_i}} \end{align} $\endgroup$
    – Sune
    Jun 24, 2021 at 12:53
  • $\begingroup$ Your formula is cleaner: I added it to the post. It may be clearer if you analyze it as an active set algorithm: we solve the problem with a given set of variables active, then check if some variables need to leave the set ($c_i > \gamma$) or enter it ($c_i < \gamma$). Indeed, $x_i = \frac{\gamma - c_i}{\beta_i}$ is only true for the active variables: all others are 0. $\endgroup$
    – Ggouvine
    Jun 25, 2021 at 11:04

Your Answer

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

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