4
$\begingroup$

Given an $n$-dimensional vector $\mathbf{c}\in [0,1]^n$, let $\Delta_{\mathbf{c}}$ be the set of points $\{\mathbf{x}\in [0,1]^n: \langle \mathbf{c},\mathbf{x} \rangle \le 1\}$, where $\langle \mathbf{c},\mathbf{x} \rangle$ is the inner product between $\mathbf{c}$ and $\mathbf{x}$.

Question: Given $\mathbf{c}$ and a vector $\mathbf{z}\in [0,1]^n$, how can we efficiently compute the projection $P(\mathbf{z}, \Delta_{\mathbf{c}})$ of $\mathbf{z}$ onto $\Delta_{\mathbf{c}}$?


By writing $P(\mathbf{z}, \Delta_{\mathbf{c}})$, we mean $\arg\min_{\mathbf{z'}\in\Delta_{\mathbf{c}}} \Vert \mathbf{z'}-\mathbf{z} \Vert$, where $\Vert \cdot \Vert$ denotes the regular Euclidean norm.

$\endgroup$
8
  • $\begingroup$ Is this a homework? Closing as it is not a research question. $\endgroup$ – Suvrit Sep 9 '18 at 23:49
  • $\begingroup$ @Suvrit Are you sure? Note that everything happens inside $[0,1]^n$ and that $\Delta_c$ is actually not a hyperplane. $\endgroup$ – Dirk Sep 10 '18 at 4:43
  • $\begingroup$ @Dirk: Project z to the plane, then restrict all entries of the projection to $[0,1]$. $\endgroup$ – Jan-Christoph Schlage-Puchta Sep 10 '18 at 8:02
  • $\begingroup$ @Jan-ChristophSchlage-Puchta No, this will throw you off the hyperplane. Of course, you could project onto the plane and the cube alternatingly until converged good enough, but I am not sure if this would qualify as "fast". $\endgroup$ – Dirk Sep 10 '18 at 8:29
  • 1
    $\begingroup$ @PenelopeBenenati You are welcome! Sorry for my presumption, though would have been great if you had provided some extra context (as motivation) in your question, to avoid the "this is homework" statement :-) -- it is quite an interesting optimization subproblem whose solution deserves to be better known. $\endgroup$ – Suvrit Sep 11 '18 at 15:08
2
$\begingroup$

As noted in the comments, this problem is not really a research level problem. Afaik, versions of it were originally solved in the 50s.

Here is an entire survey that discusses efficient algorithms (including linear-time procedures) for this problem as well as generalizations of it: M. Patriksson, A survey of classic core problems in operations research, 2005, Technical Report, Chalmers University.

If you want a more immediate answer with code (has only $\ge 0$ constraints, but handling upper bounds is easy), have a look at: Condat's L1 projection code

Another useful search time: "Continuous quadratic knapsack"

$\endgroup$
4
  • $\begingroup$ I would be interested in how to adapt Condat's projection code to upper bounds. At least the simple rule $P(z) = \max(z-\tau,0)$ fails and need to be replaced. $\endgroup$ – Dirk Sep 10 '18 at 11:20
  • $\begingroup$ @Dirk: Please check the listed references in the answer; O(n log n) methods are easy, while O(n) can also be done (by suitable breakpoint finding, or a variety of other such methods). $\endgroup$ – Suvrit Sep 10 '18 at 19:13
  • $\begingroup$ @Suvrit, thank you for your answers! I honestely did not know it can be seen as a simple homework. I am working on writing a paper and this problem simply lies outside my area of expertise. $\endgroup$ – Penelope Benenati Sep 11 '18 at 4:07
  • 1
    $\begingroup$ I think a reference to "Breakpoint searching algorithms for the continuous quadratic knapsack problem" by Krzysztof C. Kiwiel would be helpful (treats the general case and has pseudo-code).Or add that the optimal $z'$ is $\min(\max(0,z-t\mathbb{1}),\mathbb{1})$ where $t$ solves $\sum_i\min(\max(0,z_i-t),1) = 1$. $\endgroup$ – Dirk Sep 11 '18 at 6:57
3
$\begingroup$

So you want to project $z$ onto the intersection of two convex sets $$C = \{x\mid \langle x, c\rangle \leq 1\}$$ and $$D = \{x\mid 0\leq x_i\leq 1\}.$$ The projection onto each of them is straightforward: $$ P_C(z) = \begin{cases} z - \frac{\langle z,c\rangle-1}{\|c\|^2}c, &\text{if $\langle z,c\rangle>1$,}\\ z, & \text{otherwise} \end{cases} $$ and $$ P_D(z)_i = \max(\min(z_i,1),0). $$ To project onto the intersection you could use quadratic programming, of course, but here is a low-tech variant:

Alternating projections. Initialize with $z^0 = z$ and iterate $$ z^{k+1} = P_D(P_C(z^k)) $$ which converges to the desired projection $P_{C\cap D}(z)$. You could also use Dykstra's projection algorithm, but in my experiments both are about equally fast.

I don't know what value of $n$ you have in mind, but it seems that the number of iterations needed for convergence scales with $n$ not so favorably (at least for the random instances I produced).

$\endgroup$
1
  • 1
    $\begingroup$ As I noted in my answer below, this problem can be solved non-iteratively, and in O(n) time, check the continuous quadratic knapsack for sure! $\endgroup$ – Suvrit Sep 10 '18 at 19:12

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.