Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For scalar variables $x$, we have a simple solution for the following problem. \begin{eqnarray} \min_x&&\alpha(x-a)^2+\beta(x-b)^2 \\\ \mathrm{s.t. }&&x\leq a\\\ &&x\leq b \end{eqnarray} where $\alpha,\beta>0$.

The optimal solution $x=\min(a,b)$ is straightforward and independent of $\alpha,\beta$.

However, in the case of real symmetrical matrix variables, the problem seems to be much more complex because the relationship $\leq$ in constraints has to be replaced with $\preceq$ which is a more complex relationship defined as $$ A\preceq B\Leftrightarrow A-B\preceq0 $$ where $A\preceq0$ means $A$ is negative semi-definite.

Then the problem above is reformulated as following with matrix variables. Assume that all matrices in this problem are real symmetrical. \begin{eqnarray} \min_X&&\alpha\|X-A\|_F^2+\beta\|X-B\|_F^2\\\ \mathrm{s.t.}&&X\preceq A\\\ &&X\preceq B \end{eqnarray} where $\alpha,\beta\geq0$.

If $A$ and $B$ can be diagonalized by the same orthogonal matrix $U$, the problem reduces to a the problems of eigenvalues since $$ \alpha\|X-A\|_F^2+\beta\|X-B\|_F^2=\alpha\|\tilde{X}-\Lambda\|_F^2+\beta\|\tilde{X}-\Theta\|_F^2 $$ and \begin{eqnarray} X\preceq A\Leftrightarrow\tilde{X}\preceq\Lambda\\\ Y\preceq B\Leftrightarrow\tilde{X}\preceq\Theta \end{eqnarray} where $\tilde{X}=U^\top XU$, $\Lambda=U^\top AU$, $\Theta=U^\top BU$. Since $\Lambda$ and $\Theta$ are diagonal matrices, the problem can decompose to sum of some scalar variables and solved independently.

However, how to solve it if $A$ and $B$ have different eigenvectors? Is the solution independent of $\alpha$ and $\beta$ yet?

Could any one be so kind to help me with the question or give some suggestions? Thank you very much!

share|improve this question
    
The solutions are not independent of $\alpha$ and $\beta$; I just solved it numerically for various choices of the variables, obtaining differing solution values (also note, in particular, if $\alpha=\beta=0$ then we have an infinity of feasible solutions. –  Suvrit Feb 22 '12 at 0:20
    
@Suvrit, thanks for your attention and experiments! –  ppyang Feb 22 '12 at 2:38
add comment

1 Answer

up vote 6 down vote accepted

I looked at the problem again and saw that it can be simplified nicely.

In summary:

  1. If $\alpha, \beta > 0$, the solution is independent of $\alpha$ and $\beta$
  2. The solution can be easily computed (one eigenvector decomposition is needed)

Details

Introduce the variables $X=B+C$ and $Z=A-B$. We optimize over the symmetric matrix $C$ instead. With this change of variables, the problem becomes \begin{eqnarray*} \min_{C}\quad &\alpha\|C-Z\|^2 + \beta\|C\|^2\\\\ &C \preceq Z,\quad C \preceq 0. \end{eqnarray*} Let $Z=U\Lambda U^T$, and use the unitary invariance of the Frobenius norm to replace the problem by \begin{eqnarray*} \min_{D}\quad\alpha\|D-\Lambda\|^2 + \beta\|D\|^2\\\\ D \preceq \Lambda,\quad D \preceq 0. \end{eqnarray*} Clearly, $D$ must be diagonal. In which case, the problem splits and we see that \begin{equation*} d_{ii} = \min(0, \lambda_{ii}) \end{equation*} Thus, eventually, we obtain $X=B+UDU^T$ as the optimal answer.

share|improve this answer
    
It's so beautiful to use the substitution to uncover the optimal eigenvectors, which enables to split the complex problem of matrix into several simple sub-problems of eigenvalue. Thank you very much for your help! –  ppyang Feb 23 '12 at 6:19
    
You are welcome!! –  Suvrit Feb 23 '12 at 13:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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