带非欧氏范数的双稳定束方法

A Doubly Stabilized Bundle Method with Non-Euclidean Norm

关键词:  双稳定束方法  邻近函数  非光滑优化  全局收敛

Key words:  oubly stabilized bundle method  proximal function  non-smooth optimization  global convergence

摘要:

针对一类非光滑凸优化问题,提出一个带非欧氏范数的双稳定束方法.通过利用邻近函数代替传统的欧氏距离,形成更具广泛性的双稳定子问题,进而在计算上可充分利用可行集的几何结构,加快收敛速度、减少计算量.分析论证了算法的全局收敛性,当下降步有限时,最后一个稳定中心即为问题的最优解;当下降步无限时,稳定中心点列任意的聚点均为问题的最优解.该方法将传统邻近束方法和水平束方法的稳定性有机融合,从而具备更优越的理论性质和更稳定的数值效果.

Abstract:

In this paper, a doubly stabilized bundle method with non-Euclidean norm was proposed to solve a class of non-smooth convex optimization problems.By using the proximity function to replace the traditional Euclidean distance, a more general doubly stabilized sub-problem was formed, and the geometric structure of the feasible set could be fully utilized in the calculation to speed up the convergence rate and reduce the computational cost.The global convergence of the algorithm was analyzed and demonstrated.When the number of descent steps was finite, the last stable center was the optimal solution of the problem.When the number of descent steps was infinite, each accumulation point of the sequence of stable centers was the optimal solution of the problem.This method well combined the stability of traditional proximal bundle method and level bundle method, so that it had more superior theoretical properties and more stable numerical effects.