求解隨機二階錐線性互補問題的期望殘差最小化方法

張宏偉，賈 紅，陳 爽，龐麗萍

（大連理工大學 數學科學學院，遼寧 大連 116024）

0 引 言

Rn中的二階錐，也稱冰淇淋錐或洛倫茲錐，定義為其中為歐式范數.若n＝1，則Kn即為非負象限R＋.一般對包含二階錐（SOCs）的互補問題比較感興趣.二階錐互補問題作為線性互補問題的擴展，在線性問題、二次規劃問題及一些網絡均衡問題中均具有廣泛的應用.二階錐互補問題（SOCCP）的一般形式為尋找向量x，y∈Rn及ξ∈Rn，使得問題（1）

成立.其中〈·，·〉為歐幾里得內積，F：Rn→Rn與G：Rn→Rn均為光滑函數，K＝Kn1×…×KnN，N，n1，…，nN≥1，n1＋…＋nN＝n，Kni∶＝｛（x1x2）給定矩陣M∈Rn×n及向量q∈Rn，當x＝ξ，y＝F（ξ），F（ξ）∶＝Mξ＋q時，問題（1）即為二階錐線性互補問題.

確定性的二階錐互補問題在研究數學規劃、運籌學、博弈論中具有非常重要的意義，而現實問題通常具有不確定性，因此帶有隨機因素的二階錐線性互補問題越來越多地受到人們的重視.當F：K×Ω→K為帶有隨機變量的向量值函數，即F（x，ω）∶＝M（ω）x＋q（ω）時，隨機二階錐線性互補問題作為二階錐互補問題的一個擴展便產生了，即

其中M（ω）∈Rn×n，q（ω）∈Rn.Ω，（Ω，F，P）為概率空間.

解決二階錐互補問題有許多的方法，如內點法［1－2］、光滑化牛頓法［3－4］、光滑正則化方法［5］、優值函數法［6］及近似梯度下降法［7］等.后3種方法需要以二階錐互補函數為基礎.

特別地，若函數：Rl×Rl→Rl滿足下列條件則稱其為與x∈Kl（l≥1）有關的二階錐互補函數［8］．常見的二階錐互補函數為向量值Fischer－Burmeister（FB）函數，即

本文將引入期望殘差最小化（ERM）方法［9］來解決隨機二階錐線性互補問題，給出利用ERM方法解決隨機二階錐線性互補問題的模型，即為尋找向量x∈K使得互補問題的期望殘差最小：

其中Φ：K×Ω→K定義如下：

由互補問題產生多個相關的隨機方程，期望殘差方法可以看作是最小二乘法的自然擴展.本文中，以FB函數為例來求解隨機二階錐互補問題，即為FB函數，（x，y）＝x＋y－（x2＋y2）1／2.

1 預備知識

1.1 若爾當積

與標量乘法和矩陣乘法不同，若爾當積不具有結合律，這也是研究SOCCP 比較復雜的主要原因.下面給出若爾當積的定義和常用性質［4，8］.

通常將x2表示為x·x，將x＋y表示為相應分量的和，即x2＝x·x，x＋y＝（x1＋y1x2＋y2）.

下面給出·、＋與單位元e＝（1 0 …0）∈Rn的一些基礎性質：

性質1

若爾當積與二階錐可以通過以下常用的性質聯系起來．

性質2

（2）若det（x）≠0，則稱向量x＝（x1x2）∈R×Rn－1為可逆的，且-y＝（y1y2）∈R×Rn－1，使得x·y＝e，稱y為x的逆，記為x－1．計算公式為由上式顯然可得，x∈intK當且僅當x－1∈intK．

（3）若x∈K，則K中存在一個向量，記之為x1／2，滿足（x1／2）2＝x1／2·x1／2＝x.計算公式為x1／2其中若x2＝0且s＝0，則定義為零向量，即x＝0.

1.2 譜分解

譜分解的定義及本文中將用到的相關性質［4，6］敘述如下.

其中i＝1，2，w為Rn－1中滿足的任意向量.

若x2≠0，則x的譜分解形式唯一.

λ1、λ2和μ（1）、μ（2）的一些有趣的性質總結如下.

（1）譜向量μ（1）與μ（2）在若爾當積下是正交的，且長度為即μ（1）·μ（2）＝0，μ（1） ＝

（2）譜向量μ（1）與μ（2）在若爾當積下是冪等的，即μ（i）·μ（i）＝μ（i），i＝1，2.

（3）譜值λ1與λ2是非負的（正的）當且僅當x∈K（x∈intK）.

（4）x的行列式、跡及歐式范數均可以由譜值λ1與λ2表 示：det（x）＝λ1λ2，tr（x）＝λ1＋λ2，

2 解的存在性與收斂性

考慮下列問題：

其中ρ：Ω→R＋為連續密度函數且滿足

證明 因為x∈K，x＝（x1x2）∈R×Rn－1，所以由譜分解的定義與性質可得，存在λi、μ（i），i＝1，2使得x＝λ1μ（1）＋λ2μ（2），x2＝λ21μ（1）λ42）.所以

引理2x∈K，y∈K，（x－y）2＝x2＋y2－2x·y.

易得（x－y）2＝x2＋y2－2x·y.

