Sesión Análisis Numérico y OptimizaciónA two-direction Frank-Wolfe method for multiobjective optimization on polytopes
Jorge Luis Gutierrez Santos
Universidad Federal de Santa Catarina, Brasil - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Constrained multiobjective optimization problems consist in minimizing simultaneously multiple objective functions over a feasible set \(\mathcal{M} \subset \mathbb{R}^n\). Since in general these objectives are conflicting, they do not share the same minimizer and another notion of optimality is considered: a point in \(\mathcal{M}\) is called Pareto optimal if there is no other point in \(\mathcal{M}\) which improves at least one objective without increasing another.
In this work we consider \(\mathcal{M}\) as a polytope defined by the convex hull of a finite set of points (atoms) and assume the objective functions are convex and continuously differentiable. A well known method for this setting is the classical Multiobjective Frank-Wolfe (M-FW) method which achieves a sublinear convergence rate [1, 3]. One of its variants, called Away-Step Frank-Wolfe (M-ASFW) introduces an away search direction and achieves linear convergence [2] in case the objectives are strongly convex.
We propose a new Two-Direction Multiobjective Frank-Wolfe (TD-M-FW) method which at each iteration chooses between two possible search directions: the classical Frank-Wolfe direction and an alternative one, defined as the difference between two points; one in \(\mathcal{M}\) and another in the convex hull of the current active set of atoms. The choice is for the direction that yields the best improvement according to a suitable criterion. We show that this method generalizes both M-FW and M-ASFW.
Under strong convexity of the objectives and an algorithmic assumption on the step sizes, we show that the sequence generated by the resulting algorithm converges to a Pareto optimal point, and that a merit function introduced in converges \(Q\)-linearly to zero. This analysis relies on the restricted width, a geometric property of polytopes.
Finally, we propose a specific alternative direction inspired by the pairwise Frank–Wolfe direction from scalar optimization. This strategy allows us to remove the assumption on the step sizes while preserving convergence: the sequence still converges to a Pareto optimal point and the merit function converges \(R\)-linearly to zero.
Trabajo en conjunto con: Douglas Soares Gonçalves (Universidade Federal de Santa Catarina, Brasil).
Referencias
[1] Assunção, P. B., Ferreira, O. P., and Prudente, L. F. (2021). Conditional gradient method for multiobjective optimization. Computational Optimization and Applications, 78(3):741–768.
[2] Gonçalves, D. S., Gonçalves, M. L. N., and Melo, J. G. (2024). An away-step Frank-Wolfe algorithm for constrained multiobjective optimization. Computational Optimization and Applications, 88(3):759–781.
[3] Gonçalves, D. S., Gonçalves, M. L. N., and Melo, J. G. (2025). Improved convergence rates for the multiobjective Frank-Wolfe method. Journal of Optimization Theory and Applications, 205(2):20.
[4] Tanabe, H., Fukuda, E. H., and Yamashita, N. (2024). New merit functions for multiobjective optimization and their properties. Optimization, 73(13):3821–3858.