求解Fisher市場均衡問題的內點算法

畢紅梅， 劉妙華， 趙學軍

(空軍工程大學基礎部，西安，710051)

早些時候，Ye提出了求解Fisher市場均衡問題的原-對偶內點算法[1]。但該算法跟蹤的加權中心路徑并不連續，從初始可行點出發還需要通過勢函數下降算法才能尋找到滿足鄰域要求的可行點。近年來，Potra將Fisher市場均衡問題抽象為更一般的線性權互補問題，根據已知可行點構造了一條光滑的中心路徑，給出了求解線性權互補問題的內點算法[2]。當權向量為0時，權互補問題退化為一般的互補問題；對于權向量部分為0、部分大于0的情形，算法設計和分析比一般的互補問題更為復雜。自此以后，求解權互補問題逐漸成為優化領域研究熱點之一。文獻[3～4]設計了光滑牛頓算法求解權互補問題。文獻[5]在一定假設條件下提出了線性權互補問題寬鄰域的路徑跟蹤算法。文獻[6～8]提出了求解線性權互補問題的全牛頓步內點算法。線性權互補問題來源于Fisher市場均衡模型，國內外文獻重點討論了線性權互補問題的求解方法和理論證明，算法測試大多自行設計，有些算法的設定條件并不適用于解決Fisher市場均衡這一實際問題，一些初步的研究結果可參考文獻[9]。

1 Fisher市場均衡問題

在 Fisher 模型中，市場中包含消費者C和生產者P。消費者i∈C有預算wi>0從生產者手中購買商品使得個人效用函數最大化。價格均衡即給商品定價，使得每個消費者買到最多的商品，同時市場出清，即所有的預算消費完并且所有的商品銷售完。不失一般性，假定生產者j有1單位的某種商品出售。

Eisenberg和 Gale證明了市場出清價格為下述優化問題的最優拉格朗日乘子[10]：

(1)

式中：uij≥0為給定的消費者i對生產者j生產商品的效應系數；xij為消費者i從生產者j手中購買的商品數量。

更一般地，式(1)可以改寫成：

(2)

x≥0

假定最優解集非空，則式(2)的KKT 條件可以寫成線性權互補問題：

Ax=b,x≥0

-ATy+s=0,s≥0

(3)

xs=w

式中:y、s分別為拉格朗日乘子。

嚴格可行域定義為：

F++={(x,s)>0:Ax=b,s=ATy}

給定初始嚴格可行點(x0,y0,s0)∈F++，令c=x0s0，構造

w(t)=(1-t)w+tc,t∈(0,1]

(4)

文獻[2]將式(4)替換(3)中的第3個式子得到新的中心路徑：

Ax=b,x≥0
-ATy+s=0,s≥0
xs=w(t)

(5)

當t→0時，w(t)→w得到(3)的解。

2 原-對偶內點算法

2.1 搜索方向

令γ=min (c),α=βγ, 0<β<1，定義鄰域:N(α,t)={(x,y,s)∈F++:‖xs-w(t)‖≤αt}。

令t+=(1-θ)t，θ∈(0,1)。搜索方向由兩個方向構成，其中仿射方向(Δax,Δay,Δas)由下面的系統給出：

AΔax=0

-ATΔay+Δas=0

(6)

sΔax+xΔas=w-xs

中心方向(Δcx,Δcy,Δcs)由下述系統給出：

AΔcx=0

-ATΔcy+Δcs=0

(7)

sΔcx+xΔcs=c-xs

仿射方向作為預測方向，中心方向作為矯正方向。本文采用的中心方向把迭代點拉向c=x0s0以保持可行性，而文獻[2]中的中心方向希望迭代點向w(t)靠近。通過二分法搜索滿足條件的最大θ值使得新的迭代點:

(x+,y+,s+)=(x,y,s)+(1-t+)(Δax,Δay,Δas)+

t+(Δcx,Δcy,Δcs)

(8)

屬于新的鄰域:N(α,t+)={(x+,y+,s+)∈F++:‖x+s+-w(t+)‖≤αt+}。

2.2 算法

算法1 線性權互補問題內點算法。

1)輸入ε>0，θ∈(0，1)，t0=1，初始可行點(x0,y0,s0)∈N(α,t0)，令k=0。

2)若‖xksk-w‖<ε，算法停止；否則求解式(6)、(7)得搜索方向:(Δaxk,Δayk,Δask)及(Δcxk,Δcyk,Δcsk)。

3)搜索滿足鄰域條件的θ值θk，令:tk+1=(1-θk)tk;xk+1=xk+(1-tk+1)Δaxk+tk+1Δcxk；yk+1=yk+(1-tk+1)Δayk+tk+1Δcyk；sk+1=sk+(1-tk+1)Δask+tk+1Δcsk。

4)令k=k+1，轉2)。

2.3 算法收斂性分析

算法可行需要保證新的迭代點在新的鄰域內，并且隨著t的減少，x+s+與w的距離不斷下降，最終滿足精度要求。

假定當前迭代點嚴格可行且滿足‖xs-w(t)‖≤αt。

引理1xs≥(γ-α)te,其中e為單位向量。

