Minimizing quadratic cost function over an Euclidean ball

42 Views Asked by At

Let $f : \mathbb{R}^d \to \mathbb{R}$ be defined by

$$f(\theta) := \| \theta - z \|^2_\Delta := (\theta-z)^t \Delta (\theta-z)$$

where $\Delta = \operatorname{diag}(s_1, \ldots, s_d)$, where $s_i > 0$ and $\|s\|_1 \leq 1$. I am tasked with finding

$$\theta^* = \arg\underset{\| \theta \|_2 \leq D}{\min} f(\theta)$$

in the context of implementing the ADAGRAD algorithm:

Adagrad

From the KKT conditions I got the Lagrangian:

$$\mathcal{L}(\theta,\mu)=(\theta-z)^t\Delta (\theta-z)+\mu(\|x\|^2_2 - D^2)$$ and its gradient: $$\nabla_{\theta} \mathcal{L}(\theta,\mu)=2\Delta (\theta-z)+2\mu\theta $$ which gives the saddle point $$\theta^*=(\Delta+\mu^* I)^{-1}\Delta z, \qquad \mu^* = \left(\sum_{i=1}^d s_i^2 (\theta^*_i-z_i)^2 \right)^{1/2}$$ from the stationarity of the Lagrangian but I couldn't solve for $\theta^*$ explicitly. Any help is appreciated, as I don't even know the answer and if this is solvable or I'm missing a piece of info.

Edit: I think the actual update step my notes are referring to is found on page 3, first paragraph