# Positive Definite Matrix Optimization Problem

I've got trouble with matrix optimization problem..

Proving the Principal Component Analysis (PCA) algorithm, we want to maximize the objective function $u^TSu$ subject to $u^Tu=1$, where $u$ is a principal component vector, $S$ is a scatter matrix (or covariance matrix).

In my textbook, they used the technique of Lagrange multipliers and just differentiated the equation with respect to u and set the result to zero.

Is it always guaranteed for that objective function to get maximized at extrema? If I differentiate $u^TSu$ twice, only $S$ remains, which is a semi-positive definite matrix. That result reminds me of a convex function, which is minimized at extrema.

Does anyone have any insight or experience with such a problem?

Thanks,

Lee

• Lagrange multipliers method is for finding extrema. Both maxima and minima are included in extremes. So, you need to evaluate $u^T Su$ on extremes, the max value of $u^TSu$ on extremes correponds to the maximum, and the min to the minimum. – Sungjin Kim Sep 7 '16 at 6:01

It is not quite a convex problem because of the constraint. Any critical point of the objective function $f(u)=u^T S u$ under the constraint corresponds to an eigenvector of $S$ (when symmetric) and the value $f(u)$ at that point is the corresponding eigenvalue (which also pops out of the Lagrange multiplier formalism).
Geometric explanation regarding a critical point (better make a drawing): Write $S=\{u: u^T u=1\}$ for the constraint. Let $v\in S$ and consider $u: t\in (-1,1)\rightarrow S$, a $C^1$ curve with $u(0)=v$ and $u'(0)=w$. We have $u(t)^T \dot{u}(t)=v^T w=0$ because of the constraint. The tangent space to $S$ at $v$ is precisely the orthogonal complement to $v$. If $v$ is a critical point for $f_{|S}$ then $t=0$ should be a critical point for $f(u(t))$: $$v^T S w = f'(u(0)).u'(0)=0$$ which should then hold for any $w$ tangent to $S$ at $v$. So $Sv$ should be orthogonal to the orthogonal complement to $v$, i.e. $Sv$ and $v$ are parallel: $Sv=\lambda v$.