證明 由xs≥w(t)-αte≥tc-αte≥(γ-α)te，即得。令：

Δx=(1-t+)Δax+t+Δcx,Δs=(1-t+)Δas+t+Δcs。則x+=x+Δx,s+=s+Δs,于是:

sΔx+xΔs=(1-t+)(w-xs)+t+(c-xs)=

(1-t+)w+t+c-xs=w(t+)-xs

(9)

進而：

x+s+-w(t+)=(x+Δx)(s+Δs)-w(t+)=

xs+sΔx+xΔs+ΔxΔs-w(t+)=ΔxΔs

(10)

引理2[11]設u,v∈Rn,uTv≥0。 記U=diag(u),V=diag(v)，則‖UVe‖≤2-3/2‖u+v‖2。

證明式(9)兩邊同乘以(xs)-1/2，得:

x-1/2s1/2Δx+x1/2s-1/2Δs=(xs)-1/2(w(t+)-xs)。

又：‖w(t+)-xs‖≤‖w(t+)-w(t)+w(t)-xs‖≤

‖w(t+)-w(t)‖+‖w(t)-xs‖≤θt‖(w-c)‖+tα。

再由引理1即得。

要使‖x+s+-w(t+)‖≤αt+=(1-θ)tα，只需

(11)

α=βγ,令β=2/3，則：

假定θ‖w-c‖≤α/8，由式(11)可計算出θ的下界為

定理1給定ε>0,初始點(x0,y0,s0)∈N(α,t0)。若系統(3)存在最優解，則算法1至多經過

證明x+s+與w的距離

‖x+s+-w‖=‖x+s+-w(t+)+w(t+)-w‖≤

‖x+s+-w(t+)‖+‖w(t+)-w‖≤(1-θ)αt+(1-θ)t‖w-c‖=(1-θ)t(α+‖w-c‖)≤(1-θ0)t(α+‖w-c‖)=(1-θ0)k(α+‖w-c‖)。

要使‖x+s+-w‖≤ε，只需(1-θ0)k(α+‖w-c‖)≤ε。

兩邊取對數得到:klog (1-θ0)+log (α+‖w-c‖)≤logε。

3 數值實驗

本節用算法1求解Fisher 市場均衡問題。假定市場上有nc≥2個消費者，np≥2個生產者，為簡單起見，不妨設nc=np=p。記e=ones(1,p)，

對比式(1)、(2)可知

x=(x11,…,x1p,…,xp1,…,xpp,u1,…,up)T，

b=(e,01×p)T，其中01×p為1行p列0向量，

A為m×n=2p×(p2+p)矩陣

w=(01×p2,w1,…,wp)，wi,uij,i,j=1,2,…，p在區間(0，1)中隨機生成，初始點(x0,y0,s0)的取法與參考文獻[1]一致。

用MATLAB R2010b編程實現算法, 用Intel Xeon2 CPU(3.3 GHz), 8 GiB ram的微機測試。當滿足條件‖xs-w‖≤10-5時,算法終止。

為說明Fisher市場均衡問題求解過程，以最簡單的p=2時情形為例，即市場上僅有2位消費者和2位生產者。系數矩陣A為m×n=4×6矩陣

b=[1,1,0,0],權向量即預算w=[0,0,0,0,0.957 2,0.485 4],

即2位消費者預算分別為0.957 2和0.485 4，初始點為x0=[0.5,0.5,0.5,0.5,0.471 1,0.668 7]，y0=[2.871 5,2.871 5,1.523 9,1.073 5]，s0=[1.652 0,2.655 3,2.418 8,1.888 5,1.523 9,1.073 5]。

用算法1求解上述問題，迭代8次，耗時0.001 3 s后得到最優解x*=[1,0,0,1,0.800 3,0.915 7]，y*=[0.957 2,0.485 3,1.196 0,0.530 0]，s*=[0,0.787 5,0.261 8,0,1.196 0,0.530 0]。

結果表明消費者1購買了生產者1生產的1個單位的商品，消費者2購買了生產者2生產的1個單位的商品，相應的效應系數分別為0.800 3，0.915 7，若商品價格定為1.196，0.53，對應相乘得到購買商品消費金額分別為0.957 2，0.485 4，與預算一致，商品售完，市場出清。

下面對每種規模產生10個問題，計算10次結果的平均迭代次數和平均時間。表1和表2分別給出了算法1和Ye[1]、Potra[2]算法的迭代步數和迭代時間。

表1 Fisher均衡問題Ye、Potra及算法1迭代步數比較

表2 Fisher均衡問題Ye、Potra及算法1迭代時間比較

由表1和表2可見，算法1與 Potra算法在迭代次數及時間上都優于Ye 算法；當問題規模達到m×n=50×650時，算法1略優于 Potra算法。

4 結語

本文從求解Fisher市場均衡這一實際問題出發，設計線性權互補問題的內點算法，就中小規模問題給出了數值結果。對于大規模問題，迭代步數和計算時間會有所增加，因此如何調節仿射方向和中心方向參數以提高算法效率，或設計更為高效的寬鄰域內點算法是未來的研究重點。