1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ How large is $n$? $\endgroup$
    – littleO
    Apr 18, 2020 at 23:33
  • $\begingroup$ @littleO $n$ is around $1000$ $\endgroup$ Apr 18, 2020 at 23:34
  • $\begingroup$ Thanks. How fast are you hoping to be able to solve a million instances of this problem? $\endgroup$
    – littleO
    Apr 18, 2020 at 23:35
  • $\begingroup$ @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. $\endgroup$ Apr 18, 2020 at 23:44
  • 2
    $\begingroup$ I think @littleO is referring to CVXGEN cvxgen.com/docs/index.html .That does not handle QCQP (or SOCP). $\endgroup$ Apr 19, 2020 at 14:00

0

You must log in to answer this question.