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.

Improve this question
$\endgroup$
8
  • $\begingroup$ Is this a homework? Closing as it is not a research question. $\endgroup$
    – Suvrit
    Sep 9, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 15:08

2 Answers 2

Reset to default
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"

Improve this answer
$\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, 2018 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, 2018 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, 2018 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, 2018 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).

Improve this answer
$\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, 2018 at 19:12

Your Answer

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

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