American Institute of Mathematical Sciences

Advanced
doi: 10.3934/jdg.2021022
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Copositivity meets D. C. optimization

Abdellatif Moudafi 1,, and  Paul-Emile Mainge 2,

1. 

Aix-Marseille Université, Laboratoire d'Informatique et Systèmes, (LIS UMR 7020 CNRS/AMU/UTLN), Marseille, France
2. 

Université des Antilles, 97233 Martinique, F.W.I

Received  October 2020 Revised  April 2021 Early access July 2021

Based on a work by M. Dur and J.-B. Hiriart-Urruty[3], we consider the problem of whether a symmetric matrix is copositive formulated as a difference of convex functions problem. The convex nondifferentiable function in this d.c. decomposition being proximable, we then apply a proximal-gradient method to approximate the related stationary points. Whereas, in [3], the DCA algorithm was used.

Keywords: Copositive matrices, difference of convex functions, proximal-gradient algorithm, DC optimization, critical point.
Mathematics Subject Classification: Primary: 49J53, 65K10; Secondary: 49M37, 90C25.
Citation: Abdellatif Moudafi, Paul-Emile Mainge. Copositivity meets D. C. optimization. Journal of Dynamics & Games, doi: 10.3934/jdg.2021022
References:
[1]

F. J. Aragón Artacho, R. Campoy and P. T. Vuong, The Boosted DC Algorithm for linearly constrained DC programming, preprint, arXiv: 1908.01138. Google Scholar

[2]

P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), 1168-1200.  doi: 10.1137/050626090.  Google Scholar

[3]

M. Dür and J.-B. Hiriart-Urruty, Testing copositivity with the help of difference-of-convex optimization, Math. Program., 140 (2013), 31-43.  doi: 10.1007/s10107-012-0625-9.  Google Scholar

[4]

J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. I. Fundamentals, Grundlehren der Mathematischen Wissenschaften, 305, Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-02796-7.  Google Scholar

[5]

J.-B. Hiriart-Urruty and A. Seeger, A variational approach to copositive matrices, SIAM Rev., 52 (2010), 593-629.  doi: 10.1137/090750391.  Google Scholar

[6]

A. Moudafi and P.-E. Maingé, On the convergence of an approximate proximal method for DC functions, J. Comput. Math., 24 (2006), 475-480.   Google Scholar

[7]

J. C. O. Souza, P. R. Oliveira and A. Soubeyran, Global convergence of a proximal linearized algorithm for difference of convex functions, Optim. Lett., 10 (2016), 1529-1539.  doi: 10.1007/s11590-015-0969-1.  Google Scholar

[8]

W.-Y. Sun, R. J. B. Sampaio and M. A. B. Candido, Proximal point algorithm for minimization of DC function, J. Comput. Math., 21 (2003), 451-462.   Google Scholar

show all references

References:
[1]

F. J. Aragón Artacho, R. Campoy and P. T. Vuong, The Boosted DC Algorithm for linearly constrained DC programming, preprint, arXiv: 1908.01138. Google Scholar

[2]

P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., 4 (2005), 1168-1200.  doi: 10.1137/050626090.  Google Scholar

[3]

M. Dür and J.-B. Hiriart-Urruty, Testing copositivity with the help of difference-of-convex optimization, Math. Program., 140 (2013), 31-43.  doi: 10.1007/s10107-012-0625-9.  Google Scholar

[4]

J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms. I. Fundamentals, Grundlehren der Mathematischen Wissenschaften, 305, Springer-Verlag, Berlin, 1993. doi: 10.1007/978-3-662-02796-7.  Google Scholar

[5]

J.-B. Hiriart-Urruty and A. Seeger, A variational approach to copositive matrices, SIAM Rev., 52 (2010), 593-629.  doi: 10.1137/090750391.  Google Scholar

[6]

A. Moudafi and P.-E. Maingé, On the convergence of an approximate proximal method for DC functions, J. Comput. Math., 24 (2006), 475-480.   Google Scholar

[7]

J. C. O. Souza, P. R. Oliveira and A. Soubeyran, Global convergence of a proximal linearized algorithm for difference of convex functions, Optim. Lett., 10 (2016), 1529-1539.  doi: 10.1007/s11590-015-0969-1.  Google Scholar

[8]

W.-Y. Sun, R. J. B. Sampaio and M. A. B. Candido, Proximal point algorithm for minimization of DC function, J. Comput. Math., 21 (2003), 451-462.   Google Scholar

Table 1.  Results for the Horn-matrix when running the heuristic for different values of $ r $ and $ c_n $, along with 1,000 starting points
$ c_n=0.5 $ $ c_n=1 $
$ r $ average min max % failure aver. min max % failure
20 117 78 204 0 111 74 195 0
10 64 32 116 0 58 35 109 0
6 40 24 75 0 36 22 65 0
4 29 17 53 0 23 13 46 0
3.5 26 14 49 0 20 12 40 0
3.2365 25 16 43 0 19 11 35 0
$c_n=1.5$ $c_n=3$
$ r $ average min max % failure aver. min max % failure
20 110 74 192 0 108 72 188 0
10 56 33 103 0 54 25 101 0
6 34 20 64 0 32 17 60 0
4 21 13 42 0 19 13 37 0
3.5 18 8 34 0 16 9 31 0.15
3.2365 16 11 35 16 14 9 28 0.17
$c_n=5$ $c_n=40$
$ r $ average min max % failure aver. min max % failure
20 106 72 187 0 106 71 183 0
10 53 27 100 0 53 24 99 0
6 31 18 58 0 30 17 54 0
4 18 9 32 0 17 10 34 0
3.5 15 10 31 12 14 9 28 0.15
3.2365 13 9 8 12 12 8 28 0.12
Table Options

Download as excel

$ c_n=0.5 $ $ c_n=1 $
$ r $ average min max % failure aver. min max % failure
20 117 78 204 0 111 74 195 0
10 64 32 116 0 58 35 109 0
6 40 24 75 0 36 22 65 0
4 29 17 53 0 23 13 46 0
3.5 26 14 49 0 20 12 40 0
3.2365 25 16 43 0 19 11 35 0
$c_n=1.5$ $c_n=3$
$ r $ average min max % failure aver. min max % failure
20 110 74 192 0 108 72 188 0
10 56 33 103 0 54 25 101 0
6 34 20 64 0 32 17 60 0
4 21 13 42 0 19 13 37 0
3.5 18 8 34 0 16 9 31 0.15
3.2365 16 11 35 16 14 9 28 0.17
$c_n=5$ $c_n=40$
$ r $ average min max % failure aver. min max % failure
20 106 72 187 0 106 71 183 0
10 53 27 100 0 53 24 99 0
6 31 18 58 0 30 17 54 0
4 18 9 32 0 17 10 34 0
3.5 15 10 31 12 14 9 28 0.15
3.2365 13 9 8 12 12 8 28 0.12
[1]

Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[2]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control & Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[3]

Tim Hoheisel, Maxime Laborde, Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. Journal of Dynamics & Games, 2020, 7 (1) : 79-96. doi: 10.3934/jdg.2020005
[4]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021028
[5]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077
[6]

Zhongliang Deng, Enwen Hu. Error minimization with global optimization for difference of convex functions. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1027-1033. doi: 10.3934/dcdss.2019070
[7]

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027
[8]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743
[9]

Gang Li, Lipu Zhang, Zhe Liu. The stable duality of DC programs for composite convex functions. Journal of Industrial & Management Optimization, 2017, 13 (1) : 63-79. doi: 10.3934/jimo.2016004
[10]

Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381
[11]

Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[12]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial & Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[13]

Yuying Zhou, Gang Li. The Toland-Fenchel-Lagrange duality of DC programs for composite convex functions. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 9-23. doi: 10.3934/naco.2014.4.9
[14]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[15]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891
[16]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79
[17]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial & Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[18]

Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial & Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181
[19]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[20]

Gang Li, Xiaoqi Yang, Yuying Zhou. Stable strong and total parametrized dualities for DC optimization problems in locally convex spaces. Journal of Industrial & Management Optimization, 2013, 9 (3) : 671-687. doi: 10.3934/jimo.2013.9.671

 Impact Factor: 

Tools

Article outline

Figures and Tables

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences