前言

不確定讓人不舒服，可確定又是荒謬的。
——諺語(yǔ)

這本書(shū)致力于討論魯棒優(yōu)化——一種用于處理不確定數(shù)據(jù)優(yōu)化問(wèn)題的特定及相對(duì)新穎的方法。此前言的第一個(gè)目標(biāo)是讓讀者更清楚地理解以下兩個(gè)問(wèn)題：
●什么是數(shù)據(jù)不確定性，以及為什么要專(zhuān)門(mén)對(duì)它進(jìn)行處理？
●在魯棒優(yōu)化中如何處理這一現(xiàn)象，以及這種處理方法和那些對(duì)不確定數(shù)據(jù)進(jìn)行處理的傳統(tǒng)方法相比如何？
第二個(gè)目標(biāo)是概述本書(shū)主題以及描述相關(guān)內(nèi)容。

A. 優(yōu)化中的數(shù)據(jù)不確定性

在本書(shū)中，我們打算解決的第一個(gè)問(wèn)題是潛在現(xiàn)象（數(shù)據(jù)不確定性）是否值得專(zhuān)門(mén)處理。為了回答這個(gè)問(wèn)題，考慮一個(gè)簡(jiǎn)單的示例——來(lái)自著名的NETLIB庫(kù)中的問(wèn)題PILOT4。這是一個(gè)線性規(guī)劃問(wèn)題，具有1000個(gè)變量和410個(gè)約束條件，其中一個(gè)約束條件（#372）是

aTx≡-15��79081x826-8��598819x827-1��88789x828-1��362417x829-1��526049x830-
0��031883x849-28��725555x850-10��792065x851-0��19004x852-2��757176x853-
12��290832x854+717��562256x855-0��057865x856-3��785417x857-78��30661x858-
122��163055x859-6��46609x860-0��48371x861-0��615264x862-1��353783x863-
84��644257x864-122��459045x865-43��15593x866-1��712592x870-0��401597x871+
x880-0��946049x898-0��946049x916≥b≡23��387405（C）

根據(jù)CPLEX報(bào)告，該問(wèn)題的最優(yōu)解x*的相關(guān)非零坐標(biāo)如下：
x*826=255��6112787181108x*827=6240��488912232100x*828=3624��613324098961
x*829=18��20205065283259x*849=174397��0389573037x*870=14250��00176680900
x*871=25910��00731692178x*880=104958��3199274139
注意，機(jī)器保真度x*使式（C）為等式。
我們可以觀察到，式（C）中的大多數(shù)系數(shù)是“丑陋的實(shí)數(shù)”，如-15��79081或-84��644257。這類(lèi)系數(shù)（PILOT4也不例外）通常描述某些技術(shù)設(shè)備/過(guò)程、預(yù)測(cè)未來(lái)需求等，因此很難確切地知道它們的值。可以很自然地假設(shè)，“丑陋的實(shí)數(shù)”實(shí)際上是不確定的——它們與相應(yīng)數(shù)據(jù)的“真實(shí)”值相符，精度最多在3～4位之間。唯一例外的是x880的系數(shù)1，可以肯定的是，它可能反映了問(wèn)題的結(jié)構(gòu)，因此是嚴(yán)謹(jǐn)?shù)摹?br />假設(shè)a的不確定項(xiàng)是系數(shù)a~“真實(shí)”向量的未知項(xiàng)中精度為0��1%的近似值，讓我們看看這種不確定性在x*情況下對(duì)“真實(shí)”約束a~Tx≥b的影響是什么。情況如下：
●在系數(shù)a~與我們的不確定性為0��1%的假設(shè)相一致的所有向量中，a~Tx*-b的最小值＜-104��9；換句話(huà)說(shuō)，對(duì)約束條件的違背達(dá)到不等式右側(cè)的4��5倍。
●將上述最壞情況下的違背視為“最差情況”（為什么所有不確定系數(shù)的真實(shí)值應(yīng)與式（C）中“最危險(xiǎn)”的值不同？），考慮一種不那么極端的違背處理。具體來(lái)說(shuō)，假設(shè)式（C）中不確定系數(shù)的真實(shí)值是通過(guò)隨機(jī)擾動(dòng)aja~j=(1+ξj)aj從“標(biāo)準(zhǔn)值”［如式（C）所示］獲得的。aja~j=(1+ξj)aj在范圍為［-0��001,0��001］的“相對(duì)擾動(dòng)”ξj上是獨(dú)立且均勻分布的。典型的相對(duì)違背可以定義如下：
V=maxb-a~Tx*b,0×100%
在x*下，“真實(shí)”（現(xiàn)在為隨機(jī)）約束a~Tx≥b的相對(duì)違背是多少？答案幾乎和最壞的情況一樣糟糕（見(jiàn)表1）。
表1PILOT4中約束372的相對(duì)違背（不確定數(shù)據(jù)中擾動(dòng)為0��1%的1000個(gè)元素樣本）
Prob{V>0}　Prob{V>150%}　　　　Mean(V)
0.50　　　　　　 0.18　　　　　　　　　　　　　125%

