前言

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

這本書致力于討論魯棒優(yōu)化——一種用于處理不確定數(shù)據(jù)優(yōu)化問題的特定及相對新穎的方法。此前言的第一個目標是讓讀者更清楚地理解以下兩個問題：
●什么是數(shù)據(jù)不確定性，以及為什么要專門對它進行處理？
●在魯棒優(yōu)化中如何處理這一現(xiàn)象，以及這種處理方法和那些對不確定數(shù)據(jù)進行處理的傳統(tǒng)方法相比如何？
第二個目標是概述本書主題以及描述相關內(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*的相關非零坐標如下：
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
注意，機器保真度x*使式（C）為等式。
我們可以觀察到，式（C）中的大多數(shù)系數(shù)是“丑陋的實數(shù)”，如-15��79081或-84��644257。這類系數(shù)（PILOT4也不例外）通常描述某些技術設備/過程、預測未來需求等，因此很難確切地知道它們的值�？梢院茏匀坏丶僭O，“丑陋的實數(shù)”實際上是不確定的——它們與相應數(shù)據(jù)的“真實”值相符，精度最多在3～4位之間。唯一例外的是x880的系數(shù)1，可以肯定的是，它可能反映了問題的結(jié)構(gòu)，因此是嚴謹?shù)摹?br />假設a的不確定項是系數(shù)a~“真實”向量的未知項中精度為0��1%的近似值，讓我們看看這種不確定性在x*情況下對“真實”約束a~Tx≥b的影響是什么。情況如下：
●在系數(shù)a~與我們的不確定性為0��1%的假設相一致的所有向量中，a~Tx*-b的最小值＜-104��9；換句話說，對約束條件的違背達到不等式右側(cè)的4��5倍。
●將上述最壞情況下的違背視為“最差情況”（為什么所有不確定系數(shù)的真實值應與式（C）中“最危險”的值不同？），考慮一種不那么極端的違背處理。具體來說，假設式（C）中不確定系數(shù)的真實值是通過隨機擾動aja~j=(1+ξj)aj從“標準值”［如式（C）所示］獲得的。aja~j=(1+ξj)aj在范圍為［-0��001,0��001］的“相對擾動”ξj上是獨立且均勻分布的。典型的相對違背可以定義如下：
V=maxb-a~Tx*b,0×100%
在x*下，“真實”（現(xiàn)在為隨機）約束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ù)的擾動非常�。▋H0��1%），這使得“標準”最優(yōu)解x*嚴重不可行，因此實際上毫無意義。
文獻\[7\]的“案例研究”報告中顯示，我們剛才描述的現(xiàn)象并不例外——在90個NETLIB線性規(guī)劃問題中，有13個“丑陋”系數(shù)的0��01%擾動導致某些約束違背，在標準最優(yōu)解中評估超過50%。在這13個問題中，有6個問題的約束違背幅度超過100%，在PILOT4（“冠軍”）中，其規(guī)模高達210000%，也就是說，達到數(shù)據(jù)中的相對擾動的7個數(shù)量級。
本書中介紹的應用于NETLIB問題的技術可以使人們通過將標準最優(yōu)解傳遞給魯棒最優(yōu)解來消除前文所述的現(xiàn)象。在0��1%的不確定性下，對于NETLIB中的每一個問題，這種“對不確定性的免疫”（從標準解到魯棒解時目標值的增加）的代價不到1%（詳情見文獻\[7\]）。
從概述的案例研究和許多其他示例中可得出以下幾個觀察結(jié)果。
A.實際優(yōu)化問題的數(shù)據(jù)往往是不確定的——不知道問題解決時的確切時間。數(shù)據(jù)存在不確定性的原因包括：由于不可能準確測量/估計代表物理系統(tǒng)/技術過程/環(huán)境條件等特征的數(shù)據(jù)項而產(chǎn)生的測量/估計錯誤等。
實現(xiàn)過程中的錯誤來自無法完全按照計算的方式實現(xiàn)解。例如，無論上述PILOT4中的標準解x*中的“實際”項是什么——物理系統(tǒng)的控制輸入、用于各種目的分配的資源等——很顯然它們無法達到與計算時相同的高精度。實現(xiàn)錯誤的影響，如x*j(1+j)x*j，就好像沒有實現(xiàn)錯誤一樣，但PILOT4約束中的系數(shù)aij受aij(1+j)aij的擾動。
B.在優(yōu)化的實際應用中，人們不能忽視這樣一種可能性，即使數(shù)據(jù)中的一個小的不確定性，也有可能使標準最優(yōu)解在實際中失去意義。
C.因此，在優(yōu)化中，確實需要一種能夠在數(shù)據(jù)不確定情況下，檢測嚴重影響標準最優(yōu)解質(zhì)量的方法，并在這些情況下生成一個對數(shù)據(jù)不確定影響產(chǎn)生免疫的魯棒解。
魯棒優(yōu)化提供了滿足這種需求的方法，同時這也是本書的內(nèi)容。

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