×

Conditional gradient method for multiobjective optimization. (English) Zbl 1469.90127

Summary: We analyze the conditional gradient method, also known as Frank-Wolfe method, for constrained multiobjective optimization. The constraint set is assumed to be convex and compact, and the objectives functions are assumed to be continuously differentiable. The method is considered with different strategies for obtaining the step sizes. Asymptotic convergence properties and iteration-complexity bounds with and without convexity assumptions on the objective functions are stablished. Numerical experiments are provided to illustrate the effectiveness of the method and certify the obtained theoretical results.

MSC:

90C29 Multi-objective and goal programming
90C52 Methods of reduced gradient type

Software:

minpack; ALGENCAN; DFMO; NBI
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Ansary, MA; Panda, G., A modified quasi-Newton method for vector optimization problem, Optimization, 64, 11, 2289-2306 (2015) · Zbl 1327.90275
[2] Beck, A., Introduction to Nonlinear Optimization (2014), Philadelphia, PA: Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 1320.90001
[3] Beck, A., First-Order Methods in Optimization (2017), Philadelphia, PA: Society for Industrial and Applied Mathematics, Philadelphia, PA · Zbl 1384.65033
[4] Beck, A.; Teboulle, M., A conditional gradient method with linear rate of convergence for solving convex linear systems, Math. Methods Oper. Res., 59, 2, 235-247 (2004) · Zbl 1138.90440
[5] Bello Cruz, JY, A subgradient method for vector optimization problems, SIAM J. Optim., 23, 4, 2169-2182 (2013) · Zbl 1295.90065
[6] Bello Cruz, JY; Bouza Allende, G., A steepest descent-like method for variable order vector optimization problems, J. Optim. Theory Appl., 162, 2, 371-391 (2014) · Zbl 1315.90042
[7] Bento, GC; Cruz Neto, JX; López, G.; Soubeyran, A.; Souza, JCO, The proximal point method for locally Lipschitz functions in multiobjective optimization with application to the compromise problem, SIAM J. Optim., 28, 2, 1104-1120 (2018) · Zbl 1388.49013
[8] Birgin, EG; Martnez, JM, Practical Augmented Lagrangian Methods for Constrained Optimization (2014), Philadelphia, PA: Society for Industrial and Applied Mathematics, Philadelphia, PA
[9] Boyd, N.; Schiebinger, G.; Recht, B., The alternating descent conditional gradient method for sparse inverse problems, SIAM J. Optim., 27, 2, 616-639 (2017) · Zbl 1365.90195
[10] Carrizo, GA; Lotito, PA; Maciel, MC, Trust region globalization strategy for the nonconvex unconstrained multiobjective optimization problem, Math. Program., 159, 1-2, 339-369 (2016) · Zbl 1345.90081
[11] Custdio, AL; Madeira, JFA; Vaz, AIF; Vicente, LN, Direct multisearch for multiobjective optimization, SIAM J. Optim., 21, 3, 1109-1140 (2011) · Zbl 1230.90167
[12] Das, I.; Dennis, JE, Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems, SIAM J. Optim., 8, 3, 631-657 (1998) · Zbl 0911.90287
[13] Dennis, JE; Schnabel, RB, Numerical Methods for Unconstrained Optimization and Nonlinear Equations (1996), Philadelphia: Society for Industrial and Applied Mathematics, Philadelphia · Zbl 0847.65038
[14] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 2, 201-213 (2002) · Zbl 1049.90004
[15] Fliege, J.; Graña Drummond, LM; Svaiter, BF, Newton’s method for multiobjective optimization, SIAM J. Optim., 20, 2, 602-626 (2009) · Zbl 1195.90078
[16] Fliege, J.; Svaiter, BF, Steepest descent methods for multicriteria optimization, Math. Methods Oper. Res., 51, 3, 479-494 (2000) · Zbl 1054.90067
[17] Fliege, J.; Vaz, AIF, A method for constrained multiobjective optimization based on SQP techniques, SIAM J. Optim., 26, 4, 2091-2119 (2016) · Zbl 1349.90735
[18] Fliege, J.; Vaz, AIF; Vicente, LN, Complexity of gradient descent for multiobjective optimization, Optim. Method. Softw., 34, 5, 949-959 (2019) · Zbl 1429.90067
[19] Frank, M.; Wolfe, P., An algorithm for quadratic programming, Naval Res. Logist. Quart., 3, 95-110 (1956)
[20] Freund, RM; 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) · Zbl 1357.90115
[21] Fukuda, EH; Graña Drummond, LM, On the convergence of the projected gradient method for vector optimization, Optimization, 60, 8-9, 1009-1021 (2011) · Zbl 1231.90331
[22] Fukuda, EH; Graña Drummond, LM, Inexact projected gradient method for vector optimization, Comput. Optim. Appl., 54, 3, 473-493 (2013) · Zbl 1295.90069
[23] Fukuda, EH; Graña Drummond, LM, A survey on multiobjective descent methods, Pesq. Oper., 34, 585-620 (2014)
[24] Garber, D., Hazan, E.: Faster rates for the Frank-Wolfe method over strongly-convex sets. In: 32nd International Conference on Machine Learning, ICML 2015, pp. 1-12 (2015)
[25] Geoffrion, AM, Proper efficiency and the theory of vector maximization, J. Math. Anal. Appl., 22, 3, 618-630 (1968) · Zbl 0181.22806
[26] Ghadimi, S., Conditional gradient type methods for composite nonlinear and stochastic optimization, Math. Program., 173, 1-2, 431-464 (2019) · Zbl 1410.90150
[27] Gonçalves, MLN; Prudente, LF, On the extension of the Hager-Zhang conjugate gradient method for vector optimization, Comput. Optim. Appl., 76, 3, 889-916 (2020) · Zbl 1446.90142
[28] Graña Drummond, LM; Iusem, AN, A projected gradient method for vector optimization problems, Comput. Optim. Appl., 28, 1, 5-29 (2004) · Zbl 1056.90126
[29] Graña Drummond, LM; Svaiter, BF, A steepest descent method for vector optimization, J. Comput. Appl. Math., 175, 2, 395-414 (2005) · Zbl 1058.90060
[30] Grapiglia, GN; Sachs, EW, On the worst-case evaluation complexity of non-monotone line search algorithms, Comput. Optim. Appl., 68, 3, 555-577 (2017) · Zbl 1388.90111
[31] Harchaoui, Z.; Juditsky, A.; Nemirovski, A., Conditional gradient algorithms for norm-regularized smooth. Convex optimization, Math. Program., 152, 1-2, 75-112 (2015) · Zbl 1336.90069
[32] Hillermeier, C., Generalized homotopy approach to multiobjective optimization, J. Optim. Theory Appl., 110, 3, 557-583 (2001) · Zbl 1064.90041
[33] Huband, S.; Hingston, P.; Barone, L.; While, L., A review of multiobjective test problems and a scalable test problem toolkit, IEEE Trans. Evol. Comput., 10, 5, 477-506 (2006) · Zbl 1109.68603
[34] Jaggi, M.: Revisiting Frank-Wolfe: projection-free sparse convex optimization. In: Proceedings of the 30th International Conference on International Conference on Machine Learning, ICML’13, vol. 28, pp I-427-I-435 (2013)
[35] Jin, Y., Olhofer, M., Sendhoff, B.: Dynamic weighted aggregation for evolutionary multi-objective optimization: why does it work and how? In: Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation, GECCO01, San Francisco, CA, USA, pp. 1042-1049. Morgan Kaufmann Publishers Inc (2001)
[36] Kim, I.; de Weck, O., Adaptive weighted-sum method for bi-objective optimization: Pareto front generation, Struct. Multidiscip. Optim., 29, 2, 149-158 (2005)
[37] Konnov, IV, Simplified versions of the conditional gradient method, Optimization, 67, 12, 2275-2290 (2018) · Zbl 1416.90033
[38] Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank-Wolfe optimization variants (2015) arXiv e-prints, arXiv:1511.05932
[39] Lan, G.: The complexity of large-scale convex programming under a linear optimization oracle (2013) arXiv e-prints, arXiv:1309.5550
[40] Lan, G.; Zhou, Y., Conditional gradient sliding for convex optimization, SIAM J. Optim., 26, 2, 1379-1409 (2016) · Zbl 1342.90132
[41] Laumanns, M.; Thiele, L.; Deb, K.; Zitzler, E., Combining convergence and diversity in evolutionary multiobjective optimization, Evol. Comput., 10, 3, 263-282 (2002)
[42] Levitin, E.; Polyak, B., Constrained minimization methods, USSR Comput. Math. Math. Phys., 6, 5, 1-50 (1966) · Zbl 0184.38902
[43] Liuzzi, G.; Lucidi, S.; Rinaldi, F., A derivative-free approach to constrained multiobjective nonsmooth optimization, SIAM J. Optim., 26, 4, 2744-2774 (2016) · Zbl 1358.90133
[44] Lovison, A., Singular continuation: generating piecewise linear approximations to Pareto sets via global analysis, SIAM J. Optim., 21, 2, 463-490 (2011) · Zbl 1226.90094
[45] Lucambio Pérez, LR; Prudente, LF, Nonlinear conjugate gradient methods for vector optimization, SIAM J. Optim., 28, 3, 2690-2720 (2018) · Zbl 1401.90210
[46] Lucambio Pérez, LR; Prudente, LF, A Wolfe line search algorithm for vector optimization, ACM Trans. Math. Softw., 45, 4, 37:1-37:23 (2019) · Zbl 07193386
[47] Luss, R.; Teboulle, M., Conditional gradient algorithms for rank-one matrix approximations with a sparsity constraint, SIAM Rev., 55, 1, 65-98 (2013) · Zbl 1263.90094
[48] Miglierina, E.; Molho, E.; Recchioni, M., Box-constrained multi-objective optimization: a gradient-like method without a priori scalarization, Eu. J. Oper. Res., 188, 3, 662-682 (2008) · Zbl 1144.90482
[49] Mita, K.; Fukuda, EH; Yamashita, N., Nonmonotone line searches for unconstrained multiobjective optimization problems, J. Glob. Optim., 75, 1, 63-90 (2019) · Zbl 1428.90155
[50] Montonen, O.; Karmitsa, N.; Mäkelä, MM, Multiple subgradient descent bundle method for convex nonsmooth multiobjective optimization, Optimization, 67, 1, 139-158 (2018) · Zbl 1398.90158
[51] Moré, JJ; Garbow, BS; Hillstrom, KE, Testing unconstrained optimization software, ACM Trans. Math. Softw., 7, 1, 17-41 (1981) · Zbl 0454.65049
[52] Morovati, V.; Pourkarimi, L.; Basirzadeh, H., Barzilai and Borwein’s method for multiobjective optimization problems, Numer. Algorithms, 72, 3, 539-604 (2016) · Zbl 1347.65108
[53] Polyak, BT, Introduction to Optimization. Translations Series in Mathematics and Engineering (1987), New York: Optimization Software, New York
[54] Preuss, M., Naujoks, B., Rudolph, G.: Pareto set and EMOA behavior for simple multimodal multiobjective functions. In: Runarsson, T. P., Beyer, H.-G., Burke, E., Merelo-Guervós, J. J., Whitley, L. D., Yao, X (Eds) Parallel Problem Solving from Nature—PPSN IX, pp. 513-522. Springer, Berlin (2006)
[55] Schütze, O.; Laumanns, M.; Coello Coello, CA; Dellnitz, M.; Talbi, E-G, Convergence of stochastic search algorithms to finite size Pareto set approximations, J. Glob. Optim., 41, 4, 559-577 (2008) · Zbl 1152.90598
[56] Stadler, W.; Dauer, J., Multicriteria optimization in engineering: a tutorial and survey, Progr. Astronaut. Aero., 150, 209-209 (1993)
[57] Tabatabaei, M.; Lovison, A.; Tan, M.; Hartikainen, M.; Miettinen, K., ANOVA-MOP: ANOVA decomposition for multiobjective optimization, SIAM J. Optim., 28, 4, 3260-3289 (2018) · Zbl 1409.90178
[58] Thomann, J.; Eichfelder, G., A trust-region algorithm for heterogeneous multiobjective optimization, SIAM J. Optim., 29, 2, 1017-1047 (2019) · Zbl 1411.90311
[59] Toint, P. L.: Test problems for partially separable optimization and results for the routine pspmin. The University of Namur, Department of Mathematics, Belgium, technical report (1983)
[60] Zitzler, E.; Deb, K.; Thiele, L., Comparison of multiobjective evolutionary algorithms: empirical results, Evol. Comput., 8, 2, 173-195 (2000)
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.