優(yōu)化 | 為什么凸優(yōu)化這么重要？

原文鏈接：https://www.zhihu.com/question/24641575

以下整理按照知乎全部回答的默認(rèn)排序

1.為什么凸優(yōu)化重要?

凸優(yōu)化性質(zhì)好，許多日常生活中的非凸優(yōu)化問(wèn)題，目前最有效的辦法也只能是利用凸優(yōu)化的思路去近似求解。

例如：

● 帶整數(shù)變量的優(yōu)化問(wèn)題，松弛之后變成凸優(yōu)化問(wèn)題（所以原問(wèn)題其實(shí)是凸優(yōu)化問(wèn)題+整數(shù)變量）；

● 任意帶約束的非凸連續(xù)優(yōu)化問(wèn)題，其對(duì)偶問(wèn)題作為原問(wèn)題解的一個(gè)lower bound，一定是凸的！

● 針對(duì)帶有hidden variable的近似求解maximum likelihood estimate的EM算法，或者貝葉斯版本里頭所謂的variational Bayes(VB) inference。而原本的MLE其實(shí)是非凸優(yōu)化問(wèn)題，所以EM和VB算法都是找到了一個(gè)比較好優(yōu)化的concave lower bound對(duì)這個(gè)lower bound進(jìn)行優(yōu)化。

這是什么意思呢？

也就是說(shuō)到今天2019年為止，我們還是只對(duì)凸優(yōu)化問(wèn)題比較有把握。

當(dāng)然有人可能要說(shuō)了，現(xiàn)在各種深度強(qiáng)化學(xué)習(xí)、深度學(xué)習(xí)的優(yōu)化問(wèn)題都是極其復(fù)雜的非凸優(yōu)化問(wèn)題，不是大家也能解的挺好？

這個(gè)問(wèn)題的回答就更難一些，我個(gè)人觀點(diǎn)，簡(jiǎn)單來(lái)說(shuō)是這樣，目前對(duì)于這些非凸優(yōu)化問(wèn)題取得的算法理論方面的突破大體其實(shí)歸結(jié)于找到這些非凸優(yōu)化問(wèn)題中“凸”的結(jié)構(gòu)。這也是為什么我們看到一階算法（SGD, ADAM等）仍然大行其道，而分析這些非凸優(yōu)化算法的時(shí)候其實(shí)很多的lemma（引理）仍然是凸優(yōu)化（凸分析）里的引理或者引申。

舉個(gè)例子：

我們大家都知道凸函數(shù)的各種等價(jià)定義。而在Zeyuan Allen-Zhu的一系列非凸優(yōu)化算法的文章中所謂的非凸性的刻畫(huà)仍然是基于此衍生出來(lái)的：

來(lái)源：Allen-Zhu, Zeyuan. Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter. International Conference on Machine Learning. 2017.

我們知道它里面這個(gè)刻畫(huà)非凸性的參數(shù) ，如果取成0，那就等價(jià)于凸函數(shù)的定義，如果取成負(fù)的，那么實(shí)際上就是所謂strongly convex，而如果是正的，就變成它這里的non-convexity了。實(shí)際上，現(xiàn)在非凸優(yōu)化里面很多的非凸性刻畫(huà)都是脫胎于凸優(yōu)化，比如prox regularity之類的，或者一些更弱的convexity定義（這在經(jīng)典凸分析里就已經(jīng)有不少研究了，quasi-convex，psuedo-convex等等），這里不再贅述。

個(gè)人認(rèn)為，我們能真正一般化地解決非凸優(yōu)化問(wèn)題，那肯定是要對(duì)一般的混合整數(shù)（線性）規(guī)劃（MILP, mixed integer linear programming）要有好的辦法求解才算。因?yàn)槿我庖粋€(gè)非凸優(yōu)化問(wèn)題，都可以用很多的分段線性函數(shù)逼近，最后變成一個(gè)MILP。當(dāng)然，因?yàn)镻!=NP這個(gè)猜想的存在，這件事情在理論上肯定是hopeless，但是在實(shí)際當(dāng)中，基于硬件能力的提升，還有比如量子計(jì)算機(jī)一類的新技術(shù)，我個(gè)人對(duì)人類未來(lái)能夠在實(shí)際中求解MILP還是持一個(gè)比較樂(lè)觀的態(tài)度。到那個(gè)時(shí)候，我覺(jué)得我們才能說(shuō)傳統(tǒng)的凸優(yōu)化理論才是真正過(guò)時(shí)了。

