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

相关文章

来自专栏Hongten

ArrayList VS Vector(ArrayList和Vector的区别)_面试的时候经常出现

1692
来自专栏xingoo, 一个梦想做发明家的程序员

Spark踩坑——java.lang.AbstractMethodError

百度了一下说是版本不一致导致的。于是重新检查各个jar包,发现spark-sql-kafka的版本是2.2,而spark的版本是2.3,修改spark-sql-...

1200
来自专栏alexqdjay

HashMap 多线程下死循环分析及JDK8修复

1K4
来自专栏学海无涯

Android开发之奇怪的Fragment

说起Android中的Fragment,在使用的时候稍加注意,就会发现存在以下两种: v4包中的兼容Fragment,android.support.v4.ap...

3155
来自专栏xingoo, 一个梦想做发明家的程序员

20120918-向量实现《数据结构与算法分析》

#include <iostream> #include <list> #include <string> #include <vector> #include...

1716
来自专栏MelonTeam专栏

ArrayList源码完全分析

导语: 这里分析的ArrayList是使用的JDK1.8里面的类,AndroidSDK里面的ArrayList基本和这个一样。 分析的方式是逐个API进行解析 ...

4489
来自专栏ml

朴素贝叶斯分类器(离散型)算法实现(一)

1. 贝叶斯定理:        (1)   P(A^B) = P(A|B)P(B) = P(B|A)P(A)   由(1)得    P(A|B) = P(B|...

3437
来自专栏计算机视觉与深度学习基础

Leetcode 114 Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place. For example, Given...

1938
来自专栏开发与安全

算法:AOV网(Activity on Vextex Network)与拓扑排序

在一个表示工程的有向图中,用顶点表示活动,用弧表示活动之间的优先关系,这样的有向图为顶点表示活动的网,我们称之为AOV网(Activity on Vextex ...

2517
来自专栏xingoo, 一个梦想做发明家的程序员

AOE关键路径

这个算法来求关键路径,其实就是利用拓扑排序,首先求出,每个节点最晚开始时间,再倒退求每个最早开始的时间。 从而算出活动最早开始的时间和最晚开始的时间,如果这两个...

2507

扫码关注云+社区