What is the gradient of $x \mapsto \frac{1}{2}(x^2)^\top A(x^2)$?

Question

Let matrix $A$ be sparse and symmetric but not semidefinite. Since I would like to use projected gradient descent, I must find the gradient of $x \mapsto \frac{1}{2}(x^2)^\top A(x^2)$, where $x^2 = \operatorname{diag}(x)x$, $$\operatorname{diag}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} x_1 & 0 & 0 \\ 0 & x_2 & 0 \\ 0 & 0 & x_3 \end{pmatrix},$$ and $x \in \mathbb R^n$. How can I do it?

I know the cases where $x^2$ is replaced by $x$ but not this case.

Answer 1

Let \begin{gather*} f(x)=\frac{1}{2}x^{\mathsf{T}}\mathcal{A}x \\ g(x)=\mathrm{diag}(x)x \end{gather*}

You already know $$\mathcal{D}(f)(x)=x^{\mathsf{T}}\mathcal{A}$$ We can compute directly $$\mathcal{D}(g)(x)_{j,k}=\frac{\partial(x_j^2)}{\partial x_k}=2x_j\delta_{j,k}$$ where $\delta$ is the Kronecker delta. Thus $$\mathcal{D}(g)(x)=2\mathrm{diag}{(x)}$$

Finally, by the multivariate chain rule, $$\mathcal{D}(f\circ g)(x)=\mathcal{D}(f)(g(x))\mathcal{D}(g)(x)=2x^{\mathsf{T}}\mathrm{diag}(x)^{\mathsf{T}}\mathcal{A}\mathrm{diag}{(x)}$$

Answer 2

$ \def\o{{\tt1}}\def\p{\partial} \def\LR#1{\left(#1\right)} \def\diag#1{\operatorname{diag}\LR{#1}} \def\Diag#1{\operatorname{Diag}\LR{#1}} \def\trace#1{\operatorname{Tr}\LR{#1}} \def\qiq{\quad\implies\quad} \def\grad#1#2{\frac{\p #1}{\p #2}} \def\c#1{\color{red}{#1}} \def\CLR#1{\c{\LR{#1}}} \def\fracLR#1#2{\LR{\frac{#1}{#2}}} \def\h{\tfrac 12} $The gradient can be calculated using the Hadamard $(\odot)$ and Frobenius $(:)$ products $$\eqalign{ w &= x\odot x \quad\qiq {dw} = 2x\odot dx \\ \phi &= \h w^TAw \\ &= \h A:ww^T \\ d\phi &= \h A:\LR{dw\;w^T+w\;dw^T} \\ &= \h\LR{A+A^T}:\LR{\c{dw}\;w^T} \\ &= Aw:\c{dw} \\ &= Aw:\CLR{2x\odot dx} \\ &= \LR{2x\odot Aw}:dx \\ \grad{\phi}{x} &= {2x\odot Aw} \\ }$$ These specialized products can be replaced by traces and diagonal matrices $$\eqalign{ A:BC &= \trace{A^TBC} \;=\; AC^T:B \;=\; CA^T:B^T \\ X &= \Diag x \;\implies\; Xb = x\odot b \\ \grad{\phi}{x} &= {2XAXx} \\ }$$