Find the minimum of the positive semidefinite quadratic function.

116 Views Asked by At

Given quadratic function $$ f(x) = \sum_{i \in L^-} \frac{\lambda_i}{v_i^T v_i}(v_i^Tx + \frac{1}{2\lambda_i}v_i^T c)^2 + \sum_{i \in L^0} \frac{1}{v_i^T v_i}(v_i^Tc \cdot v_i^Tx) + \sum_{i \in L^+} \frac{\lambda_i}{v_i^T v_i}(v_i^Tx + \frac{1}{2\lambda_i}v_i^T c)^2 - \frac{1}{4} \sum_{i \in L^- \cup L^+} \frac{1}{\lambda_i v_i^T v_i} (v_i^T c)^2$$ where $\lambda_i$ is eigenvalue (assume that they are ordered), $L^- = \{i: \lambda_i < 0\}$ is set of indeces of negative eigenvalue, $L^0 = \{i: \lambda_i = 0\}$ and $L^+ = \{i: \lambda_i > 0\}$. Also, $v_i$ is eigenvector.

Show that if $v_i^Tc = 0$ for all $i \in L^0$ and $L^+ \neq \emptyset$, $L^0 \neq \emptyset$ and $L^- = \emptyset$, the set of minima has the form

$$\tilde X = \{x: x = \sum_{i \in L^+}-\frac{1}{2\lambda_i v_i^T v_i}v_i^T c v_i + \sum_{i \in L^0} \tau_i v_i \}$$

My attempt:

Since all the eigenvalues are nonnegative, the function $f$ is positive semidefinite then $f$ looks like this $$ f(x) = \sum_{i \in L^+} \frac{\lambda_i}{v_i^T v_i}(v_i^Tx + \frac{1}{2\lambda_i}v_i^T c)^2 - \frac{1}{4} \sum_{i \in L^+} \frac{1}{\lambda_i v_i^T v_i} (v_i^T c)^2$$

Without taking the derivative, I can say that minimal value is $$ \tilde f = - \frac{1}{4} \sum_{i \in L^+} \frac{1}{\lambda_i v_i^T v_i} (v_i^T c)$$ because the first summand is quadratic and it should be zero. It will be zero if $v_i^Tx + \frac{1}{2\lambda_i}v_i^T c = 0$. However I do not understand how to write the set $$ X = \{x: v_i^Tx + \frac{1}{2\lambda_i}v_i^T c = 0 \}$$ as $$\tilde X = \{x: x = \sum_{i \in L^+}-\frac{1}{2\lambda_i v_i^T v_i}v_i^T c v_i + \sum_{i \in L^0} \tau_i v_i \}$$

1

There are 1 best solutions below

4
On BEST ANSWER

I assume that the eigenvectors are orthogonal.

$$\nabla f(x) = 2\sum_{i \in L^+}\frac{\lambda_i}{v_i^Tv_i}(v_i^Tx+\frac1{2\lambda_i}v_i^Tc)v_i=0$$

$$\sum_{i \in L^+}\frac{\lambda_i}{v_i^Tv_i}(v_i^Tx+\frac1{2\lambda_i}v_i^Tc)v_i=0$$

$$\sum_{i \in L^+}\frac{\lambda_i}{v_i^Tv_i}v_iv_i^Tx=-\sum_{i \in L^+}\frac1{2}\frac{v_i^Tc}{v_i^Tv_i}v_i$$

This is a linear system of rank $|L^+|$, we have to find a particular solution.

We can check that for $j \in L^+$,

$$\sum_{i \in L^+} \frac{\lambda_i}{v_i^Tv_i}v_iv_i^T \left( - \frac12 \frac{v_j^Tcv_j}{\lambda_j v_j^Tv_j} \right)=-\frac12\frac{v_j^Tc}{v_j^Tv_j}v_j$$

Hence $\sum_{i \in L^+}- \frac12 \frac{v_i^Tcv_i}{\lambda_i v_i^Tv_i}$ is a particular solution.

The nullspace are those with $0$ eigenvalues.

Hence the solution is $\{ x: x=\sum_{i \in L^+}- \frac12 \frac{v_i^Tcv_i}{\lambda_i v_i^Tv_i } + \sum_{i \in L^0 } \tau_iv_i\}$.