?作者 |?李航前

單位 |?EPFL

研究方向 |?計(jì)算機(jī)圖形學(xué)與三維視覺(jué)

最近學(xué)習(xí)了一些凸優(yōu)化課程，整理筆記的同時(shí)寫(xiě)下一些自己的理解，向著頭禿的道路上越走越遠(yuǎn)。

凸優(yōu)化是應(yīng)用數(shù)學(xué)的一個(gè)基本分支，幾乎在工程、基礎(chǔ)科學(xué)和經(jīng)濟(jì)學(xué)的所有領(lǐng)域都有應(yīng)用。例如，如果不理解凸優(yōu)化的對(duì)偶理論，就不可能完全理解統(tǒng)計(jì)學(xué)習(xí)中的支持向量機(jī)（SVM）、電力市場(chǎng)中的節(jié)點(diǎn)定價(jià)、經(jīng)濟(jì)學(xué)中的基本福利定理或兩人零和博弈中的納什均衡。在計(jì)算機(jī) AI 算法學(xué)習(xí)中，凸優(yōu)化也是必要的一環(huán)。

先來(lái)做一些鋪墊，引用自 EPFL 的凸優(yōu)化課程，首先來(lái)看一個(gè)數(shù)學(xué)優(yōu)化問(wèn)題，如下圖，該問(wèn)題是為了尋找目標(biāo)函數(shù)的最小值，其中涉及了目標(biāo)函數(shù)，決策變量，可行域等概念。

▲ from MGT-418 Convex Optimization?

下面在說(shuō)下確界的問(wèn)題，下確界一定有（可以是負(fù)無(wú)窮）但是最小值不一定有。

▲?from MGT-418 Convex Optimization

▲ from MGT-418 Convex Optimization

以上說(shuō)了全局最小值，但是一些情況下沒(méi)有辦法獲得全局最小值，所以就要去計(jì)算局部最小值。它叫 優(yōu)化問(wèn)題。

▲ from MGT-418 Convex Optimization

下圖可視化展示了全局最小值和局部最小值的區(qū)別。

有了一些直觀的認(rèn)識(shí)和淺顯的理解，下面我們來(lái)具體聊凸函數(shù)的概念及判定方法、凸集、常見(jiàn)目標(biāo)函數(shù)。

凸集和凸函數(shù)

從函數(shù)的凹凸性而言，我們通常把函數(shù)分為凸函數(shù)和非凸函數(shù)。凸函數(shù)是有且只有全局最優(yōu)解的，而非凸函數(shù)可能有多個(gè)局部最優(yōu)解，這些特性我會(huì)在下文中進(jìn)行詳細(xì)解釋。在前言中，我提到過(guò)優(yōu)化問(wèn)題是機(jī)器學(xué)習(xí)模型中的核心部分，而針對(duì)不同模型，有不同的方法論對(duì)其目標(biāo)函數(shù)進(jìn)行優(yōu)化。例如針對(duì)邏輯回歸、線性回歸這樣的凸函數(shù)，使用梯度下降或者牛頓法可以求出參數(shù)的全局最優(yōu)解，針對(duì)神經(jīng)網(wǎng)絡(luò)這樣的非凸函數(shù)，我們可能會(huì)找到許多局部最優(yōu)解。

不難看出，我們希望在實(shí)際解決問(wèn)題過(guò)程中，都希望我們建立的目標(biāo)函數(shù)是凸函數(shù)，這樣我們不必?fù)?dān)心局部最優(yōu)解問(wèn)題，但實(shí)際上，我們遇到的問(wèn)題大多數(shù)情況下建立的目標(biāo)函數(shù)都是非凸函數(shù)，因此我們需要根據(jù)場(chǎng)景選擇不同的優(yōu)化方法。

凸優(yōu)化定義

就定義而言，凸優(yōu)化是：在最小化（最大化）的優(yōu)化要求下，目標(biāo)函數(shù)是凸函數(shù)且約束條件所形成的可行域集合是一個(gè)凸集的優(yōu)化方法，因此凸優(yōu)化的判定條件有兩個(gè)，1.函數(shù)定義域是凸集 2.目標(biāo)函數(shù)是凸函數(shù)。

凸集的定義：假設(shè)對(duì)于任意 x, y ∈ C and 任意參數(shù) α ∈ [0, 1], 我們有 αx + (1 ? α)y ∈ C，集合 C 為凸集。

凸集的理解：對(duì)凸集的理解，我們可以分別從理論定義的角度和函數(shù)圖像的角度兩方面理解。從定義上講，對(duì)于集合 C 中的任意兩個(gè)元素 x 和 y，需要滿(mǎn)足 αx + (1?α)y 的值也需要在集合 C 中；從函數(shù)圖像角度講，這個(gè)定義中的式子含義是，x、y 兩點(diǎn)連線上的任意一個(gè)點(diǎn)都需要屬于集合 C，如下圖所示，任何證明集合是凸集的方法都可以通過(guò)定義和函數(shù)圖像兩方面進(jìn)行。

凸集的性質(zhì)：兩個(gè)凸集的交集也是凸集。（注意，兩個(gè)凸集的并集就不一定還是凸集了）

常見(jiàn)凸集與證明方法：

凸函數(shù)定義：函數(shù) f 的定義域?yàn)橥辜?#xff0c;對(duì)于定義域里的任意 x, y，函數(shù)滿(mǎn)足：

凸函數(shù)與凹函數(shù)之間的關(guān)系：如果 f(x) 是凸函數(shù)，則 -f(x) 是凹函數(shù)

凸函數(shù)的證明方法（函數(shù)定義域?yàn)橥辜那疤嵯?#xff09;：

常見(jiàn)凸函數(shù)及證明

常見(jiàn)目標(biāo)函數(shù)

