# American Institute of Mathematical Sciences

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

 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.

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
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
 $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