1

How do I minimize the following objective function?

$$f(\theta) = \frac{1}{2}(\theta - z)^2 + \min_{\gamma \geq 0} \left\{\gamma |\theta| + \frac{a}{2}(\gamma - \lambda)^2 \right\}$$

where $z \in \mathbb{R}$, $\lambda > 0$, $a > 1$. I would share my attempt but I've not made any progress. Any hints would be much appreciated. For some context, the $\min \{ \cdot \}$ term here is equivalent to the minimax concave penalty $\rho(t,\lambda) = \lambda \int_0^t (1 - x/(a\lambda))_+dx$.

I'm adding the solution in case it helps. I'm mostly interested in the approach used to solve this rather than the solution itself.

$$\hat{\theta} = \begin{cases} \frac{a}{a-1}\text{sign}(z)(|z|-\lambda)_+ & \text{if } |z| < a\lambda \\ z & \text{if } |z| \geq a\lambda\end{cases}$$

user3294195
  • 479

1 Answers1

1

Firstly, note that the minimization over $\gamma$ is a convex optimization problem. If we set the derivative inside to zero, we get the candidate solution $\gamma^* = \lambda - \frac{\left\lvert\theta\right\rvert}{a}$; this will be the solution if it is greater than zero (which requires $\left\lvert \theta \right\rvert \leq \lambda a$), otherwise, we will have $\gamma^* = 0$.

You can plug this into the expression for $f(\theta)$ to obtain

$$ f(\theta) = \begin{cases} \frac{1}{2}(\theta - z)^2 + \frac{a\lambda^2}{2}, \:\: \text{if } \left\lvert \theta \right\rvert > \lambda a\\ \frac{1}{2}(\theta - z)^2 + \lambda \left\lvert \theta \right\rvert - \frac{\theta^2}{2a}, \:\: \text{if } \left\lvert \theta \right\rvert \leq \lambda a \end{cases} $$

Note that both pieces are convex since $a > 1$. To find the optimal solution $\hat{\theta}$, you find the optimal solution of each piece separately, and compare them to see which one is better.

For the first piece above, the optimal solution is $z$ if $\left\lvert z \right\rvert \geq \lambda a$, the optimal solution is $+\lambda a$ if $0 < z < \lambda a$, and the optimal solution is $-\lambda a$ if $0 > z > -\lambda a$, and the optimal solution is $\pm \lambda a$ if $z = 0$. I determined these by setting the derivative to zero, or looking at a boundary point.

For the second piece above, the optimal solution is $\frac{a}{a-1} (z-\lambda)$ if $\lambda \leq z \leq \lambda a$ and the optimal solution is $\frac{a}{a-1} (z+\lambda)$ if $-\lambda \geq z \geq -\lambda a$.

Can you take it from here?

madnessweasley
  • 1,723
  • Thanks, the case with $|\theta| > \lambda a$ works fine, but for the other case, the derivative I get involves $\text{sign}(\theta)$. How does that go from there to the final solution involving $\text{sign}(z)$? – user3294195 Aug 08 '19 at 01:50
  • Also, the cases involve $|\theta|$ in the expression for $f(\theta)$ but $|z|$ in the final solution. This makes sense intuitively (obviously the final solution cannot involve cases for $|\theta|$), but how do you formalize it? – user3294195 Aug 08 '19 at 01:58
  • Well, you optimize each piece separately and then check which piece the minimum corresponds to. I'll add some details soon – madnessweasley Aug 08 '19 at 02:34
  • @user3294195 Added more details – madnessweasley Aug 08 '19 at 02:44
  • Thanks again, much appreciated. – user3294195 Aug 08 '19 at 02:47