I'm trying to solve an matrix optimization problem. The stationary equation drawn from the opt problem is to find the solution for $X$ of the following nonlinear matrix equation:
$AXX^TAX-AXB+C=0$
where $A$, $B$, $C$ are known. $A$ and $B$ are symmetric.
Thanks!
We want to find a root of the matrix function $F(X)=0$ where $$\eqalign{ F &= AXX^TAX - AXB + C \\ }$$ Calculate the differential $$\eqalign{ dF &= A\,dX\,X^TAX + AX\,dX^TAX + AXX^TA\,dX - A\,dX\,B \\ }$$ Then vectorize the matrices, and calculate the Jacobian $$\eqalign{ f &= {\rm vec}(F) \\ df &= {\rm vec}(dF) \\ &= (X^TA^TX\otimes A)dx + (X^TA^T\otimes AX)P\,dx + (I\otimes AXX^TA)dx - (B^T\otimes A)dx \\ &= \Big((X^TA^TX\otimes A) + (X^TA^T\otimes AX)P + (I\otimes AXX^TA) - (B^T\otimes A)\Big)dx \\ &= J\,dx \\ }$$ where $P$ is the permutation matrix required to vectorize $X^T,\;$ i.e. $${\rm vec}(X^T) = P\,{\rm vec}(X)\\$$
Now apply Newton's insight and solve for the $dx$ which produces $\,df=-f$ $$\eqalign{ J\,dx &= -f \qquad\implies\quad dx &= -J^{-1}f \\ }$$ which suggests the following iterative scheme $$\eqalign{ F_k &= F(X_k) \\ f_k &= {\rm vec}(F_k)\\ x_k &= {\rm vec}(X_k) \\ J_k &= (X_k^TA^TX_k\otimes A) + (X_k^TA^T\otimes AX_k)P + (I\otimes AX_kX_k^TA) - (B^T\otimes A) \\ x_{k+1} &= x_k - J_k^{-1}f_k \\ X_{k+1} &= {\rm Reshape}(x_{k+1}) \\\\ }$$ This is just the basic algorithm. To improve its convergence you'll probably need to consider techniques like line-searches, trust-regions, etc.