Minimizing quadratic objective function on the unit $\ell_1$ sphere

Question

I would like to solve the following optimization problem using a quadratic programming solver

$$\begin{array}{ll} \text{minimize} & \dfrac{1}{2} x^T Q x + f^T x\\ \text{subject to} & \displaystyle\sum_{i=1}^{n} |x| = 1\end{array}$$

How can I re-write the problem using linear constraints?

Note: I have read other similar questions. However, they define the absolute value differently.

Answer 1

In one of the other answers (unfortunately now deleted) it is incorrectly assumed that we can apply a standard variable splitting technique, without worrying that both the positive and negative parts can become nonzero. I posted a comment already that this probably needs some additional binary variables to fix this. Let me try to show how I would implement this. I assume we have some upper bounds and lower bounds $U_i, L_i$ on $x_i$, i.e. $x_i \in [L_i,U_i]$ where $U_i>0$ and $L_i<0$. Then:

$$\begin{align} &x_i = x^{plus}_i - x_i^{min} \\ &x_i^{abs} = x^{plus}_i + x_i^{min} \\ &x_i^{plus} \le U_i \delta_i \\ &x_i^{min} \le -L_i (1-\delta_i) \\ &\sum x_i^{abs} =1 \\ &\delta_i \in \{0,1\}\\ &x^{plus}_i \ge 0 \\ &x^{min}_i \ge 0 \\ &x^{abs}_i \ge 0 \\ \end{align}$$

You need a MIQP solver to handle this (Cplex and Gurobi can do this).

Answer 2

This is not possible. The set $$\{x \in \mathbb R^n \mid \sum_{i=1}^n |x_i| = 1\}$$ is not convex, but the feasible set of a quadratic program is convex.