# Optimization problem

In the expression:

$${\underset{\Omega}{\min}\left\|\beta A\Omega^{-1}B+C\right\|_{F}^{2}}\, ,$$ $$\text{subject to tr}(\Omega)=1, \Omega \ge 0\, ,$$

where $${\Omega}$$ is nonnegative and symmetric matrix.

How to solve for the variable $$\Omega$$?

• Does $\Omega \ge 0$mean that elements of $\Omega$ are nonnegative elementwise, or that $\Omega$ is positive semidefinite? Jul 14, 2021 at 17:30
• Are you minimizing that expression? You need to say so (edit the question). Jul 14, 2021 at 18:35
• yes, this is a minimization problem, and ${\Omega}$ is a symmetric matrix and any element of Ω is nonnegative. Jul 14, 2021 at 23:54
• There are many issues with this post, but if we can fix'em, it is an interesting question. Is $\Omega$ full or is there a fixed sparsity pattern? This looks like a sparse approximate inverse problem, and it is clear that if $\Omega$ is full then this is very expensive to solve. Jul 15, 2021 at 0:25
• Yes, in fact, ${\Omega \in R^{c \times c}}$ and ${\Omega}$ has the full rank. Jul 15, 2021 at 0:43

$$\def\O{\Omega}\def\M{\mho}\def\t{\theta} \def\o{{\tt1}}\def\p{\partial} \def\L{\left}\def\R{\right} \def\LR#1{\L(#1\R)} \def\BR#1{\Big(#1\Big)} \def\bR#1{\big(#1\big)} \def\vecc#1{\operatorname{vec}\LR{#1}} \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\hess#1#2#3{\frac{\p^2 #1}{\p #2\,\p #3}} \def\c#1{\color{red}{#1}} \def\TE{\trace{E}}$$The constraints can be eliminated via construction.
Starting with an unconstrained matrix $$U$$ define an element-wise exponential and re-scale it \eqalign{ E &= \exp(U) \qiq E\ge 0 \\ \O &= \frac{E}{\TE} \qiq \trace{\O}=1,\;\O\ge 0 \\ } For typing convenience, define some new variables (and redefine some existing ones) \eqalign{ \t &= \TE,\qquad A = \beta A,\quad \M = \O^{-1},\quad M=A\M B+C \\ Q &= \frac{\M^TA^TMB^T\M^T}{\t^2} \\ R &= {\trace{Q^TE}\,I - \t\,Q} \\ } and use a colon to denote the Frobenius product \eqalign{ A:B &= \sum_{i=1}^m\sum_{j=1}^n A_{ij}B_{ij} \;\doteq\; \trace{A^TB} \\ A:A &= \big\|A\big\|^2_F \\ } and $$\odot$$ for the Hadamard product, which (amazingly) commutes with the Frobenius product \eqalign{ A:\LR{B\odot C} = \LR{A\odot B}:C \\ } Use the above notation to calculate the differential and gradient of the objective function \eqalign{ \phi &= \frac 12M:M \\ d\phi &= M:dM \\ &= M:\LR{A\,d\M\,B} \\ &= M:\LR{-A\M\;d\O\;\M B} \\ &= -\M^TA^TMB^T\M^T:{d\O} \\ &= -\M^TA^TMB^T\M^T:\LR{ \frac{\t\,dE-E\,\c{d\t}}{\t^2} } \\ &= Q:\BR{E\c{\LR{I:dE}}} - Q:\t\,dE \\ &= R:dE \\ &= R:\LR{E\odot dU} \\ &= \LR{R\odot E}:dU \\ \grad{\phi}{U} &= {R\odot E} \\ } Setting the gradient to zero yields a complicated nonlinear equation which is impossible to solve analytically. Instead, use the gradient derived above in your favorite gradient descent algorithm to calculate the optimal $$U$$. $$\;$$ Hint: The $$k^{th}$$ iteration will look like \eqalign{ U_{k+1} &= U_k -\lambda_k{R_k\odot E_k} \\ } where the step-length $$\lambda_k$$ is determined by a line search or some heuristic formula.
After obtaining the optimal $$U$$ you can then calculate the corresponding $$\O$$ matrix.
$${\rm If}\;\O^T\!=\O\, \big({\rm and\,therefore\;}U^T\!=U,\;E^T\!=E\big)$$ the gradient should be symmetrized \eqalign{ \grad{\phi}{U} &= \LR{\frac{R+R^T}{2}}\odot E \\ }