In http://www.compmacro.com/makoto/note/note_rbc_lq.pdf page 5, it is said that for value function $V = F^TPF$ (Bellman equation) $P$ has to be negative semi-definite matrix. Why does it have to be negative semi-definite?
P being negative semi-definite would imply that V is a concave function. The reason you would restrict P so that V would be a concave function is because of some of the assumptions you've made about about the model previously tell you that V must be concave.
In general, some of the typical assumptions that imply that the value function must be concave are something like the following:
Sorry I'm not giving the full details, but you can read more about them in chapters 4 and 9 of "Recursive Methods in Economic Dynamics" by Stokey, Lucas, and Prescott. The point that I'm making is that the assumptions of these kinds of models usually imply that the value function is concave. Therefore, if you check the assumptions and they indeed do so restrict the value function, then you can restrict your search to look only for matrices P that are negative semi-definite.