帶約束凸規(guī)劃的算法及收斂性分析

翟傳翠

摘 要：凸規(guī)劃是非線性規(guī)劃中一種重要的特殊形式，它具有很好的性質(zhì)。1976年Rockafellar利用極大單調(diào)算子的性質(zhì)提出了求解無約束凸規(guī)劃的臨近點算法，文章根據(jù)凸規(guī)劃的性質(zhì)、最優(yōu)性條件等將這一算法推廣到帶約束凸規(guī)劃上。

關(guān)鍵詞：凸規(guī)劃；極大單調(diào)算子；臨近點算法

1 凸函數(shù)的基本定義

定義1.1 設(shè)f定義在非空凸集 上，如果對任意想，x，y∈Ω和α∈[0，1]，有

則稱f是Ω上的凸函數(shù)；如果對任意x，y∈Ω和α∈（0，1），當(dāng)x≠y時，有

則稱f是Ω上的嚴(yán)格凸函數(shù)；如果存在常數(shù) ，使得

則稱f是Ω上的強凸函數(shù)，稱c是f的強凸函數(shù)。

2 凸規(guī)劃的基本概念

設(shè)f為凸函數(shù)，稱最優(yōu)化問題

為無約束凸規(guī)劃；

設(shè)f為凸函數(shù)，稱最優(yōu)化問題

是帶約束凸規(guī)劃。

3 凸規(guī)劃定義域的等價轉(zhuǎn)化

事實上，只要在上述帶約束凸規(guī)劃中令 即可。所以上述帶約束凸規(guī)劃可以寫成如下形式

4 算法及收斂性分析

以下記 ，則Ω是有界閉凸集。

引理4.1（Kuhn-Tucker條件） 如果存在 ，使得 ，則 是（CCP1）的最優(yōu)解的充分必要條件是存在常數(shù)λ≥0，使得

且λh（x*）=0。

證明 如果h（x*）﹤0，則x*∈intΩ，則x*是最優(yōu)解的充分必要條件為 。取λ=0，則結(jié)論成立。如果h（x*）=0，則x*是最優(yōu)解的充分必要條件是

于是存在常數(shù)λ≥0，使得 。顯然λh（x*）=0。

根據(jù)引理4.1可得求解（CCP1）的臨近點算法如下：

算法4.1

Step1、取初始點x0∈Ω及有界序列

Step2、如果 ，則x*=x0是最優(yōu)解；否則，轉(zhuǎn)下一步。

Step3、計算

Step4、如果xk+1=xk，則x*=xk是最優(yōu)解；否則，令k=k+1，轉(zhuǎn)Step3。

定理4.1 設(shè){xk}是算法4.1產(chǎn)生的點列，則

證明 令 ，則g（x）是Ω上的凸函數(shù)，且 有

由引理4.1知 ，從而（4.2）成立。

定理4.2 是單調(diào)映射。

證明 （1）λ=0時， 顯然為單調(diào)映射

（2）λ?0時，

令

其中，

則

由 知

以上兩式相加，有

聯(lián)立（4.3）與（4.4）知

又 ，記 則，

即 ，有

取z=y，有

同理

由（4.5）、（4.6）及（4.7）知

即 是單調(diào)映射。由引理4.1知存在常數(shù)λ使得

從而由（1）和（2）知 是單調(diào)映射。

定理4.3 設(shè){xk}是由算法4.1產(chǎn)生的點列，則{f（xk）}單調(diào)遞減并且

證明 由定理4.1知，{xk}滿足

于是存在向量u使得

從而對xk∈Ω有

并且

即{f（xk）}是單調(diào)遞減的并且

定理4.4 設(shè){xk}是由算法4.1產(chǎn)生的點列，如果（CCP1）有最優(yōu)解，則問題（CCP1）的最優(yōu)解是{xk}的極限點；

證明 （1）λ=0時，顯然成立

（2）λ?0時，

設(shè)x*∈Ω是問題（CCP1）的最優(yōu)解，由引理4.1知（4.1）成立，即存在常數(shù)λ?0，使得

且λh（x*）=0。而點列{xk}滿足（4.2），即

又由定理4.2知， 是單調(diào)映射。由（4.1）和（4.9）及單調(diào)映射的定義知以下過程成立：

由上式及柯西不等式，有

即

由k的任意性知

因此序列{xk}有界。

以下證序列{xk}的任一聚點都是問題（CCP1）的解。

設(shè){xki}是有界序列{xk}的任一收斂子列，不妨設(shè) ，則由f的連續(xù)性及{f（xk）}的單調(diào)性有 。由（4.8）知

即當(dāng)i足夠大時，有 。

又由（4.2）知

（4.10）兩邊對 取極限，再利用 與 的上半連續(xù)性知

即 是問題（CCP1）的最優(yōu)解。

[參考文獻(xiàn)]

[1]袁亞湘，孫文瑜.最優(yōu)化理論與方法[M].北京：科學(xué)出版社，1995：32-33.

[2]何堅勇.最優(yōu)化方法[M].北京：清華大學(xué)出版社，2007：283-285.

[3]Rockafellar R T.Monotone operators and the proximal point algorithm[J].Journal on Control and Optimization，1976（14）877-898.

[4]Sun Wen-yu，Sampaio R J B，Candido M. A B.Proximal point algorithms for minimization of DC function[J].Journal of Computational Mathematics，2003，（4）：451-462.