Closed-form value for $\min_{x^T\Sigma x \le 1}\|x\|_1 - x^Ta$

Question

Let $a \in \mathbb R^n$ and $\Sigma$ be a positive definite matrix of size $n$.

Question

What is the closed-form value of

$$\min_{\|x\|_\Sigma \le 1}\|x\|_1 - x^Ta, $$

where $\|x\|_\Sigma := \sqrt{x^T\Sigma x}$ is the norm induced by by the inner product $(x, y) \mapsto x^T\Sigma y$ ?

Answer 1

It has been suggested in the comments that the solution value might not be analytically expressible in general, but that there is some hope, when the matrix $\Sigma$ is diagonal. I'm going to provide a solution hereunder. Also, I'm bad at using Lagrange multiplies (e.g I always screw up the signs, etc.). I'm going to attempt a more "synthetic" solution.

Now, using the dual representation of the $\ell_1$-norm, one has

$$ \begin{split}\alpha:=\min_{\|z\|_\Sigma \le 1} \|z\|_1 - z^Ta &= \min_{\|z\|_\Sigma \le 1}\max_{\|w\|_\infty \le 1}z^Tw-z^T a =\max_{\|w\|_\infty \le 1}\min_{\|z\|_\Sigma \le 1}z^T(w-a)\\ &=\max_{\|w\|_\infty \le 1}-\left(\max_{\|z\|_\Sigma \le 1}-z^T(w-a)\right)=\max_{\|w\|_\infty \le 1}-\|w-a\|_{\Sigma^{-1}}\\ &=-\min_{\|w\|_\infty \le 1}\|w-a\|_{\Sigma^{-1}}, \end{split} $$

where I've used Sion's minimax theorem to interchange min and max. The above expression for the optimal objective value $\alpha$ is unlikely to be computable analytically in general, due to the non-separability of the objective (even though the constraint is perfectly separable as a product of 1D constraints).

In any case, it follows from the above display that $\alpha \le 0$, with equality iff $\|a\|_\infty \le 1$.

Exact formula for diagonal $\Sigma$

In the special case where $\Sigma=\text{diag}(\sigma_1,\ldots,\sigma_2)$, the square of the optimal objective value $\alpha^2$ can be separated as

$$ \alpha \le 0,\;\alpha^2 = \sum_{i=1}^n\min_{|w_i| \le 1}\sigma_i^{-2}(w_i-a_i)^2 = \sum_{i=1}^n\sigma_i^{-2}\begin{cases}(a_i+1)^2,&\mbox{ if }a_i \le -1,\\ 0,&\mbox{ if }-1 < a_i \le 1,\\ (a_i-1)^2,&\mbox{ if }a_i > 1,\end{cases} $$

which is indeed an analytical formula, albeit a very "hairy" one.

Upper and lower bounds for general $\Sigma$

Let $\sigma_n \ge \ldots \ge \sigma_2 \ge \sigma_1 > 0$ be the eigenvalues of $\Sigma$. Then, one has $$ \sigma_n^{-1}\|w-a\|_2 \le \|w-a\|_{\Sigma^{-1}} \le \sigma_1^{-1}\|w-a\|_2. $$ Thus one has the bounds

$-\sqrt{\gamma/\sigma_1} \le \alpha \le -\sqrt{\gamma/\sigma_n}$, where $\gamma := \sum_{i=1}^n\begin{cases}(a_i+1)^2,&\mbox{ if }a_i \le -1,\\ 0,&\mbox{ if }-1 < a_i \le 1,\\ (a_i-1)^2,&\mbox{ if }a_i > 1.\end{cases}$

Moreover, if $\|a\|_\infty > 1$, then it isn't hard to see that $\gamma \le n(\|a\|_\infty-1)$ (see details below), from where $\alpha \ge -\sqrt{\gamma/\sigma_1} \ge -\sqrt{n/\sigma_1}(\|a\|_\infty-1)$, which corresponds to a bound which has been observed by someone in the comments. However, by construction, this bound is potentially very loose.

---

Note that $a_i \le -1 \implies (a_i + 1)^2 \le (\|a\|_\infty - 1)^2$ and similarly $a_1 > 1 \implies 0 \le (a_i - 1)^2 \le (\|a\|_\infty-1)^2$. Thus $\gamma \le n(\|a\|_\infty-1)$.