解一類變分不等式問題的半內(nèi)點(diǎn)同倫方法

2022-01-21 08:08:18商玉鳳

吉林大學(xué)學(xué)報(bào)(理學(xué)版) 2022年1期

何非, 商玉鳳, 吳睿

(1. 長(zhǎng)春財(cái)經(jīng)學(xué)院數(shù)學(xué)教研部, 長(zhǎng)春 130122； 2. 長(zhǎng)春財(cái)經(jīng)學(xué)院經(jīng)濟(jì)學(xué)院, 長(zhǎng)春 130122)

0 引言

解有限維變分不等式問題(VI(X,F))就是找到一個(gè)向量x*∈X, 使得

(x-x*)TF(x*)≥0, ?x∈X,

(1)

其中F是從n中的一個(gè)閉凸集X到n的一個(gè)映射, 稱X為可行集.

變分不等式問題(VIP)在經(jīng)濟(jì)學(xué)、交通運(yùn)輸、區(qū)域科學(xué)等領(lǐng)域應(yīng)用關(guān)泛, 目前求解變分不等式問題的算法主要有牛頓型方法、投影型方法、半光滑牛頓法和光滑化牛頓法.這些算法一般都是局部收斂的, 而具有全局收斂性的結(jié)果都建立在單調(diào)性假設(shè)或類似的條件下[1-3].同倫算法在求解非凸規(guī)劃問題、變分不等式問題中得到了許多有效結(jié)果[4-12].利用同倫算法解變分不等式問題不需要單調(diào)性假設(shè).文獻(xiàn)[5]給出了用動(dòng)約束同倫算法求解變分不等式問題, 構(gòu)造了一個(gè)滿足X(t)?X(1)的動(dòng)約束集X(t), 在較弱條件下證明了同倫路徑的存在性, 初始點(diǎn)是X(1)的內(nèi)點(diǎn), 不需要為X的內(nèi)點(diǎn), 但不能保證解點(diǎn)x*∈X.

基于此, 本文給出一種新的同倫方程構(gòu)造方法, 同樣不需要初始點(diǎn)為X的內(nèi)點(diǎn), 但能保證解點(diǎn)x*∈X, 因此該方法使用更方便.數(shù)值算例結(jié)果表明了本文方法的有效性.

1 預(yù)備知識(shí)

本文假設(shè)可行集X為

X={x∈n:g(x)≤0,h(x)=0},

(2)

其中g(shù)(x):n→m,h(x):n→l.記X0={x∈n:g(x)<0,h(x)=0}, 稱為嚴(yán)格可行集;I(x)={i|gi(x)=0,i∈{1,2,…,m}}, 稱為緊指標(biāo)集.

引理1[13]設(shè)gi(x)(i=1,2,…,m)是二次連續(xù)可微的凸函數(shù),hj(x)(j=1,2,…,l)為線性函數(shù),X由式(2)定義, 則x*是VI(X,F)的一個(gè)解當(dāng)且僅當(dāng)存在向量y*,z*, 使得(x*,y*,z*)是VI(X,F)的KKT系統(tǒng):

(3)

的解, 其中Y*=diag(y*).

為解系統(tǒng)(3), 構(gòu)造半內(nèi)點(diǎn)法組合同倫映射為

(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}.

假設(shè)條件:

(H1) Slater條件成立, 即X內(nèi)部非空;

(5)

(H3) {gi(x),hj(x)|i∈I(x),j=1,2,…,l}正獨(dú)立, 即對(duì)任給的和z∈l, 有

2 同倫路徑的存在性及收斂定理

下面證明當(dāng)假設(shè)條件(H1)～(H3)成立時(shí),H-1(0)包含一條經(jīng)過點(diǎn)(w(0),z(0),1)的有界光滑曲線, 當(dāng)t→0時(shí), 曲線另一端極限點(diǎn)(w*,z*,0)的x分量為VI(X,F)的解.

定理1設(shè)F:n→n,F∈Cp-1,gi∈Cp(p>2)(i=1,2,…,m), 且gi(x)為凸函數(shù),h(x)為線性函數(shù).假設(shè)條件(H1)～(H3)成立, 同倫映射H(w,z,t)由式(4)定義.則對(duì)幾乎所有的非空并包含一條從(w(0),z(0),1)出發(fā)的光滑曲線Γ.如果(w*,z*,0)是曲線Γ在t=0的極限點(diǎn), 則x*為式(1)的解.

其中

P=(P1,…,Pm)T,

G(x(0))=diag(g(x(0))-α(x(0),t)).

由α(x(0),t)的定義, 有g(shù)(x(0))-α(x(0),t)<0(i=1,2,…,m), 因此

于是DH(w(0),w,z,t)是行滿秩的, 即0是H(w(0),w,z,t)的正則值.由參數(shù)化Sard定理和逆映射定理知, 對(duì)幾乎所有的x(0)∈n和是H(w,z,t)的正則值且H-1(0)由一些光滑曲線組成.又由H(w(0),z(0),1)=0知, 必存在一條從(w(0),z(0),1)出發(fā)的光滑曲線, 記該曲線為Γ.取Γ上任一點(diǎn)列并記(w*,z*,t*)為當(dāng)k→+∞時(shí)點(diǎn)列的極限點(diǎn), 則可能發(fā)生下列幾種情形: