优化问题及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 条评论
登录 后参与评论

相关文章

来自专栏机器学习算法全栈工程师

最长公共子序列与最长公共子串

0. 引言 最近鄙人面试百度,出了这道求解公子序列长度的算法题。故此总结一下,这是一个很典型的题目,希望对大家将来的面试中能起到学习的作用。 1. 问题描述 子...

35111
来自专栏Java 源码分析

枚举

​ 枚举就是尝试所有的可能性,尤其是当我们在确定一个问题是不是的这一类问题中尤其有用,例如说给一堆数,让我我们判断他们是不是素数,或者素数的数量的时候,这...

2956
来自专栏程序生活

贪心算法总结贪心算法基本思路算法实现实例分析参考

贪心算法 贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。...

6714
来自专栏進无尽的文章

基础篇- iOS开发中常用的数学函数

912
来自专栏章鱼的慢慢技术路

解救小哈——DFS算法举例

2078
来自专栏C/C++基础

网易游戏技术岗在线编程题(一)

小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2...

581
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们很流行的框架和工具很有可能几年内就会变成过时的东西.但是计算机...

3676
来自专栏数据结构与算法

欧拉函数详解

欧拉函数 我们用 表示欧拉函数 定义: 表示对于整数n,小于等于n中与n互质的数的个数 性质 1. 为积性函数 证明: 此处证明需要用到下面计算方法1中的...

2704
来自专栏数值分析与有限元编程

Jacobi方法求矩阵特征值的算例及代码

Jacobi方法用于求实对称阵的全部特征值、特征向量。对于实对称阵 A,必有正交阵 Q ,使 QT A Q = Λ 其中Λ是对角阵,其主对角线元素λii是A的特...

2144
来自专栏云时之间

NLP入门之形式语言与自动机学习(一)

第一篇:集合与推理方法 1:我们为什么要学习形式语言与自动机 任何一门科学都有其自身的理论基础,计算机科学也是这样.大家现在看看计算机的技术变化的很快,现在我们...

63213

扫码关注云+社区