MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## A positive semidefinite programming problem

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

-
 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 2012 at 17:39 I see. Thank you very much for your reply :) – KOMA Jan 8 2012 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.

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