C. R. Acad. Sci. Paris, Ser.

I 350 (2012) 313–318

Contents lists available at SciVerse ScienceDirect

C. R. Acad. Sci. Paris, Ser. I

www.sciencedirect.com

Numerical Analysis/Calculus of Variations

Multiple-gradient descent algorithm (MGDA) for multiobjective

optimization

Algorithme de descente à gradients multiples pour l’optimisation multiobjectif

Jean-Antoine Désidéri
INRIA, Centre de Sophia Antipolis Méditerranée, 2004, route des Lucioles, BP 93, 06902 Sophia Antipolis cedex, France

a r t i c l e i n f o a b s t r a c t

Article history: One considers the context of the concurrent optimization of several criteria J i (Y ) (i =
Received 6 March 2012 1, . . . , n), supposed to be smooth functions of the design vector Y ∈ R N (n  N). An
Accepted 20 March 2012 original constructive solution is given to the problem of identifying a descent direction
Available online 29 March 2012
common to all criteria when the current design-point Y 0 is not Pareto-optimal. This leads
Presented by Olivier Pironneau us to generalize the classical steepest-descent method to the multiobjective context by
utilizing this direction for the descent. The algorithm is then proved to converge to a
Pareto-stationary design-point.
© 2012 Académie des sciences. Published by Elsevier Masson SAS. All rights reserved.

r é s u m é

On se place dans le contexte de l’optimisation concourante de plusieurs critères J i (Y ) (i =

1, . . . , n), fonctions régulières du vecteur de conception Y ∈ R N (n  N). On donne une
solution constructive originale au problème de l’identification d’une direction de descente
commune à tous les critères en un point Y 0 non optimal au sens de Pareto. On est conduit
à généraliser la méthode classique du gradient au contexte multiobjectif en utilisant cette
direction pour la descente. On prouve que l’algorithme converge alors vers un point de
conception Pareto-stationnaire.
© 2012 Académie des sciences. Published by Elsevier Masson SAS. All rights reserved.

Version française abrégée

On se focalise sur l’optimisation concourante de n critères { J i (Y )} supposés fonctions régulières du vecteur de conception
Y ∈ Ω ⊂ R N (Ω : domaine admissible ; J i ∈ C 1 (Ω) ; i = 1, . . . , n  N).
On considère un point Y 0 au centre d’une boule ouverte de Ω . Ayant d’abord posé u i = ∇ J i (Y 0 ) (gradients de critères),
on propose de définir la notion de « Pareto-stationnarité » par (1). On établit alors que cette propriété constitue une condition
nécessaire d’optimalité au sens de Pareto [4]. (La démonstration est conduite selon le rang r de la famille de vecteurs {u i } ;
on traite rapidement les cas simples r = 0, et 1 ; puis le cas 0  r  n − 1  N − 1, pour lequel on pose la relation de
dépendance linéaire (2) ; on démontre alors que l’hypothèse μk < 0 conduirait à une contradiction avec celle d’optimalité
de Pareto ; la conclusion s’en déduit ; enfin, on montre que r = n est impossible car chaque critère est optimal sous la
contrainte des autres, (4), ce qui implique (5), contradictoire avec l’hypothèse sur le rang.)

E-mail address: [email protected].

1631-073X/$ – see front matter © 2012 Académie des sciences. Published by Elsevier Masson SAS. All rights reserved.
http://dx.doi.org/10.1016/j.crma.2012.03.014
314 J.-A. Désidéri / C. R. Acad. Sci. Paris, Ser. I 350 (2012) 313–318

On se place ensuite dans le cas inverse où Y 0 n’est pas Pareto-stationnaire, donc pas non plus Pareto-optimal. On intro-
duit l’enveloppe convexe des gradients U défini en (6). Cet ensemble est un fermé convexe, fermeture de l’intérieur U de U
constitué des combinaisons convexes strictes (αi > 0 (∀i )). Il admet donc un unique élément de plus petite norme, noté ω .
On établit le Lemme 2.1 selon lequel le produit scalaire (u , ω) d’un élément quelconque u ∈ U avec ω est au moins égal à
la constante ω2 . On en déduit le résultat principal suivant :

Théorème 0.1. Soit Y 0 le centre d’une boule ouverte de l’espace de conception Ω dans lequel les critères admettent des gradients
continus. On note ω l’élément de plus petite norme de l’enveloppe convexe U définie en (6). Deux cas sont possibles :

(i) ou bien ω = 0, et le point de conception Y 0 est Pareto-stationnaire ;

(ii) ou bien ω = 0, et en Y = Y 0 , le vecteur −ω définit une direction de descente commune à tous les critères ; si de plus ω appartient
à l’intérieur U de U, les dérivées de Fréchet (u i , ω) (i = 1, . . . , n), et plus généralement le produit scalaire (u , ω) (u ∈ U), sont
égaux à la constante ω2 .

S’ensuit très naturellement, la définition de l’Algorithme de Descente à Gradients Multiples (MGDA) qui généralise à l’opti-
misation concourante la méthode classique du gradient en utilisant la direction de descente −ω . On suppose que le pas est
optimisé de manière à ce que tous les critères diminuent à chaque itération. En supposant les critères positifs et infinis à
l’infini, on démontre [2] alors le

Théorème 0.2. Lorsque l’itération de MGDA est infinie, elle génère une sous-suite convergente vers un point de conception Pareto-
stationnaire.

On termine par plusieurs remarques à caractère computationnel, et une illustration numérique.

Remarque 1. Les résultats formels s’appliquent directement à l’optimisation sous contraintes à condition de considérer les
gradients projetés sur le sous-espace tangent aux surfaces de contraintes.

Remarque 2. Afin de déterminer l’elément de plus petite norme ω , ou de manière équivalente, le vecteur de coefficients
α = (α1 , . . . , αn ), on fait plusieurs changements de variables. D’abord on pose : αi = σi2 (∀i = 1, . . . , n) afin de satisfaire la
condition de positivité. En conséquence σ = (σ1 , . . . , σn ) appartient à la sphère unité de Rn , que l’on paramétrise par le
n−1
biais de n − 1 coordonnées sphériques : σi = sin φi −1 . j =i cos φ j . Enfin, comme seul compte σi2 , αi s’exprime par (8) où :
c 0 = 0, c j = cos2 φ j ∈ [0, 1]. Ainsi, l’identification de ω est ramenée à la recherche des n − 1 coefficients {c j } dans [0, 1]n−1 .
Par exemple, pour n = 4 critères, 3 paramètres c 1 , c 2 , c 3 tous dans [0, 1] sont ajustés après avoir posé (9).

Remarque 3. Sans normalisation préalable des gradients, on s’attend à ce la direction de l’élément de norme minimale ω
soit principalement influencée par les vecteurs de petites normes de la famille, comme le suggère le cas n = 2 de la Fig. 1.
Or, au cours de l’optimisation, ces vecteurs sont souvent ceux associés aux critères qui ont déjà atteint un très bon degré
de convergence. Cette direction peut correspondre à celle d’un chemin très direct vers le front de Pareto, mais on peut
doûter qu’elle corresponde au choix le plus judicieux pour une optimisation multiobjectif bien équilibrée. Nos recherches
actuelles portent sur l’analyse de différentes procédures de normalisation conçues pour s’opposer à cette tendance. On
étudie notamment les définitions alternatives données par (10) (k : index d’itération ; δ > 0, petit). La première formule
correspond à une normalisation standard dont le mérite principal réside dans sa stabilité ; la deuxième est conçue pour que
les premières variations logarithmiques des critères soient égales lorsque ω appartient à l’intérieur de l’enveloppe convexe
(ω ∈ U) ; les deux dernières sont inspirées de la méthode de Newton (dans l’hypothèse où lim J i = 0 pour la première).
Cette question reste ouverte.

1. Introduction: Pareto-stationarity

Our focus is on the concurrent optimization of n criteria { J i (Y )} supposed to be smooth functions of the design vector
Y ∈ Ω ⊂ R N (Ω : admissible domain; J i ∈ C 1 (Ω), i = 1, . . . , n  N).
Consider an admissible point Y 0 ∈ Ω . If this design-point is Pareto-optimal (see [4] for classical concepts), it is not
possible to reduce the local value of any criterion without increasing at least one of the other criteria. In the inverse
case, assuming locally smooth criteria, descent directions common to all criteria do exist. We propose to identify one such
direction appropriately.
Before developing our construction, we propose the following notion of Pareto-stationarity:

