拉格朗日乘子法和KKT条件无约束最优化方法

拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush-Kuhn-Tucker)条件是求解约束优化问题的重要方法,在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。前提是:只有当目标函数为凸函数时,使用这两种方法才保证求得的是最优解。

对于无约束最优化问题,有很多经典的求解方法,参见无约束最优化方法

拉格朗日乘子法

先来看拉格朗日乘子法是什么,再讲为什么。

$\min\;f(x)\\s.t.\;h_{i}(x)=0\;\;\;\;i=1,2...,n$

这个问题转换为

\begin{equation}min\;[f(x)+\sum_{i=1}^{n}\lambda_{i}h_{i}(x)]\end{equation}

其中$\lambda_{i}\ne{0}$,称为拉格朗日乘子。

下面看一下wikipedia上是如何解释拉格朗日乘子法的合理性的。

现有一个二维的优化问题:

\begin{equation}\min\;f(x,y)\\s.t.\;g(x,y)=c\label{eg1}\end{equation}

我们可以画图来辅助思考。

绿线标出的是约束$g(x,y)=c$的点的轨迹。蓝线是$f(x,y)$的等高线。箭头表示斜率,和等高线的法线平行。

从图上可以直观地看到在最优解处,f和g的法线方向刚好相反(或者说叫梯度共线),即

\begin{equation}\bigtriangledown[f(x,y)+\lambda(g(x,y)-c)]=0\;\;\;\;\lambda\ne{0}\label{grad}\end{equation}

而满足\ref{grad}的点同时又是\ref{F}的解。

\begin{equation}min\ F(x,y)=f(x,y)+\lambda(g(x,y)-c)\label{F}\end{equation}

所以\ref{eg1}和\ref{F}等价。

新方程$F(x,y)$在达到极值时与$f(x,y)$相等,因为$F(x,y)$达到极值时$g(x,y)-c$总等于零。

KKT条件

先看KKT条件是什么,再讲为什么。

\begin{equation}let\;L(x,\mu)=f(x)+\sum_{k=1}^q\mu_{k}g_{k}(x)\end{equation}

其中$\mu_{k}\ge{0},g_{k}(x)\le{0}$

$\because \left.\begin{matrix}\mu_{k}\ge{0}\\g_{k}(x)\le{0}\end{matrix}\right\}$=>$\mu{g(x)}\le{0}$

$\therefore$ \begin{equation}\max_{\mu}L(x,\mu)=f(x)\label{a}\end{equation}

$\therefore$\begin{equation}\min_{x}f(x)=\min_{x}\max_{\mu}L(x,\mu)\label{firsthalf}\end{equation}

上面的推导到此中断一下,我们看另外一个式子。

$\max_{\mu}\min_{x}L(x,\mu)=\max_{\mu}[\min_{x}f(x)+\min_{x}\mu{g(x)}]=\max_{\mu}\min_{x}f(x)+\max_{\mu}\min_{x}\mu{g(x)}=\min_{x}f(x)+\max_{\mu}\min_{x}\mu{g(x)}$

这里的$u$和$g$都就向量,所以去掉了下标$k$。另外一些博友不明白上式中$\max_{\mu}\min_{x}f(x)=\min_{x}f(x)$是怎么推出来的,其实很简单,因为$f(x)$与变量$u$无关,所以这个等式就是成立的。

又$\because\left.\begin{matrix}\mu_{k}\ge{0}\\g_{k}(x)\le{0}\end{matrix}\right\}$=>$\min_{x}\mu{g(x)}=\left\{\begin{matrix}0 & if\;\mu=0\;or\;g(x)=0\\ -\infty  & if\;\mu>0\;and\;g(x)<0\end{matrix}\right.$

$\therefore \max_{\mu}\min_{x}\mu{g(x)}=0$此时$\mu=0\;or\;g(x)=0$

\begin{equation}\therefore \max_{\mu}\min_{x}L(x,\mu)=\min_{x}f(x)+\max_{\mu}\min_{x}\mu{g(x)}=\min_{x}f(x)\label{secondhalf}\end{equation}此时$\mu=0\;or\;g(x)=0$

联合\eqref{firsthalf},\eqref{secondhalf}我们得到$\min_{x}\max_{\mu}L(x,\mu)=\max_{\mu}\min_{x}L(x,\mu)$

亦即$\left.\begin{matrix}L(x,\mu)=f(x)+\sum_{k=1}^q\mu_{k}g_{k}(x)\\\mu_{k}\ge{0}\\g_{k}(x)\le{0}\end{matrix}\right\}$=>$\min_{x}\max_{\mu}L(x,\mu)=\max_{\mu}\min_{x}L(x,\mu)=\min_{x}f(x)$

我们把$\max_{\mu}\min_{x}L(x,\mu)$称为原问题$\min_{x}\max_{\mu}L(x,\mu)$的对偶问题,上式表明当满足一定条件时原问题、对偶的解、以及$\min_{x}f(x)$是相同的,且在最优解$x^*$处$\mu=0\;or\;g(x^*)=0$。把$x^*$代入\eqref{a}得$\max_{\mu}L(x^*,\mu)=f(x^*)$,由\eqref{secondhalf}得$\max_{\mu}\min_{x}L(x,\mu)=f(x^*)$,所以$L(x^*,\mu)=\min_{x}L(x,\mu)$,这说明$x^*$也是$L(x,\mu)$的极值点,即$\frac{\partial{L(x,\mu)}}{\partial{x}}|_{x=x^*}=0$。

最后总结一下:

$\left.\begin{matrix}L(x,\mu)=f(x)+\sum_{k=1}^q\mu_{k}g_{k}(x)\\\mu_{k}\ge{0}\\g_{k}(x)\le{0}\end{matrix}\right\}$=>$\left\{\begin{matrix}\min_{x}\max_{\mu}L(x,\mu)=\max_{\mu}\min_{x}L(x,\mu)=\min_{x}f(x)=f(x^*)\\\mu_{k}{g_{k}(x^*)=0}\\\frac{\partial{L(x,\mu)}}{\partial{x}}|_{x=x^*}=0\end{matrix}\right.$

KKT条件是拉格朗日乘子法的泛化,如果我们把等式约束和不等式约束一并纳入进来则表现为:

$\left.\begin{matrix}L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{n}\lambda_{i}h_{i}(x)+\sum_{k=1}^q\mu_{k}g_{k}(x)\\\lambda_{i}\ne{0}\\h_{i}(x)=0\\\mu_{k}\ge{0}\\g_{k}(x)\le{0}\end{matrix}\right\}$=>$\left\{\begin{matrix}\min_{x}\max_{\mu}L(x,\lambda,\mu)=\max_{\mu}\min_{x}L(x,\lambda,\mu)=\min_{x}f(x)=f(x^*)\\\mu_{k}{g_{k}(x^*)=0}\\\frac{\partial{L(x,\lambda,\mu)}}{\partial{x}}|_{x=x^*}=0\end{matrix}\right.$

注:$x,\lambda,\mu$都是向量。

$\frac{\partial{L(x,\lambda,\mu)}}{\partial{x}}|_{x=x^*}=0$表明$f(x)$在极值点$x^*$处的梯度是各个$h_{i}(x^*)$和$g_{k}(x^*)$梯度的线性组合。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AILearning

【Scikit-Learn 中文文档】新异类和异常值检测 - 无监督学习 - 用户指南 | ApacheCN

中文文档: http://sklearn.apachecn.org/cn/stable/modules/outlier_detection.html 英文文...

1.1K70
来自专栏人工智能LeadAI

LeNet5的基本结构 | 卷积神经网络

在机器视觉,图像处理领域,卷积神经网络取得了巨大的成功。本文将参考UFLDL和DEEPLEARNING.NET的教程,结合自己的理解,梳理一下卷积神经网络的构成...

40670
来自专栏ml

神经网络模型之AlexNet的一些总结

说明: 这个属于个人的一些理解,有错误的地方,还希望给予教育哈~ 此处以caffe官方提供的AlexNet为例. 目录: 1.背景 2.框架介绍 3.步骤详细说...

34450
来自专栏深度学习与数据挖掘实战

数据科学家工具箱|xgboost原理以及应用详解

作者:雪伦_

20520
来自专栏AI科技评论

干货 | 攻击AI模型之DeepFool算法

AI 科技评论按:本文为“兜哥带你学安全”系列之三,首发于AI科技评论,未经许可不得转载。

41230
来自专栏深度学习与计算机视觉

学习SVM(三)理解SVM中的对偶问题

学习SVM(一) SVM模型训练与分类的OpenCV实现 学习SVM(二) 如何理解支持向量机的最大分类间隔 学习SVM(三)理解SVM中的对偶问题 ...

321100
来自专栏null的专栏

优化算法——截断梯度法(TG)

一、L1正则的表达形式    在机器学习中,几乎无人不知无人不晓L1正则与L2正则,L1正则与L2正则都有参数控制的作用,对模型起到约束的作用,防止过拟合。但是...

53060
来自专栏marsggbo

论文笔记系列-Simple And Efficient Architecture Search For Neural Networks

本文提出了一种新方法,可以基于简单的爬山过程自动搜索性能良好的CNN架构,该算法运算符应用网络态射,然后通过余弦退火进行短期优化运行。

15410
来自专栏红色石头的机器学习之路

台湾大学林轩田机器学习技法课程学习笔记9 -- Decision Tree

上节课我们主要介绍了Adaptive Boosting。AdaBoost演算法通过调整每笔资料的权重,得到不同的hypotheses,然后将不同的hypothe...

28900
来自专栏人工智能LeadAI

零基础入门深度学习 | 第三章:神经网络和反向传播算法

无论即将到来的是大数据时代还是人工智能时代,亦或是传统行业使用人工智能在云上处理大数据的时代,作为一个有理想有追求的程序员,不懂深度学习这个超热的技术,会不会感...

516120

扫码关注云+社区

领取腾讯云代金券