水平互補(bǔ)問題二次優(yōu)化求解

王秀玉，　李維娜

(長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長春　130012)

?

水平互補(bǔ)問題二次優(yōu)化求解

王秀玉，李維娜

(長春工業(yè)大學(xué) 基礎(chǔ)科學(xué)學(xué)院， 吉林 長春130012)

摘要：水平互補(bǔ)問題轉(zhuǎn)化為二次優(yōu)化問題,通過求二次優(yōu)化問題的K-K-T點(diǎn)獲得水平互補(bǔ)問題的解。 給出了二次優(yōu)化K-K-T點(diǎn)水平互補(bǔ)問題解的充要條件,以及水平互補(bǔ)問題有解和解集為凸集的充要條件。

關(guān)鍵詞：水平互補(bǔ); K-K-T方程; 行充分矩陣對; 列充分矩陣對

0引言

互補(bǔ)問題是數(shù)學(xué)最優(yōu)化理論問題的重要分支,它不僅在數(shù)學(xué)的各個分支領(lǐng)域應(yīng)用廣泛,而且在實(shí)際生產(chǎn)中也被廣泛應(yīng)用。因此,對于互補(bǔ)問題的理論研究就顯現(xiàn)得尤為重要。在過去幾年中,很多人在這一領(lǐng)域進(jìn)行了研究[1],給出了系數(shù)矩陣是半正定、或正定、或?yàn)镻矩陣、或?yàn)镻*等時線性互補(bǔ)問題解的存在問題[2],線性互補(bǔ)問題解的存在條件[3],線性互補(bǔ)問題的系數(shù)矩陣[4],正定矩陣的推廣及其在線性互補(bǔ)問題中的應(yīng)用[5]。文獻(xiàn)[2]~[5]主要研究了下列形式的線性互補(bǔ)問題的系數(shù)矩陣:

找x∈Rn,使得y=Mx+q≥0,而且xTy=0。

其中, M∈Rn×n,q∈Rn。越來越多的專家不僅對理論層面進(jìn)行了研究，而且在算法方面也有很多成果[6-8]。

線性互補(bǔ)問題是指在有限維實(shí)向量空間中尋找一個向量使之滿足一定條件的不等式。特別地,如上述不等式所示。線性互補(bǔ)問題通常被稱為二次優(yōu)化的一個分支,大多數(shù)的專業(yè)數(shù)學(xué)研究者們認(rèn)為線性互補(bǔ)問題和有限維最優(yōu)化問題是等價的。線性互補(bǔ)問題的許多實(shí)例早于上世紀(jì)40年代就出現(xiàn)了,然而,對該問題的真正研究始于20世紀(jì)60年代。隨著科技的不斷向前發(fā)展,線性互補(bǔ)問題逐漸走入更多人的視野。文中主要研究下列形式的水平互補(bǔ)問題：

求x∈Rn,使得Mx+Ny+q=0,x≥0,y≥0,xTy=0。

首先,將水平互補(bǔ)問題轉(zhuǎn)化為二次優(yōu)化問題。第二,利用等價的二次優(yōu)化問題,證明了二次優(yōu)化的最優(yōu)解(x*,y*)與乘子矢量u，v滿足K-K-T條件。第三,二次優(yōu)化問題的K-K-T點(diǎn)為水平互補(bǔ)問題的解的充要條件是系數(shù)矩陣對是行充分對。第四,解集S是凸集的充分和必要條件是系數(shù)矩陣對(M,N)是列充分矩陣對?？傊?文中主要進(jìn)行了線性互補(bǔ)問題解與系數(shù)矩陣對的研究。

在文中出現(xiàn)的所有向量,未強(qiáng)加說明的均為列向量。

1水平互補(bǔ)問題的相關(guān)定義

水平互補(bǔ)問題等價于下列最優(yōu)值為零時的二次優(yōu)化問題：

(1)

定義1矩陣M∈Rn×n被稱為“列充分矩陣”,如對于任意的x∈Rn,有蘊(yùn)含關(guān)系：

xi(Mx)i≤0 ?xi(Mx)i=0

i=1,2,…,n

定義2(M,N)稱為行充分矩陣對,即對于?z∈Rn,有下列蘊(yùn)含式：

(MTz)°(NTz)≥0? (MTz)°(NTz)=0

定義3(M,N)稱為列充分矩陣對。若Mx+Ny=0，且x°y≤0,則有x°y=0。

定義4對矩陣A∈Rm×n,稱其正生成錐為

文中記

v=v+-v-

|v|=v++v-

A=(M,N)

ri(pos(A))={u|u=Av,v>0}

α={i|xi>0}

α?I={1,2,…,n}