2. 現(xiàn)有的優(yōu)化方法不是都能解決（凸優(yōu)化）嗎？那凸優(yōu)化又有什么用呢？

首先先明確一點(diǎn)，凸優(yōu)化難嗎？嗯相比非凸優(yōu)化，各種NP-complete問(wèn)題，凸優(yōu)化里各種P問(wèn)題，那肯定是簡(jiǎn)單的。然而，在實(shí)際當(dāng)中，我們完全不可能滿足于有一個(gè)“多項(xiàng)式時(shí)間算法”就好了。

我們知道，運(yùn)籌學(xué)，優(yōu)化問(wèn)題，反映到現(xiàn)實(shí)世界里面就是各種數(shù)學(xué)建模問(wèn)題。這些問(wèn)題，普遍地出現(xiàn)在航空業(yè)、金融業(yè)、廣告業(yè)、電商零售業(yè)、能源業(yè)、醫(yī)療業(yè)、交通業(yè)等各個(gè)領(lǐng)域。我們必須要明確一點(diǎn)，計(jì)算復(fù)雜性理論（P,NP這套東西）在實(shí)際當(dāng)中其實(shí)是沒(méi)什么用處的。嗯，NP hard, NP complete問(wèn)題很難，沒(méi)有多項(xiàng)式時(shí)間算法，但如果你實(shí)際的問(wèn)題規(guī)模不太大，比如幾十個(gè)城市的旅行商問(wèn)題（TSP, travelling salesman problem），幾十x幾十的圖上的NP-complete問(wèn)題，是不是很難？然而現(xiàn)在2019年，你在iphone上下個(gè)app，一部小小的手機(jī)不要幾秒鐘就能給你算出最優(yōu)解。（實(shí)際上，他們這個(gè)app，1000個(gè)左右城市的TSP， iphone也頂多要算個(gè)幾小時(shí)就能找到全局最優(yōu)解，無(wú)近似）

TSP求解app，當(dāng)然，這得益于Concorde他們家目前行業(yè)領(lǐng)先的解大規(guī)模TSP底層算法...

與此相對(duì)應(yīng)的，即使是一個(gè)P問(wèn)題，但是如果實(shí)際當(dāng)中你的問(wèn)題規(guī)模超級(jí)大呢？實(shí)際上反而這個(gè)問(wèn)題會(huì)讓你更頭疼的。

舉個(gè)例子，比如現(xiàn)在優(yōu)酷、天貓、京東、亞馬遜這些個(gè)平臺(tái)，每天你登陸網(wǎng)站，它在推薦欄都需要根據(jù)你的歷史活動(dòng)記錄決定推薦哪些產(chǎn)品給你。這個(gè)在線推薦算法，本質(zhì)上只是需要求解一個(gè)線性規(guī)劃問(wèn)題（LP, linear programming, 比一般的凸優(yōu)化還簡(jiǎn)單），甚至還不是一個(gè)一般的線性規(guī)劃，有個(gè)專門(mén)的名字叫做packing LP，這類packing LP理論上可以有跟問(wèn)題規(guī)模呈線性的復(fù)雜度的算法（忽略log項(xiàng)，跟排個(gè)序差不多...）。聽(tīng)起來(lái)是不是很簡(jiǎn)單？然而，實(shí)際這些問(wèn)題的規(guī)模無(wú)比巨大，每天這些平臺(tái)上線人次數(shù)以億記，這些平臺(tái)可以推薦的商品也是至少百萬(wàn)千萬(wàn)規(guī)模的。。而且實(shí)際問(wèn)題還有各種各樣的現(xiàn)實(shí)約束，比如我們希望我們的算法可以完全在線更新（online，甚至是streaming algorithm），我們的算法需要靈活運(yùn)用存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，需要利用計(jì)算集群的并行能力，分布式能力，這也是需要非常非常專門(mén)的（一階）優(yōu)化算法設(shè)計(jì)的。。這邊就不再多說(shuō)了，因?yàn)槲覀€(gè)人確實(shí)在之前公司實(shí)習(xí)的時(shí)候，發(fā)現(xiàn)中國(guó)最好的IT公司面對(duì)這類海量規(guī)模的“簡(jiǎn)單”LP，實(shí)際上遠(yuǎn)沒(méi)有能力去完美地求解。