我們看到，“明顯不確定”的數(shù)據(jù)系數(shù)的擾動(dòng)非常�。▋H0��1%），這使得“標(biāo)準(zhǔn)”最優(yōu)解x*嚴(yán)重不可行，因此實(shí)際上毫無(wú)意義。
文獻(xiàn)\[7\]的“案例研究”報(bào)告中顯示，我們剛才描述的現(xiàn)象并不例外——在90個(gè)NETLIB線性規(guī)劃問(wèn)題中，有13個(gè)“丑陋”系數(shù)的0��01%擾動(dòng)導(dǎo)致某些約束違背，在標(biāo)準(zhǔn)最優(yōu)解中評(píng)估超過(guò)50%。在這13個(gè)問(wèn)題中，有6個(gè)問(wèn)題的約束違背幅度超過(guò)100%，在PILOT4（“冠軍”）中，其規(guī)模高達(dá)210000%，也就是說(shuō)，達(dá)到數(shù)據(jù)中的相對(duì)擾動(dòng)的7個(gè)數(shù)量級(jí)。
本書(shū)中介紹的應(yīng)用于NETLIB問(wèn)題的技術(shù)可以使人們通過(guò)將標(biāo)準(zhǔn)最優(yōu)解傳遞給魯棒最優(yōu)解來(lái)消除前文所述的現(xiàn)象。在0��1%的不確定性下，對(duì)于NETLIB中的每一個(gè)問(wèn)題，這種“對(duì)不確定性的免疫”（從標(biāo)準(zhǔn)解到魯棒解時(shí)目標(biāo)值的增加）的代價(jià)不到1%（詳情見(jiàn)文獻(xiàn)\[7\]）。
從概述的案例研究和許多其他示例中可得出以下幾個(gè)觀察結(jié)果。
A.實(shí)際優(yōu)化問(wèn)題的數(shù)據(jù)往往是不確定的——不知道問(wèn)題解決時(shí)的確切時(shí)間。數(shù)據(jù)存在不確定性的原因包括：由于不可能準(zhǔn)確測(cè)量/估計(jì)代表物理系統(tǒng)/技術(shù)過(guò)程/環(huán)境條件等特征的數(shù)據(jù)項(xiàng)而產(chǎn)生的測(cè)量/估計(jì)錯(cuò)誤等。
實(shí)現(xiàn)過(guò)程中的錯(cuò)誤來(lái)自無(wú)法完全按照計(jì)算的方式實(shí)現(xiàn)解。例如，無(wú)論上述PILOT4中的標(biāo)準(zhǔn)解x*中的“實(shí)際”項(xiàng)是什么——物理系統(tǒng)的控制輸入、用于各種目的分配的資源等——很顯然它們無(wú)法達(dá)到與計(jì)算時(shí)相同的高精度。實(shí)現(xiàn)錯(cuò)誤的影響，如x*j(1+j)x*j，就好像沒(méi)有實(shí)現(xiàn)錯(cuò)誤一樣，但PILOT4約束中的系數(shù)aij受aij(1+j)aij的擾動(dòng)。
B.在優(yōu)化的實(shí)際應(yīng)用中，人們不能忽視這樣一種可能性，即使數(shù)據(jù)中的一個(gè)小的不確定性，也有可能使標(biāo)準(zhǔn)最優(yōu)解在實(shí)際中失去意義。
C.因此，在優(yōu)化中，確實(shí)需要一種能夠在數(shù)據(jù)不確定情況下，檢測(cè)嚴(yán)重影響標(biāo)準(zhǔn)最優(yōu)解質(zhì)量的方法，并在這些情況下生成一個(gè)對(duì)數(shù)據(jù)不確定影響產(chǎn)生免疫的魯棒解。
魯棒優(yōu)化提供了滿(mǎn)足這種需求的方法，同時(shí)這也是本書(shū)的內(nèi)容。

