# A question about Lagrange multiplier in optimization

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.

• 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.) Jun 18 '16 at 23:51

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)$$
• 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) Jun 18 '16 at 23:56