針對(duì)一個(gè) AI 問(wèn)題，我們都可以將 AI 問(wèn)題拆解為建立模型+優(yōu)化模型這兩塊內(nèi)容的，對(duì)于任何一個(gè) AI 問(wèn)題，其目標(biāo)函數(shù)都可以用以下形式表示：

我將解決業(yè)務(wù)問(wèn)題中的常用套路稱(chēng)為算法思維，并總結(jié)了以下 4 個(gè)重要步驟：

將業(yè)務(wù)場(chǎng)景中需要解決的問(wèn)題轉(zhuǎn)化為數(shù)學(xué)問(wèn)題，并寫(xiě)出嚴(yán)格的數(shù)學(xué)模型（目標(biāo)函數(shù)）

針對(duì)寫(xiě)出的數(shù)學(xué)模型判斷凹凸性

根據(jù)目標(biāo)的函數(shù)的凹凸性判斷問(wèn)題類(lèi)型（如果目標(biāo)函數(shù)是凸函數(shù)，我們需要判斷該函數(shù)所屬問(wèn)題類(lèi)型，常見(jiàn)的問(wèn)題類(lèi)型有 Linear Programming、Quadratic Programming 等；如果目標(biāo)函數(shù)是非凸函數(shù)，也需要判斷其所屬問(wèn)題類(lèi)型，常見(jiàn)有 Setcover Problem，Max flow Problem 等）

根據(jù)不同的問(wèn)題類(lèi)型使用不同的優(yōu)化方法論解決問(wèn)題。

其實(shí)在實(shí)際解決問(wèn)題的過(guò)程中，其實(shí)大家都不太會(huì)在意第 1,2 個(gè)步驟點(diǎn)，可能都會(huì)直接通過(guò)經(jīng)驗(yàn)去查找相應(yīng)的工具解決問(wèn)題，但是這樣的解決思路是不太好的，因?yàn)樵谶@個(gè)過(guò)程中，我們可能不知道需要解決的問(wèn)題和我們選擇的工具是否匹配，如果結(jié)果不太理想，我們可能也不知道其中的原因。但是如果我們?cè)诮鉀Q問(wèn)題前，定義了嚴(yán)格的目標(biāo)函數(shù)，我們不僅可以針對(duì)該目標(biāo)函數(shù)選擇相應(yīng)的優(yōu)化方法，也可以根據(jù)業(yè)務(wù)場(chǎng)景，對(duì)目標(biāo)函數(shù)進(jìn)行相應(yīng)調(diào)整，增加項(xiàng)目的成功率。

而實(shí)際工作中常見(jiàn)的目標(biāo)函數(shù)大概有以下：

參考文獻(xiàn)

[1] EE-556：https://moodle.epfl.ch/course/view.php?id=14220

[2] MGT-418：https://moodle.epfl.ch/course/view.php?id=15778

[3] AI工程師必備技能-凸優(yōu)化介紹：https://www.jiqizhixin.com/articles/2019-01-23-15

特別鳴謝

感謝 TCCI 天橋腦科學(xué)研究院對(duì)于 PaperWeekly 的支持。TCCI 關(guān)注大腦探知、大腦功能和大腦健康。

更多閱讀

#投 稿?通 道#

?讓你的文字被更多人看到?

如何才能讓更多的優(yōu)質(zhì)內(nèi)容以更短路徑到達(dá)讀者群體，縮短讀者尋找優(yōu)質(zhì)內(nèi)容的成本呢？答案就是：你不認(rèn)識(shí)的人。

總有一些你不認(rèn)識(shí)的人，知道你想知道的東西。PaperWeekly 或許可以成為一座橋梁，促使不同背景、不同方向的學(xué)者和學(xué)術(shù)靈感相互碰撞，迸發(fā)出更多的可能性。?

PaperWeekly 鼓勵(lì)高校實(shí)驗(yàn)室或個(gè)人，在我們的平臺(tái)上分享各類(lèi)優(yōu)質(zhì)內(nèi)容，可以是最新論文解讀，也可以是學(xué)術(shù)熱點(diǎn)剖析、科研心得或競(jìng)賽經(jīng)驗(yàn)講解等。我們的目的只有一個(gè)，讓知識(shí)真正流動(dòng)起來(lái)。

📝?稿件基本要求：

? 文章確系個(gè)人原創(chuàng)作品，未曾在公開(kāi)渠道發(fā)表，如為其他平臺(tái)已發(fā)表或待發(fā)表的文章，請(qǐng)明確標(biāo)注?

? 稿件建議以?markdown?格式撰寫(xiě)，文中配圖以附件形式發(fā)送，要求圖片清晰，無(wú)版權(quán)問(wèn)題

? PaperWeekly 尊重原作者署名權(quán)，并將為每篇被采納的原創(chuàng)首發(fā)稿件，提供業(yè)內(nèi)具有競(jìng)爭(zhēng)力稿酬，具體依據(jù)文章閱讀量和文章質(zhì)量階梯制結(jié)算

📬?投稿通道：

? 投稿郵箱：hr@paperweekly.site?

? 來(lái)稿請(qǐng)備注即時(shí)聯(lián)系方式（微信），以便我們?cè)诟寮x用的第一時(shí)間聯(lián)系作者

? 您也可以直接添加小編微信（pwbot02）快速投稿，備注：姓名-投稿

△長(zhǎng)按添加PaperWeekly小編

🔍

現(xiàn)在，在「知乎」也能找到我們了

進(jìn)入知乎首頁(yè)搜索「PaperWeekly」

點(diǎn)擊「關(guān)注」訂閱我們的專(zhuān)欄吧

·

總結(jié)

以上是生活随笔為你收集整理的对凸优化（Convex Optimization）的一些浅显理解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。