4
$\begingroup$

We are trying to solve this optimization problem:

$$ \mathbf{u} \leftarrow \underset{||\mathbf{u} ||^2 = 1} {arg max} \ \mathbf{u}^{T} \mathbf{\Sigma} \mathbf{u} $$

Where u is a vector and $\mathbf{\Sigma}$ is the vairance-covariance matrix.

To solve this problem we can use the Lagrange Multiplier. In class we derived: $$ \tag{1} \mathcal{L}(\mathbf{u}, \lambda) = \mathbf{u}^{T} \mathbf{\Sigma} \mathbf{u} + \lambda \langle \mathbf{u} , \mathbf{u} \rangle $$

However isn't this equation wrong based on our previous constraint? Since we want $||\mathbf{u}||^2 = 1$ should't the constraint be the following:

$$ \mathcal{L}(\mathbf{u}, \lambda) = \mathbf{u}^{T} \mathbf{\Sigma} \mathbf{u} + \lambda ( \langle \mathbf{u} , \mathbf{u} \rangle - 1) $$

Or is there something I didn't understand correctly. Help is appreciated.

EDIT:

Maybe specifying the whole process we have seen in class can be more helplful to understand if that was a mistake. We are trying to derive the line that approximates optimally a given data set. The data set has been centered (points minus the mean of them) so there is only the $\mathbf{u}$ parameter that represents the slope of the line.

And $\mathbf{\Sigma} = \frac{1}{n} \sum_{i = 1}^{n} \mathbf{x}_i \mathbf{x}_{i}^{T}$ where $ \mathbf{x}_i$ are our centered point.

After forming the lagrange equation $(1)$ we perform two steps:

  • Minimize over $ \mathbf{u} \Rightarrow \mathbf{u}$ is an eigenvector because:

$$ \begin{align} \nabla_{ \mathbf{u}} \mathcal{L}(\mathbf{u}, \lambda) &= 2 (\mathbf{\Sigma}\mathbf{u} - \lambda \mathbf{u}) \\ \nabla_{ \mathbf{u}} \mathcal{L}(\mathbf{u}, \lambda) & \overset{!}{=} 0 \Leftrightarrow \mathbf{\Sigma}\mathbf{u} = \lambda \mathbf{u} \end{align} $$

  • Maximize over $ \lambda \Rightarrow \mathbf{u}$ is an principal eigenvector $\mathbf{\Sigma}$ (one with largest eigenvalue $\lambda$)

Now my questions are:

Does the $-1$ change the results, or is that a typo they missed in class?

Why can we use Lagrange if our actual optimization problem was a maximization problem and not a minimization problem?

$\endgroup$
  • 2
    $\begingroup$ you are right, the correct Lagrangian is your second version, the one with $\lambda(\|u\|^2-1)$ $\endgroup$ – Picaud Vincent Jul 1 '19 at 16:57
  • 1
    $\begingroup$ I believe as well there should be a minus sign instead of the plus one, considering $\lambda>0$, before writing the lagrangian term to penalize the objective function and thus try to maximize it, plus I believe it should consider the case when your $<u,u> being\; < \;1 \;or \;> 1$ as that would affect the sign and how you penalize your obj. function for non optimal $u$. In the case of searching for $u$ that minimises the obj.function the positive sign written up is valid. The -1 is important to push your $<u,u>$ to 1. $\endgroup$ – Mohamad Misto Jul 1 '19 at 22:29
  • 1
    $\begingroup$ One is simply the other plus a constant that does not depend on $u$. It does not matter which one you minimize with respect to $u$. $\endgroup$ – Michael Jul 2 '19 at 3:45
2
$\begingroup$