因此你說(shuō)現(xiàn)有的方法能解決所有的凸優(yōu)化問(wèn)題，但從實(shí)際的角度其實(shí)還差的遠(yuǎn)。事實(shí)上，目前的大公司面對(duì)如此規(guī)模的優(yōu)化問(wèn)題，也就LP還可以勉強(qiáng)接受，像是什么second-order cone prorgamming (SOCP), semidefinite programming (SDP)根本目前實(shí)際中都不可能大規(guī)模求解。而這兩類問(wèn)題在理論上還仍然都是“線性”的，因?yàn)榭梢詫?xiě)成linear conic programming，所以就更不要說(shuō)一般的帶約束的凸優(yōu)化問(wèn)題了。

實(shí)際上，在這個(gè)方面，無(wú)論是求解器（solver）還是更好的理論算法的開(kāi)發(fā)都還有大量的研究空間。比如，SDP實(shí)際當(dāng)中的大規(guī)模算法設(shè)計(jì)目前來(lái)看還基本一片空白，有很多很基本的問(wèn)題都還沒(méi)有在理論上得到滿意的解答（像SDP其實(shí)和另一類凸優(yōu)化問(wèn)題只有一絲之隔，copositive programming，而這類凸優(yōu)化問(wèn)題的計(jì)算復(fù)雜度卻是NP complete的，所以即使是凸優(yōu)化也未必復(fù)雜度就容易！實(shí)際上，所有mixed 0/1 nonconvex quadratic program都可以寫(xiě)成copositive program這個(gè)凸優(yōu)化的形式。兩者的算法設(shè)計(jì)也因此都很蛋疼）。。還有這么多沒(méi)有解決的問(wèn)題，又如何能說(shuō)凸優(yōu)化的問(wèn)題都已經(jīng)被“解決”了呢？

至于具體如何把mixed 0/1 nonconvex quadratic program寫(xiě)成凸優(yōu)化形式，這是個(gè)很cute的結(jié)果，有興趣的同學(xué)可見(jiàn)我這篇專欄文章的第二部分。

https://zhuanlan.zhihu.com/p/34772469 

隨手寫(xiě)寫(xiě)沒(méi)想到也吐了不少嘈，我這邊最后就再總結(jié)個(gè)幾點(diǎn)吧：

● 做研究過(guò)程中，切忌輕易下結(jié)論。

實(shí)際上，對(duì)很多看似已經(jīng)“解決”的問(wèn)題，你如果肯花點(diǎn)功夫研究研究，會(huì)發(fā)現(xiàn)總有很多細(xì)節(jié)是值得深思的。更不要說(shuō)直接說(shuō)一個(gè)大的研究領(lǐng)域就已經(jīng)被“解決”了。我記得前不久還看到NeurlIPs文章的方向匯總，凸優(yōu)化仍然是優(yōu)化方向文章里數(shù)量最多（還是第二多，具體記不清了）的。因?yàn)閷?shí)際上我前面還有很多沒(méi)提，比如像現(xiàn)在很火的強(qiáng)化學(xué)習(xí)（或者說(shuō)多階段的隨機(jī)動(dòng)態(tài)規(guī)劃）里面還有大量的凸優(yōu)化問(wèn)題沒(méi)搞定。。

