Algorithms for Difference-of-Convex Programs Based on Difference-of-Moreau-Envelopes Smoothing

References

• Ahmadi AA, Hall G (2018) DC decomposition of nonconvex polynomials with algebraic techniques. Math. Programming 169(1):69–94.Google Scholar
• Alvarado A, Scutari G, Pang JS (2014) A new decomposition method for multiuser DC-programming and its applications. IEEE Trans. Signal Processing 62(11):2984–2998.Google Scholar
• An NT, Nam NM (2017) Convergence analysis of a proximal point algorithm for minimizing differences of functions. Optimization 66(1):129–147.Google Scholar
• An LTH, Tao PD (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133(1):23–46.Google Scholar
• Artacho FJA, Fleming RM, Vuong PT (2018) Accelerating the DC algorithm for smooth functions. Math. Programming 169(1):95–118.Google Scholar
• Aybat NS, Iyengar G (2013) An augmented Lagrangian method for conic convex programming. Preprint, submitted February 26, https://arxiv.org/abs/1302.6322.Google Scholar
• Banert S, Bo RI (2019) A general double-proximal gradient algorithm for DC programming. Math. Programming 178(1–2):301–326.Google Scholar
• Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Google Scholar
• Bertsekas DP (2014) Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York).Google Scholar
• Bolte J, Sabach S, Teboulle M (2014) Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programming 146(1–2):459–494.Google Scholar
• Byrd RH, Nocedal J, Schnabel RB (1994) Representations of quasi-Newton matrices and their use in limited memory methods. Math. Programming 63(1):129–156.Google Scholar
• Cao S, Huo X, Pang JS (2022) A unifying framework of high-dimensional sparse estimation with difference-of-convex (DC) regularizations. Statist. Sci. 37(3):411–424.Google Scholar
• Chen X (2012) Smoothing methods for nonsmooth, nonconvex minimization. Math. Programming 134(1):71–99.Google Scholar
• Chen C, Mangasarian OL (1996) A class of smoothing functions for nonlinear and mixed complementarity problems. Comput. Optim. Appl. 5(2):97–138.Google Scholar
• Chen C, Zhang J, Shen L, Zhao P, Luo Z (2021) Communication efficient primal-dual algorithm for nonconvex nonsmooth distributed optimization. Banerjee A, Fukumizu K, eds. Proc. Internat. Conf. on Artificial Intelligence and Statist., vol. 130, Proceedings of Machine Learning Research (PMLR), 1594–1602.Google Scholar
• Davis D, Drusvyatskiy D (2022) Stochastic subgradient method converges at the rate O(k−1/4) on weakly convex functions. Preprint, submitted February 19, https://arxiv.org/abs/1802.02988.Google Scholar
• de Oliveira W (2019) Proximal bundle methods for nonsmooth DC programming. J. Global Optim. 75(2):523–563.Google Scholar
• de Oliveira W (2020) Sequential difference-of-convex programming. J. Optim. Theory Appl. 186(3):936–959.Google Scholar
• Drusvyatskiy D (2017) The proximal point method revisited. Preprint, submitted December 17, https://arxiv.org/abs/1712.06038.Google Scholar
• Ellaia R (1984) Contribution à l’analyse et l’optimisation de différence de fonctions convexes. PhD thesis, Université Paul Sabatier, Toulouse, France.Google Scholar
• Hajinezhad D, Hong M (2019) Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization. Math. Programming 176(1–2):207–245.Google Scholar
• Hestenes MR (1969) Multiplier and gradient methods. J. Optim. Theory Appl. 4(5):303–320.Google Scholar
• Hiriart-Urruty JB (1985) Generalized differentiability/duality and optimization for problems dealing with differences of convex functions. Convexity and Duality in Optimization (Springer, Berlin), 37–70.Google Scholar
• Hiriart-Urruty JB (1991) How to regularize a difference of convex functions. J. Math. Anal. Appl. 162(1):196–209.Google Scholar
• Hong M (2016) Decomposing linearly constrained nonconvex problems by a proximal primal dual approach: Algorithms, convergence, and applications. Preprint, submitted April 2, https://arxiv.org/abs/1604.00543.Google Scholar
• Kurdyka K (1998) On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier (Grenoble) 48:769–783.Google Scholar
• Lan G, Monteiro R (2016) Iteration-complexity of first-order augmented Lagrangian methods for convex programming. Math. Programming 155(1):511–547.Google Scholar
• Le Thi HA, Tao PD (1997) Solving a class of linearly constrained indefinite quadratic problems by DC algorithms. J. Global Optim. 11(3):253–285.Google Scholar
• Le Thi HA, Dinh TP, Van Ngai H (2012) Exact penalty and error bounds in DC programming. J. Global Optim. 52(3):509–535.Google Scholar
• Li F, Qu Z (2021) An inexact proximal augmented Lagrangian framework with arbitrary linearly convergent inner solver for composite convex optimization. Math. Programming Comput. 13(3):583–644.Google Scholar
• Li Z, Xu Y (2021) Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective. INFORMS J. Optim. 3(4):373–397.Google Scholar
• Li Z, Chen PY, Liu S, Lu S, Xu Y (2021) Rate-improved inexact augmented Lagrangian method for constrained nonconvex optimization. Banerjee A, Fukumizu K, eds. Proc. Internat. Conf. on Artificial Intelligence and Statist., vol. 130, Proceedings of Machine Learning Research (PMLR), 2170–2178.Google Scholar
• Liu Yf, Liu X, Ma S (2019) On the nonergodic convergence rate of an inexact augmented Lagrangian framework for composite convex programming. Math. Oper. Res. 44(2):632–650.Link, Google Scholar
• Lojasiewicz S (1963) Une propriété topologique des sous-ensembles analytiques réels. Equations Dérivées Partielles 117:87–89.Google Scholar
• Lu Z (2014) Iterative reweighted minimization methods for ℓp regularized unconstrained nonlinear programming. Math. Programming 147(1):277–307.Google Scholar
• Lu Z, Zhou Z (2018) Iteration-complexity of first-order augmented Lagrangian methods for convex conic programming. Preprint, submitted March 27, https://arxiv.org/abs/1803.09941.Google Scholar
• Lu Z, Zhou Z (2019) Nonmonotone enhanced proximal DC algorithms for a class of structured nonsmooth DC programming. SIAM J. Optim. 29(4):2725–2752.Google Scholar
• Lu Z, Zhou Z, Sun Z (2019) Enhanced proximal DC algorithms with extrapolation for a class of structured nonsmooth DC minimization. Math. Programming 176(1–2):369–401.Google Scholar
• Melo JG, Monteiro RDC (2020) Iteration-complexity of an inner accelerated inexact proximal augmented Lagrangian method based on the classical Lagrangian function and a full Lagrange multiplier update. Preprint, submitted August 2, https://arxiv.org/abs/2008.00562.Google Scholar
• Melo JG, Monteiro RDC, Wang H (2020) Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems. Preprint, submitted June 14, https://arxiv.org/abs/2006.08048.Google Scholar
• Melzer D (1986) On the expressibility of piecewise-linear continuous functions as the difference of two piecewise-linear convex functions. Quasidifferential Calculus (Springer, Berlin), 118–134.Google Scholar
• Nesterov YE (1983) A method for solving the convex programming problem with convergence rate O(1/k2)). Doklady Akademii Nauk SSSR 269:543–547.Google Scholar
• Pang JS, Razaviyayn M, Alvarado A (2017) Computing b-stationary points of nonsmooth DC programs. Math. Oper. Res. 42(1):95–118.Link, Google Scholar
• Powell MJ (1969) A method for nonlinear constraints in minimization problems. Fletcher R, ed. Optimization (Academic Press, Cambridge, MA), 283–298.Google Scholar
• Rockafellar RT (1970) Convex Analysis (Princeton University Press, Princeton, NJ).Google Scholar
• Rockafellar RT (1973) The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12(6):555–562.Google Scholar
• Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97–116.Link, Google Scholar
• Rockafellar RT, Wets RJB (2009) Variational Analysis, vol. 317 (Springer Science & Business Media, Boston).Google Scholar
• Sahin MF, Eftekhari A, Alacaoglu A, Latorre F, Cevher V (2019) An inexact augmented Lagrangian framework for nonconvex optimization with nonlinear constraints. Wallach H, Larochelle H, Beygelzimer A, d’Alché-Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Inc., Red Hook, NY), 13943–13955.Google Scholar
• Souza JCO, Oliveira PR, Soubeyran A (2016) Global convergence of a proximal linearized algorithm for difference of convex functions. Optim. Lett. 10(7):1529–1539.Google Scholar
• Sun Wy, Sampaio RJ, Candido M (2003) Proximal point algorithm for minimization of DC function. J. Comput. Math. 21(4):451–462.Google Scholar
• Tao PD, An LTH (1997) Convex analysis approach to DC programming: Theory, algorithms and applications. Acta Math. Vietnam 22(1):289–355.Google Scholar
• Tao PD, An LTH (1998) A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8(2):476–505.Google Scholar
• Tao M, Dong H (2018) On the linear convergence of difference-of-convex algorithms for nonsmooth DC programming. Optim. Online.Google Scholar
• Themelis A, Hermans B, Patrinos P (2020) A new envelope function for nonsmooth DC optimization. Proc. 59th IEEE Conf. on Decision and Control (IEEE, New York), 4697–4702.Google Scholar
• Tuy H (2010) Convex Analysis and Global Optimization, 2nd ed. (Springer, Berlin).Google Scholar
• Wen B, Chen X, Pong TK (2018) A proximal difference-of-convex algorithm with extrapolation. Comput. Optim. Appl. 69(2):297–324.Google Scholar
• Xu Y (2021) Iteration complexity of inexact augmented Lagrangian methods for constrained convex programming. Math. Programming 185:199–244.Google Scholar
• Yin P, Lou Y, He Q, Xin J (2015) Minimization of 1-2 for compressed sensing. SIAM J. Sci. Comput. 37(1):A536–A563.Google Scholar
• Zeng J, Yin W, Zhou DX (2022) Moreau envelope augmented Lagrangian method for nonconvex optimization with linear constraints. J. Sci. Comput. 91(2):1–36.Google Scholar
• Zhang J, Luo ZQ (2020) A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization. SIAM J. Optim. 30(3):2272–2302.Google Scholar
• Zhang J, Luo Z-Q (2022) A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization. SIAM J. Optim. 32(3):2319–2346.Google Scholar
• Zhang J, Xiao P, Sun R, Luo Z (2020) A single-loop smoothed gradient descent-ascent algorithm for nonconvex-concave min-max problems. Larochelle H, Ranzato M, Hadsell R, Balcan MF, Lin H, eds. Advances in Neural Information Processing Systems, vol. 33 (Curran Associates, Inc., Red Hook, NY), 7377–7389.Google Scholar