For $\ i = 0, 1, \cdots m$, $f_{i}(x): R^n \rightarrow R$ is defined to be $$ f_i(x) = x^TQ_ix + 2p_i^Tx + r_i $$ , where $Q_0 \cdots Q_m$ are real symmetric matrices, $p_0 \cdots p_m \in R^n$, and $r_0 \cdots r_m \in R$.

Now, for all $x$ in $R^n$, $f_{0}(x) \geq \sum_{i=1}^{m}t_if_i(x)$ holds ($t_1, \cdots, t_m \in R$).

Please show that the following matrix is positive semi-definite. $$ \begin{pmatrix} Q_0 & p_0\\ p_0^T & r_0 \end{pmatrix} -\sum_{i=1}^{m}t_i \begin{pmatrix} Q_i & p_i\\ p_i^T & r_i \end{pmatrix} $$

  • $\begingroup$ I think the essence of this problem is:$$\begin{pmatrix}x^T & 1 \end{pmatrix} \begin{pmatrix}Q & p\\p^T & r \end{pmatrix}\begin{pmatrix}x \\ 1 \end{pmatrix} \geq 0 \Leftrightarrow \begin{pmatrix}\xi^T & \eta \end{pmatrix} \begin{pmatrix}Q & p\\p^T & r \end{pmatrix}\begin{pmatrix}\xi \\ \eta \end{pmatrix} \geq 0 $$, for all $x, \xi \in R^n, y \in R$. I have difficulty in showing $r=0\Rightarrow p=0$, which is very important part of my solution. $\endgroup$ – dazaga Aug 10 '14 at 8:50
  • $\begingroup$ It follows from my proof. $\endgroup$ – Alexander Vigodner Aug 10 '14 at 15:09

EDITED version

You assume that $F(x)=x^TQx+2p^Tx+r\ge 0$ for all $x$ where $Q=Q_0-\sum_1^m t_iQ_i$, $p=p_0-\sum_1^m t_ip_i$, $r=r_0-\sum_1^m t_ir_i$. This implies

  1. $F(0)=r\ge 0$.

  2. $Q$ is positively semi-definite.

  3. $p=QQ^+p$, namely $Qx=0$ implies $p^Tx=0$.

Thus $F(x)$ can be rewritten in the following from $$ F(x)=(x+Q^+p)^TQ(x+Q^+p)+r-p^TQ^+p $$ Then $r\ge p^TQ^+p$. Now the property we want to prove that for for any $x,a$:

$$ F(x,a)=x^TQx+2ap^Tx+a^2r\ge 0 $$ We can rewrite: $$ F(x,a)=(x+aQ^+p)^TQ(x+aQ^+p)+a^2r-a^2p^TQ^+p\ge a^2r-a^2p^TQ^+p=a^2(r-p^TQ^+p)\ge 0 $$

  • $\begingroup$ I can't figure out what Q^+ implies. Please tell me! $\endgroup$ – dazaga Aug 10 '14 at 2:05
  • $\begingroup$ $Q^+$ is pseudo-inverse matrix of $Q$, generalization of inverse when $Q$ is singular. One of it's properties is $Q^+QQ^+=Q^+$ and if $Qy=p$ and $Qs=0$ iff $p^Ts=0$ then $QQ^+p=p$ and $y=Q^+p$. $\endgroup$ – Alexander Vigodner Aug 10 '14 at 2:35
  • 1
    $\begingroup$ How do you find $Q$ is positive semi-definite? $\endgroup$ – dazaga Aug 10 '14 at 3:13
  • $\begingroup$ In the symmetric case, it means that the minimum eigenvalue is zero or greater. $\endgroup$ – Michael Grant Aug 10 '14 at 3:18
  • $\begingroup$ This may be trivial, but I think $r > 0$ is false and $r\geq0$ is true. $\endgroup$ – dazaga Aug 10 '14 at 7:02

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.