翟传翠

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

又 ，记 则，

即 ，有