● 基礎(chǔ)永遠(yuǎn)是重要的。

而凸優(yōu)化就是你做非凸優(yōu)化研究的基礎(chǔ)。這么些年來(lái)，我自己也逐漸體會(huì)，研究當(dāng)中最常用的，真的還就是那些最基礎(chǔ)的微積分，線性代數(shù)，概率統(tǒng)計(jì)的基本功。很多問(wèn)題，如果你有基礎(chǔ)，就都直接不是問(wèn)題了；反過(guò)來(lái)，如果當(dāng)初在學(xué)習(xí)過(guò)程中冒進(jìn)，去追求最前沿，最時(shí)髦，最fancy的topic，卻沒(méi)好好打基礎(chǔ)，你可能就會(huì)發(fā)現(xiàn)很多基本的知識(shí)本來(lái)都不應(yīng)該成為障礙，最后卻各種讓你磕磕絆絆。

● 作為優(yōu)化研究者，埋頭研究的同時(shí)，一定要睜開(kāi)眼睛看看業(yè)界的實(shí)際情況。

當(dāng)然，總有一部分優(yōu)化大師是不在乎實(shí)際應(yīng)用的（然而Nesterov, Nemirovski這樣的人也是有應(yīng)用文章的），有志做令人高山仰止的大師的就可以忽略我這條了。我只是想說(shuō)，對(duì)于大多數(shù)做優(yōu)化的人，我們實(shí)際上應(yīng)該都是希望自己做的東西可以用在業(yè)界的實(shí)際問(wèn)題當(dāng)中。那么這個(gè)時(shí)候除了學(xué)理論知識(shí)，真的我們應(yīng)該多hands on，get your hands dirty。我自己的體會(huì)是，往往都是在實(shí)際寫(xiě)代碼求解問(wèn)題的時(shí)候才會(huì)對(duì)很多知識(shí)有更深刻的理解，并且能找到真正值得研究的有意思的問(wèn)題。

convexity is sexy~

前言：運(yùn)籌學(xué)在國(guó)內(nèi)，遠(yuǎn)沒(méi)有統(tǒng)計(jì)和人工智能來(lái)的普及。

相信很多人不知道，運(yùn)籌學(xué)正是研究?jī)?yōu)化理論的學(xué)科（包括凸優(yōu)化），而人工智能模型最后幾乎都能化簡(jiǎn)成求解一個(gè)能量/損失函數(shù)的優(yōu)化問(wèn)題。因此，我把它稱為人工智能、大數(shù)據(jù)的“引擎”。（本文的詳細(xì)版本已發(fā)表在@運(yùn)籌OR帷幄專欄：離散/整數(shù)/組合/非凸優(yōu)化概述及其在AI的應(yīng)用 - 知乎專欄）

言歸正傳，為什么凸優(yōu)化這么重要？

1. 首先大家需要知道Convex VS Non-Convex的概念吧？

數(shù)學(xué)定義就不寫(xiě)了，介紹個(gè)直觀判斷一個(gè)集合是否為Convex的方法，如下圖：

簡(jiǎn)單的測(cè)試一個(gè)集合是不是凸的，只要任意取集合中的倆個(gè)點(diǎn)并連線，如果說(shuō)連線段完全被包含在此集合中，那么這個(gè)集合就是凸集，例如左圖所示。

2. 凸優(yōu)化-相對(duì)簡(jiǎn)單

凸優(yōu)化有個(gè)非常重要的定理，即任何局部最優(yōu)解即為全局最優(yōu)解。由于這個(gè)性質(zhì)，只要設(shè)計(jì)一個(gè)較為簡(jiǎn)單的局部算法，例如貪婪算法（Greedy Algorithm）或梯度下降法（Gradient Decent），收斂求得的局部最優(yōu)解即為全局最優(yōu)。因此求解凸優(yōu)化問(wèn)題相對(duì)來(lái)說(shuō)是比較高效的。

另一個(gè)側(cè)面，可微分的凸優(yōu)化問(wèn)題滿足KKT條件，因此容易求解：

