非光滑约束优化的两阶段近似束方法

石露 刘逸

摘 要：基于两阶段束方法思想，利用近似函数值以及近似次梯度构造割平面近似模型和线搜索条件，提出了一个非光滑约束优化的两阶段近似束方法。算法最终具备全局收敛性。

关键词：非光滑优化;两阶段束方法;近似束方法;全局收敛性

中图分类号：O221.2  文献标识码：A

An Approximate Twophase Bundle Method

for Nonsmooth Constrained Optimization

Shi Lu Liu Yi

Xingjian College of Science and Liberal Arts，Guangxi University GuangxiNanning 530005

Abstract：Based on the idea of twophase bundle method，an approximate twophase bundle method is proposed by using the approximate function values and approximate subgradient to construct the cuttingplane model and line search condition.Finally，the algorithm has global convergence.

Keywords：nonsmooth optimization;twophase bundle method;approximate bundle method;global convergence

1 概述

本文研究求解如下非光滑约束优化问题：

minx∈瘙 綆

nf（x）

s.t.c（x）SymbolcB@

0（1）

其中f：瘙 綆

n→瘙 綆

为凸函数，且可能不可微。为陈述简便，本文仅考虑c（x）是一个数量值函数，若实际问题有m个约束条件时，如cj（x）SymbolcB@

0，j=1，…，m，可取c（x）=max{cj（x），j=1，…，m}。

非光滑优化存在于很多实际问题中，非光滑优化也称为不可微优化，其研究起源于20世纪60年代。经过半个多世纪的发展，非光滑优化在理论与算法研究方面取得了比较丰富的成果，并广泛应用于求解实际问题，如机器学习、最优控制、图像信息处理、人工智能、经济系统等领域。束方法[1]是目前求解非光滑优化问题最有效的方法之一。束方法可看作稳定化的割平面法，由于每次算法迭代使用一组次梯度产生求解搜索方向的子问题，因此得名“束”。但目前大多束方法使用精确的函数值和精确次梯度构造算法，而在某些问题中很难计算精确的函数值，例如拉格朗日松弛问题。

minx∈Xg（x），s.t.h（x）=0

其拉格朗日函数为L（x，μ）=g（x）+〈μ，h（x）〉，当f（x）=maxx∈XL（x，μ）时，此时计算f的精确函数值和精确次梯度都有很大的困难。因此很多学者们利用近似函数值和近似次梯度等非精确数据构造算法。文献[2]对给定的误差限，利用近似函数值和近似次梯度，结合邻近束方法思想，给出一个非光滑无约束优化的近似束方法。文献[3]对文献[2]的割平面近似模型进行改善使其更加接近目标函数。文献[4]在文献[2，3]的基础上给出了对目标函数近似程度更好的多面体函数，并将文献[5]的束集修正策略推广至非精确数据。文献[6]基于文献[2]的思想将非光滑优化强次可行方向法推广到非精确的情形，但仍需计算精确的约束函数值和梯度。

兩阶段束方法[7]是一类不可行束方法，算法能接受任意初始点，在阶段一通过使约束函数值减小搜索一个可行迭代点，若产生可行迭代点，则进入阶段二即可行下降阶段，在保证迭代点可行的条件下，使目标函数值减小，从而得到问题的最优解。

本文在文献[1，2，4，7]的基础上，提出一个近似的两阶段束方法，该算法利用近似的函数值和近似次梯度构造原问题的割平面近似模型以及线搜索条件，算法最终收敛到全局最优解。

2 算法设计

凸函数f在x处的—次微分[7]为：

f（x）={g∈瘙 綆

n|f（y）f（x）+〈g，y-x〉-，y∈瘙 綆

n}

其中≥0。集合f（x）的元素g为函数f在x处的—次梯度。记问题（1）的可行集为：

X={x∈瘙 綆

n|c（x）SymbolcB@

0}

对任意给定的x∈瘙 綆

n，定义改善函数[7]：

Hx（y）=max{f（y）-f（x），c（y）}，y∈瘙 綆

n

当x∈X时，Hx（x）=0，若Hx（y）<Hx（x），则有Hx（y）<Hx（x）且c（y）<0。