B.魯棒優(yōu)化——范式
為了解釋魯棒優(yōu)化（RO）的范式，我們首先討論線性規(guī)劃的特殊案例——通用優(yōu)化問(wèn)題，這可能是最知名以及在應(yīng)用中最常用的。除了它的重要性，這個(gè)通用問(wèn)題也非常適合我們目前的目的，因?yàn)榫�性規(guī)劃（LP）程序minx{cTx:Ax≤b}的結(jié)構(gòu)和數(shù)據(jù)是清楚的。給定規(guī)劃的形式，結(jié)構(gòu)是約束矩陣A的大小，而數(shù)據(jù)則由(c,A,b)中的數(shù)值組成。在魯棒優(yōu)化中，將不確定LP問(wèn)題定義為在給定不確定性集U中數(shù)據(jù)(c,A,b)變化的情況下，一種通用結(jié)構(gòu)的LP程序的集合{minx{cTx:Ax≤b}:(c,A,b)∈U}。后者總結(jié)了解決問(wèn)題時(shí)可用的“真實(shí)”數(shù)據(jù)的所有信息。從概念上講，最重要的是要解決不確定LP問(wèn)題意味著什么。這個(gè)問(wèn)題的答案，正如魯棒優(yōu)化在其最基本的形式中所提及的，取決于三個(gè)隱含的“決策環(huán)境”假設(shè)。
A.1.決策向量x中的所有項(xiàng)都表示“此時(shí)此地”的決策：在實(shí)際數(shù)據(jù)“顯示”之前，它們應(yīng)作為解決問(wèn)題的結(jié)果而獲得特定的數(shù)值。
A.2.當(dāng)且僅當(dāng)實(shí)際數(shù)據(jù)在預(yù)先指定的不確定性集U的范圍內(nèi)時(shí)，決策者對(duì)所做出決策的結(jié)果負(fù)責(zé)。
A.3 問(wèn)題中不確定LP的約束是“嚴(yán)格的”——當(dāng)數(shù)據(jù)在U內(nèi)時(shí)，決策者不能容忍約束違背的行為。
這些假設(shè)直接決定了對(duì)不確定問(wèn)題的“不確定性免疫”解的定義。事實(shí)上，根據(jù)A.1，這樣的解應(yīng)該是一個(gè)固定的向量，根據(jù)A��2和A��3，無(wú)論U內(nèi)的數(shù)據(jù)實(shí)現(xiàn)如何，這些約束條件都應(yīng)保持可行；我們稱(chēng)其為魯棒可行解。因此，在我們的決策環(huán)境中，一個(gè)不確定問(wèn)題有意義的解就是它的魯棒可行解。在這樣的解中，仍然需要決定如何解釋目標(biāo)的值（也可能是不確定的）。應(yīng)用到目標(biāo)時(shí)，“以最壞情況為導(dǎo)向”的理念使我們很自然地通過(guò)原始目標(biāo)的確定值來(lái)量化一個(gè)魯棒可行解的質(zhì)量，也就是通過(guò)它的最大sup{cTx：(c,A,b)∈U}。因此，最優(yōu)魯棒可行解就是解決下列優(yōu)化問(wèn)題的可行解：
minxsup(c,A,b)∈UcTx：Ax≤b,��(c,A,b)∈U
或者，以下優(yōu)化問(wèn)題的可行解：
minx,t{t：cTx≤t,Ax≤b，��(c,A,b)∈U}（RC）
后一個(gè)問(wèn)題稱(chēng)為原始不確定問(wèn)題的魯棒對(duì)等（RC）。RC的可行/最優(yōu)解稱(chēng)為不確定問(wèn)題的魯棒可行/最優(yōu)解。魯棒優(yōu)化方法（在其最簡(jiǎn)單的版本中）建議與一個(gè)不確定問(wèn)題的魯棒對(duì)等相關(guān)聯(lián)，并將魯棒最優(yōu)解作為我們“實(shí)際生活”的決策。
在這一點(diǎn)上，將RO范式與更傳統(tǒng)的方法進(jìn)行比較，特別是將優(yōu)化中的數(shù)據(jù)不確定性處理方法與隨機(jī)優(yōu)化和靈敏度分析進(jìn)行比較，是具有指導(dǎo)意義的。
魯棒優(yōu)化與隨機(jī)優(yōu)化。在隨機(jī)優(yōu)化（SO）中，不確定的數(shù)值數(shù)據(jù)被假定為隨機(jī)數(shù)據(jù)。在最簡(jiǎn)單的情況下，這些隨機(jī)數(shù)據(jù)服從事先已知的概率分布，而在更高級(jí)的設(shè)置中，分布僅部分已知。一個(gè)不確定的LP問(wèn)題再次與一個(gè)確定的對(duì)等問(wèn)題相關(guān)，特別是與下列機(jī)會(huì)約束問(wèn)題相關(guān)��機(jī)會(huì)約束的概念可以追溯到A�盋harnes、W�盬�盋opper和G�盚�盨ymonds于1958年發(fā)表的論文（見(jiàn)文獻(xiàn)\[40\]）。機(jī)會(huì)約束設(shè)置的另一種選擇是，我們希望在原始約束的某些部分中優(yōu)化目標(biāo)的期望值（后者可以包含違反不確定約束的懲罰項(xiàng)）。然而，這種方法關(guān)注的是“軟”約束，而我們主要感興趣的是硬約束。�。�
minx,t{t：Prob(c,A,b)~P{cTx≤t,Ax≤b}≥1-}（ChC）
其中＜＜1是給定的容差，P是數(shù)據(jù)(c,A,b)的分布。當(dāng)此分布僅部分已知時(shí)——眾所周知，P屬于數(shù)據(jù)空間上概率分布的給定集合P——上述設(shè)置被模糊的機(jī)會(huì)約束設(shè)置所取代，
minx,t{t:Prob(c,A,b)~P{cTx≤t，Ax≤b}≥1-，�蠵∈P}（Amb）
SO方法似乎沒(méi)有面向最壞情況的RO方法保守。然而，這一結(jié)論的前提是，如果不確定數(shù)據(jù)確實(shí)具有隨機(jī)性，如果我們足夠聰明地指出相關(guān)的概率分布（或者至少是真實(shí)數(shù)據(jù)所屬的一個(gè)“狹窄”分布族），如果我們確實(shí)準(zhǔn)備接受由機(jī)會(huì)約束給出的概率保證。在信號(hào)處理、業(yè)務(wù)系統(tǒng)分析與綜合等應(yīng)用中，上述三個(gè)條件確實(shí)得到了滿(mǎn)足�∈聦�(shí)上，在這些領(lǐng)域中，隨機(jī)因素（如信號(hào)處理中的觀測(cè)噪聲或服務(wù)系統(tǒng)中的間隔/服務(wù)時(shí)間）具有隨機(jī)性質(zhì)，其分布或多或少易于識(shí)別，尤其是當(dāng)我們有理由相信隨機(jī)數(shù)據(jù)下的不同組成部分（如觀測(cè)噪聲中的不同項(xiàng)，或單個(gè)到達(dá)間隔和服務(wù)時(shí)間）相互獨(dú)立時(shí)。在這種情況下，識(shí)別數(shù)據(jù)分布可簡(jiǎn)化為識(shí)別一系列低維分布，這是相對(duì)容易的。此外，所討論的系統(tǒng)旨在長(zhǎng)期為許多客戶(hù)提供服務(wù)，因此概率保證是有意義的。例如，每天有成千上萬(wàn)的用戶(hù)發(fā)送/接收電子郵件或聯(lián)系呼叫中心，對(duì)服務(wù)水平的概率描述（電子郵件丟失的概率，或因操作員的回應(yīng)時(shí)間很長(zhǎng)而無(wú)法接受的概率）很有意義，從長(zhǎng)遠(yuǎn)來(lái)看，一定比例的用戶(hù)/客戶(hù)會(huì)不滿(mǎn)意。��。與此同時(shí)，在許多應(yīng)用中，上述三個(gè)“如果”都過(guò)于嚴(yán)格�？紤]個(gè)別問(wèn)題的測(cè)量/估計(jì)錯(cuò)誤，例如PILOT4。即使假設(shè)為PILOT4準(zhǔn)備數(shù)據(jù)項(xiàng)確實(shí)涉及一些隨機(jī)的東西，我們也許可以考慮在給定真實(shí)數(shù)據(jù)的情況下標(biāo)準(zhǔn)數(shù)據(jù)的分布，而不