【學(xué)界】關(guān)于KKT條件的深入探討

這也是為什么機(jī)器學(xué)習(xí)中凸優(yōu)化的模型非常多，畢竟機(jī)器學(xué)習(xí)處理海量的數(shù)據(jù)，需要非常高效的算法。

3，非凸優(yōu)化-非常困難

而非凸優(yōu)化問(wèn)題被認(rèn)為是非常難求解的，因?yàn)榭尚杏蚣峡赡艽嬖跓o(wú)數(shù)個(gè)局部最優(yōu)點(diǎn)，通常求解全局最優(yōu)的算法復(fù)雜度是指數(shù)級(jí)的（NP難）。如下圖：

最經(jīng)典的算法要算蒙特卡羅投點(diǎn)法了，大概思想便是隨便投個(gè)點(diǎn)，然后在附近區(qū)域（可以假設(shè)convex）用2中方法的進(jìn)行搜索，得到局部最優(yōu)值。然后隨機(jī)再投個(gè)點(diǎn)，再找到局部最優(yōu)點(diǎn)--如此反復(fù)，直到滿足終止條件。

假設(shè)有1w個(gè)局部最優(yōu)點(diǎn)，你至少要投點(diǎn)1w次吧？并且你還要假設(shè)每次投點(diǎn)都投到了不同的區(qū)域，不然你只會(huì)搜索到以前搜索過(guò)的局部最優(yōu)點(diǎn)。

4. 為何要學(xué)習(xí)非凸優(yōu)化呢？

因?yàn)楝F(xiàn)實(shí)生活中，幾乎所有問(wèn)題的本質(zhì)都是非凸的。

把3中的圖看作山川盆地，你在現(xiàn)實(shí)中有見(jiàn)過(guò)左圖這么“光滑”的地形么？右圖才是Reality！

5. 凸優(yōu)化為何這么重要呢？

科學(xué)的本質(zhì)便是由簡(jiǎn)到難，先把簡(jiǎn)單問(wèn)題研究透徹，然后把復(fù)雜問(wèn)題簡(jiǎn)化為求解一個(gè)個(gè)的簡(jiǎn)單問(wèn)題。

例如3中經(jīng)典的蒙特卡羅投點(diǎn)法，就是在求解一個(gè)個(gè)的凸優(yōu)化問(wèn)題。

假設(shè)需要求解1w個(gè)凸優(yōu)化問(wèn)題可以找到非凸優(yōu)化的全局最優(yōu)點(diǎn)，那么凸優(yōu)化被研究透徹了，會(huì)加速凸優(yōu)化問(wèn)題的求解時(shí)間，例如0.001秒。這樣求解非凸優(yōu)化問(wèn)題=求解1w個(gè)凸優(yōu)化問(wèn)題=10秒，還是可以接受的嘛！【學(xué)界】非凸轉(zhuǎn)成凸、約束轉(zhuǎn)無(wú)約－運(yùn)籌學(xué)和支持向量機(jī)中的拉格朗日松弛法

6. 運(yùn)籌學(xué)中線性規(guī)劃與凸優(yōu)化的關(guān)系

線性規(guī)劃是運(yùn)籌學(xué)最基礎(chǔ)的課程，其可行域（可行解的集合）是多面體（polyhedron），具有著比普通的凸集更好的性質(zhì)。

因此是比較容易求解的（多項(xiàng)式時(shí)間可解）。

如有興趣，且聽(tīng)我嘮叨一下關(guān)于運(yùn)籌學(xué)的四個(gè)知乎 Live

7. 運(yùn)籌學(xué)中（混合）整數(shù)規(guī)劃與非凸優(yōu)化的關(guān)系

大家或許不知道，（混合）整數(shù)規(guī)劃被稱為極度非凸問(wèn)題（highly nonconvex problem），如下圖：

實(shí)心黑點(diǎn)組成的集合，是一個(gè)離散集，按照1中判斷一個(gè)集合是否為凸集的技巧，我們很容易驗(yàn)證這個(gè)離散集是非凸的。

因此整數(shù)規(guī)劃問(wèn)題也是一個(gè)非凸優(yōu)化問(wèn)題，并且它也是NP難的。

那么整數(shù)規(guī)劃的求解思路呢，也遵循了科學(xué)研究的本質(zhì)，即被分解為求解一個(gè)個(gè)的線性規(guī)劃（凸優(yōu)化）問(wèn)題。

感興趣的朋友可以搜索參考下文：

【學(xué)界】混合整數(shù)規(guī)劃/離散優(yōu)化的精確算法--分支定界法及優(yōu)化求解器

8.（混合）整數(shù)規(guī)劃為何重要？

雖然時(shí)間是連續(xù)的，但是社會(huì)時(shí)間卻是離散的。例如時(shí)刻表，通常都是幾時(shí)幾分，即使精確到幾秒，它還是離散的（整數(shù)）。沒(méi)見(jiàn)過(guò)小數(shù)計(jì)數(shù)的時(shí)刻表吧？

同樣，對(duì)現(xiàn)實(shí)社會(huì)各行各業(yè)問(wèn)題數(shù)學(xué)建模的時(shí)候，整數(shù)變量有時(shí)是不可避免的。例如：x輛車，y個(gè)人。x，y這里便是整數(shù)變量，小數(shù)是沒(méi)有意義的。

9. 深度學(xué)習(xí)為何非凸？

深度學(xué)習(xí)里的損失函數(shù)，是一個(gè)高度復(fù)合的函數(shù)。什么叫復(fù)合函數(shù)？好吧，例如h(x)=f(g(x))就是一個(gè)f和g復(fù)合函數(shù)。

當(dāng)f，g都是線性的時(shí)候，h是線性的。但在深度學(xué)習(xí)里用到的函數(shù)，Logistic, ReLU等等，都是非線性 ，并且非常多。把他們復(fù)合起來(lái)形成的函數(shù)h,便是非凸的。

求解這個(gè)非凸函數(shù)的最優(yōu)解，類似于求凸優(yōu)化中某點(diǎn)的gradient，然后按照梯度最陡的方向搜索。不同的是，復(fù)合函數(shù)無(wú)法求gradient，于是這里使用Back Propagation求解一個(gè)類似梯度的東西，反饋能量，然后更新。

10. 深度學(xué)習(xí)的優(yōu)化問(wèn)題在運(yùn)籌學(xué)看來(lái)是“小兒科”

這句話可能會(huì)打臉大部分觀眾。

深度學(xué)習(xí)中的優(yōu)化問(wèn)題，雖然目標(biāo)函數(shù)非常復(fù)雜，但是它沒(méi)有約束阿，是一個(gè)無(wú)約束優(yōu)化問(wèn)題！

大家如果學(xué)過(guò)運(yùn)籌學(xué)，就知道它由目標(biāo)函數(shù)和約束條件組成，而約束條件，是使得運(yùn)籌學(xué)的優(yōu)化問(wèn)題難以求解的重要因素（需要搜尋可行解）。

關(guān)于運(yùn)籌學(xué)與人工智能更多的交叉與應(yīng)用（自動(dòng)駕駛），

參見(jiàn)知乎Live：理工科的你想要轉(zhuǎn)AI？快上車！

總結(jié)：

機(jī)器學(xué)習(xí)、數(shù)據(jù)科學(xué)因?yàn)樘幚頂?shù)據(jù)量龐大，因此研究問(wèn)題主要的方法還是凸優(yōu)化模型，原因正是求解高效，問(wèn)題可以scale。

雖然目前還很小眾，但是隨著計(jì)算機(jī)硬件能力的提高，GPU并行計(jì)算的流行，以及（非）凸優(yōu)化算法、模型的進(jìn)化，想必非凸優(yōu)化，甚至（混合）整數(shù)規(guī)劃會(huì)是未來(lái)的研究熱點(diǎn)。