引理2.1[7] 设问题（1）满足Slater约束规格，即可行集X非空，则以下三个命题等价。

（a）0∈Hx-（x-）;

（b）min{Hx-（y）：y∈瘙 綆

n}=Hx-（x-）=0;

（c）x-是问题（1）的最优解。

设yi（i=1，…，k）为算法产生的试探点列，εi0为相应的误差限，假设fεi（yi），cεi（yi）和gif，gic分别为目标函数和约束函数在点yi处的近似函数值和近似次梯度，且满足下列不等式：

f（yi）-εiSymbolcB@

fεi（yi）SymbolcB@

f（yi），c（yi）-εiSymbolcB@

cεi（yi）SymbolcB@

c（yi）（2）

f（x）fεi（yi）+〈gif，x-yi〉，c（x）cεi（yi）+〈gic，x-yi〉，x∈瘙 綆

n（3）

易证gif∈εif（yi），gic∈εic（yi）。

在yi处，定义f，c的近似线性化为：

fi（x）=fεi（yi）+〈gif，x-yi〉，ci（x）=cεi（yi）+〈gic，x-yi〉

根据（3）式，可得：

fi（x）SymbolcB@

f（x），ci（x）SymbolcB@

c（x），x∈瘙 綆

n（4）

根据文[4]，可定义f，c的如下割平面近似模型：

f^k（x）=maxi∈Ik{fi（x）}=fεk（xk）+maxi∈Ik{〈gif，x-xk〉-αik}+εk，

c^k（x）=maxi∈Ik{ci（x）}=cεk（xk）+maxi∈Ik{〈gic，x-xk〉-βik}+εk。

其中Ik={1，2，…，k}，且：

αik=fεk（xk）-[fεi（yi）+〈gi，xk-yi〉]+εk，

βik=cεk（xk）-[cεi（yi）+〈gic，xk-yi〉]+εk（5）

稱为近似线性化误差，由（2）式和（3）式易知αik0，βik0。对任意的x∈瘙 綆

n，有f（x）f^k（x），c（x）c^k（x），称f^k（x），c^k（x）分别为f（x）和c（x）的下近似函数。在算法中采用某种更新准则，使误差限序列εii∈Ik单调不增，因此当前误差限εk是最小的，由文献[4]易知，本文构造的割平面近似模型比文献[2，3]的更接近原函数。

记稳定中心为xk，定义H的割平面近似模型为：

Hˇxk（y）=max{f^k（x）-fεk（xk）-εk，c^k（x）-εk}

易得Hxk（y）H^xk（y）。

定义束集：

Bk={（yi，fεi（yi），cεi（yi），gif，gic，αik，βik，i∈Ik}

利用Bk构造以下子问题产生新的试探点yk+1：

minx∈瘙 綆

n Hˇxk（y）+12γ‖y-xk‖2（6）

其中邻近参数γ>0。令y=xk+d，u=Hˇxk（y），根据两阶段束方法的思想，令c-（xk）+=max{0，cε（xk）}，则问题（6）可转化为以下子问题：

minu∈瘙 綆

，d∈瘙 綆

n u+12γ‖d‖2

s.t. （gif）Td-αik-c-（xk）+SymbolcB@

u，i∈Jk，

（gic）Td-βik+cε（xk）-c-（xk）+SymbolcB@

u，i∈Jk（7）

设（dk，uk）为问题（7）的最优解，其KKT乘子为λki，μki，i∈Jk，根据KKT条件有如下引理成立。

引理2.2 dk=-1γgk，uk=（-1γ‖gk‖2+α^k）（8）

其中：

gk=∑i∈Jkλkigif+∑i∈Jkμkigic，（9）

α^k=∑i∈Jkλkiαik+∑i∈Jkμkiβik+∑i∈Jkμki（-cε（xk））+c-（xk）+（10）

因为（0，0）为问题（7）的一个可行解，所以有ukSymbolcB@

0。若uk=0，由引理2.1和2.2可推出xk是问题（1）的最优解。若uk<0，令yk+1=xk+dk，給定参数m∈（0，1），下面给出新的线搜索条件。

若：

cε（xk）>0且cεk+1（yk+1）+εk+1SymbolcB@

