最優(yōu)化與最優(yōu)控制補(bǔ)充變分

最優(yōu)化與最優(yōu)控制補(bǔ)充變分第一頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

變分不等式實(shí)例Wardrop平衡配流原則描述如下：在起終點(diǎn)之間所有可供選擇的路線中，使用者所利用的各條路線上的出行費(fèi)用全都相等，而且不大于未被利用路線上的出行費(fèi)用。滿足這一原則的交通狀態(tài)被定義為Wardrop平衡狀態(tài)，上述配流原則又可稱為用戶平衡配流。

Beckmann采用以下數(shù)學(xué)形式描述Wardrop平衡狀態(tài)：

其中為平衡狀態(tài)下O-D對(duì)之間的出行費(fèi)用。

，

第二頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

變分不等式實(shí)例在路段費(fèi)用是流量的嚴(yán)格增函數(shù)的假定下，Dafermos（1980）將城市交通網(wǎng)絡(luò)均衡流問題改寫為變分不等式問題，最一般的形式就是：尋找均衡路段流量，使得對(duì)所有有

其中

其中為路段阻抗向量函數(shù)，它是流量的嚴(yán)格增函數(shù)，為路徑流量，為O-D需求量，代表路段/路徑關(guān)聯(lián)矩陣，代表O-D對(duì)/路徑關(guān)聯(lián)矩陣。在路段費(fèi)用是流量的嚴(yán)格增函數(shù)的假定下，這個(gè)變分不等式有唯一路段解。

第三頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

1.1變分不等式基本概念變分不等式廣泛應(yīng)用于各種問題的數(shù)學(xué)建模，主要有以下優(yōu)點(diǎn)：（1）變分不等式問題給出了包括優(yōu)化問題、互補(bǔ)問題、方程組問題和不動(dòng)點(diǎn)理論在內(nèi)的一些數(shù)學(xué)問題的一般描述。（2）變分不等式問題與等價(jià)的優(yōu)化問題之間的關(guān)系是非常重要的，根據(jù)其等價(jià)的優(yōu)化問題，可直接得到各種求解變分不等式的算法。（3）變分不等式問題的唯一性證明非常簡(jiǎn)單。（4）變分不等式問題的幾何解釋非常直觀。第四頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

現(xiàn)給出變分不等式問題的精確定義：設(shè)為一維實(shí)值函數(shù)，定義，則稱為一向量值函數(shù)。定義3.1有限維變分不等式問題（簡(jiǎn)稱為VIP）就是確定一個(gè)向量，使得，（2.1）其中是給定的連續(xù)向量值函數(shù)，是非空閉凸集。第五頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

2.2.1優(yōu)化問題

一般優(yōu)化問題的特征是：有一個(gè)取最小或最大值的目標(biāo)，同時(shí)滿足一定的約束。因此，優(yōu)化問題可描述為：（2.2）其中是特定的優(yōu)化目標(biāo)，為決策變量的函數(shù)，是可行集。定理2.1（最優(yōu)性條件）

令是非空閉凸集上的連續(xù)可微函數(shù)，且，若是優(yōu)化問題（2.2）的解，那么也是VIP（2.1）的解。反之，當(dāng)偽凸時(shí)成立。

1.2與變分不等式相關(guān)的數(shù)學(xué)問題第六頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

定理2.2

如果在上是連續(xù)可微的,且其雅克比矩陣是對(duì)稱且半正定的，則存在一個(gè)實(shí)值函數(shù)滿足，此時(shí)上述變分不等式問題的解也是下面優(yōu)化問題

的最優(yōu)解。

第七頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

定義2.2

令是連續(xù)的，互補(bǔ)問題即確定，使得

互補(bǔ)問題是定義在非負(fù)卦限上由等式和不等式構(gòu)成的系統(tǒng)。定理2.3

定義在上的VIP（2.1）和互補(bǔ)問題（2.4）~（2.6）若都有解，則其解相同。

2.2.2互補(bǔ)問題（ComplementarityProblems，簡(jiǎn)稱CP）（2.4）（2.5）（2.6）第八頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

2.2.3方程組（EquationSystems）定義2.3令定義在上，方程組問題指的是確定，使得。定理2.4向量是VIP（2.1）的解，當(dāng)且僅當(dāng)。2.2.4不動(dòng)點(diǎn)問題（FixedPointProblems）定義2.4令連續(xù)，不動(dòng)點(diǎn)問題就是確定，使得

（2.12）

第九頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

定理2.5向量是VIP（2.1）的解，當(dāng)且僅當(dāng)對(duì)任意的，是映射的不動(dòng)點(diǎn)，即（2.13）其中是正交投影映射，即（2.14）第十頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

1.3變分不等式在交通平衡配流問題中的應(yīng)用第十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

第十二頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

第十三頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

第十四頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

第十五頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

