如何在 PCA 优化中试验拉格朗日乘数?

机器算法验证 r 机器学习 主成分分析 优化
2022-03-24 00:10:23

假设我们要解决以下优化问题(这是本文中的 PCA问题

maximizew  wCws.t.      ww=1

如链接帖子中所述,使用拉格朗日乘数,我们可以将问题变为

minimize  wCwλ(ww1))
微分,我们得到Cwλw=0,这是特征向量方程。问题解决并λ是最大的特征值。


我试图在这里做一个数值示例,以了解更多关于拉格朗日乘数如何改变问题的信息,但不确定我的验证过程是否正确。

我试验了虹膜数据的协方差矩阵(见代码)。该图显示了该问题的几何解,其中黑色曲线是目标函数的轮廓,绿色曲线是约束。红色曲线表示可以最大化目标并满足约束条件的最优解。

在此处输入图像描述

在我的代码中,我试图使用optimx最小化不受约束的目标函数。我正在更换λ用本征分解的解。

X=iris[,c(1,3)]
X$Sepal.Length=X$Sepal.Length-mean(X$Sepal.Length)
X$Petal.Length=X$Petal.Length-mean(X$Petal.Length)
C=cov(X)
r=eigen(C)

obj_fun<-function(x){
  w=as.matrix(c(x[1],x[2]),ncol=1)
  lambda=r$values[1]
  v=t(w) %*% C %*% w + lambda *(t(w) %*% w -1)
  return(as.numeric(v))
}

gr<-function(w) {
  lambda=r$values[1]
  v=2* C %*% w + 2*lambda* w
  return(v)
}

res=optimx::optimx(c(1,2), obj_fun,gr, method="BFGS")

在此处输入图像描述

我得到以下结果,其中目标函数与图形解决方案的最佳值相反。并且两个参数 p1 和 p2 为 0。

我的问题是这样的验证方法对吗?即,我们可以替换λ具有最大特征值并最小化目标函数wCwλ(ww1))得到解决方案?

1个回答

我想我自己得到了答案,但希望一些专家可以确认。

令人困惑的是,在 CVX 书中,我们将一个有约束的优化问题转换为另一个没有约束的优化问题并解决对偶问题但是在 PCA 优化中我们不能。

例如,第 227 页,我们转换

minimizex  xxs.t.      Ax=b

最大化双重功能 g(v)=(1/4)vAAvbv,即

maximizex  ((1/4)vAAvbv)


在 PCA 优化问题中,问题具有拉格朗日(对于等式约束,我们可以使用λ)

L(w,λ)=wCwλ(ww1)

对于固定λ,我们得到偏导数并设置为0.

Lw=0=2Cw2λw

这是特征向量方程

Cw=λw

正如 Matthew Gunn 在评论中指出的那样,PCA 问题的目标不是凸的, 请参阅此讨论因此我们不应该试图最小化对偶函数来解决原始问题。