带约束凸规划的算法及收敛性分析

翟传翠

摘 要：凸规划是非线性规划中一种重要的特殊形式，它具有很好的性质。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.