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?
Best Answer
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.