求解最小包容球問題的一類光滑逼近算法

李 堯， 蔣 毅*， 柏雪婷

（1.四川師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，四川 成都 610066；2.四川師范大學(xué) 可視化計(jì)算與虛擬現(xiàn)實(shí)四川省重點(diǎn)實(shí)驗(yàn)室，四川 成都 610066）

在Rn空間中，令閉集合

Bi∶＝｛x∈Rn：‖x-ci‖≤ri，i ＝1，2，…，m｝，它是以ci為球心，ri≥0 為半徑的球.給定一組球

最小包容球問題是找一個(gè)能夠包容B 中m個(gè)球且半徑最小的球，簡稱SEB 問題.該問題可以表述為非光滑凸優(yōu)化問題

由于函數(shù)f（x）是嚴(yán)格凸的，所以問題（1）的解存在且是唯一的.

最小包容球問題應(yīng)用于位置分析、軍事行動(dòng)等方面，它本身也是計(jì)算幾何學(xué)中的一個(gè)有趣的問題［1-5］.當(dāng)維數(shù)n≤30 時(shí)，文獻(xiàn)［5-7］中的方法在理論和數(shù)值實(shí)驗(yàn)中都能得到令人滿意的結(jié)果；然而，這些方法在處理維數(shù)n ＞30 時(shí)的效率比較低下.

近年來，許多學(xué)者考慮n ≥100 的情況.Pan等［8］首先將具有一定組合性質(zhì)的問題（1）轉(zhuǎn)化為一個(gè)包含極大值函數(shù)φ（t）＝max｛0，t｝的確定非光滑問題，然后使用CHKS 光滑函數(shù)［9-10］來逼近φ（t），由此建立了一個(gè)全局收斂的擬牛頓算法.Zhou等［11］利用對(duì)數(shù)指數(shù)光滑逼近［12］的思想提出了一種有效求解最小包容球問題的算法.基于此類方法的啟發(fā)，本文提出了一類光滑逼近算法.

在本文中所有向量都是列向量.設(shè)Id表示d ×d單位矩陣，co（S）是集合S?Rn的凸包.對(duì)于凸函數(shù)f：Rn→R，?f（x）表示f在x處的次微分.

1 光滑逼近

首先，問題（1）中的f（x）可由線性優(yōu)化問題重新定義如下：

問題（3）滿足強(qiáng)對(duì)偶定理，對(duì)于任意x∈Rn，其最優(yōu)值與對(duì)偶線性規(guī)劃的最優(yōu)值相同.因此，有

其中，ω和ui是與約束和λi≤1（i ＝1，2，…，m）相關(guān)的拉格朗日乘子.由于

且ui≥0，令

將上式代入（4）式的目標(biāo)函數(shù)，消除變量u，可以得到

因此，原問題（1）轉(zhuǎn)化為了非光滑優(yōu)化問題，具體如下：

因?yàn)棣眨╢i（x）+ω）是不可微的，所以本文利用光滑函數(shù)對(duì)其進(jìn)行逼近.應(yīng)用的光滑函數(shù)如下：

文獻(xiàn)［13-14］證明函數(shù)φ（t；p）滿足如下性質(zhì).

引理1.1對(duì)任意p∈（0，1］，函數(shù)

滿足：

（i）φ（t；p）是嚴(yán)格凸的可微函數(shù)，且

根據(jù)光滑函數(shù)φ（t；p），定義如下函數(shù)

下面考慮光滑無約束優(yōu)化問題

首先，證明函數(shù)Φ（ω，x；p）的相關(guān)性質(zhì).

引理1.2問題（8）中定義的函數(shù)Φ（ω，x；p）具有以下性質(zhì)：

（a）對(duì)任意ω∈R，x∈Rn和0 ＜p1＜p2，則

（b）對(duì)任意ω∈R，x∈Rn和p ＞0，則

（c）對(duì)任意p ＞0，Φ（ω，x；p）是連續(xù)可微且嚴(yán)格凸的.

證明（a）對(duì)任意p ＞0，t∈R，有

又因?yàn)閒i（x；p）隨p 嚴(yán)格增加，對(duì)于任何0 ＜p1＜p2，則有

（b）經(jīng)過簡單的計(jì)算，可以得到

對(duì)任意ω∈R，x∈Rn和p ＞0，由上述等式可推出如下不等式關(guān)系成立：

上述2 個(gè)不等式相加，可以得到

又根據(jù)Φ（ω，x；p）的定義得

故不等式

成立.

（c）對(duì)任何p ＞0，顯然Φ（ω，x；p）是連續(xù)可微的.下面證明Φ（ω，x；p）是嚴(yán)格凸的，由（8）式可得

由（10）和（11）式得

其中第一個(gè)不等式是由λi（ω，x；p）的非負(fù)性和▽2fi（x；p）的表達(dá)式得到的，第二個(gè)不等式是由Cauchy-Schwartz不等式得到的.這表明對(duì)任意p ＞0，Φ（ω，x；p）是ω和x的聯(lián)合嚴(yán)格凸函數(shù).

2 光滑逼近算法

由引理1.1 和1.2 可知問題（8）是問題（6）的光滑逼近.因此，給出如下光滑逼近算法.

