|
[遇見數(shù)學(xué)翻譯小組] 核心成員: kitty 披著理科生外衣 努力探索雙語教學(xué) 內(nèi)心文藝感性的Cool Girl  麻省理工學(xué)院的一組計算機(jī)科學(xué)家最近發(fā)現(xiàn)，判斷一個數(shù)學(xué)函數(shù)是否是凸函數(shù)是非常困難的。這個結(jié)果不僅讓數(shù)學(xué)家感興趣，也讓工程師和任何從事優(yōu)化工作的人感興趣。而且幸運(yùn)的是，該團(tuán)隊也找到了一種方法來解決這個問題，這種方法在現(xiàn)實生活中的大多數(shù)情況下都還適用。 如果一個連續(xù)函數(shù)的圖形上的面積是一個凸集，那么它就是凸的，換句話說，如果連接該圖上任意兩點(diǎn)的直線位于該圖上兩點(diǎn)之間的位之上。   是凸的，如果對于任意的點(diǎn)  和  和所有在區(qū)間  范圍內(nèi)的  ，我們總是有  是凸的，那函數(shù) 就是凹的。(這些定義也適用于多個變量的函數(shù)，即函數(shù)
 應(yīng)該被理解為由所涉及的變量組成的向量。)但是我們?yōu)槭裁匆P(guān)心一個函數(shù)是否是凸的呢? 現(xiàn)實生活中的許多問題都涉及到最小化一些量。例如，如果你正在制造一輛汽車，你想要將燃油消耗降到最低，而這取決于汽車的重量和空氣動力阻力等其他變量。如果給你一個數(shù)學(xué)函數(shù)用這些變量來描述燃料消耗，那么你的工作就是找到這個函數(shù)的全局最小值，也就是說，你需要找到一個點(diǎn) ，對所有在函數(shù)的定義域內(nèi)的 ，都有 。如果您正在研究一個更復(fù)雜的函數(shù)，可能是包含多變量的，那么要找到這個全局最小值絕非易事。 但是，如果函數(shù)是凸的，那么工作就簡單得多了。凸函數(shù)只有一個極小值。從圖像中可以看出，對于單一變量或雙變量的凸函數(shù)，它們的形狀像一個槽，最小值位于槽的底部。要找到這個值很容易，相當(dāng)于使用“直覺”的技能在圖像的斜率上尋找一下。(當(dāng)你的函數(shù)有更多的變量時，這些方法也會起作用，這樣你就不用繪制圖形了。) 相比之下，一個非凸函數(shù)可以具有許多局部最小值，這讓它的圖像看起來像山脈一樣。沿著山坡向下走，會讓你進(jìn)入其中一個山谷，但是你不能確定它僅僅是一個小的傾角還是你所追求的全局最小值。 這是Amir Ali Ahmadi，Alex Olshevsky，Pablo A. Parrilo和John N. Tsitsiklis在他們的論文中提出的問題。 (mit.edu/~a_a_a/Public/Publications/convexity_nphard.pdf) 檢驗一個給定的多項式是否是凸的的方法是眾所周知的，所以問題不在于此，而在于檢驗任意一個多項式需要多長時間。很明顯，多項式中的項越多，問題就越難，所以我們希望答案取決于項的個數(shù)，而項的個數(shù)又與變量的個數(shù)有關(guān)。 在復(fù)雜的理論中，解決問題所需的“時間”是根據(jù)計算機(jī)完成任務(wù)所需的步驟數(shù)來衡量的。這取決于問題由多少個部分展開。例如，要找到一列數(shù)字中的最大項，您需要查看每個單獨(dú)的數(shù)字，并將其與您迄今為止找到的最大數(shù)字進(jìn)行比較。在算法中有 步，所以我們說它的執(zhí)行時間是與 成正比的。其他問題可能與執(zhí)行時間 , 或 成正比( 是正數(shù))。這當(dāng)然意味著執(zhí)行時間的增長隨著 的增長而增長相當(dāng)快，初始問題的規(guī)模會變大。但與以 的指數(shù)倍增長的執(zhí)行時間相比，這根本算不了什么。例如，一個正比于 的問題。執(zhí)行時間與某個多項式中的 成正比的算法稱為多項式時間算法。它們被認(rèn)為是相對較快的。這種算法可以解決的一類稱為P問題。 |
|
|