Definition 1.1 (Pareto-stationarity). Let Y 0 be a design-point at the center of an open ball in the admissible domain Ω in
which the n criteria J i (Y ) (1  i  n  N) are smooth. Let u i = ∇ J i (Y 0 ) be the local gradients. The design-point Y 0 is said
to be Pareto-stationary iff there exists a convex combination of the gradient-vectors, {u i }, that is equal to zero:
 J.-A. Désidéri / C. R. Acad. Sci. Paris, Ser. I 350 (2012) 313–318 315


n 
n
α i u i = 0, αi  0 (∀i ), α i = 1. (1)
i =1 i =1

The hypotheses of this definition being made, we have:

Lemma 1.2. If the design-point Y 0 is Pareto-optimal, it is Pareto-stationary.

Proof. Let r be the rank of the family of gradient-vectors, r = rank({u i }1i n ) = dimSp({u i }1i n ), and let us examine the
different possible cases depending on the value of r.
If r = 0, all the gradient-vectors are equal to zero and the result is trivial.
If r = 1, the gradient-vectors are colinear, say u i = βi u, where u denotes some unit vector and the coefficients βi ’s are
not all equal to zero. Then, a perturbation δ Y = −ε u about Y 0 would cause for sufficiently small ε > 0, the perturbation
δ J i = −ε βi + O (ε 2 ). Thus, if all the coefficients βi ’s were of the same sign, say positive, at least one criterion would diminish
while the other ones would remain unchanged to O (ε 2 ), and this would be a contradiction with the hypothesis that Y 0 is
Pareto-optimal. Hence, necessarily, both strictly positive and negative coefficients are present, and perhaps some are equal to
zero. Assume, for example, β1 β2 < 0 and let: α1 = −β2 /(β1 − β2 ), α2 = β1 /(β1 − β2 ) so that: α1 > 0, α2 > 0, α1 + α2 = 1,
α1 u 1 + α2 u 2 = 0; this establishes the result for r = 1.
Now consider the more general case where 2  r  n − 1. Possibly after a permutation of indices, a linear combination
of the first r + 1 (r + 1  n) gradient-vectors is equal to zero:

r +1

u1 + μk uk = 0. (2)
k =2

Then we claim that μk  0 (∀k  2). To establish this, assume instead that μ2 < 0, and define: V = Sp({u i }3i r +1 ). Then
dim V  r − 1  n − 2  N − 2, and dim V⊥  2. Let ω ∈ V⊥ , arbitrary. Taking the scalar product of (2) with ω yields the
following Fréchet derivatives:

∀ ω ∈ V⊥ , J 2,ω = γ J 1,ω (γ = −1/μ2 > 0). (3)

If the above relation were a trivial equality (0 = γ × 0) for all ω ∈ V⊥ , the vectors u 1 and u 2 would be in V; consequently, so
would be the whole family of gradient-vectors {u i } (1  i  n), which is of rank r by assumption; this is not possible since
dim V  r − 1 < r. Hence, for some ω ∈ V, (3) holds and J 1,ω = 0. Suppose for example that J 1,ω > 0. Then an infinitesimal
perturbation of the design vector Y in the direction of −ω causes a reduction of both criteria J 1 and J 2 and leaves the
other criteria unchanged to second order. This is in contradiction with the assumption that Y 0 belongs to the Pareto set.
Hence, we  have instead μ2  0, and for the same reason: ∀k  2: μk  0. Then we define μ1 = 1 and for all i (1  i  n):
αi = μi / nk=1 μk . This establishes the result for 2  r  n − 1.
Finally consider the case r = n, and let C k = J k (Y 0 ) (1  k  n). Then for some index i (in fact all), Y 0 is the solution of
the following minimization problem subject to inequality constraints:

min J i (Y ) subject to: gk (Y ) := J k (Y ) − C k  0 (∀k = i ). (4)

