1
$\begingroup$

Dear all,

I've got a SDP problem as follows:

$\min_{{\bf H}\succeq0}\quad trace({\bf H}) - {\bf a}^{\top}{\bf H}{\bf b}$,

where ${\bf a}$ and ${\bf b}$ are two constant vectors. May somebody tell me how to solve this SDP problem? Thank you very much in advance.

[Added] Thanks for Suvrit to point out some issues. I add one more parameter $\lambda$ (to be pre-defined) and assume ${\bf b}={\bf a}$ for the second term in the above problem as:

$\min_{{\bf H}\succeq0}\quad trace({\bf H}) - \lambda{\bf a}^{\top}{\bf H}{\bf a}$.

$\endgroup$
2
  • $\begingroup$ Again try the example that I gave below, say with $a=(1,0)$. If $1-\lambda \ge 0$, then we can set $H=0$ to get the minimum. If $1-\lambda < 0$, then as shown previously, the objective can be made to goto $-\infty$. $\endgroup$
    – Suvrit
    Jan 7, 2012 at 17:39
  • $\begingroup$ I see. Thank you very much for your reply :) $\endgroup$
    – mintaka
    Jan 8, 2012 at 6:30

1 Answer 1

2
$\begingroup$

Your problem has no solution. Here is why.

Let $H$ be $2 \times 2$. Let $a=(2, 0)$ and $b=(1, 0)$. Then, since $a^THb=\mbox{tr}(Hab^T)$, the objective function of your problem can be rewritten as $\mbox{tr}(H-Hab^T) = \mbox{tr}(HC)$, where $$C = I-ab^T = \begin{bmatrix} -1 & 0\\\\ 0 & 1\end{bmatrix}.$$ Now you can see that if we set \begin{equation*} H=\begin{bmatrix} \alpha & 0\\\\ 0 & 0 \end{bmatrix}, \end{equation*} then as $\alpha\to\infty$, your objective function goes to $-\infty$. Thus, in general, there is no solution.

Even if you let $a=b$, the same example above shows that there is no solution. You need to restrict $H$ to lie in a compact set.

$\endgroup$
4
  • $\begingroup$ Suvrit, thank you very much for your reply. But if we require C to be positive semidefinite (PSD), this is not the case. In fact, if we consider the dual of the problem, the lagrangian can be obtained as (suppose we have a pre-defined weight (a constant scalar $\lambda$ for the second term in the primal problem): $L=trace({\bf H})-\lambda{\bf a}^{\top}{\bf H}{\bf b}+trace({\bf H}{\bf Z}),$ where ${\bf Z}$ is PSD and also the dual variable for ${\bf H}$. Then the KKT conditions are: ${\bf I}-\lambda{\bf b}{\bf a}^{\top} + {\bf Z} = {\bf 0}$ and $trace({\bf H}{\bf Z})=0$ $\endgroup$
    – mintaka
    Jan 6, 2012 at 11:15
  • $\begingroup$ As ${\bf Z}$ is PSD, $\lambda{\bf b}{\bf a}^{\top}-{\bf I}$ is PSD. Then, we can pre-define $\lambda$ to satisfy that PSD constraint. $\endgroup$
    – mintaka
    Jan 6, 2012 at 11:17
  • 1
    $\begingroup$ $ba^T-I$ is not symmetric, so it is not PSD by the standard definition of PSD. $\endgroup$
    – Suvrit
    Jan 6, 2012 at 11:36
  • $\begingroup$ Oh.. thanks for pointing out.. what if ${\bf b}={\bf a}$ here? $\endgroup$
    – mintaka
    Jan 7, 2012 at 4:54

Your Answer

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

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