# Minimizing a matrix expression

I am trying to minimize the following function $$\min_{a \in \mathbb{R}^n} \frac{1}{n}(Ka-y)^T(Ka-y) + \lambda a^TKa$$ where $K$ is a positive semi-definite matrix. Since the first part and the second part is convex, the whole function is convex. Then taking derivative and equating to zero I get $$K((K+\lambda nI)a-y)=0$$

$\textbf{My main question}$ is from here, how can I get a solution for $a$?

I suspect that the nullspace of $K$ is not only zero. So I cannot directly write $$(K+\lambda nI)a-y=0$$

$\textbf{My second question}$ is even if I could write it, how can I be sure that the matrix $K+\lambda n I$ is invertible?

-
Indeed, if $K$ is only assumed to be semidefinite, its nullspace can very well be nontrivial. For $\lambda>0$, the matrix $K+\lambda nI$ is positive and definite, hence invertible. – 1015 Feb 10 '13 at 15:51
$K$ is positive semi-definite and $\lambda n I$ is strictly positive definite if $\lambda > 0$, so $K+\lambda n I$ is strictly positive definite and thus invertible. – Patrick Li Feb 10 '13 at 16:54

As mentioned in the comments, $K+\lambda n I$ is positive-definite and hence invertible.

This is because if $A$ is any e.g. real matrix, then for any $\epsilon \in \mathbb{R}$, the eigenvalues of $A+\epsilon I$ are those of $A$ with $\epsilon$ added to them. Proof: Let $(A+\epsilon I)x=\tilde{\lambda} x$. Then $Ax = (\tilde{\lambda}-\epsilon)x$ and thus $\tilde{\lambda}-\epsilon$ must be an eigenvalue of $A$. Thus $(\lambda,x)$ is an eigenpair of $A$ if and only if $(\lambda+\epsilon,x)$ is an eigenpair of $A+\epsilon I$. I leave the converse statement to you.

In particular, if $K$ is positive-semidefinite, then all its eigenvalues are non-negative. Since $\lambda n >0$, then the eigenvalues of the regularized matrix $K + \lambda n I$ will be at least $\lambda n$. Hence $K + \lambda n I$ will be positive-definite.

When we have $K ((K+\lambda nI) \alpha -y)=0$, that means that the vector $(K+\lambda nI) \alpha -y$ must lie inside the nullspace of $K$. Since $0$ is inside the nullspace of $K$, we can try to enforce the equality $(K+\lambda nI) \alpha -y=0$, which admits a solution, since $(K+\lambda nI)$ is invertible. In fact, for any vector $\xi$ inside the nullspace of $K$ the equation $(K+\lambda nI) \alpha -y=\xi$ always admits a solution. Hence the set of solutions is $\left\{(K+\lambda nI)^{-1}(y+\xi): \xi \in \mathcal{N}(K) \right\}$.

-
thanks. but my main question was how can I pass from eq.2 to eq.3? May I write $(K+\lambda nI)a-y=0$ from $K((K+\lambda nI)a-y)=0$ – neticin Feb 10 '13 at 21:12
I added some explanation on that. – Manos Feb 11 '13 at 5:14
so here, we found only one solution for $a$. there may be other solutions as well, right? – neticin Feb 11 '13 at 10:28
Correct. I added the complete solution. – Manos Feb 11 '13 at 14:52