Y
n
Assume i = 1 to fix the ideas. Hence, the Lagrangian L = J 1 (Y ) + k=2 λk gk ( Y ) in which the λk ’s (2  k  n) are the
Lagrange multipliers, is stationary at Y = Y 0 :


n
u1 + λk uk = 0. (5)
k =2

With our sign conventions, the Lagrange multiplier λk is nonnegative, and when gk < 0, it is equal to zero (see e.g. [3]); but
this is not essential here. Instead note that (5) is in contradiction with the hypothesis r = n, which we now reject. Therefore,
r  n − 1, and all possible cases have been examined. 2

Thus, in general, for smooth unconstrained criteria, Pareto-stationarity is a necessary condition for Pareto-optimality.
Inversely, if the smooth criteria J i (Y ) (1  i  n) are not Pareto-stationary at a given design-point Y 0 , descent directions
common to all criteria exist. We now examine how can such a direction be identified. Denoting (.,.) the usual scalar product
in R N , the problem is equivalent to finding a vector ω ∈ R N such that: (∇ J i (Y 0 ), ω)  0 (∀i = 1, . . . , n). Then, −ω is one
such descent direction. Noting that an arbitrary normalization of the gradients leaves the problem unchanged, the condition
is restated as follows: (u i , ω)  0 (∀i = 1, . . . , n) where now u i = ∇ J i (Y 0 )/ S i , and the definition of the strictly-positive
scaling factors { S i } (i = 1, . . . , n) will be examined ultimately.
316 J.-A. Désidéri / C. R. Acad. Sci. Paris, Ser. I 350 (2012) 313–318

This problem admits a general solution in the convex hull of the family of vectors {u i } (i = 1, . . . , n):
 
 
n 
n
 N
U= u∈R u= αi u i ; αi  0 (∀i = 1, . . . , n); αi = 1 . (6)
i =1 i =1

This result is established in the next section and then exploited to define a Multiple-Gradient Descent Algorithm (MGDA) that
generalizes the steepest-descent method [3] to multiobjective optimization. The algorithm is then proved to converge to a
Pareto-stationary design-point.

2. Main results

The convex hull U is a closed set, closure of its interior U, made of the elements of U associated with strictly-positive
coefficients {αi } (i = 1, . . . , n). Hence the norm admits at least one realization of a minimum in U. Secondly, U is evidently
convex, and the minimum is unique.

Proof. Suppose there were two realizations of the minimum norm in U: ω1  = ω2 . Since U is convex, ∀ ∈ [0, 1],
u = (1 − )ω1 + ω2 ∈ U; therefore: u 2  ω1 2 , that is: (ω1 + ω12 , ω1 + ω12 )  (ω1 , ω1 ) where ω12 = ω2 − ω1 . Hence
2 (ω1 , ω12 ) + 2 (ω12 , ω12 )  0. Then (ω1 , ω12 )  0, since otherwise a contradiction would appear for sufficiently small .
Consequently, for = 1, the inequality is strict unless ω12 = 0; but then u = ω2 and the equality should hold; thus the only
possibility is that ω12 = 0. 2

Let us denote ω the minimum-norm element in U: ω = Argminu∈U u . Then the following holds:

Lemma 2.1. For all u ∈ U: (u , ω)  ω2 .

Proof. Let v = u − ω . Since U is convex, ∀ ∈ [0, 1], ω + v ∈ U and (ω + v , ω + v )  (ω, ω). Hence 2 (ω, v )+ 2 ( v , v )  0.
Consequently, (ω, v )  0 since otherwise a contradiction would appear for sufficiently small . Replacing v by u − ω then
gives the result. 2

Theorem 2.2. With the same setting as in Lemmas 1.2 and 2.1, two cases are possible:

(i) either ω = 0, and the design-point Y 0 is Pareto-stationary;

(ii) or ω = 0, and at Y = Y 0 , the vector −ω defines a descent direction common to all the criteria; if additionally ω belongs to the
interior U of U, the Fréchet derivatives (u i , ω) (i = 1, . . . , n), and more generally the scalar product (u , ω) (u ∈ U), are equal to
the constant ω2 .

Proof. The conclusions of this theorem are reformulations of previous lemmas, except for the statement concerning the
scalar product (u , ω) in the second case, when additionally ω ∈ U (and not simply U). Under these assumptions, the element
ω is the solution to the following minimization problem:

