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

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

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .