A proximal bundle method for nonsmooth DC optimization utilizing nonconvex cutting planes

被引:0
作者
Kaisa Joki
Adil M. Bagirov
Napsu Karmitsa
Marko M. Mäkelä
机构
[1] University of Turku,Department of Mathematics and Statistics
[2] Federation University Australia,Faculty of Science and Technology
来源
Journal of Global Optimization | 2017年 / 68卷
关键词
Nonsmooth optimization; Nonconvex optimization; Proximal bundle methods; DC functions; Cutting plane model; 90C26; 49J52; 65K05;
D O I
暂无
中图分类号
学科分类号
摘要
In this paper, we develop a version of the bundle method to solve unconstrained difference of convex (DC) programming problems. It is assumed that a DC representation of the objective function is available. Our main idea is to utilize subgradients of both the first and second components in the DC representation. This subgradient information is gathered from some neighborhood of the current iteration point and it is used to build separately an approximation for each component in the DC representation. By combining these approximations we obtain a new nonconvex cutting plane model of the original objective function, which takes into account explicitly both the convex and the concave behavior of the objective function. We design the proximal bundle method for DC programming based on this new approach and prove the convergence of the method to an ε\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon $$\end{document}-critical point. The algorithm is tested using some academic test problems and the preliminary numerical results have shown the good performance of the new bundle method. An interesting fact is that the new algorithm finds nearly always the global solution in our test problems.
引用
收藏
页码:501 / 535
页数:34
相关论文
共 56 条
[1]  
An LTH(2012)Exact penalty and error bounds in DC programming J. Glob. Optim. 52 509-535
[2]  
Ngai HV(1997)Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms J. Glob. Optim. 11 253-285
[3]  
Tao PD(2005)The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems J. Glob. Optim. 133 23-46
[4]  
An LTH(2010)DC models for spherical separation J. Glob. Optim. 48 657-669
[5]  
Tao PD(2012)Margin maximization in spherical separation Comput. Optim. Appl. 53 301-322
[6]  
An LTH(2002)A method for minimizing of quasidifferentiable functions Optim. Methods Softw. 17 31-60
[7]  
Tao PD(2010)A quasisecant method for minimizing nonsmooth functions Optim. Methods Softw. 25 3-18
[8]  
Astorino A(2011)Codifferential method for minimizing nonsmooth DC functions J. Glob. Optim. 50 3-22
[9]  
Fuduli A(2006)A new nonsmooth optimisation algorithm for minimum sum-of-squares clustering problems Eur. J. Oper. Res. 170 578-596
[10]  
Gaudioso M(1984)Optimization of upper semidifferentiable functions J. Optim. Theory Appl. 44 545-568