n 
n
ω=u= αi u i , α = Argminj(u ), j(u ) = (u , u ), αi = 1 (7)
i =1 i =1

since by hypothesis, none of the inequality constraints is saturated (αi > 0 (∀i )). Consequently, using the vector α ∈ Rn as
n
the finite-dimensional variable, the Lagrangian writes: L(α , λ) = j + λ( i =1 αi − 1) and the optimality conditions satisfied
by the vector α are the following: ∂ L/∂ αi = 0 (∀i ), ∂ L/∂λ = 0. These equations imply that for all indices i: ∂ j/∂ αi + λ = 0.
n
But, j(u ) = (u , u ) and for u = ω = i =1 αi u i , one has: ∂ j/∂ αi = 2
(∂ u /∂ αi , u ) = 2(u i , ω) = −λ. Hence, 
the Fréchet derivatives
(u i , ω) = −λ/2 (∀i ) are equal. Finally, for any u ∈ U, say u = ni=1 μi u i where μi  0 (∀i ) and n
i =1 μi = 1, one has:

(u , ω) = ni=1 μi (u i , ω) = −λ/2, a constant, necessarily equal to ω2 . 2

This theorem leads us to generalize the classical steepest-descent method to multiobjective optimization by defining the
Multiple-Gradient Descent Algorithm (MGDA) as the iteration whose generic step is:

(i) Compute the normalized gradient-vectors u i = ∇ J i (Y 0 )/ S i , and determine the minimum-norm element ω in the convex
hull U. If ω = 0 (or sufficiently small), stop.
(ii) Otherwise, determine the step-size h as the largest strictly-positive real number for which all the functions j i (t ) =
J i (Y 0 − t ω) (1  i  n) are monotone-decreasing over the interval [0, h].
(iii) Reset Y 0 to Y 0 − hω .
 J.-A. Désidéri / C. R. Acad. Sci. Paris, Ser. I 350 (2012) 313–318 317

Fig. 1. Case n = 2: possible positions of vector ω with respect to the two gradients u 1 and u 2 .

Since at each iteration of the MGDA, all the criteria diminish, we refer to this process as a cooperative-optimization
method. The above MGDA can stop after a finite number of iterations if a Pareto-stationary design-point has been reached.
Otherwise, we have the following:

Theorem 2.3. If the sequence of iterates {Y k } generated by the MGDA is infinite, it admits a subsequence that converges to a Pareto-
stationary design-point.

Proof. Without loss of generality, it can be assumed that the multiobjective problem has been formulated by means of
strictly-positive criteria that are infinite when Y  is (see [2]). Then:

– Since the sequence of values of any considered criterion, say { J 1 (Y k )}, is positive and monotone-decreasing, it is
bounded.
– Since J 1 (Y ) is infinite whenever Y  is infinite, the sequence of iterates {Y k } is also bounded, and this implies the
convergence of a subsequence to some Y  .

The limiting design-point Y  is necessarily Pareto-stationary since otherwise, if ω(Y  ) = 0, a new iteration would potentially
diminish each criterion of a finite amount, and a better iterate be found. 2

Remark 1. The formal results can be applied straightforwardly to the case of constrained optimization provided the gradients
are projected onto the subspace tangent to the constraint surfaces.

Remark 2. For the determination of the minimum-norm element ω , or, equivalently, the vector of coefficients α =
(α1 , . . . , αn ), appropriate changes of variables are made. First, one lets αi = σi2 (∀i = 1, . . . , n) to satisfy the positivity
condition. As a result σ = (σ1 , . . . , σ
n ) is to be found on the unit sphere of R , which is then parameterized using n − 1
n
n−1
spherical coordinates: σi = sin φi −1 · j =i cos φ j . But since only σi2 matters, αi is expressed as follows:

−1
n
αi = (1 − c i−1 ) · cj ( i = 1, . . . , n ; j = 1, . . . , n − 1) (8)
j =i

where: c 0 = 0, c j = cos2 φ j ∈ [0, 1]. Thus, the identification of ω is realized by a search in [0, 1]n−1 . For example, with n = 4
criteria, 3 parameters c 1 , c 2 , c 3 all in [0, 1] are adjusted optimally after letting:

α1 = c1 c2 c3 , α2 = (1 − c1 )c2 c3 , α3 = (1 − c2 )c3 , α4 = (1 − c3 ). (9)

Remark 3. If the gradients are not normalized (S i = 1, ∀i), the direction of the minimum-norm element ω is expected
to be mostly influenced by the gradients of small norms in the family, as the case n = 2 illustrated in Fig. 1 sug-
gests. In the course of the iterative optimization, these vectors are often associated with the criteria that have already
achieved a fair degree of convergence. If this direction may yield a very direct path to the Pareto front, one may ques-
tion whether it is adequate for a well-balanced multiobjective iteration. On-going research is focused on analyzing various
normalization procedures to circumvent this undesirable trend. These correspond to the following possible alternative defi-
nitions:
(k−1) 0
∇ J i (Y 0 ) ∇ J i (Y 0 ) J i (Y 0 ) 0
max( J i (Y ) − J i(k) (Y 0 ), δ)
ui = , , ∇ J i Y , or ∇ Ji Y 0 (10)
∇ J i (Y 0 ) J i (Y 0 ) ∇ J i (Y 0 )2 ∇ J i (Y 0 )2
(k: iteration number; δ > 0, small). The first formula is a standard normalization: it has the merit of providing a stable
definition; the second realizes equal logarithmic first variations of the criteria whenever ω belongs to the interior U of the
convex hull since then, the Fréchet derivatives (u i , ω) are equal; the last two are inspired from Newton’s method (assuming
lim J i = 0 for the first). This question is still open.

Remark 4. If the original gradients {∇ J i (Y 0 )} (i = 1, . . . , n) are linearlyindependent, applying the Gram–Schmidt or-
thogonalization process to them produces the family u i = [∇ J i (Y 0 ) − k<i μi ,k u k ]/ S i , where: S 1 = ∇ J 1 ( Y ), and
0
318 J.-A. Désidéri / C. R. Acad. Sci. Paris, Ser. I 350 (2012) 313–318

Fig. 2. Fonseca testcase –√convergence of the MGDA in the concurrent optimization of the following two functions of the 3-component vector Y : f ± (Y ) =
3
1 − exp[− i =1 (Y i ± 1/ 3)2 ]. In (a) and (b): distribution of initial and Pareto-optimal points, in design and function space respectively; in (c) and (d):
illustration of one particular path. The exact Pareto set is indicated by a dashed line. (Results from [5].)

∀i  2, ∀k < i : μi ,k = (∇ J i (Y 0 ), uk ), S i > 0 and (u i , u i ) = 1. The minimum-norm element of the convex hull associated
n
with this new family is ω = i =1 u i /n and for all i: (u i , ω ) = ω 2 = 1/n. Consequently, (∇ J i (Y 0 ), ω ) = S i /n where
S i = S i + k<i μi ,k . Then, if the condition S i > 0 (∀i) is satisfied, −ω is also an appropriate descent direction.

Lastly, on Fig. 2, we illustrate the capability of the MGDA to identify sharply a Pareto set in a testcase from the literature
(Fonseca testcase in [1]) in which the front is nonconvex in function space.

References

[1] K. Deb, A. Pratap, S. Agarwal, T. Meyarivan, A fast and elitist multiobjective genetic algorithm: NSGA-II, IEEE Transactions on Evolutionary Computa-
tion 6 (2) (2002) 182–197.
[2] J.-A. Désidéri, Multiple-gradient descent algorithm (MGDA), INRIA Research Report No. 6953, June 2009, http://hal.inria.fr/inria-00389811.
[3] Ph.E. Gill, W. Murray, M.H. Wright, Practical Optimization, Academic Press, New York, London, 1986.
[4] K.M. Miettinen, Nonlinear Multiobjective Optimization, Kluwer Academic Publ., Boston, London, Dordrecht, 1999.
[5] A. Zerbinati, J.-A. Désidéri, R. Duvigneau, Comparison between MGDA and PAES for multi-objective optimization, INRIA Research Report No. 7667,
June 2011, http://hal.inria.fr/inria-00605423.