0

I have a simple and light quadratic programming problem that I need to solve, as following: \begin{align} & \underset{x}{\arg\min} & & \dfrac{1}{2}x^T x-z^T x\\ & \text{subject to} & & \sum_{i=1}^n x_i=1,\\ & & & x_i\geq 0\;\forall i\in\{1,\ldots,n\},\\ & & & x=\left[x_1,\ldots,x_n\right]^T, z=\left[z_1,\ldots,z_n\right]^T. \end{align}

where $z$ is a constant vector.
I know there are methods like barrier method or interior-point method that can be used to solve such a problem, but I feel like this problem probably does not require a complicated method like those?

Is there any light solution that I could use to solve such a problem?

Thanks.

  • Is $z$ a variable? Without any restrictions? Also $x>0$ is a difficult concept in optimization ($x\ge0$ is more digestable). – Erwin Kalvelagen Mar 14 '16 at 01:07
  • yes, z is a vector without any restrictions. Yes it should be x>=0. Sorry about this. @ErwinKalvelagen –  Mar 14 '16 at 01:20
  • Looks like an unbounded problem to me. Actually I think $z$ is not a variable but a constant. – Erwin Kalvelagen Mar 14 '16 at 01:26
  • The qp algorithm of Goldfarb and Idnani is widely used (e.g. in R quadprog). – Erwin Kalvelagen Mar 14 '16 at 01:46
  • @ErwinKalvelagen Yes it is a constant vector. Sorry that I was not clear before. –  Mar 14 '16 at 03:23
  • @ErwinKalvelagen Thanks, but my goal is to implement that quadratic programming method. I only need a light solution that is enough to solve the above problem though. –  Mar 14 '16 at 03:24

1 Answers1

2

We have the following property: $$ \frac{1}{2} x^T x - z^T x = \frac{1}{2}(x^T x - 2 z^T x) = \frac{1}{2}||x - z||_2^2 - \frac{1}{2}z^T z = \frac{1}{2}||x - z||_2^2 + CONST $$ Hence, your problem is equivalent to: $$ \begin{aligned} \operatorname*{argmin}_x &\quad \frac{1}{2} ||x - z||^2 \\ \text{subject to} &\quad \sum_{i=1}^n x_i = 1 \\ &\quad x \geq 0 \end{aligned} $$

This the well known problem of projecting $z$ onto the unit simplex, and can be solved in $O(n \log n)$ time. You can google it, or look here.

Community
  • 1
Alex Shtoff
  • 12
  • Hum... you can project onto a simplex in linear time. There are methods due to Duchi et al. (a randomized algo, so $\mathcal O(n)$ complexity is in an ergodic sense), Condat et al. (deterministic, but complicated), etc. – dohmatob Mar 14 '16 at 13:52
  • Thanks. I have tried to derive a $O(n)$ solution during the weekend. I will verify it and see if it's correct and worth posted here. –  Mar 14 '16 at 18:05
  • @dohmatob Thanks. I will check their methods. –  Mar 14 '16 at 18:12