李博，卜晴晴

(青島科技大學(xué) 數(shù)理學(xué)院，山東 青島 266061)

0 引言

DC規(guī)劃是非凸規(guī)劃中的重要內(nèi)容之一.DC規(guī)劃又可分為無約束DC規(guī)劃和約束DC規(guī)劃[1].本文將對一類無約束DC規(guī)劃進(jìn)行研究，尋找這類DC規(guī)劃的全局最優(yōu)解.

首先，在本文第一節(jié)中給出所要研究的無約束DC規(guī)劃和一些相關(guān)的概念及性質(zhì).第二節(jié)主要針對該類DC規(guī)劃，找出它的最優(yōu)解充分條件、必要條件以及充要條件.

1 基本概念和性質(zhì)

可以表示成兩個凸函數(shù)的差的函數(shù)稱為DC函數(shù).目標(biāo)函數(shù)是DC函數(shù)的無約束規(guī)劃問題稱為無約束DC規(guī)劃.

命題1[2]二階偏導(dǎo)數(shù)處處連續(xù)的函數(shù)是DC函數(shù).

命題2[3]若f(x)在開凸集S上具有二階連續(xù)偏導(dǎo)數(shù)，則f(x)是S上的凸函數(shù)的充要條件是：f(x)的海森矩陣▽2f(x)在S上處處半正定.

考慮下面的規(guī)劃問題：

min{f(x):x∈Rn}

其中f(x)的二階偏導(dǎo)數(shù)處處連續(xù)，且▽2f(x)在Rn上處處半正定.

由命題1可知f(x)是DC函數(shù)，即f(x)=g(x)-h(x)，其中g(shù)(x)，h(x)均為凸函數(shù)，因此該規(guī)劃問題等價(jià)于下述無約束DC規(guī)劃：

min{g(x)-h(x):x∈Rn}

(1)

其中g(shù)(x)，h(x)均為凸函數(shù)，f(x)=g(x)-h(x)的二階偏導(dǎo)數(shù)處處連續(xù)且▽2f(x)在Rn上處處半正定.

下面我們將尋找這類DC規(guī)劃的最優(yōu)性條件.

2 最優(yōu)性條件

定理1 對無約束DC規(guī)劃(1)，若存在x*，使得▽g(x*)=▽h(x*)，則x*是該規(guī)劃的局部最優(yōu)解.

證明因?yàn)閒(x)=g(x)-h(x)具有二階連續(xù)偏導(dǎo)數(shù)，所以對任意的x*∈Rn，f(x)在x*的一個δ鄰域N(x*,δ)內(nèi)二次可微，因此對任意的x∈N(x*,δ)，恒有

其中0<θ<1.

又因?yàn)楱実(x*)=▽h(x*)，故▽f(x*)=0，即▽f(x*)T=0.

因此對任意的x∈N(x*,δ)，恒有f(x)≥f(x*)，即f(x*)是f(x)的局部極小值，所以x*是規(guī)劃問題(1)的局部最優(yōu)解.

定理2 對無約束DC規(guī)劃(1)，若x*是該規(guī)劃的局部最優(yōu)解，則有▽g(x*)=▽h(x*).

證明 用反證法.

因?yàn)閒(x)=g(x)-h(x)二階偏導(dǎo)數(shù)處處連續(xù)，所以對任意的x*∈Rn，f(x)在x*處可微.

假設(shè)▽g(x*)≠▽h(x*)，則有▽f(x*)=▽g(x*)-▽h(x*)≠0.

令p=-▽f(x*)，則▽f(x*)Tp=-▽f(x*)T▽f(x*)=-||▽f(x*)||2<0.

因?yàn)閒(x)可微，在x*處對f(x)作一階泰勒展開，對任意的λ>0，有f(x*+λp)=f(x*)+λ▽f(x*)Tp+ο(||λp||).

因?yàn)棣?0，▽f(x*)Tp<0，所以λ▽f(x*)Tp<0.

又因?yàn)棣?||λp||)是比||λp||高階的無窮小量，所以存在δ>0，當(dāng)λ∈(0,δ)時，恒有λ▽f(x*)Tp+ο(||λp||)<0.

所以對任意的λ∈(0,δ)，恒有f(x*+λp)

這與x*是局部最優(yōu)解矛盾，因此假設(shè)不成立，所以▽g(x*)=▽h(x*).

推論對無約束DC規(guī)劃(1)，x*是該規(guī)劃的局部最優(yōu)解的充要條件是▽g(x*)=▽h(x*).

證明 由定理1和定理2的證明易知該結(jié)論成立.

下面考慮該規(guī)劃問題(1)的全局最優(yōu)解.

定理3 對無約束DC規(guī)劃(1)，x*是該規(guī)劃的全局最優(yōu)解的充要條件是▽g(x*)=▽h(x*).

證明 由推論可知，x*是該規(guī)劃的局部最優(yōu)解的充要條件是▽g(x*)=▽h(x*)，下面只需證明該規(guī)劃的局部最優(yōu)解就是全局最優(yōu)解.

因?yàn)閤∈Rn，Rn是開凸集，f(x)=g(x)-h(x)的海森矩陣▽2f(x)在Rn上處處半正定，所以由命題2可知g(x)-h(x)是Rn上的凸函數(shù).

由凸函數(shù)的性質(zhì)可知g(x)-h(x)在Rn上的任一極小點(diǎn)就是它在Rn上的全局極小點(diǎn)，即該規(guī)劃的局部最優(yōu)解x*是該規(guī)劃的全局最優(yōu)解.

所以x*是無約束DC規(guī)劃(1)的全局最優(yōu)解的充要條件是▽g(x*)=▽h(x*).

3 小結(jié)

本文對一類特殊的DC規(guī)劃進(jìn)行研究，利用凸函數(shù)的性質(zhì)，找到了這類DC規(guī)劃的全局最優(yōu)解的充要條件.但是這類DC規(guī)劃僅僅是DC規(guī)劃中具有較好性質(zhì)的一個特例，對于一般的DC規(guī)劃的研究還需要繼續(xù)進(jìn)行.

參考文獻(xiàn)

[1]楊杰.DC規(guī)劃的臨近點(diǎn)算法和全局收斂性算法[D].南京:南京航空航天大學(xué),2007:1-36.

[2]Horst R, Thoai NV. DC Programming: Overview [J].Journal of Optimization Theory and Applications, 1999,103:1-43.

[3]何堅(jiān)勇.最優(yōu)化方法[M].北京:清華大學(xué)出版社,2007.

[4]霍斯特.全局優(yōu)化引論[M].北京:清華大學(xué)出版社,2003.

[5]解可新,韓健,林友聯(lián).最優(yōu)化方法[M].天津:天津大學(xué)出版社,2008.