第1章凸集和凸函數(shù)
　　本章首先簡要介紹最優(yōu)化方法這門學(xué)科，然后著重介紹凸集和凸函數(shù)這兩個基本概念及其相關(guān)的性質(zhì).凸集和凸函數(shù)在最優(yōu)化方法中廣泛出現(xiàn)在線性規(guī)劃、無約束優(yōu)化以及約束優(yōu)化等問題的描述和求解方法中.
　　1.1最優(yōu)化問題和方法
　　最優(yōu)化方法學(xué)科研究優(yōu)化問題的求解方法.現(xiàn)實生活中，優(yōu)化問題多種多樣，最優(yōu)化方法主要研究那些可以用數(shù)學(xué)模型刻畫的優(yōu)化問題.這些問題從總體上可分為組合優(yōu)化問題和連續(xù)優(yōu)化問題兩類，它們是按照數(shù)學(xué)模型中所使用的變量的不同類型來劃分的.
　　在歷史上，優(yōu)化技術(shù)出現(xiàn)得很早.17世紀(jì)時，在微積分技術(shù)的發(fā)展過程中，牛頓就研究過極值問題.后來又出現(xiàn)了處理帶約束的目標(biāo)函數(shù)極值問題的拉格朗日(Joseph-Louis Lagrange，法國，1736-1813)乘數(shù)法 1847年，柯西(Augustin-LouisCauchy，法國，1789-1857)研究了函數(shù)值沿什么方向下降最快的問題，提出了最速下降法.1939年，康托羅維奇(Kantorovich，蘇聯(lián)，1912-1986)提出了下料問題和運(yùn)輸問題的求解方法.直至20世紀(jì)30年代，最優(yōu)化這個古老的課題尚未形成獨(dú)立的學(xué)科.
　　20世紀(jì)40年代以來，由于工業(yè)生產(chǎn)和科學(xué)研究的迅猛發(fā)展，特別是計算機(jī)的日益廣泛應(yīng)用，最優(yōu)化理論和算法迅速發(fā)展起來，成為運(yùn)籌學(xué)的主體內(nèi)容.運(yùn)籌學(xué)(最優(yōu)化方法)中的組合優(yōu)化部分和計算機(jī)科學(xué)中的算法設(shè)計與分析部分是部分重合的，由于組合優(yōu)化技術(shù)更強(qiáng)調(diào)了數(shù)學(xué)方法的運(yùn)用，因此組合優(yōu)化可以看作是傳統(tǒng)的算法設(shè)計與分析的延伸.運(yùn)籌學(xué)中的連續(xù)優(yōu)化部分是在數(shù)學(xué)分析中的求導(dǎo)數(shù)和求極值的基礎(chǔ)上發(fā)展起來的.現(xiàn)在，機(jī)器學(xué)習(xí)中損失函數(shù)的求解正好是連續(xù)優(yōu)化問題.因此，運(yùn)籌學(xué)的連續(xù)優(yōu)化部分也構(gòu)成了應(yīng)用計算機(jī)科學(xué)解決實際問題的基礎(chǔ).
　　最優(yōu)化方法的組合優(yōu)化技術(shù)主要包括整數(shù)線性規(guī)劃、動態(tài)規(guī)劃以及面向問題的各種啟發(fā)式方法等.最優(yōu)化方法中的連續(xù)優(yōu)化技術(shù)可分為線性規(guī)劃和非線性規(guī)劃，也可分為無約束優(yōu)化和約束優(yōu)化，這是分別按照不同的劃分標(biāo)準(zhǔn)劃分的.值得指出的是，線性規(guī)劃技術(shù)，按照變量的類型劃分屬于連續(xù)優(yōu)化，但線性規(guī)劃技術(shù)也可以用于求解組合優(yōu)化問題.例如在近似算法中，線性規(guī)劃是獲得廣泛成功的一種算法設(shè)計方法.使用線性規(guī)劃技術(shù)設(shè)計組合優(yōu)化問題的近似算法時，人們首先用線性規(guī)劃描述組合優(yōu)化問題的松弛，然后求解線性規(guī)劃得到最優(yōu)解，再通過舍入等方法將線性規(guī)劃最優(yōu)解轉(zhuǎn)化為組合優(yōu)化問題的可行解.
　　下面我們看幾個典型的優(yōu)化問題.
　　例1.1.1利潤最大化問題.某工廠用種原料生產(chǎn)種產(chǎn)品.第種原料的數(shù)量為每單位的第種產(chǎn)品需要第種原料的數(shù)量為，可獲利潤為.問如何安排生產(chǎn)，才能使總利潤最大？
　　例1.1.1中的利潤最大化問題是經(jīng)濟(jì)領(lǐng)域中經(jīng)常遇到的一個非常基本的問題.這個問題可以用線性規(guī)劃或整數(shù)線性規(guī)劃進(jìn)行描述和求解.
　　在這里，我們定義為第種產(chǎn)品的產(chǎn)量.則所有種產(chǎn)品的總利潤就是.問題的目標(biāo)是最大化這個總利潤.當(dāng)然，利潤不可能無限大，因為安排生產(chǎn)受限于原材料的供給.當(dāng)?shù)诜N產(chǎn)品的產(chǎn)量為時，生產(chǎn)這種產(chǎn)品對原料的需求為，顯然應(yīng)有，因為第種原料總共有那么多.另外，每種產(chǎn)品的產(chǎn)量也不能為負(fù)數(shù).綜合起來，我們就得到
　　(1.1.1)
　　這就是例1.1.1的數(shù)學(xué)模型，這是一個線性規(guī)劃，因為在這個規(guī)劃中目標(biāo)函數(shù)和約束條件都只包含變量的一次項，沒有變量的二次項以及更高次項，更沒有變量的冪以外的其他函數(shù).
　　值得指出的是，線性規(guī)劃(1.1.1)適用于描述那些產(chǎn)品“無限可分”的利潤最大化問題，如產(chǎn)品為面粉、食用油等.換言之，產(chǎn)品數(shù)量取值為實數(shù)應(yīng)該是有意義的.
　　如果在利潤最大化問題中，產(chǎn)品數(shù)量僅能取值為整數(shù)，例如產(chǎn)品為家具、門窗等，則我們需要使用整數(shù)線性規(guī)劃為利潤最大化問題建模，如線性規(guī)劃(1.1.2)所示.
　　(1.1.2)
　　1.1最優(yōu)化問題和方法
　定義1.1.2設(shè)施選址問題(FacilityLocation Problem)
　　實例：有個設(shè)施和個客戶，設(shè)施和客戶之間，以及設(shè)施之間、客戶之間都有距離，這些距離滿足三角不等式.打開第個設(shè)施有一個費(fèi)用方.每個客戶都需要連接到一個打開的設(shè)施上.
　　目標(biāo)：打開若干設(shè)施，滿足客戶的連通需求，使得設(shè)施的打開費(fèi)用和客戶的連接費(fèi)用之和最小.
　　設(shè)施選址問題是組合優(yōu)化領(lǐng)域中一個著名的最小優(yōu)化問題.它描述了這樣一種場景：比如有一個工廠，它有分布在多處地點的零售點.現(xiàn)在這個工廠要建立若干倉庫，以滿足向零售點配送貨物的需要.建設(shè)倉庫就有一個建設(shè)費(fèi)用，倉庫建好之后，零售點就會選擇距離最近的倉庫供貨.如何在若干的候選位置建設(shè)倉庫，以滿足零售點的供貨需求，就表達(dá)為設(shè)施選址問題.在這里，倉庫的候選位置就是設(shè)施位置，零售點就是客戶.設(shè)施的打開費(fèi)用就是建設(shè)倉庫的費(fèi)用，客戶的連接費(fèi)用就是所有零售點到其最近的倉庫的距離之和.
　　在定義1.1.2中，一個問題是按照實例和目標(biāo)兩部分?jǐn)⑹龅?這是在計算機(jī)科學(xué)中對問題描述的一種常見的形式.定義1.1.2中的“實例”也可以叫做“輸入”，“目標(biāo)”也可以叫做“輸出當(dāng)問題是判定問題時(即，回答“是”和“否”的問題)，“目標(biāo)”也可以寫作“詢問.
　　關(guān)于設(shè)施選址問題，“從m個設(shè)施中選擇若干設(shè)施打開”和“從m個設(shè)施位置中選擇若干位置建立設(shè)施”這兩種說法是等價的.
　　在這里，我們繼續(xù)用線性規(guī)劃對設(shè)施選址問題進(jìn)行建模，以領(lǐng)略線性規(guī)劃強(qiáng)大的表達(dá)能力.
　　定義變量表示是否打開設(shè)施，若，表示不打開設(shè)施，若，則表示打開設(shè)施定義變量表示客戶是否連接到設(shè)施上，它的值也是或者.這樣，問題的總費(fèi)用就可以表達(dá)為里表示頂點和之間的距離.客戶要連接到設(shè)施上，必須設(shè)施打開的條件下才行，這可以用來表達(dá).另外，每個客戶一定要連接到某個設(shè)施上，這可表達(dá)為.因此，設(shè)施選址問題的線性規(guī)劃模型為.
　　這個線性規(guī)劃是一個整數(shù)線性規(guī)劃，因為它的每個變量只能取整數(shù)值.
　　設(shè)施選擇問題是一個基本的NP困難問題.設(shè)施選址問題還有很多的變形.對于設(shè)施選址問題及其變形，學(xué)者們設(shè)計了很多的近似算法，其中有若干算法是非常有名的.感興趣的讀者可進(jìn)一步參考等著作及其引用的論文.
　　例1.1.3機(jī)器學(xué)習(xí)中的函數(shù)優(yōu)化問題.神經(jīng)網(wǎng)絡(luò)是機(jī)器學(xué)習(xí)中的一種模型，它和優(yōu)化問題密切相關(guān).多層感知機(jī)(Multi-Layer Perceptron，MLP)是一種由若干模擬的神經(jīng)元排列成矩陣結(jié)構(gòu)的前饋神經(jīng)網(wǎng)絡(luò)，它所完成的基本任務(wù)是進(jìn)行分類.可以使用一個函數(shù)來表達(dá)多層感知機(jī)所完成的任務(wù).這里，向量是輸入數(shù)據(jù)，向量:是多層感知機(jī)使用的參數(shù)，是多層感知機(jī)的輸出，其含義是把輸入數(shù)據(jù)在參數(shù)最的控制下分類成所表達(dá)的那種類型.例如，在實際應(yīng)用中，可將圖像數(shù)據(jù)輸入給神經(jīng)網(wǎng)絡(luò)，讓它將圖像分成若干種類型.
　　為了使神經(jīng)網(wǎng)絡(luò)能夠以盡量高的準(zhǔn)確率完成分類，需要設(shè)定參數(shù)最的合適的值，這是在訓(xùn)練數(shù)據(jù)的幫助下完成的，即人們通常說的“訓(xùn)練一個神經(jīng)網(wǎng)絡(luò)訓(xùn)練集可表達(dá)為，即，已經(jīng)知道數(shù)據(jù)，的類型為，也稱為數(shù)據(jù)的標(biāo)簽.訓(xùn)練一個神經(jīng)網(wǎng)絡(luò)，就是調(diào)整參數(shù)，使得某種損失函數(shù)的值盡量地小.若選擇平方誤差為損失函數(shù)，則多層感知機(jī)的優(yōu)化模型為.
　　其中，表示范數(shù)，其定義為按照最優(yōu)化方法的觀點，這是一個無約束優(yōu)化問題.在這里，為了簡單說明問題，我們將優(yōu)化模型簡化了.實際使用的優(yōu)化模型還要加上一個正則項來進(jìn)行修正.這些細(xì)節(jié)就略去了.
　　在足夠強(qiáng)大的訓(xùn)練集的支持下將一個神經(jīng)網(wǎng)絡(luò)訓(xùn)練好(即，選擇好了參數(shù)a:的值)，就可以在應(yīng)用中使用這個神經(jīng)網(wǎng)絡(luò)完成數(shù)據(jù)分類任務(wù)了.
　　1.2凸集及相關(guān)性質(zhì)
　　定義1.2.1
　　兩個點，的凸組合還是中的一個點.它們的所有凸組合構(gòu)成以這兩個點為端點的一條線段.
　　定義I.2.2
　　定義1.2.3
　　例如，歐氏空間中三角形區(qū)域、矩形區(qū)域、圓形區(qū)域都是凸集.在幾何直觀上，凸集就是邊界“向外鼓”的集合.
　　例1.2.4
　　例1.2.5
　　定義1.2.6
　　在幾何直觀上，三角形區(qū)域的頂點、矩形區(qū)域的頂點都是符合定義1.2.6的頂點.讀者可領(lǐng)略定義1.2.6的精妙.注意，圓形區(qū)域是凸集，它有無數(shù)個頂點.
　　凸集具有良好的性質(zhì)，人們對凸集有比較深入的把握.當(dāng)一個數(shù)學(xué)規(guī)劃的可行解的集合是一個凸集時，意味著這個數(shù)學(xué)規(guī)劃可能會比較容易求解.例如，線性規(guī)劃的可行域是凸集，當(dāng)一個線性規(guī)劃有解時，它的最優(yōu)解可在頂點上取得.這些知識將在第2章中詳細(xì)介紹.
　　1.3凸集的分離
　　凸集是點的集合，不在一個凸集中的點，在直觀上，位于這個凸集的“外面我們?nèi)绾问褂脭?shù)學(xué)的語言來精確描述這種直觀？進(jìn)而，兩個凸集若不相交，它們是“分離”開的，這樣的直觀用數(shù)學(xué)語言如何表達(dá)？令人驚奇的是，這種看上去非常基本的直觀概念，卻蘊(yùn)含著深刻的道理.例如，由點和凸集的分離定理1.3.3，可以推導(dǎo)出著名的Farkas引理(引理1.3.4)(G.Farkas，匈牙利，1847-1930)，而Farkas引理可推導(dǎo)出線性規(guī)劃的強(qiáng)對偶定理(定理4.2.5).再如，由凸集和凸集的分離定理1.3.9可推導(dǎo)出戈丹引理(引理1.3.10)(P.A.Gordan，德國，1837—1912)，而戈丹引理又可推導(dǎo)出關(guān)于約束優(yōu)化的著名的K-T定理(定理10.3.7).
　　1.3.1點和凸集的分離
　　在介紹定理1.3.2之前，先來回顧一下下確界符號inf.
　　定義1.3.1令SgR是一個集合，若3m，使得Vze民都有;則稱m是S的一個下界.記L是S的所有下界所組成的集合.則L中的最大元素a稱為S的下確界，記為
　　定理1.3.2
　　證明
　　則f(x)是連續(xù)函數(shù).
　　若S是有界集，則是非空、有界且閉的，所以函數(shù)在上可以達(dá)到最小值，即，使得
　　即，
　　現(xiàn)在假設(shè)不是有界集.在中任取一點以為球心，為半徑做一個球，如圖1.3.1所示.
……