Analytic formula for minimizer of $f(x) := \sqrt{(x-a)^\top S(x-a)}+ r \|x\|_2$

Question

Let $S$ be a positive-definite $n \times n$ matrix and define $\|z\|_S := \sqrt{x^\top S x}$ for any $x \in \mathbb R^n$. Let $a$ be a fixed vector in $\mathbb R^n$ and $r \ge 0$, and consider the function $f:\mathbb R^n \to \mathbb R$ defined by $f(x) := \|x-a\|_S + r\|x\|_2$.

Question. Is there an analytic formula for the minimizer $x_{opt}$ of $f$ ?

Solution for special case where $S = \sigma^2 I_n$

Here, one has $f(x) = \sigma g(x)$, where $g(x) := \|x-a\|_2 + (r/\sigma) \|x\|_2$. Now, if $r \ge \sigma$, then for all $x \in \mathbb R^n$, it holds that $$ g(x) \ge \|x-a\|_2 + \|x\|_2 \ge \|a\|_2 = g(0). $$ Likewise, if $r \le \sigma$, then for all $x \in\mathbb R^n$ it holds that $$ g(x) \ge (r/\sigma) (\|x-a\|_2 + \|x\|_2) \ge (r/\sigma)\|a\|_2 = g(a). $$

We conclude that \begin{eqnarray} x_{opt} = \begin{cases} a,&\mbox{ if }r \le \sigma,\\ 0,&\mbox{ else.} \end{cases} \end{eqnarray}

Answer 1

Here is what you can do. Replacing $S$ with $S/r^2$, we assume that $r=1$.

Passing to the principal axes of $S$, we may assume that $S=\mathop{\mathrm{diag}}(s_1,\dots,s_n)$. Now we also assume that $a=[a_1,\dots,a_n]^T$ with $a_i\geq 0$. So we want to minimize $$ f(x)=\sqrt{\sum_{i=1}^n |x_i|^2}+\sqrt{\sum_{i=1}^ns_i|a_i-x_i|^2}. $$

Take the minimizer; clearly, $0\leq x_i\leq a_i$ for all $i$. In particular, if $a_i=0$, then clearly $x_i=0$, and we can get rid of those coordinates. Now we assume $a_i>0$, and it is easy to see that $x_i\in(0,a_i)$.

Taking derivative with respect to $x_i$, we get $$ \frac{x_i}{b}=\frac{s_i(a_i-x_i)}c. $$ where $b=\|x\|$ and $c=\|a-x\|_S$. Denoting $t=b/c\in[0,+\infty]$, we arrive at $$ s_i(a_i-x_i)=tx_i, \quad\text{or}\quad x_i=\frac{s_ia_i}{t+s_i}, $$ so the minimizer lies on a fixed curve (parametrized by $t$).

To optimize in $t$, we need to chect that $t$ is indeed equal to $\|x\|/\|a-x\|_S$, i.e., that $$ \sum_i\frac{(s_ia_i)^2}{(t+s_i)^2}=t^2\sum_i\frac{s_i(s_ia_i)^2}{(t+s_i)^2}. $$ I doubt this (algebraic) equation can be solved explicitly; but its solution (at least one of them) provides a desired point.