Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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
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 '12 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/icml11.pdf –  Suvrit Jun 26 '12 at 14:29

3 Answers 3

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.

share|improve this answer
    
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$?

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.

share|improve this answer
    
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
    
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 '12 at 14:51

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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