求解不可微凸可行问题的一种新算法  

A New Algorithm for Solving the Non-differentiable Convex Feasibility Problem

作　　者：王旭婷[1] 赵金玲[1] 

机构地区：[1]北京科技大学数理学院,北京100083

出　　处：《南开大学学报（自然科学版）》2017年第2期33-37,共5页Acta Scientiarum Naturalium Universitatis Nankaiensis

基　　金：国家自然科学基金(11101028);北京高校青年英才计划资助(YETP0385)

摘　　要：针对传统算法无法得到不可微函数下降方向的困难,结合方向导数信息,提出了不可微凸可行问题的一种直接算法.首先,为避免在每次迭代过程中计算投影,将凸可行问题转化为求解极大值函数的0-水平集中元素的问题;然后利用方向导数信息构造出下降方向,并且运用一维搜索法确定步长.证明了算法的收敛性,该算法无需利用梯度或次梯度,只需用到函数值信息,易于实现,数值试验表明了该算法的有效性.For the difficulty that the classical algorithms are unable to obtain the descent direction of non-differentiable function, the direct algorithm, combining the information of directional derivative, for non-differentiable convex feasibility problem is proposed. Firstly, to avoid calculating projections in each iteration, the convex feasibility problem is converted into a problem of finding one element in 0-level set of the maximum function. Then according to the characteristics of directional derivative, we construct a de- scent direction, and determine the step-size by using the one-dimension search method. The algorithm is is proved to be convergent. The algorithm only requires the information of function value, instead of gradient or subgradient, and easy to implement. Finally, numerical experiments are carried out to explain of the effectiveness of the algorithm.

关 键 词：不可微 凸可行问题 极大值函数 下降方向 方向导数 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]