算法A步驟1令σ∈（0，1），（ω0，x0）∈R×Rn，?1，?2＞0 和p0＞0.

步驟2k 取值0，1，2，…，序列（wk，xk）按如下方式產(chǎn)生：使用有限內(nèi)存BFGS 算法求解光滑無約束優(yōu)化問題

得到相應(yīng)的最優(yōu)解記為（ωk，xk），且滿足

步驟3若pk≤?1，則停止計(jì)算，輸出（ωk，xk）；否則，轉(zhuǎn)步驟4.

步驟4令pk+1＝σpk，更新k ∶＝k+1，轉(zhuǎn)步驟2.

算法A采用有限內(nèi)存BFGS方法求解問題（12），它能有效地求解維數(shù)較大的最小包容球問題.接下來，將證明算法A的收斂性以及求出的最優(yōu)解就是問題（1）的最優(yōu)解.

引理2.1設(shè)｛ωk，xk｝k≥1為算法A 產(chǎn)生的點(diǎn)序列，則｛xk｝k≥1的極限點(diǎn)為問題（1）的最優(yōu)解.

證明設(shè)｛ω*，x*｝為｛ωk，xk｝的極限點(diǎn)，并假設(shè)當(dāng)k→+∞時(shí)，｛ωk，xk｝→｛ω*，x*｝.由于｛ωk，xk｝是問題（12）的解，則

此外，由（1）和（6）式，可以推斷出

定義指標(biāo)集如下：

由（15）式，fi（x）和max｛0，t｝的連續(xù)性，可以得到

由（14）式可以得到

則（18）和（19）式表明

0∈co｛?fi（x*），i∈I（x*）｝＝?f（x*）.從而，x*是問題（1）的最優(yōu)解.因此，要完成引理2.1的證明，只需要證明（20）式成立.

首先，由（17）式可以很容易地推斷出

現(xiàn)在，分別考慮|I（x*）| ＝1 和|I（x*）| ＞1 的情況，其中| I（x*）|表示集合I（x*）中的元素個(gè)數(shù).

情形1如果|I（x*）| ＝1，則假設(shè)

由（21）式可以推斷出，對(duì)于足夠大的k，有

結(jié)合λi（ωk，xk；pk）的定義有

又由（13）式可以得到

由（23）和（24）式可以得到（20）式成立.

情形2如果|I（x*）| ＞1，則很容易證明（21）式嚴(yán)格成立，即

否則，一方面有

另一方面，（17）式表明

它表明（20）式成立.因此，引理2.1 的證明完成.

定理2.2設(shè)｛xk｝為算法A產(chǎn)生的點(diǎn)序列，如果x*是問題（1）的唯一最優(yōu)解，則

證明對(duì)于任何k≥1，通過引理1.2 和算法A，可以看出

由f（x）是強(qiáng)制的，可知水平集

是有界的.結(jié)合（26）式，有｛xk｝?L.因此，｛xk｝在Rn中有界.如果x*是問題（1）的唯一最優(yōu)解，則引理2.1 表明

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

下面給出數(shù)值實(shí)驗(yàn)結(jié)果.使用Core i7 2.4 GHz個(gè)人電腦，在Matlab 環(huán)境下，運(yùn)用算法A 和文獻(xiàn)［8］中的算法求解最小包容球問題.算法中的參數(shù)定義如下：

采用文獻(xiàn)［8］的隨機(jī)序列

球的半徑ri和球心ci（i ＝1，2，…，m）依次設(shè)置為，…，順序如下：

初始點(diǎn)設(shè)為ω0＝0 和x0＝0.

數(shù)值結(jié)果匯總在表1 和表2 中，歐幾里德空間的維數(shù)和球的個(gè)數(shù)分別用n 和m 表示，平均CPU時(shí)間用時(shí)間（單位：s）表示，平均迭代次數(shù)用迭代次數(shù)（單位：次）表示.

表1 n固定時(shí)，算法A與文獻(xiàn)［8］中算法的比較Tab.1 Performances of Algorithm A and that used in reference［8］with fixedn

表2 m固定時(shí)，算法A與文獻(xiàn)［8］中算法的比較Tab.2 Performances of Algorithm A and that used in reference［8］with fixedm

對(duì)于每對(duì)（m，n），用437、441、445、449 和453代替整數(shù)445，對(duì)（27）式中產(chǎn)生的5 組數(shù)據(jù)分別運(yùn)行本文的算法.表1 和表2 中的結(jié)果均取平均數(shù).當(dāng)球的個(gè)數(shù)m 增加時(shí)，本文所給算法A 的平均CPU時(shí)間比文獻(xiàn)［8］中的算法快的優(yōu)勢越明顯，并且當(dāng)維數(shù)n增加時(shí)，算法A具有同樣的優(yōu)勢.

與文獻(xiàn)［8］中算法相比，算法A有2 個(gè)優(yōu)點(diǎn)：一是在處理的數(shù)據(jù)逐漸增大時(shí)，算法A具有計(jì)算的速度優(yōu)勢；二是它的迭代次數(shù)比文獻(xiàn)［8］中的算法要少.因此，本文所給的算法A 對(duì)于求解最小包容球問題是有效的.