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

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

share|improve this question
    
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$. –  Suvrit Jan 7 '12 at 17:39
    
I see. Thank you very much for your reply :) –  KOMA Jan 8 '12 at 6:30
add comment

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
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$ –  KOMA Jan 6 '12 at 11:15
    
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. –  KOMA Jan 6 '12 at 11:17
1  
$ba^T-I$ is not symmetric, so it is not PSD by the standard definition of PSD. –  Suvrit Jan 6 '12 at 11:36
    
Oh.. thanks for pointing out.. what if ${\bf b}={\bf a}$ here? –  KOMA Jan 7 '12 at 4:54
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.