隨著人類社會(huì)的不斷發(fā)展，實(shí)際問題的規(guī)模越來(lái)越大，結(jié)構(gòu)越來(lái)越復(fù)雜，涉及到對(duì)問題做出決策的人也越來(lái)越多，而且這些決策者各自處于不同的層次上。一般的，高一級(jí)決策機(jī)構(gòu)（者）自上而下的對(duì)下一級(jí)決策機(jī)構(gòu)（者）行使某種控制、引導(dǎo)權(quán)，而下一級(jí)決策機(jī)構(gòu)（者）在這一前提下，亦可以在其管理職責(zé)范圍內(nèi)行使一定的決策權(quán)，雖然這種決策權(quán)比較起來(lái)處于從屬的地位。另外，在這種多層次決策系統(tǒng)中，每一級(jí)都有自身的目標(biāo)函數(shù)，而越高層機(jī)構(gòu)的決策目標(biāo)越重要，越權(quán)威，越具有全局性，因此最終的決策結(jié)果往往是尋求使各層決策機(jī)構(gòu)之間達(dá)到某種協(xié)調(diào)的具體方案。2雙層規(guī)劃簡(jiǎn)介第十六頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

在這一方案下，既可使最高層決策機(jī)構(gòu)的目標(biāo)達(dá)到“最優(yōu)”，也可使作為上級(jí)決策的“約束”的較低層決策機(jī)構(gòu)的目標(biāo)在從屬位置上相應(yīng)達(dá)到“最優(yōu)”，即下層決策以上層決策變量為參數(shù)，一般稱具有以上基本特征的決策問題為主從遞階（或多層）決策問題。主從遞階決策問題最初是由VonStackelberg于1952年在研究市場(chǎng)經(jīng)濟(jì)問題時(shí)提出的，因此此問題有時(shí)候也稱為Stackelberg問題，也就是通常所說(shuō)的多層規(guī)劃問題。第十七頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

雙層規(guī)劃是具有兩個(gè)層次系統(tǒng)的規(guī)劃與管理（控制）問題。很多決策問題由多個(gè)具有層次性的決策者組成，這些決策者具有相對(duì)的獨(dú)立性，即是說(shuō)上層決策只是通過自己的決策去指導(dǎo)（或引導(dǎo)）下層決策者，不直接干涉下層的決策；而下層決策者只需把上層的決策作為參數(shù)或約束，它可以在自己的可能范圍內(nèi)自由決策。如果組成這種上、下層關(guān)系不止一個(gè)時(shí)，這樣的系統(tǒng)為多層決策系統(tǒng)。如果只有一個(gè)上、下層關(guān)系時(shí)，這樣的系統(tǒng)通常稱為雙層規(guī)劃問題。由此可見，雙層規(guī)劃問題雖然是多層決策系統(tǒng)的特殊形式，但它是最基本的形式。

第十八頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

其中由下述規(guī)劃求得（U）（L）

上層決策者通過設(shè)置的值影響下層決策者。下層決策變量是上層決策變量的函數(shù)，即,這個(gè)函數(shù)一般被稱為反應(yīng)函數(shù)。

一般來(lái)說(shuō)，雙層規(guī)劃（簡(jiǎn)稱BP）模型具有如下形式

第十九頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

雙層規(guī)劃系統(tǒng)按如下過程進(jìn)行決策：上層給下層一定的信息，下層在這些信息下，按自己的利益或偏好做出反應(yīng)（決策），上層再根據(jù)這些反應(yīng)，做出符合全局利益的決策。上層給出的信息是以一種可能的決策形式給出的，下層的反應(yīng)實(shí)際上是對(duì)上層決策的對(duì)策，這種對(duì)策在下層看來(lái)是最好的，它顯然與上層給出的信息有關(guān)，為了使整個(gè)系統(tǒng)獲得“最好的”利益，上層必須綜合下層的對(duì)策，調(diào)整自己的決策。第二十頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

如果每個(gè)決策者都按規(guī)定的指標(biāo)函數(shù)在其可能范圍內(nèi)做出決策，那么，雙層決策系統(tǒng)可能描述為雙層規(guī)劃問題。如果每個(gè)決策者的指標(biāo)函數(shù)由單個(gè)函數(shù)組成，這樣的雙層規(guī)劃為雙層單目標(biāo)規(guī)劃問題；如果有的決策者的指標(biāo)函數(shù)是一組函數(shù)，這樣的雙層規(guī)劃問題為雙層多目標(biāo)規(guī)劃問題。第二十一頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

雙層規(guī)劃問題一般具有如下幾大特點(diǎn)：層次性——系統(tǒng)分層管理，下層服從上層，但下層有相對(duì)的自主權(quán)。獨(dú)立性——各層決策者各自控制一部分決策變量，以優(yōu)化各自的目標(biāo)。沖突性——各層決策者有各自不同的目標(biāo)，且這些目標(biāo)往往是相互矛盾的。優(yōu)先性——上層決策者優(yōu)先做出決策，下層決策者在優(yōu)化自己的目標(biāo)而選擇策略時(shí)，不能改變上層的決策。

第二十二頁(yè)，共三十一頁(yè)，編輯于2023年，星期三

自主性——上層的決策可能影響下層的行為，因而部分地影響下層目標(biāo)的實(shí)現(xiàn)，但上層不能完全控制下層的選擇行為，在上層決策允許范圍內(nèi)，下層有自主決策權(quán)。制約性——下層的決策不但決定著自身目標(biāo)的實(shí)現(xiàn)，而且也影響上層目標(biāo)的實(shí)現(xiàn)，因此上層在選擇策略優(yōu)化自己的目標(biāo)時(shí)，必須考慮到下層可能采取的策略對(duì)自己的不利影響。依賴性——各層決策者的容許策略集通常是不可分離的，形成一個(gè)相關(guān)聯(lián)的整體。

第二十三頁(yè)，共三十一頁(yè)，編輯于20