何 非, 商玉鳳, 吳 睿
(1. 長春財經學院 數學教研部, 長春 130122; 2. 長春財經學院 經濟學院, 長春 130122)
解有限維變分不等式問題(VI(X,F))就是找到一個向量x*∈X, 使得
(x-x*)TF(x*)≥0, ?x∈X,
(1)
其中F是從n中的一個閉凸集X到n的一個映射, 稱X為可行集.
變分不等式問題(VIP)在經濟學、 交通運輸、 區域科學等領域應用關泛, 目前求解變分不等式問題的算法主要有牛頓型方法、 投影型方法、 半光滑牛頓法和光滑化牛頓法.這些算法一般都是局部收斂的, 而具有全局收斂性的結果都建立在單調性假設或類似的條件下[1-3].同倫算法在求解非凸規劃問題、 變分不等式問題中得到了許多有效結果[4-12].利用同倫算法解變分不等式問題不需要單調性假設.文獻[5]給出了用動約束同倫算法求解變分不等式問題, 構造了一個滿足X(t)?X(1)的動約束集X(t), 在較弱條件下證明了同倫路徑的存在性, 初始點是X(1)的內點, 不需要為X的內點, 但不能保證解點x*∈X.
基于此, 本文給出一種新的同倫方程構造方法, 同樣不需要初始點為X的內點, 但能保證解點x*∈X, 因此該方法使用更方便.數值算例結果表明了本文方法的有效性.
本文假設可行集X為
X={x∈n:g(x)≤0,h(x)=0},
(2)
其中g(x):n→m,h(x):n→l.記X0={x∈n:g(x)<0,h(x)=0}, 稱為嚴格可行集;I(x)={i|gi(x)=0,i∈{1,2,…,m}}, 稱為緊指標集.
引理1[13]設gi(x)(i=1,2,…,m)是二次連續可微的凸函數,hj(x)(j=1,2,…,l)為線性函數,X由式(2)定義, 則x*是VI(X,F)的一個解當且僅當存在向量y*,z*, 使得(x*,y*,z*)是VI(X,F)的KKT系統:
(3)
的解, 其中Y*=diag(y*).
為解系統(3), 構造半內點法組合同倫映射為
(4)
其中:
z∈l;w=(x,y)T,w(0)=(x(0),y(0))T;α(x(0),t)=(α1(x(0),1),…,αm(x(0),1))T,
式中δ∈(0,1).
記
X(t)={x∈n:gi(x)-αi(x(0),t)≤0,i=1,2,…,m},
X0(t)={x∈n:gi(x)-αi(x(0),t)<0,i=1,2,…,m},
?X(t)=X(t)-X0(t),
I(x,t)={i∈{1,2,…,m}:gi(x)-αi(x(0),t)=0}.
假設條件:
(H1) Slater條件成立, 即X內部非空;
(5)
(H3) {gi(x),hj(x)|i∈I(x),j=1,2,…,l}正獨立, 即對任給的和z∈l, 有
下面證明當假設條件(H1)~(H3)成立時,H-1(0)包含一條經過點(w(0),z(0),1)的有界光滑曲線, 當t→0時, 曲線另一端極限點(w*,z*,0)的x分量為VI(X,F)的解.
定理1設F:n→n,F∈Cp-1,gi∈Cp(p>2)(i=1,2,…,m), 且gi(x)為凸函數,h(x)為線性函數.假設條件(H1)~(H3)成立, 同倫映射H(w,z,t)由式(4)定義.則對幾乎所有的非空并包含一條從(w(0),z(0),1)出發的光滑曲線Γ.如果(w*,z*,0)是曲線Γ在t=0的極限點, 則x*為式(1)的解.
其中
P=(P1,…,Pm)T,
G(x(0))=diag(g(x(0))-α(x(0),t)).
由α(x(0),t)的定義, 有g(x(0))-α(x(0),t)<0(i=1,2,…,m), 因此
于是DH(w(0),w,z,t)是行滿秩的, 即0是H(w(0),w,z,t)的正則值.由參數化Sard定理和逆映射定理知, 對幾乎所有的x(0)∈n和是H(w,z,t)的正則值且H-1(0)由一些光滑曲線組成.又由H(w(0),z(0),1)=0知, 必存在一條從(w(0),z(0),1)出發的光滑曲線, 記該曲線為Γ.取Γ上任一點列并記(w*,z*,t*)為當k→+∞時點列的極限點, 則可能發生下列幾種情形:
(1-tk)(F(x(k))+g(x(k))y(k)+h(x(k))z(k))+tk(x(k)-x(0))=0,
(6)
Y(k)(g(x(k))-α(x(0),tk))-tkY(0)(g(x(0))-α(x(0),1))=0,
(7)
h(x(k))-tkz(k)=0,
(8)
由方程(7)可知, 情形(iii)也不可能發生. 下證情形(i)也不可能發生.
由g(x(k))為凸函數, 有
(10)
對式(10)兩端右乘y(k), 并利用式(7), 有
(11)
于是
(12)
又因為
(13)
其次, 分下列3種情形說明‖(y(k),z(k))‖是有限的.
h(x*)α*+g(x*)β*=0,
(15)
與條件(H3)矛盾, 因此‖(y*,z*)‖是有限值.
(16)
與g為凸函數矛盾, 因此‖y*‖是有限值.
與g為凸函數矛盾, 因此‖y(k)‖是有限的.
綜上所述, 只有情形(iv)成立, 因此當k→∞時, 極限點(x*,y*,z*)是系統(3)的解.
下面給出求解變分不等式問題的算例.
例1
例2
例3
表1 非內點法的計算結果
表2 半內點法的計算結果