2
$\begingroup$

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?

$\endgroup$
8
  • $\begingroup$ Have you tried minConf? di.ens.fr/~mschmidt/Software/minConf.html $\endgroup$ Jun 26, 2012 at 1:22
  • $\begingroup$ @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. $\endgroup$ Jun 26, 2012 at 1:28
  • $\begingroup$ 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? $\endgroup$ Jun 26, 2012 at 1:51
  • 1
    $\begingroup$ @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. $\endgroup$ Jun 26, 2012 at 2:04
  • 1
    $\begingroup$ 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 $\endgroup$
    – Suvrit
    Jun 26, 2012 at 14:29

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2012 at 14:54
  • $\begingroup$ I don't see how we know that $sum_{i}{\| A_i (x-\lambda_n d_n )\|} = \tau$ has a solution. $\endgroup$ Jul 21, 2012 at 20:36
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jun 27, 2012 at 6:07
  • $\begingroup$ For problems of that size, you'll definitely want to look at first order methods such as the alternating direction method of multipliers. $\endgroup$ Jun 27, 2012 at 14:51
0
$\begingroup$

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

$\endgroup$

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.