A Bregman-Frank-Wolfe Algorithm for DC Optimization Problems

Abstract

In this paper, we consider a class of difference-of-convex (DC) optimization problems, whose objective function is the difference of a relatively smooth convex function and a continuously convex function. We first propose a novel Bregman-Frank-Wolfe (BFW) algorithm for solving a DC optimization problem. In our algorithm, we mainly use the Bregman distance rather than the Euclidean distance in the selection of the step size. Moreover, we introduce an Adaptive BFW (ABFW) algorithm by adaptively selecting the step-size parameter $L_k$ that corresponds to the relatively smooth information of the objective function. The convergence analysis of the proposed algorithm can be established based on the triangle scaling property. We prove that all accumulation points of BFW and ABFW algorithms are stationary points. Then, we show that the convergence rates of the Frank-Wolfe (FW) gap of BFW and ABFW algorithms are both $ \mathcal {O} (k^{ \frac{1-\gamma }{\gamma }})$. Finally, some numerical experiments on non-convex quadratic inverse problems are conducted to demonstrate the effectiveness of our algorithms.

Keywords

Frank-Wolfe (FW) algorithm / Difference-of-convex (DC) optimization / Relatively smooth / Bregman distance / Adaptive step size / Triangle scaling property / 90C26 / 90C30 / 65K05

References

[1] Aivazian, G.V., Stonyakin, F.S., Pasechnyk, D.A., Alkousa, M.S., Raigorodsky, A.M., Baran, I.V.: Adaptive variant of the Frank-Wolfe algorithm for convex optimization problems. Program. Comput. Softw. 49(6), 493–504 (2023)

[2] Bashiri, M.A., Zhang, X.: Decomposition-invariant conditional gradient for general polytopes with line search. Adv. Neural Inf. Process. Syst. 30, 2690–2700 (2017)

[3] Bauschke, H.H., Bolte, J., Teboulle, M.: A descent lemma beyond Lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res. 42(2), 330–348 (2017)

[4] Benning, M., Betcke, M.M., Ehrhardt, M.J., Schnlieb, C.B.: Choose your path wisely: gradient descent in a Bregman distance framework. SIAM J. Imag. Sci. 14(2), 814–843 (2021)

[5] Bertero, M., Boccacci, P., Desiderà, G., Vicidomini, G.: Image deblurring with Poisson data: from cells to galaxies. Inverse Prob. 25(12), 123006 (2009)

[6] Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)

[7] Bialoń P. Some variants of projection methods for large nonlinear optimization problems. J. Telecommun. Inf. Technol., 2003, 3: 43-49

[8] Bolte, J., Sabach, S., Teboulle, M., Vaisbourd, Y.: First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM J. Optim. 28(3), 2131–2151 (2018)

[9] Bomze, I.M., Rinaldi, F., Zeffiro, D.: Frank-Wolfe and friends: a journey into projection-free first-order optimization methods. 4OR 19(3), 313–345 (2021)

[10] Bregman LM. The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys., 1967, 7(3): 200-217.

[11] Clarke, F.H.: Optimization and Nonsmooth Analysis. Society for Industrial and Applied Mathematics, Philadelphia (1990)

[12] Díaz Millán, R., Ferreira, O.P., Ugon, J.: Frank-Wolfe algorithm for DC optimization problem. arXiv: 2308.16444 (2023)

[13] Frank, M., Wolfe, P.: An algorithm for quadratic programming. Naval Res. Logist. Q. 3(1/2), 95–110 (1956)

[14] Freund, R.M., Grigas, P., Mazumder, R.: An extended Frank-Wolfe method with “in-face” directions, and its application to low-rank matrix completion. SIAM J. Optim. 27(1), 319–346 (2017)

[15] Garber D, Hazan E. A linearly convergent variant of the conditional gradient algorithm under strong convexity with application to online and stochastic optimization. SIAM J. Optim., 2016, 26(3): 1493-1528.

[16] Goldstein AA. Convex programming in Hilbert space. Bull. Am. Math. Soc., 1964, 70: 709-710.

[17] Guélat, J., Marcotte, P.: Some comments on Wolfe’s ‘away step’. Math. Program. 35(1), 110–119 (1986)