2水平互補(bǔ)問題的解集性質(zhì)

定理1設(shè)

Mx+Ny=0

x≥0,y≥0

是可行的。則二次優(yōu)化式(1)必有一對最優(yōu)解(x*，y*),(x*，y*)與乘子矢量u,v滿足K-K-T條件：

(2)

(3)

(4)

(5)

(6)

滿足式(2)~式(6)的點(diǎn)稱為水平互補(bǔ)問題的K-K-T點(diǎn)。且有K-K-T點(diǎn)為水平互補(bǔ)問題的解當(dāng)且僅當(dāng)(M,N)為行充分矩陣對。

證明根據(jù)K-K-T條件的充分性定理[2],可得水平互補(bǔ)問題(1)的K-K-T條件根據(jù)式(2)~(6)將式(5)和式(6)改寫為如下形式：

MTz=u-y*

NTz=v-x*

所以,對于?i=1,2,…,n

(MTz)i°(NTz)i=(u-y*)i(v-x*)i=

(7)

(8)

且

(9)

因此,由式(8)和式(9)可得,對于?i=1,2,…,n有

(MTz)i°(NTz)i=(u-y*)i(v-x*)i=

再由式(8)可得：

(MTz)i°(NTz)i=(u-y*)i(v-x*)i=

另外,因?yàn)橐阎?M,N)為行充分對,則由定義2必然可以推出對于?z∈Rn,有

(MTz)°(NTz)=0

成立。

所以

(10)

聯(lián)立式(8)~式(10)必然有：

所以

x*Ty*=0

證明必要性:假設(shè)(M,N)不是行充分矩陣對,那么,必?z∈Rn,z≠0,使得

(MTz)°(NTz)≥0

并且,?k,使得

(MTz)k°(NTz)k≥0

等價于

(MTz)°(-NTz)≤0

且,?k,使得

(MTz)k°(-NTz)k<0

不妨設(shè)(MTz)k<0,(-NTz)k>0。

取

x=(-NTz)+

y=(MTz)-

因此有

-NTz=(-NTz)+-(-NTz)-

MTz=(MTz)+-(MTz)-

令

那么

令

u=MTz+y=MTz+(MTz)-=

(MTz)+≥0

令

v=NTz+x=NTz+(-NTz)+=

(-NTz)+-(-NTz)=

(-NTz)-≥0

(x,y,u,v)滿足優(yōu)化問題的K-K-T方程,即為K-K-T點(diǎn)。另外

又

(MTz)-°(-NTz)+≥0

故

xTy≥0

又,?k,使得

因此

xTy≥0

這與

xTy=0

矛盾。

所以(M,N)是行充分對,即命題成立。證畢。

定理2令S={(x,y)|Mx+Ny+q=0,x≥0,y≥0,xTy=0},那么S為凸集 ?(M,N)為列充分矩陣對。

所以

那么

i=1,2,…,n

因(M,N)為列充分矩陣對,由定義3可得

又

故

令

則

Mx(λ)+Ny(λ)+q=0

又因?yàn)?x(λ)≥0,y(λ)≥0,且

λ2×0+λ(1-λ)×0+λ(1-λ)×0+λ(1-λ)2×0=0

因此有(x(λ),y(λ))∈S。故S為凸集。

必要性:已知S為凸集,往證(M,N)為列充分對。

假設(shè)(M,N)不是列充分矩陣對,即?(u,v)

Mu+Nv=0

u°v≤0

且?k

ukvk<0

取x=u+

u=u+-u-

Mu=Mu+-Mu-

y=v+

v=v+-v-

Nv=Nv+-Nv-

令

那么

即

ui>0

vi≤0

則

必有

同時

-Mu+-Nv+=

-(Mu+Mu-)-(Nv+Nv-)=

-Mu-Mu--Nv-Nv-=

-Mu--Nv-

所以

即

(u+,v+)∈S

(u-,v-)∈S

因S為凸集,故對?λ∈[0,1],必有

(λu++(1-λ)u-,λv++(1-λ)v-)∈S

然而

因此,(M,N)為列充分矩陣對。

定理3水平線性互補(bǔ)問題x≥0,y≥0,且xTy=0, Mx+Ny=-q有解?-q∈pos(Cα(A))

其中

A=(M,N)

證明必要性:已知x≥0,y≥0,且xTy=0時,Mx+Ny=-q有解,往證-q∈pos(Cα(A))。

因?yàn)镸x+Ny=-q有解,因而-q=Mx+Ny可以改寫成

令

α={i|xi>0}

則

同時記

那么

故

-q∈pos(Cα(A))

必要性得證。

證明充分性:已知-q∈pos(Cα(A)),往證x≥0,y≥0,且xTy=0時,Mx+Ny=-q有解。