現在，將利用擬蒙特卡羅方法進行積分計算.特別地，利用轉換函數ω＝μ（）將Ω上的積分轉化為單位立方體［0，1］n上的積分并在單位立方體中產生變量｛，i＝1，…，N｝.從而，f（x）可以表示如下：

下面將著重研究式（3）的離散近似問題的性質.

定義

其中I＝｛1，…，Nk｝，Ωk∶＝｛ωi，i＝1，…，Nk｝是由擬蒙特卡羅方法產生的變量集且滿足ΩkΩ，當k→∞時Nk→∞.

式（6）中，尾項［10］具有重要意義，是保證f（k）（x）水平集非空有界的重要條件，在文獻［6］中有詳細證明.

由Φ（·，ω）的連續性可得，f（k）（x）為連續函數.定義的最優解集為的最優解集為Sk，函數f的水平集為D（γ）∶＝｛x∈Rn｜f（x）≤γ｝.

定理1 設｜〈x，F（x，ω）〉｜≤M，M為一正的常數且對ω∈Ω，M（ω）與q（ω）不同時為0，則對任意給定的

證明

為簡便公式，設a∶＝x，b∶＝F（x，ω），則由引理可得

從而

因為

所以，當Nk→∞時

由式（4），且對任意確定的x∈K，是連續的，非負有界.因此，由數列分布的收斂性分析可得

注 隨機二階錐線性互補問題中〈x，F（x，ω）〉＝0，若｜〈x，F（x，ω）〉｜無界，則與原問題偏離太大，所以題設條件｜〈x，F（x，ω）〉｜≤M具有其合理性.

引理3［6］假設F（x，ω）：R→R可微單調，且存在使得∈intK，F（x，ω）∈intK，則對任意的γ≥0，水平集D（γ）∶＝｛x∈R｜f（k）（x）≤γ｝非空有界.

證明 因為對任意的ω∈Ω，M（ω）為半正定的，F（x，ω）∶＝M（ω）x＋q（ω）.

由引理3可得，對任意的γ≥0，水平集D（γ）∶＝｛x∈Rn｜f（k）（x）≤γ｝非空有界.

易知，對 任 意 確 定 的ω，Φ（x，ω）是 全 局Lipschitz 連 續 的［9］，即 對 任 意 的x，y∈Rn，其 中L（ω）為與ω有關的正常數.易得，存在C1＞0，使得

與定理1類似可證明，-C0＞0，使得對1）.由引理3可得，水平集D（γ）是閉且有界的，因此可定義從而，

其中C∶＝2C0C1（1＋C2）.

由對密度函數ρ的假設及題設條件可得

其中T為常數，且對所有充分大的k，T≥從而當k→∞時，

又因為f（k）（x）→f（x），所以，當k→∞時，

由定義可得，對任意的x∈K，f（k）（x（k））≤f（k）（x）.所以，綜上所述可得

即證得｛x（k）｝的所有聚點均包含在S內.

注 若-γ≥0，使得D（γ）∩K＝，則Sk∩K＝，即目標函數無解.從而，定理的假設是合理的.

3 結 語

FB函數是一類重要的二階錐互補函數，本文通過它將隨機二階錐線性互補問題轉化為求解目標函數的極小化問題.據了解，這是首次在二階錐范圍內利用期望殘差最小化方法來解決隨機線性互補問題.本文對題設條件進行了合理假設并著重證明了離散型目標函數解的存在性與收斂性.

［1］ Alizadeh F，Goldfarb D.Second－order cone programming ［J］.Mathematical Programming，2003，95（1）：3－51.

［2］ Andersen E D，Roos C，Terlaky T.On implementing a primal－dual interior－point method for conic quadratic optimization［J］.Mathematical Programming，2003，95（2）：249－277.

［3］ Chen X D，Sun D，Sun J.Complementarity functions and numerical experiments on some smoothing Newton methods for second－order－cone complementarity problems ［J］.Computational Optimization and Applications，2003，25（1－3）：39－56.

［4］ Fukushima M，Luo Z Q，Tseng P.Smoothing functions for second－order－cone complementarity problems ［J］.SIAM Journal on Optimization，2002，12（2）：436－460.

［5］ Hayashi S，Yamashita N，Fukushima M.A combined smoothing and regularization method for monotone second－order cone complementarity problems ［J］.SIAM Journal on Optimization，2005，15（2）：593－615.

［6］ Chen J S，Tseng P.An unconstrained smooth minimization reformulation of the second－order cone complementarity problem ［J］.Mathematical Programming，2005，104（2－3）：293－327.

［7］ Pan S，Chen J S.A proximal gradient descent method for the extended second－order cone linear complementarity problem ［J］.Journal of Mathematical Analysis and Applications，2010，366（1）：164－184.

［8］ Pan S，Chen J S.A damped Gauss－Newton method for the second－order cone complementarity problem［J］.Applied Mathematics and Optimization，2009，59（3）：293－318.

［9］ Chen X，Fukushima M.Expected residual minimization method for stochastic linear complementarity problems ［J］.Mathematics of Operations Research，2005，30（4）：1022－1038.

［10］ Yamashita N，Fukushima M.A new merit function and a descent method for semidefinite complementarity problems［M］／／Reformulation：Nonsmooth，Piecewise Smooth，Semismooth and Smoothing Methods.New York：Springer US，1999：405－420.