王秀玉，　李維娜

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

?

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

王秀玉，李維娜

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

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

關鍵詞：水平互補; K-K-T方程; 行充分矩陣對; 列充分矩陣對

0引言

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

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

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

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

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

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

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

1水平互補問題的相關定義

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

(1)

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

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

i=1,2,…,n

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

(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水平互補問題的解集性質

定理1設

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)的點稱為水平互補問題的K-K-T點。且有K-K-T點為水平互補問題的解當且僅當(M,N)為行充分矩陣對。

證明根據(jù)K-K-T條件的充分性定理[2],可得水平互補問題(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=

另外,因為已知(M,N)為行充分對,則由定義2必然可以推出對于?z∈Rn,有

(MTz)°(NTz)=0

成立。

所以

(10)

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

所以

x*Ty*=0

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

(MTz)°(NTz)≥0

并且,?k,使得

(MTz)k°(NTz)k≥0

等價于

(MTz)°(-NTz)≤0

且,?k,使得

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

不妨設(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點。另外

又

(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

又因為,x(λ)≥0,y(λ)≥0,且

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

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

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

假設(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水平線性互補問題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))。

因為Mx+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有解。

因為-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

可得

反證法:設?α≠β?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)]

又因為對于

?α≠β?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為凸集。

假設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

矛盾。

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

參考文獻：

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

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

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

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

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

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

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

[8]徐俊彥,苗壯,劉慶懷.解廣義水平線性互補問題的組合同倫方法[J].吉林大學學報,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è)大學教授，碩士，主要從事最優(yōu)化理論與算法方向研究,E-mail:wangxiuyu@ccut.edu.cn

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

收稿日期：2014-06-13

中圖分類號：O 221.2

文獻標志碼：A

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

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