Thank everybody in advance. I'd like to solve an optimization problem for a matrix function $f(C)$. However, the matrix pseudo-inverse constraint gives me big troubles.

Vectors $V_{n\times 1}$, $F_{m\times 1}$ and matrix $B_{m\times n}$ are known. Matrix $C_{n\times m}$ is unknown. How to numerically solve: $$ \min\limits_{C}f(C)=V^T CF $$ $$ {\rm subject\,\, to}: BC=I_{m\times m} \\ m<n $$ $I_{m\times m}$ is an $m\times m$ Identity matrix.

I know this problem can be (sort of, because non-square matrices) formulated into linear matrix inequality (LMI). Similar to: optimization of inverse matrix with constraint on matrix elements. But my processor does not allow such numerical method (LMI) to be used. Plus I do not know how to non-square LMI. So I am looking for a different approach to solve this problem.

I have an ugly gradient descent approach for this problem. But it is complicated and I do not like it. I will not post it for now to limit people's thoughts. I will post it 4 days after the question.

In addition, I'm not sure if adding following constraint would make the problem easier: $$ {\rm subject\,\,to}: -I_{n\times n}<(CF)^T I_{n\times n}<I_{n\times n} $$

Appendix - Formulate problem to (sort of) LMI: (May not be correct, since matrix is not sqaure) Define invertible matrix $E_{n\times n}$, $$ BC = BEE^{-1}C=(BE)(E^{-1}C)=I \\ E^{-1}C = pinv(BE) \\ C=E\,\,pinv(BE) $$ Introducing $E$ is to represent all possible $C$ - parameterize $C$. Then the problem $\min\limits_{C}f(C)=V^T CF$ is equivalent of finding the $\min$ of scalar $\alpha$, that below inequality is feasible (i.e. some $E$ exists) $$ V^T CF < \alpha \\ V^T E\,\,pinv(BE) F < \alpha $$ With Schur complement, it is equivalent to following LMI $$ \left[\begin{array}{cc} BE & F\\ V^T E & \alpha \end{array} \right]<0 $$

  • 1
    $\begingroup$ What is that $E$ below the min? If this is a linear space you have a linear optimization problem (objective $C\mapsto V^TCF$ is linear in $C$ and constraint $BC=I$ is linear in $C$, too). $\endgroup$
    – Dirk
    Commented Jan 17, 2019 at 8:33
  • 1
    $\begingroup$ Im assuming $F\neq 0$, otherwise the problem is trivial. If $u \in \mathbb{R}^n$ is in the kernel of $B$ and $V^TU \neq 0$ you can make $f(C)$ arbitrarily small by adding multiples of $u$ to a column of $C$. If there exist no such $u$ we have $V=B^TW$ for some $W\in \mathbb{R}^m$. Then we have $f(C)=V^TCF=W^TBCF=W^TF$, i.e. $f(C)$ is independent of $C$. $\endgroup$
    – user100927
    Commented Jan 17, 2019 at 10:33
  • $\begingroup$ @Dirk, sorry, it should be $C$ than $E$. Fixed. $\endgroup$
    – sentry5588
    Commented Jan 17, 2019 at 12:57
  • $\begingroup$ @user100927, Thank you. $F\neq 0$. $\endgroup$
    – sentry5588
    Commented Jan 17, 2019 at 13:03
  • $\begingroup$ Just a quick observation... With a change of variables you can assume that $B=\begin{bmatrix}I_{m\times m} & 0\end{bmatrix}$; then $C = \begin{bmatrix}I_{m\times m}\\ X\end{bmatrix}$, with an unknown $X$, without further constraints, and then the problem should be easier because it's just an unconstrained linear problem. $\endgroup$ Commented Jan 17, 2019 at 13:57


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.