你印象中的线性规划是什么样的?先在二维平面上画图再找最优解?
但毕竟是学理论嘛,大家或多或少都会觉得枯燥晦涩。那么为何不试试更加直观、好玩的学习方式呢?例如这样:
这是一位国外博主发布的机器学习 3D 教程,用可视化的方法展示如何在线性规划问题中逐步逼近最优解。
这篇帖子仅在一天之内就在 Reddit 上收获了接近 200 点的热度:
还收到了很多网友的好评:
我喜欢对数学问题高度可视化的描述,太棒了!
是什么内容这么优质?不妨看看他到底做了什么工作。
线性规划也可以一目了然
关于线性规划问题大家应该都不陌生。
在一组线性方程或不等式的约束下,求某一线性目标函数极值的问题就是线性规划问题。
而它的其中一个解法,就是上文中动图展示的单纯形法,还曾被评为 20 世纪最伟大的算法之一。在生产计划,日程管理,交通运输,农业等诸多领域都有广泛的应用。
接下来我们以一个生产计划为例子做讲解:
假如你现在是老板,经营一家货运公司,一共有两种货车。
第一种货车跑一趟需要两天,烧 4 桶油,可以创造 1000 的利润。
第二种跑一趟要 15 天,烧 8 桶油,但是可以创造 5000 的利润。
那如果你手上有 500 桶油,应该怎么配比两种货车的货运次数才能在一年内获得最大利润呢?
这就是一个简单的线性规划问题。
这样的约束条件看起来并没有什么感觉,但是放在空间中就不一样了。
类似于许多平面把完整空间分割出一块多面体:
分割出的多面体(粉色部分)为可行域或者可行多面体。它包含了所有符合约束条件的点。
线性规划的目的,简单来说就是在可行多面体上找到一个点,来满足预期。比如前面例子中的获得最大利润。
那应该怎么找呢?博主对比了两种办法。
第一种是单纯形法。
由于约束函数和目标函数都是线性的,所以最优解必然存在于可行多面体的顶点。
所以寻找最优解的过程就可以描述为:沿着在可行多面体的棱上沿着目标函数值增加的方向搜索顶点。
听起来不明所以吧?但是用图形解释就清楚多了:
但是这个方法只能用于求解线性规划的问题。对于非线性规划就无能为力了。
而第二种内点法,在更广泛的凸集优化问题中都可以应用。
它和单纯形法不同的地方在于,内点法是通过增加一个惩罚函数 P (x) 来不断地调整路径:
在逐渐靠近可行多面体边界时,惩罚函数会取越来越小的值。
内点法直观来看是这样的:
它不再沿着可行多面体的棱进行迭代,而是直接从内部开始,逐渐逼近最优解。是不是一目了然了?
相比于纯数学或者算法的推演,可视化的形式明显更容易让人印象深刻。
更多的可视化教程
除了这篇 3D 教程之外,该博主还在另一个介绍凸优化的 KKT 条件和内点法的视频中,可视化了内点法是如何通过牛顿迭代逐渐得到最优解的:
视频中 x (t) 每经过一个黄色的圆框代表进行一次牛顿迭代,左下方的图像代表 x (t) 在不断地迭代下趋近于最优解。同样,也比视频上方的一长串公式容易理解多了。
用这样的形式去呈现复杂的内容不禁让网友联想到了另一位可视化视频博主:
好内容!还看到了 3blue1brown 的影子,动画也很清晰。
在博主的回复中,也能看到他受到另一个数学可视化博主 3blue1brown 的启发。
后者也同样输出了很多数学可视化的相关视频,如果有兴趣可以多多了解。
参考链接:
https://www.reddit.com/r/MachineLearning/comments/qtx8hn/d_back_to_basics_linear_programming/
话题标签:3D
- 最热文章
- 1男子头顶西瓜骑电动车被查:不戴头盔、自称在锻炼身体阅读:102632
- 2韩国暴雨 首尔上演现实版《寄生虫》:降雨量可怕 现场狼藉阅读:87356
- 3苏炳添是苏轼后代上热搜 被写入苏氏宗祠:网友评论厉害了阅读:62999
- 4董明珠:格力1万台空调仅3台需要维修阅读:51130
- 517年坚持2元不涨价:武汉糖水爷爷遭网暴 不摆摊了阅读:44625
- 6电视不良率竟达20%!乐视痛斥南京熊猫:钱都被当竹子吃了阅读:41762
- 7RTX 40马上供货中国!黄仁勋严令RTX 30全力清库存阅读:41690
- 8台风木兰登陆 女子吹成“赛亚人:画面逗乐网友 喜提新造型阅读:38801
- 9与两只骆驼发生碰撞致人死亡 于月仙车祸肇事人被判1年阅读:36805
- 10爱马仕推出新款自行车:28斤重、卖16.5万阅读:36159
- 关注我们
-
微博:快科技官方
快科技(原驱动之家)官方微博 -
今日头条:快科技
带来硬件软件、手机数码最快资讯! -
抖音:快科技mydrivers
科技快讯、手机开箱、产品体验、应用推荐...