## Efficient Algorithm For Projection Onto A Convex Set

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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 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 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 at 1:51

1
@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 at 2:04

1
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/… – S. Sra Jun 26 at 14:29
show 3 more comments

## 3 Answers

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 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 at 20:36

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

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$?

Your problem is an example of a "sum of norms" optimization problem. Searching with Google Scholar will lead you to published research on this class of problems.

CVX is using a standard approach for solving this problem by reformulating it as a second order cone programming (SOCP) problem and then using a primal-dual interior point method (SeDuMi's or SDPT3) to solve the resulting SOCP. For small problem instances, this should be a very robust and reasonably fast approach to solving the problem, but there are faster primal-dual codes for SOCP available (both CPLEX and MOSEK can be used to solve SOCP's.) You could ask CVX to extract the SOCP problem and export it in SeDuMi format and then try to use another solver on the SOCP.

You might also look at first order methods to solve the SOCP- For example, I believe that TFOCS could be used to solve the problem.

-

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 at 6:07
For problems of that size, you'll definitely want to look at first order methods such as the alternating direction method of multipliers.   – Brian Borchers Jun 27 at 14:51

Check out Dattorro's convex optimization book, page 748.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 21, "mathjax_display_tex": 4, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9429044127464294, "perplexity_flag": "head"}