前言

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

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

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

在本書中，我們打算解決的第一個問題是潛在現(xiàn)象（數(shù)據(jù)不確定性）是否值得專門處理。為了回答這個問題，考慮一個簡單的示例——來自著名的NETLIB庫中的問題PILOT4。這是一個線性規(guī)劃問題，具有1000個變量和410個約束條件，其中一個約束條件（#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報告，該問題的最優(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。這類系數(shù)（PILOT4也不例外）通常描述某些技術(shù)設(shè)備/過程、預(yù)測未來需求等，因此很難確切地知道它們的值�？梢院茏匀坏丶僭O(shè)，“丑陋的實(shí)數(shù)”實(shí)際上是不確定的——它們與相應(yīng)數(shù)據(jù)的“真實(shí)”值相符，精度最多在3～4位之間。唯一例外的是x880的系數(shù)1，可以肯定的是，它可能反映了問題的結(jié)構(gòu)，因此是嚴(yán)謹(jǐn)?shù)摹?br />假設(shè)a的不確定項(xiàng)是系數(shù)a~“真實(shí)”向量的未知項(xiàng)中精度為0��1%的近似值，讓我們看看這種不確定性在x*情況下對“真實(shí)”約束a~Tx≥b的影響是什么。情況如下：
●在系數(shù)a~與我們的不確定性為0��1%的假設(shè)相一致的所有向量中，a~Tx*-b的最小值＜-104��9；換句話說，對約束條件的違背達(dá)到不等式右側(cè)的4��5倍。
●將上述最壞情況下的違背視為“最差情況”（為什么所有不確定系數(shù)的真實(shí)值應(yīng)與式（C）中“最危險”的值不同？），考慮一種不那么極端的違背處理。具體來說，假設(shè)式（C）中不確定系數(shù)的真實(shí)值是通過隨機(jī)擾動aja~j=(1+ξj)aj從“標(biāo)準(zhǔn)值”［如式（C）所示］獲得的。aja~j=(1+ξj)aj在范圍為［-0��001,0��001］的“相對擾動”ξj上是獨(dú)立且均勻分布的。典型的相對違背可以定義如下：
V=maxb-a~Tx*b,0×100%
在x*下，“真實(shí)”（現(xiàn)在為隨機(jī)）約束a~Tx≥b的相對違背是多少？答案幾乎和最壞的情況一樣糟糕（見表1）。
表1PILOT4中約束372的相對違背（不確定數(shù)據(jù)中擾動為0��1%的1000個元素樣本）
Prob{V>0}　Prob{V>150%}　　　　Mean(V)
0.50　　　　　　 0.18　　　　　　　　　　　　　125%

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

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