# Efficient Algorithm For Projection Onto A Convex Set

Given $\mathbf{x} \in \mathbb{R}^n$ and $\tau$ a scalar, I would like to solve the following Euclidean projection problem:

$\underset{\mathbf{p}}{\mathrm{argmin}} \; \|\mathbf{p}-\mathbf{x}\|_2 \;\; \mathrm{s.t.} \;\; \displaystyle \sum_{i}{ \left \| \left [ \begin{array}{c} \mathbf{f}_i^\mathrm{T} \\ \mathbf{g}_i^\mathrm{T} \end{array} \right] \cdot \mathbf{p} \right \|_2 } \leq \tau$,

where $\mathbf{f}_i,\mathbf{g}_i \in \mathbb{R}^n$.

The above is a convex function over a convex set and as such should have a unique solution. Moreover, we can find the upper bound on the summation as follows:

$\displaystyle \sum_{i}{ \left \| \left [ \begin{array}{c} \mathbf{f}_i^\mathrm{T} \\ \mathbf{g}_i^\mathrm{T} \end{array} \right] \cdot \mathbf{p} \right \|_2 } \leq \|\mathbf{p}\|_2 \cdot \sum_i \sigma_i$,

where $\sigma_i$ is the operator norm of the $2 \times n$ matrix $[\mathbf{f}_i \;\; \mathbf{g}_i]^{\mathrm{T}}$.

I have been using CVX to solve the above, but it's just too slow in its current form. I have not figured out how to make use of them, but the operator norms are easily found before-hand. Can anyone suggest a re-formulation of the above or an algorithm that is tailored to these types of problems?

-
Have you tried minConf? di.ens.fr/~mschmidt/Software/minConf.html –  Vidit Nanda Jun 26 '12 at 1:22
@Vel Nias: I looked at minConf but unless I have misread the page, it requires one to provide a function to compute the projection onto the convex set, which is the problem I am trying to find an efficient solution for. –  AnonSubmitter85 Jun 26 '12 at 1:28
I'm confused: aren't you trying to minimize the distance to a fixed $x \in \mathbb{R}^n$ constrained by a single convex inequality? It sounds like "distance to $x$" is the function that you should use. Have I misunderstood? –  Vidit Nanda Jun 26 '12 at 1:51
@Vel Nias: I think you understand things correctly. However, in order to use either minConf_SPG() or minConf_SPG() I have to supply a projection function of the form: funProj(x) = argmin_y ||x - y||_2, subject to y is in X. Is this not the very problem I trying to solve? I am left looking at minConf thinking it is for problems for which my problem above is only a sub-problem. –  AnonSubmitter85 Jun 26 '12 at 2:04
Either you can solve it as an SOCP (presumably that's something you've already tried), or you can use an ADMM style method to solve it. The details are somewhat messy, but it seems that one can do a fairly good job of efficiently solving this. Some of the key ideas that you can exploit, are discussed in the paper: Barbero and Sra (2011), people.kyb.tuebingen.mpg.de/suvrit/work/papers/icml11.pdf –  Suvrit Jun 26 '12 at 14:29

It's easier to just write $A_i = [f_i \ g_i]^T$ so then the problem is:

$$\min_p \frac{1}{2}\|x-p\|^2 \quad \mbox{s.t. } \sum_i \|A_ip\| \le \tau$$

Forming the Lagrangian and minimizing shows that the optimal $p^*$ satisfies:

$$p^* = x - \lambda^* \sum_i A_i^T \frac{ A_i p^* }{ \|A_i p^* \|}$$

So one obvious thing to try is just iterating this equation. We can solve for $\lambda^*$ with a 1-dimensional root-finding procedure since we know that $\sum_i \|A_i p^*\| = \tau$ (assuming that $x$ is not already in the interior of the feasible region). In summary, we iterate:

$$d_n = \sum_i A_i^T \frac{ A_i p_{n-1} }{ \|A_i p_{n-1} \|}$$ $$p_n = x - \lambda_n d_n, \mbox{ where } \lambda_n \mbox{ is given by } \sum_i \|A_i(x - \lambda_n d_n)\| = \tau$$ Of course, you need to be careful not to divide zero by zero in case $A_i p_n=0$. Unfortunately, I don't know if this procedure converges, but it might be sufficient for your purposes.

-
This iteration is a simple version of what is called "the method of multipliers" in optimization. Its convergence isn't robust, but can be improved by using an augmented Lagrangian to stabilize the algorithm. –  Brian Borchers Jun 27 '12 at 14:54
I don't see how we know that $sum_{i}{\| A_i (x-\lambda_n d_n )\|} = \tau$ has a solution. –  AnonSubmitter85 Jul 21 '12 at 20:36
You haven't told us anything about the size of your problem instances. How many terms are there in the sum of norms? What is $n$?
I am working with images, so each $n$ is the total number of pixels and there will be $n+p-1$ terms in the sum of norms, where $p$ will probably be less than 20 . I am currently trying to get a rough cut working, so I am using smaller images, say, $100 \times 100 \Rightarrow n = 10000$. However, I'd like to use more realistic image sizes, so $n$ could be over a million. –  AnonSubmitter85 Jun 27 '12 at 6:07