蔣 瓊,周光明

(湘潭大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院,湖南 湘潭 411105)

0 引言

Minkowski和是計(jì)算幾何的一個(gè)重要概念,在理論和實(shí)際應(yīng)用中都有重要的作用,常用于機(jī)器學(xué)習(xí)、路徑規(guī)劃、動(dòng)態(tài)仿真等領(lǐng)域.

Han[1]等提出一種計(jì)算平面幾何模型的Minkowski和的有效算法;張劍飛,郭希娟[2]針對非凸多面體的Minkowski和計(jì)算過程中剖分和合并復(fù)雜度過高的問題,提出一種基于閾值剖分的非凸多面體的Minkowski和計(jì)算方法;馬紹惠[3]等采用凹多面體回路的近似精確算法設(shè)計(jì)對求Minkowski和的邊界值的算法進(jìn)行改進(jìn);郭希娟[4]等提出一種基于邊平移理論的二維平面內(nèi)兩凸多邊形的Minkowski和構(gòu)造算法,并分析驗(yàn)證了所提算法的性能;Yan[5]給出n維歐幾里得空間中兩個(gè)任意取向?qū)嵭臋E球的Minkowski和的和差邊界的顯式閉型參數(shù)化公式;Mizrahi[6]等提出一種計(jì)算兩個(gè)自由曲面Minkowski和的方法;Higashitani[7]研究了整凸多邊形Minkowski 和的正態(tài)性或整數(shù)分解性質(zhì);Zhao[8]設(shè)計(jì)了一種新的三維凸包計(jì)算方法,通過空間兩凸多面體外表的點(diǎn)云信息直接計(jì)算其Minkowski和,用計(jì)算得到的凸包的面集表示Minkowski和的邊界信息;Bauschke[9]等提供了一個(gè)完整的答案來表明閉凸集Minkowski和上的投影等于單個(gè)投影的和;Gabidullina[10]對歐氏空間原點(diǎn)在凸多面體上的投影問題進(jìn)行了研究,系統(tǒng)地給出了不同公式;Qin[11]等研究了從一點(diǎn)到一般凸集的Minkowski和的投影的計(jì)算問題以及最小距離的計(jì)算問題.

本文針對兩個(gè)閉半代數(shù)集的 Minkowski和,提出計(jì)算零點(diǎn)到該和上的投影的數(shù)值算法.這里不要求閉半代數(shù)集是凸的.進(jìn)一步分析了算法的收斂性,并通過數(shù)值實(shí)驗(yàn)驗(yàn)證了算法的有效性.

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

Ω1,Ω2是 ?n的兩個(gè)子集,集合 Ω1,Ω2的Minkowski和的定義為:

下面給出相關(guān)符號(hào)、定義和定理等[12].

設(shè)α=(α11,…,α1n,α21,…,α2n)T∈ ?2n,x:=(x1,x2)=(x11,…,x1n,x21,…,x2n)T∈?2n,記

其中所有的單項(xiàng)式xα的次數(shù)都小于等于d,以上向量稱為次數(shù)不超過d的多項(xiàng)式集?[x]d的標(biāo)準(zhǔn)基,其維數(shù)為

定理1[12](Riesz-Haviland) 令且 Ω??2n是閉集.在Ω上存在一個(gè)有限的Borel測度μ使得

成立,當(dāng)且僅當(dāng)Ly(f)≥0對任意在Ω上的正多項(xiàng)式f∈?[x]都成立.

下面是矩矩陣與局部矩矩陣的定義.

給定s(2r)維的序列則矩矩陣Mr(y)的維數(shù)為s(r),其元素為

等價(jià)地有Mr(y)=Ly(vr(x)vr(x)T)成立.

設(shè)多項(xiàng)式u(x) ∈?[x],其系數(shù)向量為u={uγ},局部矩矩陣Mr(u(x)y)的元素為

等價(jià)地有Mr(u(x)y)=Ly(u(x)vr(x)vr(x)T)成立.

本文主要討論的零點(diǎn)到兩個(gè)閉半代數(shù)集的Minkowski和上投影問題為如下最小范數(shù)問題:

其中

是 ?n上的閉的基本半代數(shù)集,gij(xi) ∈?[x]且gij(xi)的次數(shù)為2vij或2vij-1.

由式(1)、(8)和(9)可知,我們需要求解的是如下等價(jià)的多項(xiàng)式優(yōu)化問題:

根據(jù)Lasserre半正定松弛方法[12],將多項(xiàng)式優(yōu)化問題(10)轉(zhuǎn)化為半正定規(guī)劃問題:

其中s≥s0:=maxi=1,2,j=1,2,…,qivij.