cε（xk）+muk（11）

或：

cεk+1（yk+1）+εk+1SymbolcB@

0且fεk+1（yk+1）+εk+1SymbolcB@

fε（xk）+muk（12）

成立，则更新稳定中心，令xk+1=yk+1，称为有效步;否则，稳定中心保持不变，令xk+1=xk，称为无效步。根据（2）式，由（1112）式也可推出文献[7]两阶段束方法的线搜索条件，因此本文算法的收敛性分析类似文献[7]。

下面给出算法的具体步骤。

算法2.1

步骤1（初始化）选取初始迭代点x1∈瘙 綆

n，初始误差限ε10，令I1={1}，y1=x1，fε1（y1）=fε1（x1），cε1（y1）=cε1（x1），B1={（y1，fε1（y1），cε1（y1），g1f，g1c，ε1，ε1）}。

设置参数0<m<m-<1，δ>0，令k：=1。

步骤2（求解QP子问题）求解子问题（7）得到最优解（dk，vk）以及乘子λki，i∈Ik。

步骤3（更新误差限）若εk>-（m--m）uk3，置εk=εk2，并返回步骤2;否则，令εk+1=εk，转步骤3。

步骤4（终止准则）如果|uk|SymbolcB@

δ，算法终止;否则，转步骤5。

步骤5（线搜索）若（11）式或（12）式成立，令yk+1=xk+d，xk+1=yk+1（有效步）;否则令xk+1=xk（无效步）。计算fεk+1（yk+1），cεk+1（yk+1），gk+1f，gk+1c。

步骤6（扩充束集）若为有效步，令αk+1k+1=βk+1k=εk+1，利用（5）式更新αik+1，βik+1，i∈Ik;若为无效步，令αik+1=αik，βik+1=βik，i∈Ik，利用（5）式计算αk+1k+1，βk+1k+1。令Ik+1=Ik∪{k+1}，且：

Bk+1={（yi，fεi（yi），cεi（yi），gif，gic，αik+1，βik+1），i∈Ik+1}

令k：=k+1，转步骤1。

类似文献[4]和文献[7]可得如下引理成立。

引理2.3 （i）gk∈αkHxk（xk）;

（ii）若|uk|SymbolcB@

δ，则有Hxk（y）Hxk（xk）-δ‖y-xk‖-δ，y∈瘙 綆

n。

证明 根据（2）～（3）式以及（8）～（10）式，结合H的定义，可证明引理成立，证明类似文献[8]的引理2.3。

3 算法的全局收敛性

令终止参数δ=0，下面分析算法2.1的全局收敛性。

引理3.1[7] 令ωk=12γ‖γdk‖2+α^k，则ωk是以下问题的最优值：

minλki，μki，i∈Ik 12γ‖∑i∈Ikλkigif+∑i∈Ikμkigic‖2+

∑i∈Ikλkiαik+∑i∈Ikμkiβik-∑i∈Ikμkicε（xk）+c-（xk）+

s.t.∑i∈Ikλki+∑i∈Ikμki=1，λki0，μki0，i∈Ik

引理3.2[7] 设n维向量d，g及常数η∈（0，1），C，ω，ρ，α^和α满足：

ω=12γ‖γd‖2+α^，u=-（γ‖d‖2+α^）

-α+〈g，d〉ηu，Cmax{‖γd‖，‖g‖γ，α^，1}

令ω-=min{Q（ρ），ρ∈[0，1]}，其中Q（ρ）=12γ‖（1-ρ）（-γd）+ρg‖2+（1-ρ）α^+ρα，则ω-SymbolcB@

ω-（1-η）2ω2/（8C2）。

引理3.3 若算法的有效步有限，则存在一个无限指标集K，使得uk→0，k∈K。

证明 根据（2）～（3）式，引理3.1—3.2，类似文献[6]定理2.1的情形2，可得引理成立。

引理3.4 若算法的有效步无限，且f在可行集X上有下界，设有效步指标集为K-，则：

∑k∈K-（-uk）<+SymboleB@

证明 根据（2）～（3）式，类似于文献[8]引理2.4的证明，可得引理成立。

