Find maximum $\theta$ such that $|x + \theta a| \leq b$

Question

I have an optimisation problem:

$$ \max_{\theta} \quad \theta \\ \text{such that} \qquad |x + \theta a| \leq b $$

where $x, a \in \mathbb{R}^{n}$. We know that $|x| \leq b$. The norm referred to here is the $\ell_{1}$-norm.

Is there a simple way to solve this kind of optimisation problem that does not require using a full blown convex optimisation technique? Given that the problem is one dimensional my only thought was to solve this problem for different intervals of $\theta$ manually. i.e. for $\theta \in [0, 10]$ we may know that $x_{1} + \theta a_{1} \leq 0$ and $x_{i} + \theta a_{i} \geq 0$ for all $ 1< i \leq n$. Then we can replace the constraint with a simple sum and solve. But this would still require a number of checks dependent on the dimension of $a$ which I would like to avoid if possible. Does this problem have a well known analytical solution?

Answer 1

The function $f(\theta) =||x-\theta a||_1$ is piecewise linear and you know $f(0) \leq b$. Here is an $\mathcal{O}(n\log n)$ algorithm:

1. Precompute the breakpoints $x_i / a_i$ and sort the positive breakpoints in ascending order.

2. Set $\theta^0=0$ and compute $f(\theta^0)$ and $f_+'(\theta^0)$ (the right derivative).

3. Iteratively move to the next breakpoint $\theta^{k+1}$, and check if $f(\theta^{k+1})=f(\theta^k) + f_+'(\theta^k)(\theta^{k+1}-\theta^k) \leq b$. If yes, set $f_+'(\theta^{k+1}) := f_+'(\theta^k) + 2|a_{i(k)}|$ and repeat this step. If no (or if there is no next breakpoint), solve $f(\theta^k) + f_+'(\theta^k)(\theta^{k+1}-\theta^k) = b$ for the solution.

Answer 2

Here is one computational solution:

We can write the constraint as $\sum_{a_k \neq 0} |x_k+\theta a_k| = b-\sum_{a_k = 0} |x_k|$, so we can suppose that $a_k \neq 0$ for all $k$.

Let $f(\theta) = \|x+\theta a\|_1$, we are given that $f(0) \le b$. Note that $f$ is convex and piecewise affine.

Let $\theta_k^*$ solve $x_k+\theta a_k = 0$ and note that $f(\theta) = \sum_k |a_k| |\theta-\theta_k|$.

Let $B = \{ \theta_k^* | \theta_k^* >0 \} \cup \{0\}$. Sort the collection into $t_0=0,t_1,...,t_m$

If $f(t_m) \le b$ and $\theta \ge t_m$ then $f(\theta) = \sum_k |a_k| (\theta-\theta_k)$ and so the solution is given by $\theta^* = {b + \sum_k \theta_k^* |a_k| \over \sum_k |a_k| }$.

Otherwise we have $f(t_m) >b$. Find the largest index $k$ such that $f(t_k) \le b$, then we know that the solution lies in $[t_k,t_{k+1})$ and is given by $\theta^* = \lambda t_{k+1} + (1-\lambda)t_k$ where $\lambda = {b - f(t_k) \over f(t_{k+1})-f(t_k)}$.