你印象中的線性規(guī)劃是什么樣的？先在二維平面上畫圖再找最優(yōu)解？
但畢竟是學(xué)理論嘛，大家或多或少都會(huì)覺得枯燥晦澀。那么為何不試試更加直觀、好玩的學(xué)習(xí)方式呢？例如這樣：
這是一位國外博主發(fā)布的機(jī)器學(xué)習(xí) 3D 教程，用可視化的方法展示如何在線性規(guī)劃問題中逐步逼近最優(yōu)解。
這篇帖子僅在一天之內(nèi)就在 Reddit 上收獲了接近 200 點(diǎn)的熱度：
還收到了很多網(wǎng)友的好評(píng)：
我喜歡對(duì)數(shù)學(xué)問題高度可視化的描述，太棒了！
是什么內(nèi)容這么優(yōu)質(zhì)？不妨看看他到底做了什么工作。
線性規(guī)劃也可以一目了然
關(guān)于線性規(guī)劃問題大家應(yīng)該都不陌生。
在一組線性方程或不等式的約束下，求某一線性目標(biāo)函數(shù)極值的問題就是線性規(guī)劃問題。
而它的其中一個(gè)解法，就是上文中動(dòng)圖展示的單純形法，還曾被評(píng)為 20 世紀(jì)最偉大的算法之一。在生產(chǎn)計(jì)劃，日程管理，交通運(yùn)輸，農(nóng)業(yè)等諸多領(lǐng)域都有廣泛的應(yīng)用。
接下來我們以一個(gè)生產(chǎn)計(jì)劃為例子做講解：
假如你現(xiàn)在是老板，經(jīng)營一家貨運(yùn)公司，一共有兩種貨車。
第一種貨車跑一趟需要兩天，燒 4 桶油，可以創(chuàng)造 1000 的利潤。
第二種跑一趟要 15 天，燒 8 桶油，但是可以創(chuàng)造 5000 的利潤。
那如果你手上有 500 桶油，應(yīng)該怎么配比兩種貨車的貨運(yùn)次數(shù)才能在一年內(nèi)獲得最大利潤呢？
這就是一個(gè)簡(jiǎn)單的線性規(guī)劃問題。
這樣的約束條件看起來并沒有什么感覺，但是放在空間中就不一樣了。
類似于許多平面把完整空間分割出一塊多面體：
分割出的多面體（粉色部分）為可行域或者可行多面體。它包含了所有符合約束條件的點(diǎn)。
線性規(guī)劃的目的，簡(jiǎn)單來說就是在可行多面體上找到一個(gè)點(diǎn)，來滿足預(yù)期。比如前面例子中的獲得最大利潤。
那應(yīng)該怎么找呢？博主對(duì)比了兩種辦法。
第一種是單純形法。
由于約束函數(shù)和目標(biāo)函數(shù)都是線性的，所以最優(yōu)解必然存在于可行多面體的頂點(diǎn)。
所以尋找最優(yōu)解的過程就可以描述為：沿著在可行多面體的棱上沿著目標(biāo)函數(shù)值增加的方向搜索頂點(diǎn)。
聽起來不明所以吧？但是用圖形解釋就清楚多了：
但是這個(gè)方法只能用于求解線性規(guī)劃的問題。對(duì)于非線性規(guī)劃就無能為力了。
而第二種內(nèi)點(diǎn)法，在更廣泛的凸集優(yōu)化問題中都可以應(yīng)用。
它和單純形法不同的地方在于，內(nèi)點(diǎn)法是通過增加一個(gè)懲罰函數(shù) P (x) 來不斷地調(diào)整路徑：
在逐漸靠近可行多面體邊界時(shí)，懲罰函數(shù)會(huì)取越來越小的值。
內(nèi)點(diǎn)法直觀來看是這樣的：
它不再沿著可行多面體的棱進(jìn)行迭代，而是直接從內(nèi)部開始，逐漸逼近最優(yōu)解。是不是一目了然了？
相比于純數(shù)學(xué)或者算法的推演，可視化的形式明顯更容易讓人印象深刻。
更多的可視化教程
除了這篇 3D 教程之外，該博主還在另一個(gè)介紹凸優(yōu)化的 KKT 條件和內(nèi)點(diǎn)法的視頻中，可視化了內(nèi)點(diǎn)法是如何通過牛頓迭代逐漸得到最優(yōu)解的：
視頻中 x (t) 每經(jīng)過一個(gè)黃色的圓框代表進(jìn)行一次牛頓迭代，左下方的圖像代表 x (t) 在不斷地迭代下趨近于最優(yōu)解。同樣，也比視頻上方的一長(zhǎng)串公式容易理解多了。
用這樣的形式去呈現(xiàn)復(fù)雜的內(nèi)容不禁讓網(wǎng)友聯(lián)想到了另一位可視化視頻博主：
好內(nèi)容！還看到了 3blue1brown 的影子，動(dòng)畫也很清晰。
在博主的回復(fù)中，也能看到他受到另一個(gè)數(shù)學(xué)可視化博主 3blue1brown 的啟發(fā)。
后者也同樣輸出了很多數(shù)學(xué)可視化的相關(guān)視頻，如果有興趣可以多多了解。
參考鏈接：
https://www.reddit.com/r/MachineLearning/comments/qtx8hn/d_back_to_basics_linear_programming/
廣告聲明：文內(nèi)含有的對(duì)外跳轉(zhuǎn)鏈接（包括不限于超鏈接、二維碼、口令等形式），用于傳遞更多信息，節(jié)省甄選時(shí)間，結(jié)果僅供參考，IT之家所有文章均包含本聲明。