基于上述引理，可以得到如下全局收敛性定理。

定理3.1 設算法2.1产生无限迭代点列xk，则：

（i）若算法的有效步有限，则存在一个无限指标集K，使得算法产生的试探点序列ykk∈K收敛到最后一个稳定中心，且最后一个稳定中心为问题（1）的一个最优解;

（ii）若算法在第k次迭代时在步骤2和步骤3之间无限次循环，则xk是问题（1）的一个最优解;

（iii）若算法的有效步无限，且存在k～，使得xk～∈X，则当f在X上有下界时，xk收敛到问题（1）的一个最优解。

证明 （1）若算法的有效步有限，根据引理3.3可知，则存在一个无限指标集K，使得uk→0，k∈K。根据（8）—（10）式可知limk∈Kdk=limk∈Kgk=limk∈Kα^k=0。设存在正整数l>0使得xl为最后一个稳定中心，则对任意的k>l有xk=xl，根据引理2.3可知0∈Hxl（xl），再结合引理2.1可知，最后一个稳定中心xl为问题（1）的一个最优解。

（2）若算法在第k次迭代时在步骤2和步骤3之间无限次循环，由εk>-（m--m）uk3且εk0可εk→0，又因为εk>-（m--m）uk3，m--m>0，则有uk>-3εkm--m，结合uk的非负性可推出uk→0。因此根据引理2.3可得0∈Hxk（xk），再由引理2.1可得知xk为问题（1）的最优解。

（3）若算法的有效步无限，设有效步指标集为K-，由引理3.4知∑k∈K-（-uk）<+SymboleB@

，从而有uk→0，k∈K-，根据（8）—（10）式可推出limk∈Kdk=limk∈Kgk=limk∈Kα^k=0，结合引理2.3可证明序列xk有界，令x-为xkK-的一个聚点，则x-是问题（1）的最优解。证明类似文献[9]定理4.1（ii）的证明。

结语

针对某些函数的精确函数值难以计算的问题，本文利用近似的函数值和近似次梯度构造原函数的割平面近似模型以及线搜索条件，结合两阶段束方法的思想，提出一个非光滑约束优化的两阶段近似束方法，该方法能接受任意初始点，若初始点在可行域外，算法会在阶段一寻找可行迭代点，一旦产生可行迭代点，接着进入阶段二即可行下降阶段，算法最终具备全局收敛性。

参考文献：

[1]Schramm H，Zowe J.A version of the bundle idea for minimizing a nonsmooth function：Conceptual idea，convergence analysis，numerical results[J].SIAM Journal on Optimization，1992，2：121152.

[2]Kiwiel K C.An algorithm for nonsmooth convex minimization with errors[J].Mathematics of Computation，1985，171（45）：173180.

[3]Shen J，Xia Z Q，Pang L P.A proximal bundle method with inexact data for convex nondifferentiable minimization[J].Nonlinear Analysis，2007，66（9）：20162027.

[4]石露，高扬，刘逸.非光滑无约束优化带束集修正的近似束方法[J].南宁师范大学学报：自然科学版，2020，37（4）：3340.

[5]Demyanov A V，Fuduli A，Miglionico G.A bundle modification strategy for convex minimization[J].European Journal of Operational Research，2007，180（1）：3847.

[6]唐春明，律金曼.基于非精确数据的非光滑优化强次可行方向法[J].广西科学，2016，23（5）：404408.

[7]Kiwiel K C.Methods of descent for nondifferentiable optimization[M].Berlin：SpringerVerlag，1985.

[8]石露，唐春明，简金宝.非光滑约束优化带束集修正的两阶段束方法[J]，数学进展，2021，50（5）：742758.

[9]Jian，J.B.，Tang，C.M.and Shi，L.，A feasible point method with bundle modification for nonsmooth convex constrained optimization，Acta Math.Appl.SINE.，2018，34（2）：254273.

基金项目：广西大学行健文理学院科研项目（No.Y2018ZKK03）;广西高校中青年教师科研基础能力提升项目（No.2020KY54013）

作者简介：石露（1987— ），女，广西玉林人，硕士，讲师，主要从事光滑优化和非光滑优化等最优化算法、数学教学等方面的研究。