畢紅梅， 劉妙華， 趙學軍

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

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

1 Fisher市場均衡問題

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

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

(1)

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

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

(2)

x≥0

假定最優(yōu)解集非空，則式(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)由下面的系統(tǒng)給出：

AΔax=0

-ATΔay+Δas=0

(6)

sΔax+xΔas=w-xs

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

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)。若系統(tǒng)(3)存在最優(yōu)解，則算法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‖)≤ε。

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

3 數(shù)值實驗

本節(jié)用算法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在區(qū)間(0，1)中隨機生成，初始點(x0,y0,s0)的取法與參考文獻[1]一致。

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

為說明Fisher市場均衡問題求解過程，以最簡單的p=2時情形為例，即市場上僅有2位消費者和2位生產者。系數(shù)矩陣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后得到最優(yōu)解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個單位的商品，相應的效應系數(shù)分別為0.800 3，0.915 7，若商品價格定為1.196，0.53，對應相乘得到購買商品消費金額分別為0.957 2，0.485 4，與預算一致，商品售完，市場出清。

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

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

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

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

4 結語

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