American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Explaining the definition of wholesale access prices in the Portuguese telecommunications industry
  • JDG Home
  • This Issue
  • Next Article
    Zero-sum games for pure jump processes with risk-sensitive discounted cost criteria
January  2022, 9(1): 27-32. doi: 10.3934/jdg.2021022

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 Published  January 2022 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 and Games, 2022, 9 (1) : 27-32. 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.

[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.

[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.

[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.

[5]

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

[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. 

[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.

[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. 

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.

[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.

[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.

[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.

[5]

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

[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. 

[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.

[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. 

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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243
[13]

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

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

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

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control and 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 and 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 and 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 and 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 and 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 © 2022 American Institute of Mathematical Sciences | Privacy Policy