因?yàn)?q∈pos(Cα(A)),因此存在一系列的xi,yi,使得

那么

因而

Mx+Ny=-q

有解。充分性得證。

定理4解集S為凸集?ri(pos(Cα(A))∩ri(pos(Cβ(A))=?,?α≠β?I。

證明必要性。

已知解集S為凸集,往證

ri(pos(Cα(A))∩ri(pos(Cβ(A))=?

?α≠β?I

可得

反證法:設(shè)?α≠β?I,使得

ri(pos(Cα(A))∩ri(pos(Cβ(A))≠?

那么，必然可得

?-q∈ri(pos(Cα(A))∩ri(pos(Cβ(A))

故

再者,由ri(pos(Cα(A))∩ri(pos(Cβ(A))≠?和定理3的充分性可推出,Mx+Ny=-q有解。

因此

(x(1),y(1))∈S

(x(2),y(2))∈S

由S為凸集可知,對于? 0≤λ≤1,有

(λx(1)+(1-λ)x(2),λy(1)+(1-λ)y(2))∈S

因而

[λx(1)+(1-λ)x(2)]T[λy(1)+(1-λ)y(2))]=λ(1-λ)[x(1)Ty(2)+x(2)Ty(1)]

又因?yàn)閷τ?/p>

?α≠β?I

有

因此

λ(1-λ)[x(1)Ty(2)+x(2)Ty(1)]>0

矛盾。故

ri(pos(Cα(A))∩ri(pos(Cβ(A))≠?

?α≠β?I

充分性:已知

ri(pos(Cα(A))∩ri(pos(Cβ(A))=?

?α≠β?I

往證S為凸集。

假設(shè)S非凸,且?-q使得

其中

再者,對于

?α≠β?I

有

必然可得?k,使得

λk>0

μk>0

U.k=M.k

V.k=N.k

記

γ={i|U.i=V.i}

那么必有

另外,記

令

同時

這與

ri(pos(Cα(A))∩ri(pos(Cβ(A))=?

對于

?α≠β?I

矛盾。

因此,充分性成立。證畢。

參考文獻(xiàn)：

[1]袁亞湘,孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社,1997.

[2]韓繼業(yè),修乃華,戚厚鐸.非線性互補(bǔ)理論與算法[M].上海:上?？茖W(xué)技術(shù)出版社,2006.

[3]雍龍泉,劉淳安.線性互補(bǔ)問題解得存在條件[J].寶雞文理學(xué)院學(xué)報(bào),2005(4):262-264.

[4]孫艷波,線性互補(bǔ)問題的相關(guān)矩陣研究[J].科學(xué)技術(shù)與工程,2008(10):2518-2522.

[5]雍龍泉,正定矩陣的推廣及其在線性互補(bǔ)問題中的應(yīng)用[J].廣西科學(xué),2007,14(2):120-121.

[6]姜興武,王秀玉.P0線性互補(bǔ)問題的新同倫方法[J].吉林大學(xué)學(xué)報(bào),2013(5):807-810.

[7]徐俊彥,苗壯,譚佳偉,等.解線性互補(bǔ)問題的組合同倫方法[J].長春工業(yè)大學(xué)學(xué)報(bào):自然科學(xué)版,2010，31(3):269-274.

[8]徐俊彥,苗壯,劉慶懷.解廣義水平線性互補(bǔ)問題的組合同倫方法[J].吉林大學(xué)學(xué)報(bào),2010(3):647-653.

Quadratic optimization algorithm for

the horizontal complementarity problem

WANG Xiu-yu,LI Wei-na

(School of Basic Sciences, Changchun University of Technology, Changchun 130012， China)

Abstract：The horizontal complementarity problem is transformed into quadratic optimization to get the solution of horizontal complementarity by obtaining the K-K-T point quadratic optimization. We give the necessary and sufficient conditions for both the K-K-T point quadratic optimization and with solution and convex set solution horizontal complementarity problems.

Key words：horizontal complementarity; K-K-T equation; row sufficient; column sufficient.

作者簡介：王秀玉(1965-)，女，漢族，吉林長春人，長春工業(yè)大學(xué)教授，碩士，主要從事最優(yōu)化理論與算法方向研究,E-mail:wangxiuyu@ccut.edu.cn

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目(10771020)； 吉林省自然科學(xué)基金資助項(xiàng)目(201215128,20101597)

收稿日期：2014-06-13

中圖分類號：O 221.2

文獻(xiàn)標(biāo)志碼：A

文章編號：1674-1374(2015)01-0101-06

DOI:10.15923/j.cnki.cn22-1382/t.2015.1.21