以上半正定規(guī)劃問題(11)在約束集合為緊的情況下其對偶也是一個(gè)半正定規(guī)劃問題,有如下形式:

綜上可知,所求最小范數(shù)問題是一個(gè)多項(xiàng)式優(yōu)化問題,可以利用Lasserre提出的半正定松弛方法進(jìn)行求解,具體算法如下:

輸入:目標(biāo)函數(shù)f(xi)和約束條件gij(xi)≥0,i=1,2,j=1,2,…,qi以及最高松弛次數(shù)k.

輸出:最優(yōu)值f*和一列全局最小解,i=1,2,l=1,2,…,n或f*的下界ρk.

Step 1 求解半正定優(yōu)化問題的最優(yōu)值ρs和最優(yōu)解x*(如果存在的話).

Step 2 若沒有最優(yōu)解x*,則ρk只作為一個(gè)滿足ρk≤f*的下界.若s＜k,則令s:=s+1,返回Step 1進(jìn)行計(jì)算;若s≥k,則終止運(yùn)算并輸出ρk.

Step 3 若 rankMs-s0(x*)=rankMs(x*),則ρs=f*且至少存在 rankMs(x*)個(gè)全局最小值點(diǎn).

Step 4 若 rankMs-s0(x*)≠rankMs(x*)且s＜k,則令s:=s+1,返回Step 1進(jìn)行計(jì)算;若s≥k,則終止運(yùn)算并輸出滿足條件ρk≤f*的ρk.

2 收斂性分析

其中i=1,2,j=1,2,…,qi.

假設(shè)1存在u(x)=u(x1,x2) ∈Q(g)使得水平集 {x∈?2n:u(x)≥0}是緊集.

前述算法的收斂性定理為:

定理2令假設(shè)1成立且半正定松弛問題(11)有最優(yōu)解ρs,則

(a)ρs↑f*(s→∞),

證明因?yàn)?10)是一個(gè)多項(xiàng)式優(yōu)化問題,所以根據(jù)假設(shè)1以及相關(guān)定理[12]直接可得結(jié)論成立.

3 數(shù)值實(shí)驗(yàn)

下面通過數(shù)值實(shí)驗(yàn)來檢驗(yàn)上述算法的有效性.所有數(shù)值結(jié)果均通過 MATLAB 2016b 計(jì)算得到.實(shí)驗(yàn)電腦配置如下:雙核2.20 GHz CPU,運(yùn)行內(nèi)存為4GB.MATLAB 通過調(diào)用SeDuMi[14]和GloptiPoly[15,16]來求解轉(zhuǎn)化后的多項(xiàng)式優(yōu)化問題.

表1和表2中L-SDP行表示由 Lasserre 半正定松弛方法求得的結(jié)果;fmincon行表示由MATLAB 中的函數(shù)fmincon求得的結(jié)果.其中x0表示初始點(diǎn);x*表示最優(yōu)解;f*表示最優(yōu)值;‘’/’’ 表示不需初始點(diǎn).

算例1令

這里Ω1與Ω2都是非凸的,零點(diǎn)到的投影問題為:

算例1的數(shù)值結(jié)果見表1.

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

由表1可以看出,Lasserre 半正定松弛方法求得的最優(yōu)值與fmincon函數(shù)在以初始點(diǎn)為(3,2,7,7)時(shí)計(jì)算得到的最優(yōu)值幾乎一致,比用fmincon函數(shù)計(jì)算的另兩個(gè)初始點(diǎn)的結(jié)果更好.

算例2令

這里1Ω與Ω2都是非凸的,零點(diǎn)到的投影問題為:

算例2的數(shù)值結(jié)果見表2.

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

由表2可以看出,Lasserre 半正定松弛方法求得的最優(yōu)值與fmincon函數(shù)在以初始點(diǎn)為時(shí)計(jì)算得到的最優(yōu)值幾乎一致,比用fmincon函數(shù)計(jì)算的另兩個(gè)初始點(diǎn)的結(jié)果更好.

以上數(shù)值結(jié)果表明Lasserre半正定松弛方式是有效的，且具有不依賴初始點(diǎn)的優(yōu)點(diǎn).

4 總結(jié)

本文主要討論了零點(diǎn)到兩個(gè)閉半代數(shù)集的Minkowski和上的投影問題,通過將問題轉(zhuǎn)化為多項(xiàng)式優(yōu)化問題,提出用Lasserre半正定松弛方法對其進(jìn)行求解的數(shù)值算法,該算法不要求閉半代數(shù)集是凸的,并進(jìn)行了一系列數(shù)值實(shí)驗(yàn),數(shù)值結(jié)果表明了算法的有效性.