1
$\begingroup$

I read @amoeba 's answer in this post, PCA optimization problem is

$$ \underset{\mathbf w}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw} \\ \text{s.t.}~~~~~~ \|\mathbf w\|_2=1 $$

where $\mathbf C$ is the co-variance matrix. $\mathbf w$ is first principal direction. As mentioned in the post, using the Lagrange multiplier, we can change the problem into a minimization problem.

$$ \underset{\mathbf w}{\text{minimize}} ~~(\underset{\lambda}{\text{maximize}}~~ \mathbf w^\top \mathbf{Cw}-\lambda(\mathbf w^\top \mathbf w-1)) $$ Differentiating, we obtain $\mathbf{Cw}-\lambda\mathbf w=0$, which is the eigenvector equation. The end.

I think I need more examples to understand the Lagrange multiplier. Specifically, I was trying to practice it in a ridge regression problem but got stuck. The original problem is

$$ \underset{\mathbf w}{\text{minimize}}~~ \|\mathbf {Xw}-\mathbf y\|_2^2\\ \text{s.t.}~~~~ \|\mathbf w\|_2=c $$

($\mathbf X$ is the data matrix) But Using Lagrange multiplier are we transform it into following equation?

$$ \underset{\mathbf w}{\text{minimize}}~~ \underset{\lambda}{\text{maximize}} ~~\|\mathbf {Xw}-\mathbf y\|_2^2 + \lambda \mathbf w^\top \mathbf w $$

PS1. I know my math may be wrong in the problem description, please feel free to correct me in my question.

PS2. Thanks Nick Alger, I made the revisions on my equations.

Thank you.

$\endgroup$
  • 1
    $\begingroup$ One view of Lagrange multipliers is that they allow you to replace constraints with penalty terms in the objective function. If you can find just the right value for the Lagrange multiplier, then any minimizer for the original problem is also a minimizer of the Lagrangian. (This is one of the KKT conditions.) $\endgroup$ – littleO Jun 18 '16 at 23:51
1
$\begingroup$

By introducing the Lagrange multiplier, you are converting if from a minimization problem to a saddle-point problem. One seeks: $$\min_w \max_\lambda w^T C w + \lambda(w^Tw - 1).$$ The following is not correct: $$\min_w \min_\lambda w^T C w + \lambda(w^Tw - 1)$$

The saddlepoint is still a location where the gradient is zero, just like a minimum - perhaps that is the source of the confusion.

$\endgroup$
  • $\begingroup$ Thank you. I found the problem with min over both $w$ and $\lambda$. However, how can I do some numerical examples with it (if there are both min and max)? Sorry for the ugly code here. I do not know how to format it in comment. (Currently I am doing this experiment in R: obj_fun<-function(x){ w=as.matrix(c(x[1],x[2]),ncol=1) lambda=x[3] return(t(w) %*% C %*% w - lambda *(t(w) %*% w -1)) } optim(c(0.1,0.1,0.1),obj_fun) $\endgroup$ – hxd1011 Jun 18 '16 at 23:56
  • $\begingroup$ In this particular problem the maximizing vector is the largest singular vector, and there are lots of standard algorithms and libraries to find it. The state of the art algorithm is the Lanczos algorithm, which can be called from within Matlab with the command svds() and in python/scipy via scipy.sparse.linalg.svds. I'm sure there is something equivalent in R, but am not familiar with the language. If you are interested in constrained optimization more generally (not just this particular problem), I highly recommend the book "Numerical Optimization" by Nocedal and Wright. $\endgroup$ – Nick Alger Jun 19 '16 at 2:27
  • $\begingroup$ Thank you very much. Your answer is extremely helpful. I was trying to read the book convex optimization by stephen boyd but it is too hard for me to follow. That is why I want to do some numerical experiment first. Definitely will check your book recommendation. $\endgroup$ – hxd1011 Jun 19 '16 at 10:34

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.