I am trying to formulate following problem (with some constraint) as a semidefinite programming problem (SDP),

\begin{equation} \text{minimize } ~~ -a^T B^{-1} a \end{equation}

where $B$ is a positive definite matrix. I used auxiliary variable and Schur complement and tried to formulate it as following :

\begin{eqnarray} \text{minimize }~~ t \\ \text{s.t.} ~~~t \geq -a^T B^{-1} a \end{eqnarray}

then tried to to reformulate the constraint as a Linear Matrix inequality (LMI) using Schur complement, but I got stuck to following:

\begin{align*} \left[\begin{array}{cc} t & a' \\ a & -B^{-1} \end{array}\right] \overset{\Large\text{??}}\geq 0 \end{align*}

but the LMI is not positive definite because $-B^{-1}$ is not positive definite.

Is there another way /scape that I can formulate the original problem as SDP?

  • $\begingroup$ I suggest to double check the original problem. It's a convex relaxation of an Np-hard combinatorial problem? $\endgroup$ – user85361 Sep 23 '15 at 22:10
  • $\begingroup$ no it's not , actually it is Mean Square Error minimization of an LMMSE estimator as var[unknown] - $a'B^{-1}a$, so I wanted to minimize it $\endgroup$ – Alireza Sep 23 '15 at 22:13
  • $\begingroup$ i know, that is the problem $\endgroup$ – Alireza Sep 23 '15 at 22:40
  • 1
    $\begingroup$ that is the original problem math.stackexchange.com/questions/1445731/… $\endgroup$ – Alireza Sep 23 '15 at 22:57
  • 1
    $\begingroup$ It's not convex, so it cannot be cast as an SDP. End of story, I'm afraid. $\endgroup$ – Michael Grant Sep 24 '15 at 15:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.