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}$.

  • $\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 '12 at 17:39
  • $\begingroup$ I see. Thank you very much for your reply :) $\endgroup$ – mintaka Jan 8 '12 at 6:30

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.

| cite | improve this answer | |
  • $\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 '12 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 '12 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 '12 at 11:36
  • $\begingroup$ Oh.. thanks for pointing out.. what if ${\bf b}={\bf a}$ here? $\endgroup$ – mintaka Jan 7 '12 at 4:54

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.