Let $\mathbf{B} \in \mathbb{R}^{M \times M}$, $\mathbf{X} \in \mathbb{R}^{N \times M}$, and $\mathbf{A} \in \mathbb{R}^{M \times N}$. We intend to solve for $\mathbf{X}$ by solving the following optimization problem

\begin{align} \arg \min_{\mathbf{X}} Tr( (\mathbf{A} \mathbf{X})^T \mathbf{B} ( \mathbf{A} \mathbf{X})) - 2Tr( \mathbf{B} \mathbf{A} \mathbf{X}) \end{align}

where $Tr()$ is the trace operator. The above problem can be rewritten as

\begin{align} \arg \min_{\mathrm{vec}(\mathbf{AX})} \mathrm{vec}(\mathbf{AX})^T (\mathbf{B} \otimes \mathbf{I}) \mathrm{vec}(\mathbf{AX}) - 2 \mathrm{vec}(\mathbf{B} ) \mathrm{vec}(\mathbf{AX}). \end{align}

The above optimization can be solved easily for $\mathrm{vec}(\mathbf{AX})$ as it is a quadratic program with no constraints. Suppose, we are given prior information that $\mathbf{X}_{ik}^{min}<\mathbf{X}_{ik}<\mathbf{X}_{ik}^{max}$. How do I solve it as an inequality constrained optimization problem for $\mathrm{vec}(\mathbf{X})$ not $\mathrm{vec}(\mathbf{AX})$?

  • $\begingroup$ Is $ B $ a PD Matrix? $\endgroup$
    – Royi
    May 5 '20 at 12:59

In case $ B $ is a Positive Definite Matrix then there is $ {C}^{T} C = B $ by the Cholesky Decomposition.

So the problem can be rewritten as:

$$\begin{aligned} \arg \min_{X} \quad & \frac{1}{2} {\left\| A X C \right\|}_{F}^{2} - \operatorname{Tr} \left( D X \right) \\ \text{subject to} \quad & L \leq X \leq U \quad \text{Element wise} \end{aligned}$$

Where $ D = B A $.

Then the gradient of the objective function is easy:

$$ {A}^{T} A X C {C}^{T} - {D}^{T} $$

Now, just use Projected Gradient Descent and you're done.

In case the matrix is Positive Semi Definite, then you can use the LDL Decomposition and build $ C $ from there in the same manner. If $ B $ is neither PSd nor PD then the problem is not convex. Then you can do the same but only local solution is guaranteed.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.