下载: -
非线性共轭梯度法由于具有算法简单、所需的存储需求小等特点，被广泛应用于大规模光滑无约束优化问题的求解，出现了如PRP[1-2]，HS[3]，LS[4]，FR[5]等一批经典的共轭梯度算法.然而在实际生活中，我们经常会碰到大规模的非光滑优化问题，如图形图像处理、生物工程等等.充分利用共轭梯度法的特点来求解非光滑凸优化问题是一个有意义的问题，目前这方面的研究成果还比较少.文献[6]提出了一种新的修正Polak-Ribière-Polyak共轭梯度法，通过利用Moreau-Yosida正则化技术，并结合非单调线搜索，新算法能够有效解决非光滑凸优化问题.同时，文献[6]也提出了一个修正Hestenes-Stiefel(HS)参数公式，但是并未进一步设计相应的共轭梯度法，也未对方法的收敛性质和数值效果做讨论.本文将以修正HS参数公式为基础建立相应的共轭梯度算法，并讨论其相关性质.
全文HTML
-
考虑如下非光滑无约束优化问题：
其中f：ℝn→ ℝ是凸函数(可能非光滑).
目标函数f经过Moreau-Yosida正则化后记作F：ℝn→ ℝ：
这里参数λ＞0，‖·‖指欧氏范数.令
并定义
因为ψ(z，x)对每一个固定的x强凸，所以h(x)唯一.因此函数F(x)可以表示为
(ⅰ) F是有限凸函数，且处处可微：
进一步地，g：ℝn→ ℝnLipschitz连续，即
(ⅱ) x是(1)式的最优解当且仅当▽F(x)=0，即h(x)=x.
从以上定义容易看出，F(x)和g(x)可以通过argminz∈ℝnψ(z，x)的最优解来获得.然而argminz∈ℝnψ(z，x)=h(x)很难精确求出，甚至不可能.因此在实际计算中，不能用精确的h(x)去定义F(x)和g(x).由于对∀x∈ℝn，ε＞0，存在向量hα(x，ε)∈ℝn，使得
因此，当ε充分小的时候，可用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参数公式：
这里yk*=yk+γk*sk，yk=gα(xk+1，εk+1)-gα(xk，εk)，sk=xk+1-xk，dk是搜索方向，常数c＞0，并且
但相应算法并未建立.本文将在参数公式(11)基础上，结合非单调Armijo-type线搜索，提出以下包含函数值信息的求解非光滑问题的修正HS共轭梯度法.通过研究，该算法不仅自动满足充分下降条件，而且搜索方向属于信赖域.在适当条件下，证明了新算法全局收敛.初步的数值实验也表明新算法在求解非光滑无约束凸优化问题方面是有效的.
算法1
步骤1 取x0∈ℝn，γ0∈(0，1)，σ∈(0，1)，c＞0，s＞0，λ＞0，ρ∈[0, 1]，Q0=1，R0=Fα(x0，ε0)，d0=-gα(x0，ε0)，γ∈(0，1)，令k=0.
步骤2 若‖gα(xk，εk)‖＜γ，则停止；否则进行步骤3.
步骤3 选取一个标量εk+1满足0＜εk+1＜εk，利用以下非单调Armijo-type线搜索计算步长tk：
其中tk=s2-ik，ik∈{0，1，2，…}.
步骤4 令xk+1=xk+tkdk，若‖gα(xk+1，εk+1)‖＜γ，则停止；否则进行步骤5.
步骤5 利用以下公式校正Rk：
步骤6 利用(12)式计算搜索方向dk+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)的步长tk存在.
引理4 若假设A成立，序列{(xk，tk)}由算法1产生，假设
则存在常数m＞0，使得步长tk满足：
证 设步长tk满足线搜索(12)式.下面用反证法证明.
假设tk→0，则存在
满足
把引理3中的Fα(xk， εk)≤Rk≤Ck代入上式，可得
由(8)，(18)式及假设A，并利用泰勒展开式，有
因为
根据(10)，(14)式及εk+1≤εk，由(19)式可得
再由εk=o(tk2‖dk‖2)和(15)式，上式变为
不等式两边除以tk并同取极限，得
矛盾.故假设不成立.命题得证.
根据引理1-4证明算法1的全局收敛性：
定理1 设引理4的条件都成立，则
且序列{xk}的聚点即为问题(1)的最优解.
证 先证明
用反证法.假设(21)式不成立，则存在正数γ0＞0和k0＞0，使得
利用(12)，(14)，(17)，(22)式，得
由(13)式可得：
由假设A知F有下界，因而Fα(x，ε)有下界.又由引理3知对所有的k，Fα(xk，εk)≤Rk，因此不难知道Rk有下界.因而根据(23)式，有
但由于根据Qk+1的定义(13)式容易得到Qk+1≤k+2，因此
这与(24)式矛盾.因此(21)式成立.
另一方面，由(10)式有
因而结合假设A(ⅲ)，即可得到
令x*是序列{xk}的聚点，则存在子序列{xk}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，迭代次数Ni＞104时算法失效.表 1列出了测试问题名称及初始点，表 2则列出两种方法数值实验的结果，其中x0表示初始点， Ni为迭代次数， Nf表示函数值的计算次数， f(x)为近似最优点的函数值.
从表 2容易看出，新算法不仅能够有效求解50 000维的非光滑问题，而且相比求解非光滑问题的传统LMBM算法优势明显.由此可以认为，新算法对大规模非光滑无约束凸优化问题的求解是有效的.