[18] Hanzely F, Richtarik P, Lin X. Accelerated Bregman proximal gradient methods for relatively smooth convex optimization. Comput. Optim. Appl., 2021, 79: 405-440.

[19] Harchaoui Z, Juditsky A, Nemirovski A. Conditional gradient algorithms for norm-regularized smooth convex optimization. Math. Program., 2015, 152(1): 75-112.

[20] He H, Zhang Z. A unified Bregman alternating minimization algorithm for generalized DC programs with application to imaging. J. Sci. Comput., 2024, 101(3): 76.

[21] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals. Springer, Berlin (1996)

[22] Jaggi, M.: Revisiting Frank-Wolfe: projection-free sparse convex optimization. In: International Conference on Machine Learning. PMLR, pp. 427–435 (2013)

[23] Khamaru K, Wainwright MJ. Convergence guarantees for a class of nonconvex and non-smooth optimization problems. J. Mach. Learn. Res., 2019, 20(154): 1-52

[24] Lacoste-Julien, S.: Convergence rate of Frank-Wolfe for non-convex objectives. arXiv: 1607.00345 (2016)

[25] Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of FW optimization variants. In: Cortes, C., Lee, D.D., Sugiyama, M., Garnett, R. (eds) NIPS’15: Proceedings of the 29th International Conference on Neural Information Processing Systems, vol. 1, pp. 496–504. MIT Press, Cambridge (2015)

[26] Lan G, Romeijn E, Zhou Z. Conditional gradient methods for convex optimization with general affine and nonlinear constraints. SIAM J. Optim., 2021, 31(3): 2307-2339.

[27] Lan G, Zhou Y. Conditional gradient sliding for convex optimization. SIAM J. Optim., 2016, 26(2): 1379-1409.

[28] Levitin ES, Polyak BT. Constrained minimization methods. USSR Comput. Math. Math. Phys., 1966, 6(5): 1-50.

[29] Lu H, Freund RM, Nesterov Y. Relatively smooth convex optimization by first-order methods, and applications. SIAM J. Optim., 2018, 28(1): 333-354.

[30] Oviedo H, Dalmau O, Lara H. Two adaptive scaled gradient projection methods for Stiefel manifold constrained optimization. Numer. Algorithms, 2021, 87: 1107-1127.

[31] Pan, C., Zhou, Y., He, H., Ling, C.: An inertial Bregman proximal DC algorithm for generalized DC programming with application to data completion. arXiv: 2409.05069 (2024)

[32] Pedregosa, F., Negiar, G., Askari, A., Jaggi, M.: Linearly convergent Frank-Wolfe with backtracking line-search. In: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics. PMLR, pp. 1–10 (2020)

[33] Pokutta, S.: The Frank-Wolfe algorithm: a short introduction. Jahresber. Deutsch. Math.-Verein. 126(1), 3–35 (2024)

[34] Takahashi S, Fukuda M, Tanaka M. New Bregman proximal type algorithms for solving DC optimization problems. Comput. Optim. Appl., 2022, 83(3): 893-931.

[35] Takahashi, S., Pokutta, S., Takeda, A.: Fast Frank-Wolfe algorithms with adaptive Bregman step-size for weakly convex functions. arXiv: 2504.04330 (2025)

[36] Takahashi S, Takeda A. Approximate Bregman proximal gradient algorithm for relatively smooth nonconvex optimization. Comput. Optim. Appl., 2025, 90(1): 227-256.

[37] Takahashi S, Tanaka M, Ikeda S. Blind deconvolution with non-smooth regularization via Bregman proximal DCAs. Signal Process., 2023, 202. ArticleID: 108734

[38] Takahashi, S., Tanaka, M., Ikeda, S.: Majorization-minimization Bregman proximal gradient algorithms for NMF with the Kullback-Leibler divergence. J. Optim. Theory Appl. 208(1), 1–34 (2026)

[39] Vyguzov, A.A., Stonyakin, F.S.: An adaptive variant of the Frank-Wolfe method for relative smooth convex optimization problems. Comput. Math. Math. Phys. 65(3), 591–602 (2025)

Funding

National Natural Science Foundation of China(11801131)

RIGHTS & PERMISSIONS

Shanghai University