×

Accelerating the DC algorithm for smooth functions. (English) Zbl 1461.65118

The authors introduce the concept of DC-functions as functions, which can be expressed as the difference of two convex functions. They consider minimization problems, the objective function of which is a DC-function. Two new algorithms for solving such problems are proposed. The algorithms accelerate the convergence of the algorithms under an additional condition that the objective function has the so-called Łojasiewicz property. The convergence of the proposed algorithms is proved and the corresponding rate of convergence is analyzed. The methods are applied to problems, which occur in the study of biochemical reaction networks. Numerical tests show that the algorithms are faster than the known methods in both computational time and the number of iterations.

MSC:

65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization
92C42 Systems biology, networks
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Absil, PA; Mahony, R; Andrews, B, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim., 16, 531-547, (2005) · Zbl 1092.90036
[2] Artacho Aragón, FJ; Fleming, RMT, Globally convergent algorithms for finding zeros of duplomonotone mappings, Optim. Lett., 9, 569-584, (2015) · Zbl 1339.90311
[3] Attouch, H; Bolte, J, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., 116, 5-16, (2009) · Zbl 1165.90018
[4] Bolte, J; Daniilidis, A; Lewis, A, The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim., 17, 1205-1223, (2007) · Zbl 1129.26012
[5] Bolte, J; Sabach, S; Teboulle, M, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 459-494, (2013) · Zbl 1297.90125
[6] Collobert, R., Sinz, F., Weston, J., Bottou, L.: Trading convexity for scalability. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 201-208. ACM (2006)
[7] Fukushima, M; Mine, H, A generalized proximal point algorithm for certain non-convex minimization problems, Int. J. Syst. Sci., 12, 989-1000, (1981) · Zbl 0467.65028
[8] Gevorgyan, A; Poolman, MG; Fell, DA, Detection of stoichiometric inconsistencies in biomolecular models, Bioinformatics, 24, 2245-2251, (2008)
[9] Huang, Y; Liu, H; Zhou, S, A Barzilai-Borwein type method for stochastic linear complementarity problems, Numer. Algorithms, 67, 477-489, (2014) · Zbl 1327.90312
[10] Thi, HA; Pham Dinh, T, The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems, Ann. Oper. Res., 133, 23-46, (2005) · Zbl 1116.90122
[11] Thi, HA; Pham Dinh, T, On solving linear complementarity problems by DC programming and DCA, Comput. Optim. Appl., 50, 507-524, (2011) · Zbl 1237.90234
[12] Thi, HA; Pham Dinh, T; Muu, LD, Numerical solution for optimization over the efficient set by D.C. optimization algorithms, Oper. Res. Lett., 19, 117-128, (1996) · Zbl 0871.90074
[13] Le Thi, H.A., Huynh, V.N., Pham Dinh, T.: Convergence analysis of DC algorithm for DC programming with subanalytic data. Ann. Oper. Res. Technical Report, LMI, INSA-Rouen (2009)
[14] Lee, JD; Sun, Y; Saunders, MA, Proximal Newton type methods for minimizing composite functions, SIAM J. Optim., 24, 1420-1443, (2014) · Zbl 1306.65213
[15] Li, G; Pong, TK, Douglas-Rachford splitting for nonconvex optimization with application to nonconvex feasibility problems, Math. Progr., 159, 371-401, (2016) · Zbl 1346.90584
[16] Łojasiewicz, S.: Ensembles semi-analytiques. Institut des Hautes Etudes Scientifiques, Bures-sur-Yvette (Seine-et-Oise), France (1965) · Zbl 0241.32005
[17] Mine, H; Fukushima, M, A minimization method for the sum of a convex function and a continuously differentiable function, J. Optim. Theory Appl., 33, 9-23, (1981) · Zbl 0422.90070
[18] Moudafi, A; Mainge, P, On the convergence of an approximate proximal method for DC functions, J. Comput. Math., 24, 475-480, (2006) · Zbl 1104.65058
[19] Nesterov, Y, Gradient methods for minimizing composite functions, Math. Program., 140, 125-161, (2013) · Zbl 1287.90067
[20] Nocedal, J., Wright, S.J.: Numerical optimization. In: Mikosch, T.V., Resnick, S.I., Robinson, S.M. (eds.) Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006) · Zbl 1104.65059
[21] Parks, H.R., Krantz, S.G.: A Primer of Real Analytic Functions. Birkhäuser, Basel (1992) · Zbl 0767.26001
[22] Pham Dinh, T; Thi, HA, A DC optimization algorithm for solving the trust-region subproblem, SIAM J. Optim., 8, 476-505, (1998) · Zbl 0913.65054
[23] Pham Dinh, T; Souad, EB; Hiriart-Urruty, J-B (ed.), Algorithms for solving a class of nonconvex optimization problems. methods of subgradients, 249-271, (1986), Amsterdam
[24] Schnörr, C., Schüle, T., Weber, S.: Variational reconstruction with DC-programming. In: Herman, G.T., Kuba, A. (eds.) Advances in Discrete Tomography and its Applications, pp. 227-243. Springer, Berlin (2007) · Zbl 1237.90234
[25] Thiele, I; etal., A community-driven global reconstruction of human metabolism, Nat. Biotechnol., 31, 419-425, (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.