這不，最近就有研究智能算法求解深度學(xué)習(xí)損失函數(shù)的paper：遺傳算法，模擬退火算法，粒子群算法，神經(jīng)網(wǎng)絡(luò)等智能算法的作用？

之前看過(guò)Nesterov的 Introductory Lectures on Convex Programming 頗有一些收獲，再這里就把Nesterov 關(guān)于凸函數(shù)的觀點(diǎn)簡(jiǎn)單的解讀一下。

這個(gè)條件被稱為一階必要條件，什么是必要條件呢，就是滿足這個(gè)條件的不一定是最優(yōu)解，而不滿足的一定不是最優(yōu)解。如果把在茫茫人海中尋找到你的最佳伴侶比喻成找到優(yōu)化問(wèn)題的最優(yōu)解，那么這個(gè)一階必要條件就相當(dāng)于一個(gè)篩選條件，例如有房有車的。沒(méi)房沒(méi)車的人肯定不是最佳伴侶，下面僅僅在有房有車的人當(dāng)中找最佳伴侶，這樣事情會(huì)變得簡(jiǎn)單一些了。

一階必要條件可以幫我們篩選掉一些肯定不是局部最優(yōu)解的，讓問(wèn)題變得簡(jiǎn)單，但是這個(gè)一階必要條件有兩個(gè)致命傷：一是它是一個(gè)必要條件啊，必要條件多多少少看著就讓人有點(diǎn)不爽。我們辛辛苦苦用梯度法，擬牛頓法或者共軛梯度法找到了一個(gè)滿足必要條件的點(diǎn)，然后一階必要條件告訴我們，這個(gè)點(diǎn)可能是最優(yōu)解，也可能不是。二是該條件是針對(duì)局部最優(yōu)解的，根本沒(méi)談全局最優(yōu)的事情，能不能找到全局最優(yōu)只能看運(yùn)氣嘍，梯度法的初始點(diǎn)選得好興許能找到，也興許沒(méi)找到。概括以上兩點(diǎn)就是“局部最優(yōu)不一定，全局最優(yōu)全靠碰。”

那么到這里肯定就想問(wèn)一下，有沒(méi)有辦法讓這個(gè)一階必要條件變成充要條件，同時(shí)讓局部最優(yōu)變成全局最優(yōu)的情況呢？

答案是有的，對(duì)一些特殊一點(diǎn)的而言，一階必要條件會(huì)變成充要條件。那這類性質(zhì)非常好的函數(shù)長(zhǎng)什么樣呢？

答案是 凸函數(shù)。

也就是說(shuō)對(duì)于是可微的凸函數(shù)而言，一階必要條件就變成了充要條件，同時(shí)局部最優(yōu)也升格為全局最優(yōu)。如果各位想看該命題的嚴(yán)謹(jǐn)證明的話 參考Introductory Lectures on Convex Programming 的chapter2即可。

到此為止，我們可以自信滿滿的說(shuō)若是可微還是凸函數(shù)的話，滿足的點(diǎn)，一定是全局最優(yōu)解。哈哈，梯度法，擬牛頓法或者共軛梯度法等基于梯度的算法都可以完完全全保證能收斂到全局最優(yōu)解上去。

所以說(shuō)對(duì)優(yōu)化問(wèn)題而已 凸函數(shù)的性質(zhì)簡(jiǎn)直好到爆炸啊。個(gè)人感覺(jué)這就是凸優(yōu)化為何那么重要的原因之一吧。套用一句經(jīng)典話語(yǔ)：優(yōu)化問(wèn)題的分水嶺不是線性和非線性，而是凸和非凸。

參考文獻(xiàn)

Nesterov, Yurii. "Introductory lectures on convex programming volume i: Basic course." Lecture notes (1998).

Allen-Zhu, Zeyuan. Natasha: Faster Non-Convex Stochastic Optimization via Strongly Non-Convex Parameter. International Conference on Machine Learning. 2017.

?------------------------------------------------

雙一流高校研究生團(tuán)隊(duì)創(chuàng)建 ↓