《非光滑无约束优化次梯度法》.pdf

《《非光滑无约束优化次梯度法》.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第36卷第2期玉林师范学院学报(自然科学)Vo1．36No．22015年JOURNALOFYULINNORMALUNIVEKSITY(NaturalScience)非光滑无约束优一化困次梯度法口张玉凤(广西大学数学与信息科学学院，广西南宁530004)[摘要]次梯度法是求解非光滑优化问题的一类经典算法，也是解决大规模问题的有效方法．它在经济学、力学、工程和最优控制等许多实际问题中有着广泛应用．本文概述了经典次梯度法的来源、算法基本框架及进一步的改进方法，为次梯度方法的进一步研究提供参考．[关键词]非光滑优化；次梯度法；椭球法；变尺度

2、[中图分类号]0224[文献标识码]A[文章编号]1004—4671(2015)02—0027—04文考虑求解如下形式的非光滑无约束优化问题min，()(1)其中，：一R为凸函数，但不一定可微，即函数在某些点没有通常意义下的导数(梯度)．因此，需要对梯度的概念进行推广，引入厂在处的次微分：a厂()={g∈Rfgr(z—)f(z)一厂()，Vz∈R}．集合)中的元素称为厂在处的次梯度．在算法设计时，通常假设对任意给定的X，能计算出函数．值f(x)及任意一个次梯度g∈af(．类似于光滑情形，有如下最优性条件(见文[1])：是问题(1)的

3、最优解，当且仅当0∈a．厂()．然而，直接用次梯度法取代光滑优化算法中的梯度求解问题(1)，也是行不通的，原因大致归结为以下三点：(a)终止条件不再适用．对于光滑无约束优化问题，梯度存在且连续，并且在极小点处梯度为零．由此可知当迭代点充分靠近最优解时，梯度的范数小于一个充分小量，而对于非光滑优化问题，则没有类似的结果．(b)负次梯度方向不再是下降方向．对于光滑优化问题，负梯度方向总是下降方向．而对于非光滑优化问题，并非所有的负次梯度方向都是下降方向．实际计算表明，由于非光滑优化问题中函数的数学性态较差，许多不使用导数的直接搜索方法也

4、难以对其求解；(C)对于非光滑优化问题，存在“锯齿”现象．在这种情况下，如用精确搜索的最速下降法求解非光滑优化问题时，可能会收敛到非最优解．因此，对于求解非光滑优化问题必须建立新的理论及方法．众所周知，次梯度法u是求解非光滑优化问题(1)最经典的方法，其基本思想是用次梯度代替梯度推广光滑优化的方法．次梯度法结构简单，计算量小，虽然在求解非光滑优化问题方面仍存在缺点，但它是求解非光滑优化问题的基础，也是解决大规模非光滑优化问题的有效算法．次梯度法简单的算法结构，引起众多学者的关注，并被广泛应用于求解各类实际问题．尽管如此，但如何构造一

5、个目标函数的下降方向以及保证算法的快速收敛性仍是研究次梯度算法所面临的难题．本文将重点介绍非光滑优化问题经典次梯度算法的基本框架及改进方法．[收稿日期]2015-03-31[基金项目]广西自然科学基金创新研究团队(2014GXNSFFA118001)。[作者简介】张玉凤(1987~)，女，河北河间人，广西大学数学与信息科学学院研究生。主要研究方向：最优化理论与算法。7}墓2015正玉林师范学院学报第2期2经典次梯度法在光滑优化问题中，通过计算迭代点处的梯度、投影梯度、共轭梯度等容易获得目标函数的下降方向．但在非光滑优化中，由于目标函

6、数不可微导致在某些点处没有通常意义下的梯度，故许多基于梯度理论的算法失效．为此，N．Z．ShorEl1]首次提出使用次梯度代替梯度的次梯度法，进而将光滑优化中基于梯度的方法推广到求解非光滑优化问题．下面给出求解问题(1)的次梯度法的基本框架，见文[12]．算法1(经典次梯度法)步骤0选取初始点X。及满足一定条件的步长序列}，令k=0；步骤l计算g∈afk)，若gk=0，则停止；否则转步骤2；步骤2令=一，k=k+l，返回步骤1．由算法l可知，一方面，经典次梯度法结构简单，在每一个迭代点处只需计算目标函数的一个次梯度即可．另一方面，次

7、梯度法不需要线搜索，步长事先给定，无需求解不等式，降低了计算量．在以下三种情况下，算法产生的迭代点列均可收敛到最优解，见文[13]．情形1：≥0，1g【一0(k一∞)，∑}g1=+。。；k=l情形2：=l-—_，0<￡l2一￡2<2；lgI情形3：0，一0(k一。。)，∑：+。。；{gk}07有界．k=0其中情形2假设函数的最优值f已知．不同的步长策略对算法的收敛性有不同的影响，当步长序列选取得当时，可避免锯齿现象，获得好的收敛性．另外，通过改变算法的搜索方向也可提高算法的收敛速率．下面介绍两种从不同角度出发改进搜索方向的次梯度法．

8、3椭球次梯度法经典次梯度方法的搜索方向直接利用负次梯度．在光滑优化算法中，最速下降法中相邻两方向的梯度正交，在正交方向外搜索最优解效果非常差．在非光滑优化问题中为了加快收敛，充分利用前面迭代点的次梯度信息，让相邻两个搜索方向尽量正交．