A Modified Hestenes-Stiefel Conjugate Gradient Algorithm for Large-Scale Nonsmooth Optimization Problems

考虑如下非光滑无约束优化问题：

其中f：ℝⁿ→ ℝ是凸函数(可能非光滑).

目标函数f经过Moreau-Yosida正则化后记作F：ℝⁿ→ ℝ：

这里参数λ＞0，‖·‖指欧氏范数.令

并定义

因为ψ(z，x)对每一个固定的x强凸，所以h(x)唯一.因此函数F(x)可以表示为

根据文献[7-9]容易知道F具有以下重要性质：

(ⅰ) F是有限凸函数，且处处可微：

进一步地，g：ℝⁿ→ ℝⁿLipschitz连续，即

(ⅱ) x是(1)式的最优解当且仅当▽F(x)=0，即h(x)=x.

从以上定义容易看出，F(x)和g(x)可以通过argmin_z∈ℝⁿψ(z，x)的最优解来获得.然而argmin_z∈ℝⁿψ(z，x)=h(x)很难精确求出，甚至不可能.因此在实际计算中，不能用精确的h(x)去定义F(x)和g(x).由于对∀x∈ℝⁿ，ε＞0，存在向量h^α(x，ε)∈ℝⁿ，使得

因此，当ε充分小的时候，可用h^α(x， ε)近似定义F(x)和g(x)：

这样定义的F^α(x，ε)和g^α(x，ε)有以下重要性质：

命题1  设h^α(x，ε)满足(5)式，F^α(x，ε)和g^α(x，ε)分别由(6)，(7)式定义，则有

以上命题说明，可以通过选取充分小的参数ε，使得F^α(x，ε)和g^α(x， ε)无限接近F(x)和g(x).命题1及其证明详见文献[10].

针对非光滑无约束凸优化问题(1)，Yuan等在文献[6]提出一个修正HS参数公式：

这里y_k^*=y_k+γ_k^*s_k，y_k=g^α(x_k+1，ε_k+1)-g^α(x_k，ε_k)，s_k=x_k+1-x_k，d_k是搜索方向，常数c＞0，并且

但相应算法并未建立.本文将在参数公式(11)基础上，结合非单调Armijo-type线搜索，提出以下包含函数值信息的求解非光滑问题的修正HS共轭梯度法.通过研究，该算法不仅自动满足充分下降条件，而且搜索方向属于信赖域.在适当条件下，证明了新算法全局收敛.初步的数值实验也表明新算法在求解非光滑无约束凸优化问题方面是有效的.

算法1

步骤1  取x₀∈ℝⁿ，γ₀∈(0，1)，σ∈(0，1)，c＞0，s＞0，λ＞0，ρ∈[0, 1]，Q₀=1，R₀=F^α(x₀，ε₀)，d₀=-g^α(x₀，ε₀)，γ∈(0，1)，令k=0.

步骤2  若‖g^α(x_k，ε_k)‖＜γ，则停止；否则进行步骤3.

步骤3  选取一个标量ε_k+1满足0＜ε_k+1＜ε_k，利用以下非单调Armijo-type线搜索计算步长t_k：

其中t_k=s2^-i_k，i_k∈{0，1，2，…}.

步骤4  令x_k+1=x_k+t_kd_k，若‖g^α(x_k+1，ε_k+1)‖＜γ，则停止；否则进行步骤5.

步骤5  利用以下公式校正R_k：

步骤6  利用(12)式计算搜索方向d_k+1.

步骤7  令k：=k+1，转步骤2.

算法中的非单调Armijo-type线搜索(12)选自文献[11]，ρ是控制非单调程度的参数.当ρ=0时，线搜索(12)就是普通的单调Armijo-type线搜索.

引理1  对所有k∈$\mathbb{N}$∪{0}，以下充分下降条件成立：

证  当k=0时，

(14)式显然成立.

当k≥1时，由(11)式，有

(14)式成立.证毕.

引理2  对所有k∈$\mathbb{N}$∪{0}，以下信赖域性质成立：

证  由(11)式得

因为

所以

证毕.

算法1的全局收敛性的证明需要用到以下假设：

假设 A  (ⅰ)设目标函数f经Moreau-Yosida正则化后得到F，则存在常数M＞0，使得

(ⅱ) F有下界.

(ⅲ)序列{ε_k}收敛于0.

根据文献[11]，我们得到以下引理：

引理3  若假设A成立，针对算法1中的每一个k，有

其中

而且满足Armijo-type线搜索(12)的步长t_k存在.

引理4  若假设A成立，序列{(x_k，t_k)}由算法1产生，假设

则存在常数m＞0，使得步长t_k满足：

证  设步长t_k满足线搜索(12)式.下面用反证法证明.

假设t_k→0，则存在

满足

把引理3中的F^α(x_k， ε_k)≤R_k≤C_k代入上式，可得

由(8)，(18)式及假设A，并利用泰勒展开式，有

因为

根据(10)，(14)式及ε_k+1≤ε_k，由(19)式可得

再由ε_k=o(t_k²‖d_k‖²)和(15)式，上式变为

不等式两边除以t_k并同取极限，得

矛盾.故假设不成立.命题得证.

根据引理1-4证明算法1的全局收敛性：

定理1  设引理4的条件都成立，则

且序列{x_k}的聚点即为问题(1)的最优解.

证  先证明

用反证法.假设(21)式不成立，则存在正数γ₀＞0和k₀＞0，使得

利用(12)，(14)，(17)，(22)式，得

由(13)式可得：

由假设A知F有下界，因而F^α(x，ε)有下界.又由引理3知对所有的k，F^α(x_k，ε_k)≤R_k，因此不难知道R_k有下界.因而根据(23)式，有

但由于根据Q_k+1的定义(13)式容易得到Q_k+1≤k+2，因此

这与(24)式矛盾.因此(21)式成立.

另一方面，由(10)式有

因而结合假设A(ⅲ)，即可得到

令x^*是序列{x_k}的聚点，则存在子序列{x_k}_K满足

根据(3)式以及F(x)的性质易知

因此由(25)和(26)式可知

成立，故x^*是问题(1)的最优解.证毕.

为了考查本文所提算法对大规模非光滑优化问题的数值表现，本文对该方法进行数值实验，并将数值结果与LMBM(limited memory bundle method)方法^[12]结果进行比较.测试问题选自文献[12]，所采用的程序是在文献[12]的程序基础上利用Fortran语言修改而得，操作系统为Windows 7，软件平台为Fortran90，处理器为Pentium Dual E5800 3.20 GHz，内存为2.0 GB，参数选取如下：s=λ=1，ρ=0.5，σ=0.8，${\varepsilon _k}{\rm{ = }}\frac{1}{{{{\left({k{\rm{ + 2}}} \right)}^2}}}$；终止条件为‖g^α(x，ε)‖≤10^-15，迭代次数N_i＞10⁴时算法失效.

表 1列出了测试问题名称及初始点，表 2则列出两种方法数值实验的结果，其中x₀表示初始点， N_i为迭代次数， N_f表示函数值的计算次数， f(x)为近似最优点的函数值.

从表 2容易看出，新算法不仅能够有效求解50 000维的非光滑问题，而且相比求解非光滑问题的传统LMBM算法优势明显.由此可以认为，新算法对大规模非光滑无约束凸优化问题的求解是有效的.