求解不可微凸优化问题的充分下降共轭梯度法

黄元元

(河南科技大学 数学与统计学院， 河南 洛阳 471023)

0 引言

考虑无约束优化问题：

minf(x)，x∈Rn，

(1)

其中f：Rn→R是连续的凸函数，但不一定可微。该问题在机器学习、数据分析、信号处理和图像处理等领域[1-4]均有应用。若f是连续可微的，则共轭梯度(conjugate gradient,CG)法是求解问题(1)较常用且有效的一类方法。若f为连续的凸函数但不可微，则求解问题(1)的较早算法是邻近点方法 (proximal point methods, PPM)[5-6]，将问题(1)转化为极小化问题：

minF(x)，x∈Rn，

(2)

进行求解，其中：

(3)

为函数f的Moreau-Yosida正则化函数。鉴于两者解集相同[7]，文献[8]引入近似求解函数F(x)的值及其梯度值的策略，在邻点算法基础上设计了求解问题(2)的一种切实可行的算法，该算法是Moreau-Yosida正则化和一般牛顿法的结合。之后，文献[9]提出求解问题(2)的两项和三项Polak-Ribière-Polyak(PRP)共轭梯度法，文献[10-11]提出求解问题(2)的改进的PRP共轭梯度法和Hestenes-Stiefel(HS)共轭梯度法，文献[12]提出共轭参数非负的改进共轭梯度法。但在求解光滑的无约束优化问题上非常具有优势且满足充分下降条件的CG_DESCENT方法[13-14]，在求解问题(1)方面却未有相关文献进行研究。本文将基于CG_DESCENT方法求解光滑无约束优化问题的更一般形式[15]，给出求解问题(1)的一类具有充分下降条件的共轭梯度法，并证明它们在不依赖于任何线搜索的情况下满足充分下降条件且全局收敛。

1 预备知识

下面给出本文要用到的基本命题和引理，具体证明过程请参阅相关文献。

命题1[7]设函数F如式(3)定义，则函数F是有界的凸函数且处处可微，其梯度为g(x)=▽F(x)=λ(x-p(x))。该梯度映射g:Rn→Rn是逆强单调的，即

并且是λ-Lipschitz 连续的，即

(4)

命题2[7]若x*是问题(1)的最优解，则x*也是问题(2)的最优解，且与以下几条陈述相互等价：