# Efficient projection onto the intersection of a scaled Euclidean ball and the unit simplex

Let $$y \in \mathbb{R}^n$$ be a given point, and $$\alpha \in \mathbb{R}^n_+$$ and $$r > 0$$ be given parameters. What is an efficient way to project $$y$$ onto the set $$S := \left\lbrace x \in \mathbb{R}^n \: : \: x \geq 0, \sum_i x_i = 1, \sum_i \alpha_i x^2_i \leq r \right\rbrace$$ that is the intersection of a (scaled) Euclidean ball and a simplex (assuming $$S \neq \emptyset$$)?

I can think of three plausible approaches:

1. Solve the projection problem directly using a convex QCQP solver (such as CPLEX/Gurobi)
2. Use the method of alternating projections by projecting alternately on the simplex and the scaled Euclidean ball, but I am not sure that this will yield the projection even in the limit
3. Following the approach outlined here, we can write the Lagrangian as $$L(x,\mu,\lambda) := \frac{1}{2} \left\lVert x - y \right\rVert^2 + \mu \left( \sum_i x_i - 1 \right) + \lambda \left(\sum_i \alpha_i x^2_i - r \right)$$ and the dual function as $$g(x,\mu,\lambda) := \min_{x \geq 0} L(x,\mu,\lambda).$$ The solution to the dual problem is then $$x^*_i = \left(\frac{y_i - \mu}{1+2\alpha_i\lambda}\right)_+, \quad \forall i \in \{1,\cdots,n\}.$$ The KKT conditions yield $$\sum_i \left(\frac{y_i - \mu}{1+2\alpha_i\lambda}\right)_+ = 1, \quad \lambda \geq 0, \quad \lambda \left(\sum_i \alpha_i (x^*_i)^2 - r \right) = 0, \quad \sum_i \alpha_i (x^*_i)^2 \leq r.$$ We can first check if $$\lambda = 0$$ satisfies the KKT conditions; if not, we could use bisection over $$\lambda$$ (with a large upper bound for $$\lambda$$), which fixes the value of $$\lambda$$ at a positive value and tries to solve the nonlinear system of equations $$\sum_i \left(\frac{y_i - \mu}{1+2\alpha_i\lambda}\right)_+ = 1, \quad \sum_i \alpha_i \left(\frac{y_i - \mu}{1+2\alpha_i\lambda}\right)^2 - r = 0,$$ for $$\mu$$ using bisection or the approach suggested here.

Is there a faster approach that can exploit the problem structure? I wish to solve this projection problem on the order of a million times within my algorithm, so speed is critical.

EDIT: The dimension $$n$$ is around $$1000$$. For $$n = 1000$$, Gurobi takes $$\approx 0.1$$ seconds on my laptop for each projection step. I'm hoping to reduce the time at least by an order of magnitude.

• How large is $n$? Apr 18, 2020 at 23:33
• @littleO $n$ is around $1000$ Apr 18, 2020 at 23:34
• Thanks. How fast are you hoping to be able to solve a million instances of this problem? Apr 18, 2020 at 23:35
• @littleO Gurobi takes $\approx 0.1$ seconds for each projection step. I'm hoping to reduce the time at least by an order of magnitude. Apr 18, 2020 at 23:44
• I think @littleO is referring to CVXGEN cvxgen.com/docs/index.html .That does not handle QCQP (or SOCP). Apr 19, 2020 at 14:00