Copositivity meets D. C. optimization

Abdellatif Moudafi; Paul-Emile Mainge

doi:10.3934/jdg.2021022

Article Contents

2022, Volume 9, Issue 1: 27-32. Doi: 10.3934/jdg.2021022

This issue Previous Article Zero-sum games for pure jump processes with risk-sensitive discounted cost criteria Next Article Explaining the definition of wholesale access prices in the Portuguese telecommunications industry

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

Published: January 2022

Abstract / Introduction Full Text(HTML) Figure(0) / Table(1) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 49J53, 65K10; Secondary: 49M37, 90C25.

Citation:

Full Text(HTML)

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.