优化问题及KKT条件

整理自其他优秀博文及自己理解。

目录

  • 无约束优化
  • 等式约束
  • 不等式约束(KKT条件)

1、无约束优化

无约束优化问题即高数下册中的 “多元函数的极值"  部分。

驻点:所有偏导数皆为0的点;

极值点:在邻域内最大或最小的点;

最值点:在定义域内最大或最小的点;

关系:

驻点不一定是极值点,极值点一定是驻点;

极值点不一定是最值点,最值点一定是极值点;

求解最值:

求出所有的极值点,将所有的极值点带入函数中,最大或最小的那个就是最值点。

2、等式约束

等式约束问题即高数下册中的 “条件极值  拉格朗日乘数法” 部分。

对于$z=f(x,y)$在$\varphi(x,y)=0$的条件下的最值问题:

构造拉格朗日函数:$L(x,y,\lambda)=f(x,y)+\lambda\varphi(x,y)$;

对拉格朗日函数求解,得到的即为在条件$\varphi(x,y)=0$下,$z=f(x,y)$所有可能的极值点。再利用问题本身的其他约束条件(如果有的话)筛选极值点,比较之后求得最值点。

直观的解释:目标函数和约束函数在最优解处的法线共线,即$\bigtriangledown f(x,y)=\lambda\bigtriangledown g(x,y)$

具体证明请查阅高数课本。

3、不等式约束

 当约束是不等式的时候,可以在不等式约束中加入松弛变量,使其变为等式约束问题,再进行一些分析。

最后$x^*$是极值点的必要条件(KKT条件)为: 

$f(x)=\left\{ \begin{aligned} \bigtriangledown f(x) & = & \lambda \bigtriangledown c_i(x) \\ \lambda_ic_i(x) & = & 0\\ \lambda_i & \geq & 0 \end{aligned} \right.$

不等式约束可以直接利用KKT条件求出可能的极值点。

具体推导和证明可参见:https://zhuanlan.zhihu.com/p/26514613

他们之间的关系:(此图来自知乎上链接,入侵可删)

至此,梳理完毕。

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专知

【论文推荐】最新6篇行人重识别相关论文—深度空间特征重构、生成对抗网络、图像生成、系列实战、图像-图像域自适应方法、行人检索

【导读】专知内容组整理了最近六篇行人重识别(Person Re-identification)相关文章,为大家进行介绍,欢迎查看! 1. Deep Spatia...

6486
来自专栏编程

FPGA图像处理之rgbtogray算法的实现

FPGA图像处理之rgbtogray算法的实现 作者:lee神 1.背景知识 在正是入题之前先给大家讲解一下gray图像,YUV图像以及Ycbcr图像。 Gra...

3874
来自专栏大数据挖掘DT机器学习

Logistic回归模型、应用建模案例

一、logistic回归模型概述 广义线性回归是探索“响应变量的期望”与“自变量”的关系,以实现对非线性关系的某种拟合。这里面涉及到一个“连接...

4024
来自专栏专知

【干货】计算机视觉实战系列08——用Python做图像处理

2132
来自专栏文武兼修ing——机器学习与IC设计

基于sklearn的几种回归模型理论代码实现

理论 支持向量机回归器 支持向量机回归器与分类器相似,关键在于从大量样本中选出对模型训练最有用的一部分向量。回归器和分类器的区别仅在于label为连续值 K临近...

5555
来自专栏Coding迪斯尼

使用矩阵运算加速实现神经网络误差的反向传播

1413
来自专栏机器之心

教程 | 详解如何使用Keras实现Wassertein GAN

选自Deeply Random 机器之心编译 参与:晏奇、李泽南 在阅读论文 Wassertein GAN 时,作者发现理解它最好的办法就是用代码来实现其内容。...

42710
来自专栏PPV课数据科学社区

重要的机器学习算法

关键词:机器学习,算法 正文: 本文旨在为那些获取关于重要机器学习概念知识的人们提供一些机器学习算法,同时免费提供相关的材料和资源。并且附上相关算法的程序实现...

2756
来自专栏进击的程序猿

如何生成一幅艺术作品

假设我们有一幅大师的画作了,我们怎么能够提取出“大师作品”中的纹理和颜色这些细节让我们的计算机知道,而不是只看到画的整体造型呢?

1053
来自专栏PPV课数据科学社区

聚类分析:k-means和层次聚类

尽管我个人非常不喜欢人们被划分圈子,因为这样就有了歧视、偏见、排挤和矛盾,但“物以类聚,人以群分”确实是一种客观的现实——这其中就蕴含着聚类分析的思想。 前面所...

4067

扫码关注云+社区