擬凸優化問題中常值步長準則下次梯度算法的收斂性

趙婷婷

西安交通工程學院公共課部 陜西西安 710300

1 概述

數學優化是很多學科的研究基礎，凸優化是數學優化的一個重要的分支。在一些實際問題的研究，尤其是在經濟管理等領域，“凸”的要求過于苛刻，見文獻[11-12]。而“擬凸”不僅有“凸”的優勢(有全局最小值)，又能刻畫很多實際研究中的問題，見文獻[13]。

擬凸優化問題在很多領域都有重要的應用，尤其在經濟學、工程學和管理學中，見文獻[13]。用次梯度法去解決擬凸問題的研究有限。Kiwil給出了在遞減步長準則下目標函數為上半連續時擬凸優化算法的收斂性及收斂速度，見文獻[16]。Gasimov改進了對偶次梯度算法，見文獻[17]。胡耀華等給出了一個不精確的次梯度算法解決擬凸優化問題，并證明了其收斂性，見文獻[5]。本文主要研究的是以下擬凸優化問題:

其中

f

：

R

→

R

是一個擬凸函數，約束集

S

是非空閉凸集。我們將最優解集和最優解分別記為

S

和

f

，并假設最優解集

S

是非空的和緊的。

次梯度算法是解決擬凸優化問題的一種常用的方法，但算法的收斂理論，尤其是算法的收斂速度理論與算法的步長準則的選取有關系。本文首先給出了一個次梯度算法的統一框架；其次給出擬凸優化中次梯度算法在常值步長準則下的收斂性；最后進行數值實驗，對算法的收斂性進行了數值分析。

2 相關符號

對問題(1)，我們首先給出以下的相關符號：

f

和

S

分別表示最優值和最優點集，即有，

S

：={

x

|

f

(

x

)=

f

}.記

x

在

S

上的投影和

x

到

S

距離分別為：

設

a

∈

R

，記函數

f

的水平集L(

α

)={

x

∈

R

|

f

(

x

)≤

α

}.

以下是擬凸的定義：

定義1：函數

f

：

R

→

R

稱為擬凸函數，如果滿足

f

((1-

α

)

x

+

αy

)≤max{

f

(

x

)，

f

(

y

)}，?

x

，

y

∈

R

，?

α

∈[0，1]

.

次微分的定義對于解決擬凸優化問題相當重要。凸分析中常用的次梯度為Fenchel-Moreau(FM)次微分，詳見文獻[15]，函數

f

在

x

處的FM次微分定義為：?

f

(

x

)={

g

∈

R

|〈

g

，

y

-

x

〉≤

f

(

y

)-

f

(

x

)，?

y

∈

R

}.次梯度法的主要思想是將梯度法中的梯度用任意的次梯度代替。因為擬凸函數的次FM微分可能會是空集(

y

=

x

在

x

=0時)，為了擬凸函數次微分的計算，1973年Greenberg-Pierskalla最先提出了GP次微分，函數

f

在

x

處的GP次微分定義為(詳見文獻[3])：?

f

(

x

)={

g

∈

R

|〈

g

，

y

-

x

〉≥0?

f

(

y

)≥

f

(

x

)，?

y

∈

R

}.

除此之外，擬凸函數的次微分的定義還有其他的形式，見文獻[3，5，18，19]。但是，GP次微分不是閉集，為了克服這一點，Kiwiel和胡耀華引入了一種擬次微分，其定義如下(本文使用的就是這種次微分)：

定義2：

f

：

R

→

R

是一個擬凸函數，且

ε

>0，則函數

f

在

x

∈

R

處的擬次微分及

ε

-擬次微分定義分別如下：?

f

(

x

)={

g

∈

R

|〈

g

，

y

-

x

〉≤0，?

y

∈lev<()

f

}，

3 算法及收斂性分析

在這一部分，首先，我們參考凸優化中的次梯度算法，給出了擬凸優化中的次梯度算法，在算法中選取的步長準則為常值步長準則；其次，對算法的收斂性給出了分析。下面是擬凸優化中的次梯度算法。

算法1：

步1給出初值

x

∈

R

，

k

=1；

步3令

z

=

x

-

v

g

/

‖

g

‖，

x

+1=

P

(

z

)，

k

=

k

+1，轉步2。算法的收斂性。對于凸優化和擬凸優化來說，次梯度迭代的基本不等式是分析算法收斂性的重要工具。YU提出了對多種次梯度算法收斂的統一框架，詳見文獻[10]。在實際應用中，由于誤差的存在，胡耀華提出了非精確的次梯度算法。本文討論了次梯度算法產生的點列{

x

}滿足一個非精確的基本不等式(即為引理1)，且討論了在次不等式下算法的收斂性。引理1 設{

x

}為算法1產生的點列，對于每個

x

∈

S

及

k

∈{

i

∈

N

：

f

(

x

)>

f

+

ε

}，有:

(1)

{

α

}和{

η

}是兩個正數列，滿足:

(2)

其中固定

ε

≥0，

p

>0。

從引理中的式(1)可以看出，算法的迭代點到最優解之間的距離是在不斷接近的。式(2)是對參數的假設。為了對算法收斂性的分析，下面給出算法收斂性分析中會用到的一個重要引理，詳見文獻[20]中的Lemma2.1。

下面對常值步長準則下算法的收斂性給出分析。

定理1 設{

x

}為算法1采用常值步長

α

≡

α

產生的點列，且{

x

}滿足引理1，則有:

證明：在算法1中，我們不妨假設有有限個

k

滿足

f

(

x

)≤

f

+

ε

，否則定理1一定成立。即，存在

K

∈

N

，對任意

k

≥

K

，都有:

f

(

x

)>

f

+

ε

.令

x

∈

S

，則由引理1、式(1)可得，對任意

k

≥

K

，都有:

將上式從

k

=

K

，

K

+1，…，

n

進行累加，可得:

上式結合引理2可得:

即可得此定理成立。

4 數值實驗

在這一節，我們將以數值實驗的形式來對算法1在常值步長準則下的收斂性進行分析，編程軟件為Matlab 2016a。所用的數值算例均來源于文獻[21]。

例1 求解

其中

S

=[-1，1]，

f

：

R

→

R

定義為對?

x

∈

S

，

容易驗證，

f

(

x

)為擬凸函數，且

f

=-1。

例2 求解

其中

S

=[-1，2]，

f

：

R

→

R

定義為對?

x

∈

S

，

容易驗證，

f

(

x

)為擬凸函數，且

f

=-1。

圖1

圖2

表1

結語