You are right, the correct Lagrangian is: $$ (A)\ \ \mathcal{L}(u,\lambda)=u^t\Sigma u+\lambda(\langle u,u \rangle -1) $$ but you could also have taken $(B)$: $$ (B)\ \ \mathcal{L}(u,\lambda)=u^t\Sigma u+\lambda(1-\langle u,u \rangle) $$ This is equivalent as we have an equality constraint. Taking care of sign is only revelant when you have inequality constraints ($g(x)\le 0$, $\lambda\ge 0$ and $\mathcal{L}(u,\lambda)=f(u) + \lambda g(x)$).

A necessary condition for local optimum is the KKT conditions:

For equality constraints you only have to check:

  1. stationarity: $\nabla_u\mathcal{L}$

  2. primal feasibility: $g(u)=0$

For the $(A)$ Lagrangian you have: $$ \nabla_u\mathcal{L} = 2(\lambda I+ \Sigma)u $$ For (1.) you must solve: $$ \Sigma u = -\lambda u $$

the solutions are $(\lambda,u)=(-\mu,u)$ where $(\mu,u)$ is any eigen pair of $\Sigma$. Here we will take (there is no restriction for that) normalized eigen pairs for which $\|u\|=1$.

(Note: as $\Sigma$ is a real symmetric semi-definite positive matrix, your eigen values are all nonegative real numbers, $\mu\ge 0$)

For (2.) the equation $\langle u,u \rangle -1=0$ is already satisfied as we are using normalized eigen vectors.

Remember this was a necessary condition for local optima. As we have a finite set of eigen pairs $(\mu_i,u_i)$, we then have a finite set of candidate solutions $(\lambda_i,u_i)=(-\mu_i,u_i)$.

We can check all candidate solutions and take the best one. For that you search for the $u_i$ that maximize the objective function:

\begin{align} u^* & =\arg\max_i u_i^t\Sigma u_i \\ &= \arg\max_i \mu_i \| u_i \|^2 \\ &= \arg\max_i \mu_i \end{align}

The best solution is $(\lambda^*,u^*)=(-\mu^*,u^*)$ where $(\mu^*,u^*)$ is the eigen pair with the highest eigen value $\mu^*\ge 0$.

Now concerning your questions:

  • The KKT conditions are only necessary conditions for stationnary points (that can be local maxima, local minima or even saddle points). The advantage is you can use them the search for possible local maxima or minima. The disadvantage is that, from these stationary points you still have some work to do to check if you are in presence of a local maxima or a local minima. This last step can be done by inspection of the objective function in a neighborhood of these stationary points (you can use second order information (Hessian matrix), convexity argument, etc...).

  • another possible origin of your doubts is maybe a confusion between the Lagrangian multiplier $\lambda$ and the eigen value $\mu$ (this is true that for this peculiar exercise the confusion is easy).

So to clarfy this, let's examine the (B) Lagrangian case.

The modifications are as follows:

  1. stationarity: $\nabla_u\mathcal{L}=2(-\lambda I+ \Sigma)u$

  2. primal feasibility: $g(u)=0=1-\langle u,u \rangle$

Solving $\nabla_u\mathcal{L}=0$ is now equivalent to $\Sigma u = \lambda u$. The solutions are $(\lambda,u)=(\mu,u)$ where $(\mu,u)$ is any normalized eigen pair of $\Sigma$.

As before 2. is automatically fulfilled.

The maximization of $\arg\max_i u_i^t\Sigma u_i$ is again the same as before and its conclusion is identical. The best candidate $(\lambda^*,u^*)$ is $(\lambda^*,u^*)=(\mu^*,u^*)$ where $(\mu^*,u^*)$ is the eigen pair with the highest eigen value $\mu^*$

Now observe that:

  • for both Lagrangian (A) and (B), the optimal primal solution $u^*$ is identical (the objective function value is also the same as it only depends on $u$ and not on the multpliers)

  • only the dual solution (the Lagrangian multiplier) change: $$ \lambda^*_A=-\mu^*=-\lambda^*_B $$ this is explained because we changed the signe of the equality contraint $g(u)$, in one case we have: $(\langle u,u \rangle -1)=0$, in the other $(-\langle u,u \rangle +1)=0$

$\endgroup$

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.