可變盒子集合投影算子的研究

胡 旭，劉勇進，劉梅嬌，高靜茹

(1.沈陽航空航天大學 理學院，沈陽 110136；2.沈陽師范大學 教師專業(yè)發(fā)展學院，沈陽 110034)

本文研究可變盒子集合投影算子的計算方法，即，令(x,t)是IRn×IR空間中給定的向量，我們試圖找到(x,t)在可變盒子集合C上投影算子ΠC(x,t)的顯示表達式，其中，可變盒子集合C定義如下：

C:={(z,τ)∈IRn×IR:l≤z≤τw}

的唯一最優(yōu)解。

凸錐上投影算子的性質(zhì)在相關錐約束優(yōu)化問題理論與算法的研究過程中起著極其重要的作用，如錐約束優(yōu)化問題的穩(wěn)定性分析，增廣拉格朗日算法的應用與收斂性分析都需要涉及投影算子的性質(zhì)。基于凸錐上投影算子在錐約束優(yōu)化問題研究中的重要作用，對各類閉凸集上投影算子的研究引起眾多學者的關注和興趣，并取得了較為豐富的理論研究成果[1-9]，在此我們不一一贅述。

對于給定的l,u∈IRn，?x∈IRn，我們很容易知道盒子約束集合D:={y∈IRn:l≤y≤u}上的投影算子ΠD(x)可以表示為ΠD(x)=min{max{x,l},u}，然而，對于可變盒子約束集合C上的投影算子并不是容易計算的，因為C中的τ本身是可變化的。最近，Liu,Wang,Sun[9]給出了如下凸優(yōu)化問題顯示解的計算

s.t.eTy≤τ

0≤y≤τe

其中e是各分量均為的向量。為了研究上述凸二次優(yōu)化問題的顯示解，Liu,Wang,Sun[9]討論了F:={(y,τ)∈IRn×IR:0≤y≤τe}上投影算子的顯示解。本文的目的是給出可變盒子集合C上投影算子顯示解的計算方法，容易看出C包含F(xiàn)作為其特殊情形，因此，本文的結(jié)果是文[9]相關結(jié)果的推廣，但是分析難度更大，因為C更為復雜。應當指出的是，由于問題(P)是凸二次優(yōu)化問題，我們可以通過現(xiàn)有的求解凸二次優(yōu)化問題的方法和軟件對其進行求解，然而，這種方法存在兩個明顯的缺點，一方面，已有的求解一般凸二次優(yōu)化問題的方法往往只能求得最優(yōu)解的近似解；另一方面，已有的求解一般凸二次優(yōu)化問題的方法計算效率偏低，且不能解決大規(guī)模問題。針對以上兩個缺點，本文工作的貢獻包括以下兩方面：其一，通過對優(yōu)化問題的KKT條件，我們得到了求解C上投影算子顯示解的計算方法；其二，本文研究的計算方法能夠非常高效的求解大規(guī)模問題，具體的數(shù)值結(jié)果表明，當向量維數(shù)達到100萬時，只需要1.2秒左右就能得到其顯示解。

本文的結(jié)構(gòu)如下：第1節(jié)詳細討論了可變盒子集合C上投影算子顯示解的計算方法；第2節(jié)給出了具體的數(shù)值結(jié)果，數(shù)值結(jié)果表明本文研究方法的有效性和高效性；第3節(jié)給出了本文的結(jié)束語。

1 投影算子的計算方法

在這節(jié)中，我們首先給出問題(P)的等價問題(P*)，然后根據(jù)等價問題的KKT條件，給出問題(P*)最優(yōu)解的具體形式。

令y=z-l，于是我們可以得到問題(P)的等價問題：

我們很容易知道，如果問題(P*)的最優(yōu)解為(y*,τ*)，那么問題(P)的最優(yōu)解可以表示為

(z*,τ*)=(y*+l,τ*)

下面我們研究問題(P*)最優(yōu)解的具體形式。

[x/w]π(1)≥[x/w]π(2)≥…≥[x/w]π(n)

(1)

令

定義：

(2)

以及i=1,2,…,n，

(3)

為了計算在可變盒子上的投影算子，我們在下述定理中給出問題(P*)最優(yōu)解的刻畫，并給出詳細的論證。

證明：我們分兩種情形對本定理的結(jié)論加以證明。

(4)

(5)

下面驗證(y*,τ*,u*,v*)滿足問題(P*)的KKT條件：

y-x+l-u+v=0

(6)

τ-t-vTw=0

(7)

0≤u⊥y≥0

(8)

0≤v⊥(wτ-l-y)≥0

(9)

代入(7)后，經(jīng)簡單計算可得，τ*-t-〈v*,w〉=0。因此，(y*,τ*)是問題(P*)的最優(yōu)解。

設(y,τ)是問題(P*)的任一可行解，即有0≤y≤τw-l，于是有τ≥τ*。下面證明f(y,τ)≥f(y*,τ*)。為此，我們定義下述指標集

I1(τ):={i:xi≤li},I2(τ):={i:xi≥τwi},I3(τ):={i:li

由于τ≥τ*，我們有

對于任意固定的τ，設y(τ)是下述問題的最優(yōu)解

s.t. 0≤y≤τw-l

(10)

容易知道，y(τ)由下式給出

由于(y,τ)是問題(10)的可行解，所以有f(y(τ),τ)≤f(y,τ)。接下來我們來計算f(y(τ),τ)的最小值。注意到

且

g(τ)≥g(τ*)

依據(jù)以上國內(nèi)外研究現(xiàn)狀，本研究認為融入行業(yè)英語(EOP)是高職公共英語教學改革的必然，EOP融入后自然會導致原教學生態(tài)失衡，提出以生態(tài)語言學為指導，改革教學內(nèi)容、方法、評價及加強師資建設等生態(tài)再平衡策略，消除失衡生態(tài)中的失調(diào)現(xiàn)象及不良影響，使融入EOP的高職公共英語教學生態(tài)達到良性平衡。

即

f(y(τ),τ)-f(y*,τ*)≥0

因此有

f(y,τ)-f(y*,τ*)≥0

由于(y,τ)是問題(P*)的任一可行解，所以(y*,τ*)是問題(P*)的最優(yōu)解。

綜合情形1和情形2，根據(jù)問題(P*)目標函數(shù)的強凸性，我們完成了定理的證明。

根據(jù)定理1的結(jié)果，以及問題(P*)與問題(P)最優(yōu)解的關系，對于IRn×IR空間中給定的向量(x,t)，我們得到(x,t)在集合C上的投影算子ΠC(x,t)=(z*,τ*)，其中

以及i=1,2,…,n，

2 數(shù)值結(jié)果

我們使用Matlab語言對可變盒子集合投影算子的計算進行了有效實現(xiàn)，本節(jié)給出計算可變盒子集合投影算子具體算例的數(shù)值結(jié)果，本節(jié)的數(shù)值結(jié)果是在系統(tǒng)環(huán)境為Windows 7、Matlab版本為 7.12的Laptop(雙核，CPU 2.8GHz，內(nèi)存4GB)運行得到的。

下面給出兩個例子。例1為給定的四維的具體算例，我們給出其計算詳細數(shù)值結(jié)果，目的是驗證我們算法的正確性；例2為隨機產(chǎn)生的大規(guī)模具體算例，我們給出其計算時間，目的是闡述算法的有效性。

例1假定問題(P)中的x,t,l,w分別為

x=(0.8,0.6,0.3,0.4)T,t=-0.2

l=(0.1,0.1,0.5,0.5)T

w=(0.5,0.5,1,1)T

通過對定理1的結(jié)果編程，得到ΠC(x,t)=(z*,τ*)，其中

z*=(0.25,0.25,0.5,0.5)T,τ=0.5

例2對于給定的n=5000，104，5×104，5×105，116，5×106，107，向量x的每個分量服從[0,1]均勻分布，其Matlab命令：x=rand(n,1):t=-0.001n；向量l,w分別由下列Matlab命令產(chǎn)生：

1=0.3*ones(n,1)

w=randi(10,n,1)/10

其中，randi(10,n,1)表示產(chǎn)生1至10范圍內(nèi)的n維隨機整數(shù)向量。

表1給出了例2的數(shù)值結(jié)果。表中n表示向量x的維數(shù)，對每一個n的情形，我們隨機產(chǎn)生10個算例，然后計算其平均時間，表中“s”表示秒。從表1我們可以看出，當n=107時，其計算平均時間約為1.2秒。

表1 例2數(shù)值結(jié)果

3 結(jié)束語

本文研究了可變盒子約束上投影算子顯示解的計算方法，并給出了具體算例的數(shù)值結(jié)果。本文的結(jié)果可以應用到相關優(yōu)化問題的研究中，例如，增廣拉格朗日方法，無窮范數(shù)約束下的最小二乘問題等。今后我們將繼續(xù)對投影算子的微分性質(zhì)及其應用開展深入的研究。

參考文獻(References)：

[1] HELGASON R,KENNINGTON J,LALL H.A polynomially bounded algorithm for a singly constrained quadratic program [J].Mathematical Programming,1980,18(1):338-343.

[2] BRUCKER P.An O(n) algorithm for quadratic knapsack problems [J].Operations Research Letters,1984,3(3):163-166.

[3] MACULAN N,PAULA G G De.A linear-time median-finding algorithm for projecting a vector on the simplex of [J].Operations Research Letters,1989,8(4):219-222.

[4] PARDALOS P M,KOVOOR N.An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds [J].Mathematical Programming,1990,46(1-3):321-328.

[5] MACULAN N,SANTIAGO C P,MACAMBIRA E M,et al.An O(n) algorithm for projecting a vector on the intersection of a hyperplane and a box in [J].Journal of Optimization Theory and Applications,2003,117(3):553-574.

[6] KIWIEL K C.Breakpoint searching algorithms for the continuous quadratic knapsack problem [J].Mathematical Programming,2008,112(2):473-491.

[7] DING C,SUN D F,TOH K-C.An introduction to a class of matrix cone programming [J].Methematical Programming,2010(12):1-39.

[8] WU B,Ding C,SUN D F,et al.On the Moreau-Yoshida regularization of the vector k-norm related function [DB/OL].http://www.optimization-online.org/DB_FILE/2011/03/2978.pdf,下載時間:2013-03-26.

[9] LIU Y-J,WANG S Y,SUN J-H.Finding the projection onto the intersection of a closed half-space and a variable box [J].Operations Research Letters,2013,41:259-264.

[10] GRANT M,BOYD S.CVX:Matlab software for disciplined convex programming,version 2.0 beta[DB/OL].http://cvxr.com/cvx,下載時間:2012-12-09.