帶約束凸規劃的算法及收斂性分析

翟傳翠

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

關鍵詞：凸規劃；極大單調算子；臨近點算法

1 凸函數的基本定義

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

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

則稱f是Ω上的嚴格凸函數；如果存在常數 ，使得

則稱f是Ω上的強凸函數，稱c是f的強凸函數。

2 凸規劃的基本概念

設f為凸函數，稱最優化問題

為無約束凸規劃；

設f為凸函數，稱最優化問題

是帶約束凸規劃。

3 凸規劃定義域的等價轉化

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

4 算法及收斂性分析

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

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

且λh（x*）=0。

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

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

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

算法4.1

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

Step2、如果 ，則x*=x0是最優解；否則，轉下一步。

Step3、計算

Step4、如果xk+1=xk，則x*=xk是最優解；否則，令k=k+1，轉Step3。

定理4.1 設{xk}是算法4.1產生的點列，則

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

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

定理4.2 是單調映射。

證明 （1）λ=0時， 顯然為單調映射

（2）λ?0時，

令

其中，

則

由 知

以上兩式相加，有

聯立（4.3）與（4.4）知

又 ，記 則，

即 ，有

取z=y，有

同理

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

即 是單調映射。由引理4.1知存在常數λ使得

從而由（1）和（2）知 是單調映射。

定理4.3 設{xk}是由算法4.1產生的點列，則{f（xk）}單調遞減并且

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

于是存在向量u使得

從而對xk∈Ω有

并且

即{f（xk）}是單調遞減的并且

定理4.4 設{xk}是由算法4.1產生的點列，如果（CCP1）有最優解，則問題（CCP1）的最優解是{xk}的極限點；

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

（2）λ?0時，

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

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

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

由上式及柯西不等式，有

即

由k的任意性知

因此序列{xk}有界。

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

設{xki}是有界序列{xk}的任一收斂子列，不妨設 ，則由f的連續性及{f（xk）}的單調性有 。由（4.8）知

即當i足夠大時，有 。

又由（4.2）知

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

即 是問題（CCP1）的最優解。

[參考文獻]

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

[2]何堅勇.最優化方法[M].北京：清華大學出版社，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.