# An incremental descent method for multi-objective optimization

I. F. D. Oliveira<EMAIL_ADDRESS>Institute of Science, Engineering and
Technology, Federal University of the Valleys of Jequitinhonha and MucuriR.
Cruzeiro, 1Teófilo OtoniMinas GeraisBrazil39803-371 and  R. H. C. Takahashi
<EMAIL_ADDRESS>Department of Mathematics, Federal University of Minas
GeraisAv. Pres. Antônio Carlos, 6627Belo HorizonteMinas GeraisBrazil31270-901

###### Abstract.

Current state-of-the-art multi-objective optimization solvers, by computing
gradients of all $m$ objective functions per iteration, produce after $k$
iterations a measure of proximity to critical conditions that is upper-bounded
by $O(1/\sqrt{k})$ when the objective functions are assumed to have
$L-$Lipschitz continuous gradients; i.e. they require $O(m/\epsilon^{2})$
gradient and function computations to produce a measure of proximity to
critical conditions bellow some target $\epsilon$. We reduce this to
$O(1/\epsilon^{2})$ with a method that requires only a constant number of
gradient and function computations per iteration; and thus, we obtain for the
first time a multi-objective descent-type method with a query complexity cost
that is unaffected by increasing values of $m$. For this, a brand new multi-
objective descent direction is identified, which we name the _central descent
direction_ , and, an incremental approach is proposed. Robustness properties
of the central descent direction are established, measures of proximity to
critical conditions are derived, and, the incremental strategy for finding
solutions to the multi-objective problem is shown to attain convergence
properties unattained by previous methods. To the best of our knowledge, this
is the first method to achieve this with no additional a-priori information on
the structure of the problem, such as done by scalarizing techniques, and,
with no pre-known information on the regularity of the objective functions
other than Lipschitz continuity of the gradients.

gradient descent, multi-objective optimization

††copyright: acmcopyright††journal: TOMS††journalyear: 2019††journalvolume:
0††journalnumber: 0††article: 0††publicationmonth: 0††doi: 0††ccs: Mathematics
of computing Nonconvex optimization††ccs: Theory of computation Nonconvex
optimization

##  1\. Introduction

In this paper we deal with the problem of finding _critical_ points of multi-
objective optimization problems. The multi-objective function
$F:\mathbb{R}^{n}\to\mathbb{R}^{m}$ is defined as the concatenation of $m$
mono-objective functions as
$F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x}),...,f_{m}(\boldsymbol{x})]^{T}$
that are assumed to have L-Lipschitz continuous gradients, i.e. for some
$L\geq 0$ and for all $\boldsymbol{x},\boldsymbol{y}\in\mathbb{R}$ and all
$i=1,...,m$ the inequality $||\nabla f_{i}(\boldsymbol{x})-\nabla
f_{i}(\boldsymbol{y})||\leq L||\boldsymbol{x}-\boldsymbol{y}||$ holds. And,
following the definition of (Fliege and Svaiter, 2000), a point
$\boldsymbol{x}\in\mathbb{R}^{n}$ is said to be _critical_ (also referred to
as stationary) if and only if there does not exist a direction
$\boldsymbol{v}\in\mathbb{R}^{n}$ such that $\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}<0$ for all $i=1,...,m$.

The search for stationary points is motivated by the fact that standard first
order conditions for local optimality, akin to $\nabla f(\boldsymbol{x})=0$ in
mono-objective optimization, is that $\boldsymbol{x}$ be stationary
(Luenberger and Ye, 2008). Descent direction algorithms, analogous to those
employed in mono-objective problems, have been devised and analysed
extensively for the multi-objective setting, including: (i) _steepest descent_
strategies (Fliege and Svaiter, 2000; Vieira et al., 2010; Fliege et al.,
2018); (ii) _Newton_ type methods (Fliege et al., 2009; Povalej, 2014); (iii)
_projected gradient_ strategies (Drummond and Iusem, 2004; Cruz et al., [n.
d.]); amongst others (Pérez and Prudente, 2019; Gebken and Peitz, 2021;
Moudden and Mouatasim, 2021; Tanabe et al., 2019). These generally follow the
same structure as mono-objective optimization strategies:

1 initialize $\boldsymbol{\hat{x}}\in\mathbb{R}^{n}$;

2 while  _True_ do

3 compute a descent direction $\boldsymbol{d}$;

4 find an appropriate step-size $\alpha\in\mathbb{R}_{+}$;

5 update the estimate
$\boldsymbol{\hat{x}}\leftarrow\boldsymbol{\hat{x}}+\alpha\boldsymbol{d}$;

6

7 end while

Algorithm 1 Descent direction method

The multi-objective steepest descent method is perhaps the benchmark to which
other methods are typically compared (Fliege and Svaiter, 2000; Fliege et al.,
2009, 2018; Fukuda and Drummond, 2014; Cocchi et al., 2020). For any given
estimate $\boldsymbol{\hat{x}}$, the steepest descent method defines
$\boldsymbol{d}$ as
$\boldsymbol{d}\equiv\boldsymbol{V}_{s}(\boldsymbol{\hat{x}})$ where

(1)
$\boldsymbol{V}_{s}(\hat{x})\equiv\text{arg}\min_{\boldsymbol{V}\in\mathbb{R}^{n}}\max_{i=1,...,m}\nabla
f_{i}(\boldsymbol{\hat{x}})^{T}\boldsymbol{V}+\frac{1}{2}||\boldsymbol{V}||^{2}.$

And, if line 3 of Algorithm 1 is implemented with
$\boldsymbol{d}\equiv\boldsymbol{V}_{s}(\boldsymbol{\hat{x}})$, and line 4 is
implemented with step-size $\alpha$ produced by Armijo’s backtracking
procedure delineated in (Fliege and Svaiter, 2000) or the Fibonacci search of
(Vieira et al., 2010), then, under mild technical assumptions, global
convergence is guaranteed irrespective of the starting point, analogous to the
guarantees of mono-objective gradient descent. See Theorem 1 of (Fliege and
Svaiter, 2000) and Theorem 3 of (Vieira et al., 2010) for the details.
Furthermore, the computational complexity of the mono-objective gradient
descent method, which upperbounds the norm of the gradient by $O(1/\sqrt{k})$
after $k$ steps, is also echoed by it’s multi-objective counterpart as the
analogous measure of proximity to critical conditions
$\min_{l=1,...,k}||\boldsymbol{V}_{s}(\hat{\boldsymbol{x}}^{l})||$ is also
upper-bounded by $O(1/\sqrt{k})$ after $k$ steps under the Lipschitz
continuous gradient assumption; see Theorem 3.1 of (Fliege et al., 2018). This
worst case query complexity, in the mono-objective setting, is known to be
optimal and is not improved on even with the addition of second order
information, such as with the use of Newton’s method; see Section 3 of (Cartis
et al., 2010). Analogous convergence guarantees to those of gradient descent
in mono-objective optimization are also known for convex functions as well as
strongly convex functions when the multi-objective steepest descent method is
employed (Fliege et al., 2018; Fukuda and Drummond, 2014). And furthermore,
similar results have been developed for Newton-type methods as well as
projected gradient-type methods in the multi-objective optimization literature
(Fliege et al., 2009; Povalej, 2014; Drummond and Iusem, 2004; Cruz et al.,
[n. d.]).

#### Problem description

While multi-objective steepest descent recovers the $O(1/\sqrt{k})$ rate of
convergence of mono-objective problem solving, since the computation of
$\boldsymbol{d}$ in each iteration requires querying all $m$ gradients, and,
the production of $\alpha$ in both exact and inexact line searches requires
querying all $m$ functions per iteration, the overall query complexity of
multi-objective steepest descent is still $m$ times that of mono-objective
optimization; i.e. when we take into consideration the dependence on $m$ the
number of calls to gradient and function evaluations to upper-bound the
measure of proximity to critical conditions by $\epsilon$ is more precisely of
the order of $O(m/\epsilon^{2})$. That is, with the same query complexity
budget, gradient descent can produce solutions to each of the $m$ mono-
objective minimization problems separately with the similar $\epsilon$ worst
case bounds as one run of the multi-objective steepest descent method. A close
analysis of this complexity gap produces a somewhat puzzling set of informal
propositions:

P1. The requirement ‘$\tilde{x}$ is stationary with respect to
$F(x)\equiv[f_{1}(x),...,f_{m}(x)]^{T}$’ is a relaxation of the mono-objective
equivalent ‘$\tilde{x}$ is stationary with respect to $F(x)\equiv[f_{1}(x)]$’.
P2. Multi-objective steepest descent with $m$ objective functions collects $m$
times more queries of gradient and function values per iteration than gradient
descent applied to the mono-objective problem.
P3. Multi-objective steepest descent requires the same amount of iterations as
gradient descent to produce an estimate with similar worst case bounds.

That is, combining P1 to P3 we find that multi-objective steepest descent
requires more queries to produce one estimate that is associated with weaker
requirements than the $m$ mono-objective solutions produced by gradient
descent with the same query complexity budget. One should expect quite the
opposite: to produce an estimate ‘$\boldsymbol{\tilde{x}}$ stationary with
respect to
$F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x}),...,f_{m}(\boldsymbol{x})]^{T}$
(for some pre-specified tolerance)’ should be less computationally demanding
than to produce an estimate ‘$\boldsymbol{\tilde{x}}$ stationary with respect
to $F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x})]^{T}$ (for some pre-
specified tolerance)’. In fact, a trivial proof that this is the case is
obtained by P1 alone: since critical points with respect to each mono-
objective function are also critical with respect to the multi-objective
problem, the computational cost of gradient descent on any one objective
function is an upper-bound on the cost of the task of producing
‘$\boldsymbol{\tilde{x}}$ stationary with respect to
$F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x}),...,f_{m}(\boldsymbol{x})]^{T}$
(for some pre-specified tolerance)’.

To the best of our knowledge, and somewhat unsatisfyingly, the strategy of
“ignore all but one objective and employ an off-the-shelf mono-objective
optimization algorithm” is still more computationally efficient than the
methods available in the multi-objective optimization literature when the task
at hand is to produce _any_ multi-objective stationary point. This ‘trivial’
approach of ignoring all but one objective, however unsatisfactory, can be
seen as an instance of the well known _scalarization_ techniques often
employed in multi-objective optimization; the most basic of which involves:
(i) selecting a weight vector $\boldsymbol{\pi}\in\mathbb{R}^{m}_{+}$ such
that $\pi_{1}+...+\pi_{m}=1$; then (ii) defining a scalarized mono-objective
function
$F_{\boldsymbol{\pi}}(\boldsymbol{x})\equiv\sum_{i=1}^{m}\pi_{i}f_{i}(\boldsymbol{x})$;
and finally (iii) finding a solution to the mono-objective minimization
problem $\boldsymbol{\hat{x}_{\pi}}=\text{arg}\min
F_{\boldsymbol{\pi}}(\boldsymbol{x})$ via gradient descent (or any other mono-
objective optimization method of choice). These techniques are further
discussed ahead, however, we point out that overall, scalarization choices not
only (almost always) stumble on the same query complexity problems pointed
above, but also, have a well documented collection of a priori shortcomings
associated with the use of surrogate loss functions111Information is either
lost or added when surrogate optimization strategies are employed thus placing
the practitioner at risk of producing artificial non-realizable solutions, or,
at risk of producing sub-optimal solutions, or, to the very least at risk of
producing an artificially narrowed down (meta-parameter dependent) set of
alternatives to the decision maker; decision making alternatives that become
difficult to quantify and compared to the hypothetical alternatives that would
be produced by the original problem. instead of dealing with the original
problem directly. Hence, we consider two questions to address the complexity
gap that arises when considering P1 to P3:

Q1. Is it possible to produce global convergence guarantees to stationary
points of
$F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x}),...,f_{m}(\boldsymbol{x})]$
with a multi-objective approach that has an iteration cost no greater than
that of mono-objective iterative approaches?
Q2. Is it possible to obtain an analogous $\epsilon$-measure of proximity to
critical conditions of
$F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x}),...,f_{m}(\boldsymbol{x})]$
with only $O(1/\epsilon^{2})$ queries to gradients and function values using a
multi-objective approach without arbitrary scalarization? That is, a global
computational cost that is unaffected by increasing values of m?

In this paper we attempt to answer both Q1 and Q2 separately: Q1 is addressed
in Theorem 3.1 and Q2 in Theorem 3.3. Both results provide positive answers to
the questions above, and, to the best of our knowledge, Algorithms 2 and 3,
analysed in the aforementioned theorems, provide for the first time efficient
first order descent direction methods for multi-objective optimization. That
is, unlike the descent direction methods proposed so far within the
multiobjective literature, our methods are the first to have a query
complexity that is unaffected by increasing values of $m$ (a property that can
substantially reduce the computational cost of the search the higher the value
of $m$).

The methods we propose here are perhaps more similar to what are known as
_incremental gradient_ methods (Gürbüzbalaban et al., 2019; Bertsekas, 2017;
Nedic and Bertsekas, 2006) rather than _steepest descent methods_ within the
mono-objective literature. Incremental gradient methods are alternatives to
full gradient methods developed to reduce the computational cost of solving
mono-objective minimization problems of the form $\min
F_{\boldsymbol{\pi}}(\boldsymbol{x})\equiv\sum_{i=1}^{m}\pi_{i}f_{i}(\boldsymbol{x})$
by estimating the descent directions with only small number of gradients
$\nabla f_{i}(\cdot)$ per iteration. When done concomitantly with
randomization of the sampled gradients, then, these are some times referred to
as stochastic gradient descent methods (Vaswani et al., 2019; Ruder, 2017).
Much of the literature of incremental gradient methods can be directly
transposed to the multi-objective setting by considering scalarizing
techniques (discussed ahead). However, as mentioned above scalarizing with
a-priori weights either requires a-priori knowledge of the proper scaling of
the objectives or may produce undesirable solutions associated with the use of
surrogate loss functions, and, despite some analogies between the techniques
here developed and the incremental gradient strategies, our method deals with
the multi-objective problem directly thus avoiding such problems all together.
Furthermore, to the best of our understanding, to fully enjoy the theoretical
speed-ups of incremental gradient techniques known so far, strong convexity of
the loss function, or to the very least convexity, must be assumed, whereas
here we only assume Lipschitz continuity of the gradient.

#### Paper layout

In the remainder of this section we give a brief overview of scalarization
techniques employed to reduce the multi-objective problem to a mono-objective
problem as well as a brief overview of incremental methods. There we point out
how mono-objective incremental strategies are already equipped to tackle
scalarized problems with a reduced query complexity when compared to the
state-of-the-art in multi-objective optimization, albeit, with the
shortcomings associated with the use of surrogate loss functions instead of
tackling the multi-objective problem directly. In Section 2 we define the
_central descent direction_ , an alternative generalization of the mono-
objective steepest descent direction much similar to $\boldsymbol{V}_{s}$ in
(1) that plays a key role in our analysis. There we provide key properties of
the central descent direction that separate it from $\boldsymbol{V}_{s}$ as
well as descent directions derived from scalarization. In this section we also
provide geometric and robustness properties of the central descent direction
as well as several illustrations to facilitate the understanding of the
methods developed in the following sections. The main results are provided in
Section 3. In the first part of Section 3 we define the _incremental central
descent_ algorithm and provide the most general global convergence guarantees
under the assumption of non-additive vanishing step-sizes irrespective of the
starting point; producing either (i) a sub-sequence of estimates with
converging critical conditions or, (ii) a sequence of function values that
tends to $-\infty$. Then, in second part we provide one specific instantiation
of the incremental central descent method and we prove that, for functions
bounded from below, the critical conditions converge at the rate of
$1/\sqrt{k}$ irrespective of the starting point. The algorithm analysed in the
first part of Section 3 has an iteration cost of at most one gradient
computation per iteration, and, in the second part at most two gradient
computations per iteration plus a mono-objective Armijo-type line search thus
improving the current best known complexity guarantees in multi-objective
optimization by eliminating the dependence on $m$.

###  1.1. On scalarizing techniques and incremental approaches

Several multi-objective alternatives to descent direction algorithms can be
found in the literature, including multi-objective evolutionary approaches
(Veldhuizen and Lamont, 2000; Zitzler and Thiele, 1999), multi-objective trust
region methods (Ryu and Kim, 2014; Villacorta et al., 2014; Thomann and
Eichfelder, 2019) amongst others (Mahdavi-Amiri and Sadaghiani, 2020; Tsionas,
2019). However, perhaps the most popular approach in dealing with multi-
objective optimization problems is characterized by using mono-objective
strategies to scalarized instances of the multi-objective problem (Ulivieri,
2014; Ghane-Kanafi and Khorram, 2015; Gunantara, 2018; Eiger et al., 2009;
Kasimbeyli et al., 2019). These have the immediate benefit of inheriting the
convergence guarantees associated with the mono-objective optimization
algorithm, and, can typically be inserted within larger iterative processes
that enable the construction of a representative sample of efficient solutions
of the multi-objective problem - a feature that is often the motivating factor
behind adopting a multi-objective formulation in decision making processes
(Cocchi et al., 2020). The most basic of these scalarizing approaches
involves: (i) selecting a weight vector
$\boldsymbol{\pi}\in\mathbb{R}^{m}_{+}$ such that $\pi_{1}+...+\pi_{m}=1$;
then (ii) defining a scalarized mono-objective function
$F_{\boldsymbol{\pi}}(\boldsymbol{x})\equiv\sum_{i=1}^{m}\pi_{i}f_{i}(\boldsymbol{x})$;
and (iii) finding a solution to the mono-objective minimization problem
$\boldsymbol{\hat{x}_{\pi}}=\text{arg}\min
F_{\boldsymbol{\pi}}(\boldsymbol{x})$ via gradient descent (or any other mono-
objective optimization method of choice). Under this approach, the computation
of the direction $\boldsymbol{d}$ is typically much simpler than (1) as the
gradient of $F_{\boldsymbol{\pi}}(\cdot)$ is simply the weighted sum of the
individual gradients $\nabla
F_{\boldsymbol{\pi}}(\boldsymbol{x})\equiv\sum_{i=1}^{m}\pi_{i}\nabla
f_{i}(\boldsymbol{x})$. More sophisticated scalarizing methods include
constrained optimization formulations in the form “$\min
f_{i}(\boldsymbol{x})$ subject to $f_{j}(\boldsymbol{x})\leq z_{j}$ for all
$j\neq i$” for varying values of $\boldsymbol{z}\in\mathbb{R}^{m}$ as well as
unconstrained goal-programming formulations in the form
$\min||F(\boldsymbol{x})-\boldsymbol{z}||$ for some pre-specified norm
$||\cdot||$ in $\mathbb{R}^{m}$ and varying values of $\boldsymbol{z}$; see
(Ulivieri, 2014) for an extensive list.

Since, scalarization employs off the shelf mono-objective methods to solve an
instance of the multi-objective problem, these can also attain (trivially) the
minmax $O(1/\sqrt{k})$ rate of convergence to find an efficient solution to
the original problem. However, these formulations also (almost always) require
$m$ gradient computations per iteration and thus they carry the same overall
worst-case query complexity as the multi-objective steepest descent approach
in producing a stationary point; i.e. when the dependence on $m$ is made
explicit, the query complexity is more precisely of $O(m/\sqrt{k})$. For
example, the goal programming approach of reducing the multi-objective problem
by minimizing $g(\boldsymbol{x})=||F(\boldsymbol{x})-\boldsymbol{z}||_{2}$
still requires the computation of all $m$ gradients to calculate a descent
direction of the surrogate loss function just as the weighted sum approach of
minimizing
$F_{\boldsymbol{\pi}}(\boldsymbol{x})\equiv\sum_{i=1}^{m}\pi_{i}f_{i}(\boldsymbol{x})$.
And, the constrained optimization formulations, when solved with a projected
descent direction type approach will typically require more than one
computation of each individual function $f_{i}(\cdot)$ for verifying
feasibility, which in turn adds dependency on $m$ in each step even if the
gradient is computed on one function alone during the iteration. Thus, to the
best of our knowledge, the dependence on $m$ does not hold only under two
exceptions: the first being when the scalarization parameters trivially
discard objectives (such as by taking many null weights $\pi_{i}$ in the
minimization of
$F_{\boldsymbol{\pi}}(\boldsymbol{x})\equiv\sum_{i=1}^{m}\pi_{i}f_{i}(\boldsymbol{x})$
) and the second being when the mono-objective solver is capable of exploiting
the inherit structure of a scalarized problem (such as with the use of
incremental gradient descent approaches).

#### Incremental gradient descent

The incremental gradient descent is a mono-objective optimization technique
developed to reduce the query complexity of minimization problems with
objective functions of the form
$F_{\boldsymbol{\pi}}(\boldsymbol{x})\equiv\sum_{i=1}^{m}\pi_{i}f_{i}(\boldsymbol{x})$.
These techniques, together with stochastic gradient descent methods, have
served as the back-bone of practical solvers developed for extremely large and
computationally expensive neural network training problems (Vaswani et al.,
2019; Ruder, 2017; Gürbüzbalaban et al., 2019; Bertsekas, 2017; Nedic and
Bertsekas, 2006). The main difference between both stochastic and
deterministic incremental strategies and full gradient methods is that
incremental strategies do not compute the full gradient of
$F_{\boldsymbol{\pi}}(\cdot)$ in each iteration; instead, in each iteration
$k$ a small sample of gradients $\nabla f_{i}(\boldsymbol{x}_{k})$ is
collected, typically of size $O(1)$, and a descent direction $\boldsymbol{d}$
is estimated/updated with both new and old information available. The choice
of the sampled gradients and the method of producing $\boldsymbol{d}$ is where
the main difference between different incremental methods lie.

Perhaps the first deterministic results that achieved a speed of convergence
independent of $m$ are found in (Blatt et al., 2007), where the iterations are
defined as

(2)
$\boldsymbol{x}^{k+1}\equiv\boldsymbol{x}^{k}-\frac{\alpha}{L}\sum_{l=0}^{L-1}\nabla
f_{(k-l)_{L}}(\boldsymbol{x}^{k-l});$

for some sufficiently small constant $\alpha\in\mathbb{R}_{+}$ and some
$L\in\mathbb{N}$. There they find that for quadratic functions an estimate
$\hat{\boldsymbol{x}}$ that satisfies
$||F_{\boldsymbol{\pi}}(\hat{\boldsymbol{x}})-F_{\boldsymbol{\pi}}(\boldsymbol{x}^{*})||\leq\epsilon$
can be produced in less than $O(log(1/\epsilon))$ iterations. Since this
seminal result, variations of (2) have been produced that extended these
guarantees for general classes of Lipschitz continuous and strongly convex
functions (Liu and Xia, 2020; N.D. Vanli and Ozdaglar, 2018; Gürbüzbalaban et
al., 2017; Tseng and Yun, 2014; Mokhtari et al., 2017); achieving guarantees
that are even tighter than full gradient descent methods (Mokhtari et al.,
2017).

The application of incremental descent methods to _scalarized_ versions of the
multi-objective problem are fairly straight forward: it suffices to (i) choose
weights; (ii) reduce the multi-objective problem to a mono-objective problem;
and, (iii) employ an off-the-shelf incremental solver to the scalarized
problem. And, given that the objective functions satisfy the convexity
requirements of (Liu and Xia, 2020; N.D. Vanli and Ozdaglar, 2018;
Gürbüzbalaban et al., 2017; Tseng and Yun, 2014; Mokhtari et al., 2017), then
a reduced computational complexity that does not depend on $m$ can be enjoyed.
However, as mentioned above, all the drawbacks associated with the reduction
of a multi-objective to a mono-objective problem are also to be expected. If
such a reduction to a mono-objective problem were known a-priori, then there
would be no point in adopting a multi-objective formulation in the first
place; multi-objective formulations are typically chosen precisely because no
such satisfiable reductionistic approach is known. Furthermore, the convexity
assumptions necessary for guaranteed improvements on the convergence speed can
be hard to ensure when multiple objectives (typically of very different
natures) are considered. Unlike neural network training problems where each
$f_{i}$ is typically the loss functions measured on one training point, in
multi-objective optimization each $f_{i}$ typically a measures objectives that
are impossible to put on one common scale: one may represent cost of
production, the other safety protocol measures, and the last variance in
quality control etc.

##  2\. The central descent direction

For non-critical points $\boldsymbol{x}$, any $\boldsymbol{v}$ that satisfies
$\nabla f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}<0$ for all $i=1,...,m$ is
called a descent direction. In this paper one specific uniquely defined
descent direction, which we call the _central descent direction_ , is of
interest. The central descent direction is denoted by
$\boldsymbol{V}_{c}(\boldsymbol{x})$ and is defined as:

(3)
$\boldsymbol{V}_{c}(\boldsymbol{x})\equiv\left\\{\begin{array}[]{ll}\text{argmin
}&\tfrac{1}{2}||\boldsymbol{V}||^{2}\\\ \text{st. }&\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{V}\leq-||\nabla
f_{i}(\boldsymbol{x})||\text{ for all i = 1, ..., m}\end{array}\right.$

Problem (3) can only admit a solution if $\boldsymbol{x}$ is non-critical or
if at least one of the gradients $\nabla f_{i}(\boldsymbol{x})$ is null.
Otherwise, critical points $\boldsymbol{x}$ with non-null gradients $\nabla
f_{i}(\boldsymbol{x})$ do not admit a solution. Hence, the conditions for a
point in $\mathbb{R}^{n}$ to be critical can be restated in terms of the
central descent direction:

###### Lemma 2.1.

A point $\boldsymbol{x}\in\mathbb{R}^{n}$ is critical if and only if (i) at
least one gradient $\nabla f_{i}(\boldsymbol{x})$ is null for some $i=1,...,m$
or (ii) the central descent direction $\boldsymbol{V}_{c}(\boldsymbol{x})$
defined in (3) is empty or (iii) both.

###### Proof.

Follows immediately from the definition of critical points. ∎

Furthermore, the central descent direction provides a means of “measuring” the
proximity to critical conditions (as discussed bellow). To see this we will
need the following lemma:

###### Lemma 2.2.

Let $\\{\boldsymbol{x}_{k}\\}_{k=1,...,\infty}$ be a sequence of non-critical
points converging to $\boldsymbol{x}_{\infty}\in\mathbb{R}^{n}$. Then, if
neither the gradients $\nabla f_{i}(\boldsymbol{x}_{k})$ goes to zero with
$k\to\infty$, we have that either (ii) the accumulation point
$\boldsymbol{x}_{\infty}$ is critical and
$||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||\to\infty$; or (ii) the
accumulation point $\boldsymbol{x}_{\infty}$ is not critical and
$\boldsymbol{V}_{c}(\boldsymbol{x}_{k})$ converges to
$\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})$.

###### Proof.

This proof will use make use of continuity-type results on the dependence of
the central descent direction with respect to the gradients, described in
Lemma 2.3 whose proof is found in the appendix Section A.

###### Lemma 2.3.

Given a collection of vectors $\boldsymbol{g}_{i}$ for $i=1,...,m$ define
$\mathcal{S}\equiv\\{\boldsymbol{v}\text{ st.
}\boldsymbol{g}_{i}^{T}\boldsymbol{v}\leq-||\boldsymbol{g}_{i}||\text{ for all
i = 1, ...,m }\\}$. Then:

  1. (1)

If for some $R>0$ the intersection of $\\{\boldsymbol{v}\text{ st.
}||\boldsymbol{v}||\leq R\\}$ with $\mathcal{S}$ is empty, then, there exists
an $\epsilon>0$ such that for every collection of $\hat{\boldsymbol{g}}_{i}$’s
such that $||\hat{\boldsymbol{g}}_{i}-\boldsymbol{g}_{i}||\leq\epsilon$ for
all $i=1,...,m$ the intersection of $\\{\boldsymbol{v}\text{ st.
}||\boldsymbol{v}||\leq R\\}$ with
$\\{\boldsymbol{v}|\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}\leq-||\hat{\boldsymbol{g}}_{i}||\text{
for all i = 1, ...,m }\\}$ is also empty.

  2. (2)

If $\boldsymbol{v}_{I}$ is vector in $\mathbb{R}^{n}$ that satisfies
$\boldsymbol{g}_{i}^{T}\boldsymbol{v}_{I}<-||\boldsymbol{g}_{i}||\text{ for
all i = 1, ...,m }$, then, there exists an $\epsilon>0$ such that for every
collection of $\hat{\boldsymbol{g}}_{i}$’s in $\mathbb{R}^{n}$ such that
$||\hat{\boldsymbol{g}}_{i}-\boldsymbol{g}_{i}||\leq\epsilon$ for all
$i=1,...,m$ the vector $\boldsymbol{v}_{I}$ also satisfies
$\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}_{I}<-||\hat{\boldsymbol{g}}_{i}||\text{
for all i = 1, ...,m }$.

  3. (3)

If $\boldsymbol{v}_{E}$ is a vector in $\mathbb{R}^{n}$ that satisfies
$\boldsymbol{g}_{i}^{T}\boldsymbol{v}_{E}>-||\boldsymbol{g}_{i}||\text{ for
some i = 1, ...,m }$, then, there exists an $\epsilon>0$ such that for every
collection of $\hat{\boldsymbol{g}}_{i}$’s in $\mathbb{R}^{n}$ such that
$||\boldsymbol{g}_{i}-\hat{\boldsymbol{g}}_{i}||\leq\epsilon$ for all
$i=1,...,m$ the vector $\boldsymbol{v}_{E}$ also satisfies
$\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}_{E}>-||\hat{\boldsymbol{g}}_{i}||\text{
for some i = 1, ...,m }$.

###### Proof.

Refer to the Appendix Section A. ∎

Given that the gradients are L-Lipschitz continuous, we must have that
$||\nabla f_{i}(\boldsymbol{x}_{k})-\nabla f_{i}(\boldsymbol{x}_{\infty})||\to
0$ as $k\to\infty$. Let us assume that $\boldsymbol{x}_{\infty}$ is critical
with $\nabla f_{i}(\boldsymbol{x}_{\infty})\neq 0$ for all i = 1, …, m. Under
these conditions the feasible set
$\mathcal{S}_{\infty}\equiv\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x}_{\infty})^{T}\boldsymbol{v}\leq-||\nabla
f_{i}(\boldsymbol{x}_{\infty})||\text{ for all i = 1, ..., m }\\}$ is empty,
and thus for any given $R>0$ the intersection between $\\{\boldsymbol{v}\text{
st. }||\boldsymbol{v}||\leq R\\}$ and $\mathcal{S}_{\infty}$ is empty. Hence,
as a consequence of Lemma 2.3 part 1 we have: for any $R>0$ there will exist
an $\epsilon>0$ such that any collection of $\hat{\boldsymbol{g}}_{i}$’s in
which $||\hat{\boldsymbol{g}}_{i}-\nabla
f_{i}(\boldsymbol{x}_{\infty})||\leq\epsilon$ for all $i=1,...,m$ and any
$\boldsymbol{v}$ which satisfies $||\boldsymbol{v}||\leq R$ we have that the
intersection between $\\{\boldsymbol{v}\text{ st. }||\boldsymbol{v}||\leq
R\\}$ and $\\{\boldsymbol{v}\text{ st.
}\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}\leq-||\hat{\boldsymbol{g}}_{i}||\text{
for all i = 1,...,m }\\}$ is also empty. As a consequence of this fact, as
$\nabla f_{i}(\boldsymbol{x}_{k})$ approaches $\nabla
f_{i}(\boldsymbol{x}_{\infty})$, the value of
$||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||$ must arbitrarily increase.

Now, let us assume that $\boldsymbol{x}_{\infty}$ is non-critical, and hence,
$\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})$ is non empty. We recall the
definition of the feasible set $\mathcal{S}_{\infty}$ as
$\mathcal{S}_{\infty}\equiv\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x}_{\infty})^{T}\boldsymbol{v}\leq-||\nabla
f_{i}(\boldsymbol{x}_{\infty})||\text{ for all i = 1, ..., m }\\}$, and, we
will refer to the _interior_ of $\mathcal{S}_{\infty}$ as the set of vectors
that satisfy all the inequalities strictly, i.e. the interior of
$\mathcal{S}_{\infty}$ is the set $\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x}_{\infty})^{T}\boldsymbol{v}<-||\nabla
f_{i}(\boldsymbol{x}_{\infty})||\text{ for all i = 1, ..., m }\\}$. By
considering the vector
$\boldsymbol{v}_{\delta}\equiv(1+\delta)\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})$
for any $\delta>0$ it is easy to see that $\boldsymbol{v}_{\delta}$ is in the
interior of $\mathcal{S}_{\infty}$. As a consequence of Lemma 2.3 part 2, for
every $\boldsymbol{v}_{I}$ in the interior of $\mathcal{S}_{\infty}$ there
exists an $\epsilon>0$ such that for every collection of
$\hat{\boldsymbol{g}}_{i}$’s for $i=1,...,m$ that satisfy
$||\hat{\boldsymbol{g}}_{i}-\nabla
f_{i}(\boldsymbol{x}_{\infty})||\leq\epsilon$ we will have
$\boldsymbol{v}_{I}$ also in the interior of $\\{\boldsymbol{v}\text{ st.
}\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}\leq-||\hat{\boldsymbol{g}}_{i}||\text{
for all i = 1, ..., m }\\}$. The same can be said about points in the exterior
of $\mathcal{S}_{\infty}$ by applying Lemma 2.3 part 3, where
$\boldsymbol{v}_{E}$ is said to be in the exterior of $\mathcal{S}_{\infty}$
if there exists an $i$ between $1$ and $m$ such that $\nabla
f_{i}(\boldsymbol{x}_{\infty})^{T}\boldsymbol{v}_{E}>-||\nabla
f_{i}(\boldsymbol{x}_{\infty})||$. Hence, if any subsequence of
$\boldsymbol{V}_{k}$’s converges, then, since it cannot converge to the
interior of $\mathcal{S}_{\infty}$ nor the exterior, it must converge to the
subset of $\mathcal{S}_{\infty}$ where at least one of the constraints $\nabla
f_{i}(\boldsymbol{x}_{\infty})^{T}\boldsymbol{v}\leq-||\nabla
f_{i}(\boldsymbol{x}_{\infty})||$ is satisfied with an equality.

Now, notice that every point in the interior of
$\mathcal{S}_{k}\equiv\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x}_{k})^{T}\boldsymbol{v}<-||\nabla
f_{i}(\boldsymbol{x}_{k})||\text{ for all i = 1, ..., m }\\}$ provides an
upper-bound on the value of $||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||$ since
$\boldsymbol{V}_{c}(\boldsymbol{x}_{k})$ is the minimizer of
$||\boldsymbol{v}||$ over $\mathcal{S}_{k}$. One such upper-bound is
sufficient to recognize that $\boldsymbol{V}_{c}(\boldsymbol{x}_{k})$ remains
bounded for $k>\bar{k}$ for some $\bar{k}\in\mathbb{N}$. Thus, since bounded
sequences must have at least one converging sub-sequence, all that is left is
to show that every such sub-sequence converges to
$\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})$.

Since every point in the interior of $\mathcal{S}_{k}$ provides an upper-bound
on the value of $||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||$ we know that
$\lim_{k\to\infty}||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||\leq\lim_{\delta\to
0}||\boldsymbol{v}_{\delta}||=||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$.
Now, to see that $\lim_{k\to\infty}||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||$
also satisfies
$\lim_{k\to\infty}||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||\geq||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$
notice that if $\\{\boldsymbol{v}\text{ st. }||\boldsymbol{v}||\leq
R\\}\cap\mathcal{S}_{\infty}$ is empty for some $R>0$, then, by Lemma 2.3 part
1 we have that for $\epsilon>0$ sufficiently small, any collection of
$\hat{\boldsymbol{g}}_{i}$’s that satisfy $||\hat{\boldsymbol{g}}_{i}-\nabla
f_{i}(\boldsymbol{x}_{\infty})||\leq\epsilon$ will also have an empty
intersection between $\\{\boldsymbol{v}\text{ st. }||\boldsymbol{v}||\leq
R\\}$ and $\\{\boldsymbol{v}\text{ st.
}\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}\leq-||\hat{\boldsymbol{g}}_{i}\text{
for all i = 1, ..., m}||\\}$. This is the case for any
$R<||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$, and thus for any
$R<||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$ and for any $k\geq\bar{k}$
for some sufficiently large $\bar{k}\in\mathbb{N}$ the value of
$||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$ is greater than or equal to
$R$. Taking the limit of $R$ to
$||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$ we obtain that
$\lim_{k\to\infty}||\boldsymbol{V}_{c}(\boldsymbol{x}_{k})||\geq||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$.

Defining
$\boldsymbol{v}_{\text{lim}}\equiv\lim_{k\to\infty}\boldsymbol{V}_{c}(\boldsymbol{x}_{k})$,
since we have established that
$||\boldsymbol{v}_{\text{lim}}||=||\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})||$
while satisfying $\nabla
f_{i}(\boldsymbol{x}_{\infty})^{T}\boldsymbol{v}_{\text{lim}}\leq-||\nabla
f_{i}(\boldsymbol{x}_{\infty})||$ for all i = 1, …, m (because it cannot be in
the interior or the exterior of $\mathcal{S}_{\infty}$); and, since
$\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})$ is the unique minimizer of
$||\boldsymbol{v}||$ over $\mathcal{S}_{\infty}$, we must conclude that
$\lim_{k\to\infty}\boldsymbol{V}_{c}(\boldsymbol{x}_{k})=\boldsymbol{V}_{c}(\boldsymbol{x}_{\infty})$.
∎

Thus, Lemma 2.2 gives us a measure of proximity to critical conditions of
multi-objective optimization problems in terms of the central descent
direction. In mono-objective optimization, convergence to critical conditions
are typically measured in terms of the norm of the gradient; that is, non-
critical points with small values of $||\nabla f(\boldsymbol{x})||$ are
interpreted as “near critical”. From Lemma 2.2, in the multi-objective setting
we can analogously interpret non-critical points as “near critical” if either
for some $i=1,...,m$ the value of $||\nabla f_{i}(\boldsymbol{x})||$ is small,
or, if the value of $\boldsymbol{V}_{c}(\boldsymbol{x})$ is large. In Figure 1
we illustrate a multi-objective optimization problem and the regions that
approximate the efficient set with the measures here delineated.

Figure 1.  The top figure depicts the level curves and the efficient set of
the multi-objective optimization problem with objective functions
$f_{1}(\boldsymbol{x})\equiv(x_{1}+2)^{2}+3x_{2}^{2}$ and
$f_{2}(\boldsymbol{x})\equiv 3x_{1}^{2}+(x_{2}+2)^{2}$. The bottom left
depicts the level curves of $\min\\{||\nabla f_{1}(\boldsymbol{x})||;||\nabla
f_{1}(\boldsymbol{x})||\\}$ and the bottom right depicts the level curves of
$||\boldsymbol{V}_{c}(\boldsymbol{x})||$. Both measures are complementary to
quantify proximity to critical conditions; the $\min\\{||\nabla
f_{1}(\boldsymbol{x})||;||\nabla f_{1}(\boldsymbol{x})||\\}$ measures
proximity to local minima of the mono objective sub-problems, and,
$||\boldsymbol{V}_{c}(\boldsymbol{x})||$ measures proximity to intermediate
solutions of the multi-objective problem.

#### On the geometric properties and robustness of $\boldsymbol{V}_{c}$

The central descent direction in addition to providing a measure of proximity
to critical conditions that is complimentary to the measure used in mono-
objective optimization, it also enjoys of several geometric and robustness
properties. Here we highlight a few; the first is that

###### Proposition 2.4.

The descent direction
$\boldsymbol{V}_{c}(\boldsymbol{x})/||\boldsymbol{V}_{c}(\boldsymbol{x})||$ is
the unit vector maximally distant from non-descent directions
$\mathbb{R}^{n}\setminus\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}\leq 0\text{ for i = 1,...,m}\\}$.

###### Proof.

Given a unit vector $\boldsymbol{u}$ in $\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}\leq 0\text{ for i = 1,...,m}\\}$, the
$L_{2}$ distance of $\boldsymbol{u}$ to
$\mathbb{R}^{n}\setminus\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}\leq 0\text{ for i = 1,...,m}\\}$ is
given by $d(\boldsymbol{u})=\min_{i=1,...,m}\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{u}/||\nabla f_{i}(\boldsymbol{x})||$.
Therefore, the maximization problem that defines the unit vector maximally
distant from non-descent directions can be expressed as

$\begin{array}[]{ll}\max_{z,\boldsymbol{u}}&z\\\ \text{st.}&z||\nabla
f_{i}(\boldsymbol{x})||\leq\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{u}\text{ for }i=1,...,m;\\\
&||\boldsymbol{u}||=1;\end{array}$

which, by defining $\boldsymbol{V}\equiv\boldsymbol{u}/-z$ the objective $\max
z$ turns out to be equivalent to $\min||\boldsymbol{V}||_{2}$, and, the
constraint $z||\nabla f_{i}(\boldsymbol{x})||\leq\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{u}\text{ for }i=1,...,m;$ turns out to be
equivalent to $-||\nabla f_{i}(\boldsymbol{x})||\geq\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{V}\text{ for }i=1,...,m$. The remaining
constraint of $||\boldsymbol{u}||=1$ can be dropped by recognizing that
$|z|=1/||\boldsymbol{V}||$ is non-restrictive on the remaining variables. ∎

Proposition 2.4 ensures that the central descent direction is maximally
distant from non-descent directions as measured by the $L_{2}$ norm. As a
consequence, numerical errors or approximations in the calculation of
$\boldsymbol{V}_{c}/||\boldsymbol{V}_{c}||$ are less likely to produce a non-
descent direction when compared to any other descent directions in the
negative cone of the gradients. A similar claim can be done if only orthogonal
perturbations to the descent direction are considered, that is, the direction
$\boldsymbol{V}_{c}/||\boldsymbol{V}_{c}||$ also happens to be maximally
distant from non-descent directions if the distance of $\boldsymbol{u}$ in
$\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}\leq 0\text{ for i = 1, ..., m}\\}$ to
non descent directions $\mathbb{R}^{n}\setminus\\{\boldsymbol{v}\text{ st.
}\nabla f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}\leq 0\text{ for i =
1,...,m}\\}$ is measured only over the orthogonal plane defined by
$\\{\boldsymbol{x}\text{ st.
}(\boldsymbol{x}-\boldsymbol{u})^{T}\boldsymbol{u}=0\\}$. Hence, the direction
$\boldsymbol{V}_{c}/||\boldsymbol{V}_{c}||$ seems to be a natural choice if
the descent direction $\boldsymbol{d}$ in line 3 of Algorithm 1 is obtained
through approximations rather than exact computations.

###### Proposition 2.5.

Given a collection objective functions $f_{1},...,f_{m}$ and a collection of
strictly increasing and differentiable transformations
$g_{1},...,g_{m}:\mathbb{R}\to\mathbb{R}$, the central descent direction
$\boldsymbol{V}_{c}(\boldsymbol{x})$ calculated with respect to the objective
functions $f_{1},...,f_{m}$ is equal to the central descent direction
calculated with respect to the objective functions $g_{1}\circ
f_{1},...,g_{m}\circ f_{m}$.

###### Proof.

The proof follows immediately from the chain rule: $\tfrac{\partial}{\partial
x_{j}}\left(g_{i}(f_{i}(\boldsymbol{x}))\right)=g^{\prime}_{i}(f_{i}(\boldsymbol{x}))\cdot\tfrac{\partial}{\partial
x_{j}}f_{i}(\boldsymbol{x})$. Applying the chain rule to the central descent
direction on the monotonically transformed problem we find that
arg$\min\\{\tfrac{1}{2}||\boldsymbol{V}||^{2}\text{ st.
}g^{\prime}_{i}(f_{i}(\boldsymbol{x}))\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{V}\leq-||g^{\prime}_{i}(f_{i}(\boldsymbol{x}))\nabla
f_{i}(\boldsymbol{x})||\\}$ is equal to
arg$\min\\{\tfrac{1}{2}||\boldsymbol{V}||^{2}\text{ st. }\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{V}\leq-||\nabla
f_{i}(\boldsymbol{x})||\\}$ since the terms
$g^{\prime}_{i}(f_{i}(\boldsymbol{x}))$ cancel out. ∎

Thus, Proposition 2.5 ensures that the central descent direction is invariant
to changes on the scales of the objective functions. In contrast, the steepest
descent direction in (1) is not only sensitive to monotone transformations,
but also, sensitive to linear transformations of the objectives; i.e. the
direction $\boldsymbol{V}_{s}(\boldsymbol{x})$ obtained by considering the
objective functions in
$F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x}),f_{2}(\boldsymbol{x})]^{T}$ is
not the same as the one obtained by considering
$F(\boldsymbol{x})\equiv[f_{1}(\boldsymbol{x}),\kappa
f_{2}(\boldsymbol{x})]^{T}$ for $\kappa>0$ with $\kappa\neq 1$. This property
can dramatically warp the path taken by the descent direction algorithm if the
scales are not a-priori fine tuned, a requirement that might be difficult to
meet since multi-objective optimization is adopted precisely when the relative
weights of the objectives is unknown. We illustrate this contrast between
$\boldsymbol{V}_{s}$ and $\boldsymbol{V}_{c}$ in Figures 2 to 4. Figure 2
depicts the level sets of the measure of proximity to critical conditions
induced by $\boldsymbol{V}_{s}$ as well as the stream-lines (the curves
produced by “releasing a particle to flow in the direction of
$\boldsymbol{V}_{s}$” ) of the problem illustrated in Figure 1 when the
objective functions are multiplied by different constants. The warping effect
can over-weigh one objective over the other producing contour-lines and
stream-lines that can even parallel the efficient set making the descent
direction algorithm unnecessarily “go arround” close-by solutions to converge
at distant ones. And, this effect can be dramatically intensified with
different monotone transformations. Figure 3 shows both the contour-lines as
well as the stream-lines induced by $\boldsymbol{V}_{c}$, and, as can be seen
the curves follow a more natural path towards a close-by efficient solution
irrespective of the scale adopted in the representation of the objective
functions. Finally, Figure 4 depicts $\boldsymbol{V}_{s}$ and
$\boldsymbol{V}_{c}$ for varying values of $||\nabla f_{i}(\boldsymbol{x})||$
for $i=1,2$ as well as an approximate the construction of
$\boldsymbol{V}_{c}$.

Figure 2. The top two images depict the level sets of the measure of proximity
induced by the steepest descent (1), i.e the level sets of
$\min_{\boldsymbol{V}\in\mathbb{R}^{n}}\max_{i=1,...,m}\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{V}+\frac{1}{2}||\boldsymbol{V}||^{2}$.
Since the steepest descent direction is not metric-independent, the level sets
of the measure of proximity can be warped (as it is on the left side) when the
objectives are not measured with some comparable scale (as on the right side).
The path taken by the steepest descent method is affected by the warping and
can produce curves that are arbitrarily closet to the efficient set and yet
parallel the efficient set. The path of the steepest descent method (when the
steps are sufficiently small) will follow the stream lines depicted on the two
lower images.  Figure 3. The top image depicts the level sets of
$||\boldsymbol{V}_{c}(\boldsymbol{x})||$ (the same as the bottom right of
Figure 1); and, the bottom image depicts the stream lines induced by the
central descent direction. Notice that since the central descent direction is
unaffected by the rescaling of the objective functions, these level sets are
not warped by different scales/representations of the same collection of
objectives. Also, notice that proximity to the minima of the mono-objective
functions is not measured by this metric, as the level curves meet at a sharp
angle at each individual minima; instead it measures the angle between the
gradients independently of their norms. This produces (on the bottom figure)
stream lines that are metric independent and are not warped by arbitrary
scaling choices. Figure 4.  The background image depicts the effect of
changing the scales of the objective functions. The adoption of different
scales on the objective functions alter the sizes of the gradients
$\boldsymbol{g}_{i}\equiv\nabla f_{i}(\boldsymbol{x})$ for $i=1,2$, but not
the directions of the gradients. Both size and direction of the central
descent are unaffected by these changes in scale, however the direction of
$\boldsymbol{V}_{s}$ described in (1) is affected by these changes in scale.
The size of $\boldsymbol{V}_{s}$ is also affected by such changes, however,
here we only depict the projections of the vectors $\boldsymbol{V}_{s}$ and
$\boldsymbol{V}_{c}$ to the unit ball for ease of visualization. The smaller
image in the bottom right circle depicts the geometric construction of the
vector $\boldsymbol{V}_{c}$. The central descent direction can be obtained by
bisecting the angle between $-\nabla f_{1}(\boldsymbol{x})$ and $-\nabla
f_{2}(\boldsymbol{x})$; and, the value of
$||\boldsymbol{V}_{c}(\boldsymbol{x})||$ is obtained by intersecting
perpendicular lines from $\boldsymbol{g}_{1}/||\boldsymbol{g}_{1}||$ and
$\boldsymbol{g}_{2}/||\boldsymbol{g}_{2}||$. The longer the vector depicting
$\boldsymbol{V}_{c}(\cdot)$ the closer $\boldsymbol{g}_{1}$ and
$\boldsymbol{g}_{2}$ are from pointing in opposite directions.

##  3\. Incremental central descent method

In this section we delineate our main results. Here we describe a multi-
objective incremental descent approach and analyse both global guarantees as
well as theoretical speed of convergence. The choice of performing incremental
approximations to the central descent, rather than the steepest descent, seems
to be well justified since, as demonstrated in the last section, the central
descent direction is robust under monotone transformations of the objective
functions (i.e. no a priori fine-tuning of the scales is necessary to avoid
warping of the directions) and more importantly, it is the direction farthest
away from the non-descent directions. Hence, small errors in the estimate
$\hat{\boldsymbol{d}}$ of $\boldsymbol{V}_{c}/||\boldsymbol{V}_{c}||$ are less
likely to produce a non-descent direction when compared to any other unit
vector in $\\{\boldsymbol{v}\text{ st. }\nabla
f_{i}(\boldsymbol{x})^{T}\boldsymbol{v}\leq 0\text{ for i = 1,...,m}\\}$.

First we provide our global guarantees for vanishing step-sizes:

###  3.1. Global guarantees for vanishing step-sizes

In the following, all that is assumed is that the sequence of step-sizes
$\\{\alpha_{k}\\}_{k=1,2,...}$ satisfy $\alpha_{k}>0$ for all $k$ and
$\lim_{k\to\infty}\alpha_{k}=0$ and $\sum_{k\in\mathbb{N}}\alpha_{k}=\infty$.
This condition can be ensured by pre-specifying the step-sizes (e.g.
$\alpha_{k}=1/k$) or by performing a search in vanishing intervals. The
algorithm described bellow is initiated with arbitrary values for
$\boldsymbol{\hat{x}}\in\mathbb{R}^{n}$ and non-null
$\boldsymbol{\hat{g}}_{1},...,\boldsymbol{\hat{g}}_{m}\in\mathbb{R}^{n}$.

1 initialize $\boldsymbol{\hat{x}}\in\mathbb{R}^{n}$ and
$\boldsymbol{\hat{g}}_{1},...,\boldsymbol{\hat{g}}_{m}\in\mathbb{R}^{n}\setminus\boldsymbol{0}$
and $k\leftarrow 1$ and $\alpha\leftarrow\alpha_{k}$ and $t\leftarrow 1$;

2 while  _True_ do

3 $\boldsymbol{\hat{g}}_{t}\leftarrow\nabla f_{t}(\hat{x})$ and if
$\boldsymbol{\hat{g}}_{t}$ is null then stop;

4 $\boldsymbol{\hat{V}}\leftarrow\text{argmin}\\{||\boldsymbol{V}||^{2}\text{
st.
}\boldsymbol{\hat{g}}_{i}^{T}\boldsymbol{V}\leq-||\boldsymbol{\hat{g}}_{i}||\text{
for }i=1,...,m\\}$ and if $\boldsymbol{\hat{V}}$ is empty then stop;

5
$\hat{\boldsymbol{x}}\leftarrow\hat{\boldsymbol{x}}+\alpha\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||$
and $k\leftarrow k+1$ and $\alpha\leftarrow\alpha_{k}$ and
$t\leftarrow(t+1)\text{ mod }m$;

6

7 end while

Algorithm 2 Increment central descent

We will now prove the convergence properties of Algorithm 2.

###### Theorem 3.1.

Algorithm 2 produces a subsequence of estimates
$\\{\boldsymbol{\hat{x}}_{k_{j}}\\}_{j=1,2,...}$ such that as $j\to\infty$
either (i) the gradient $\nabla
f_{i}(\boldsymbol{\hat{\boldsymbol{x}}}_{k_{j}})$ vanishes for some
$i=1,...,m$; or (ii) the the central descent direction
$\boldsymbol{V}_{c}(\boldsymbol{\hat{\boldsymbol{x}}}_{k_{j}})$ is unbounded;
or (iii) all functions are unbounded from bellow and decrease indefinitely:

(4) $\begin{array}[]{llllllll}(i)&\lim_{j\to\infty}||\nabla
f_{i}(\boldsymbol{\hat{\boldsymbol{x}}}_{k_{j}})||=0&\text{ or
}&(ii)&||\boldsymbol{V}_{c}(\boldsymbol{\hat{\boldsymbol{x}}}_{k_{j}})||\to\infty&\text{
or }&(iii)&\lim_{j\to\infty}f_{i}(\hat{\boldsymbol{x}}_{k_{j}})=-\infty.\\\
&\text{for some i = 1,...,m}&&&&&&\text{for all i = 1,...,m}\end{array}$

###### Proof.

In this proof we will show that if (i) does not occur, then either (ii) or
(iii) must occur. The negation of (i) implies that $||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})||$ is lower-bounded by some positive real
value $c_{1}$ for all $i=1,...,m$ and all $k\in\mathbb{N}$ is thus assumed
henceforth.

Notice that for any iteration $k\geq m+1$ and any $i=1,...,m$ we have that
$||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})-\boldsymbol{\hat{g}}_{i,k}||=||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})-\nabla
f_{i}(\boldsymbol{\hat{x}}_{\tau})||\leq
L||\boldsymbol{\hat{x}}_{k}-\boldsymbol{\hat{x}}_{\tau}||$ for some $\tau$
between $k-m$ and $k$; and furthermore
$||\boldsymbol{\hat{x}}_{k}-\boldsymbol{\hat{x}}_{\tau}||\leq||\boldsymbol{\hat{x}}_{k}-\boldsymbol{\hat{x}}_{k-1}||+||\boldsymbol{\hat{x}}_{k-1}-\boldsymbol{\hat{x}}_{k-2}||+...+||\boldsymbol{\hat{x}}_{k-m+1}-\boldsymbol{\hat{x}}_{k-m}||=\sum_{k-m}^{k}\alpha_{j}$;
and therefore

(5) $||\nabla f_{i}(\boldsymbol{\hat{x}}_{k})-\boldsymbol{\hat{g}}_{i,k}||\leq
L\sum_{k-m}^{k}\alpha_{j}\ \ \text{ for any }k\geq m+1\text{ and }i=1,...m;$

and thus $||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})-\boldsymbol{\hat{g}}_{i,k}||$ goes to zero as
$k$ increases. With this fact established we will now analyse two
complementary cases:
Case 1. There exists a subsequence $\\{k_{j}\\}_{j=1,...,\infty}$ for which
$\lim_{j\to\infty}||\boldsymbol{\hat{V}}_{k_{j}}||=\infty$.
Case 2. There exists an upper-bound $c_{2}>0$ for which
$||\boldsymbol{\hat{V}}_{k}||\leq c_{2}$ for every $k\in\mathbb{N}$.

Analysis of Case 1.

Under the conditions of Case 1 all that is needed is to show that when
$||\boldsymbol{\hat{V}}_{k_{j}}||\to\infty$ for $j\to\infty$, then the points
$\boldsymbol{\hat{x}}_{k}$ produce a subsequence of central descent directions
$\boldsymbol{V}_{k}\equiv\text{argmin}\\{||\boldsymbol{V}||^{2}\text{ st.
}f_{i}(\boldsymbol{\hat{x}_{k}})^{T}V\leq-||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})||\\}$ that diverge. For this, notice that over
the subsequence in which $||\boldsymbol{\hat{V}}_{k_{j}}||$ diverges we have:
(A) the vectors $\hat{\boldsymbol{g}}_{i,k}/||\hat{\boldsymbol{g}}_{i,k}||$
are contained in a unit ball, and thus, there must exist a converging
subsequence where
$\lim_{k\to\infty}\hat{\boldsymbol{g}}_{i,k}/||\hat{\boldsymbol{g}}_{i,k}||=\boldsymbol{u}_{i}$;
and (B) $||\nabla f_{i}(\boldsymbol{\hat{x}}_{k})||$ is lower-bounded by some
positive real value $c_{1}$ for all $i=1,...,m$ and all $k\in\mathbb{N}$; and
(C) the value of $||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})-\boldsymbol{\hat{g}}_{i,k}||$ goes to zero as
$k$ increases. The combination of (A), (B) and (C) imply that $\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})/||\nabla f_{i}(\boldsymbol{\hat{x}}_{k})||$
also converges to $\boldsymbol{u}_{i}$, and thus, by Lemma 2.3 part 1 we
conclude that the points $\boldsymbol{\hat{x}}_{k}$ produce a subsequence of
central descent directions
$\boldsymbol{V}_{k}\equiv\text{argmin}\\{||\boldsymbol{V}||^{2}\text{ st.
}f_{i}(\boldsymbol{\hat{x}}_{k})^{T}V\leq-||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})||\\}$ that diverge.

Analysis of Case 2.

Lipschitz continuity of the gradients ensures that for each i = 1,…,m we have

(6)
$f_{i}(\boldsymbol{\hat{x}}_{k+1})-f_{i}(\boldsymbol{\hat{x}}_{k})\leq\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})^{T}(\boldsymbol{\hat{x}}_{k+1}-\boldsymbol{\hat{x}}_{k})+\tfrac{1}{2}L||\boldsymbol{\hat{x}}_{k+1}-\boldsymbol{\hat{x}}_{k}||^{2};$

and thus

$f_{i}(\boldsymbol{\hat{x}}_{k+1})-f_{i}(\boldsymbol{\hat{x}}_{k})\leq\alpha_{k}\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})^{T}\boldsymbol{\hat{V}}_{k}/||\boldsymbol{\hat{V}}_{k}||+\tfrac{1}{2}L\alpha_{k}^{2}=\alpha_{k}[\boldsymbol{\hat{g}}_{i,k}+(\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})-\boldsymbol{\hat{g}}_{i,k})]^{T}\boldsymbol{\hat{V}}_{k}/||\boldsymbol{\hat{V}}_{k}||+\tfrac{1}{2}L\alpha_{k}^{2}$
$\leq\alpha_{k}\boldsymbol{\hat{g}}_{i,k}^{T}\boldsymbol{\hat{V}}_{k}/||\boldsymbol{\hat{V}}_{k}||+\alpha_{k}L\sum_{k-m}^{k}\alpha_{j}+\tfrac{1}{2}L\alpha_{k}^{2}\leq-\alpha_{k}||\boldsymbol{\hat{g}}_{i,k}||/||\boldsymbol{\hat{V}}_{k}||+\alpha_{k}L\sum_{k-m}^{k}\alpha_{j}+\tfrac{1}{2}L\alpha_{k}^{2};$

where the first inequality of the second line is a consequence of (5) and the
second inequality is a consequence of the definition of
$\boldsymbol{\hat{V}}_{k}$. Now, using (5) a second time on the first term we
obtain $-||\boldsymbol{\hat{g}}_{i,k}||\leq-||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})||+L\sum_{k-m}^{k}\alpha_{j}$ and thus
$-\alpha_{k}||\boldsymbol{\hat{g}}_{i,k}||/||\boldsymbol{\hat{V}}_{k}||\leq-\alpha_{k}||\nabla
f_{i}(\boldsymbol{\hat{x}}_{k})||/||\boldsymbol{\hat{V}}_{k}||+\alpha_{k}L(\sum_{k-m}^{k}\alpha_{j})/||\boldsymbol{\hat{V}}_{k}||$,
and since by construction $||\boldsymbol{\hat{V}}_{k}||\geq 1$ (when it
exists) and by assumption $||\nabla f_{i}(\boldsymbol{\hat{x}}_{k})||\geq
c_{1}$, then we conclude that the first term is upper-bounded by
$-\alpha_{k}c_{1}/||\boldsymbol{\hat{V}}_{k}||+\alpha_{k}L\sum_{k-m}^{k}\alpha_{j}$.
Hence for every $i=1,...,m$ and every $k\geq m+1$ we have

(7)
$f_{i}(\boldsymbol{\hat{x}}_{k+1})-f_{i}(\boldsymbol{\hat{x}}_{k})\leq\alpha_{k}\left(2L\sum_{k-m}^{k}\alpha_{j}+\tfrac{1}{2}L\alpha_{k}-\frac{c_{1}}{||\boldsymbol{\hat{V}}_{k}||}\right).$

Furthermore, under the conditions of Case 2, there exists a constant $c_{2}>0$
such that $||\boldsymbol{\hat{V}}_{k}||\leq c_{2}$ and thus
$-c_{1}/||\boldsymbol{\hat{V}}_{k}||\leq-c_{1}/c_{2}$. Inserting this back
into (7) we obtain

$f_{i}(\boldsymbol{\hat{x}}_{k+1})-f_{i}(\boldsymbol{\hat{x}}_{k})\leq\alpha_{k}\left(2L\sum_{k-m}^{k}\alpha_{j}+\tfrac{1}{2}L\alpha_{k}-c_{1}/c_{2}\right).$

Now notice that the first term within the brackets vanishes with increasing
values of $k$, and thus for sufficiently large $k$ we have
$2L\sum_{k-m}^{k}\alpha_{j}+\tfrac{1}{2}L\alpha_{k}\leq\tfrac{1}{2}c_{1}/c_{2}$.
Hence, for all $i=1,...,m$ and for all $k\geq\bar{k}$, for some
$\bar{k}\in\mathbb{N}$, we have

(8)
$f_{i}(\boldsymbol{\hat{x}}_{k+1})-f_{i}(\boldsymbol{\hat{x}}_{k})\leq-\tfrac{1}{2}\alpha_{k}c_{1}/c_{2}.$

Summing up the terms for $k\geq\bar{k}$ in equation (8) we obtain:

$\left[\lim_{k\to\infty}f_{i}(\boldsymbol{\hat{x}}_{k})\right]-f_{i}(\boldsymbol{\hat{x}}_{\bar{k}})\leq-\tfrac{1}{2}\frac{c_{1}}{c_{2}}\sum_{k\geq\bar{k}}\alpha_{k}=-\infty.$

In this case all functions are unbounded and the sequence produces a
subsequence of points in which all functions are simultaneously decreased
indefinitely. This concludes our proof. ∎

###  3.2. A global $1/\sqrt{k}$ convergence of critical conditions for bounded
functions

Assuming all $f_{i}$ are bounded from bellow we include one additional
gradient computation per iteration and an Armijo-type sufficient decrease
condition with some pre-specified parameter $\beta\in(0,1)$ for the
construction of the step size:

1 initialize $\boldsymbol{\hat{x}}\in\mathbb{R}^{n}$ and
$\boldsymbol{\hat{g}}_{1},...,\boldsymbol{\hat{g}}_{m}\in\mathbb{R}^{n}\setminus\boldsymbol{0}$
and $k\leftarrow 1$ and $j\leftarrow 1$ and $t\leftarrow 2$;

2 while  _While True_ do

3 $\boldsymbol{\hat{g}}_{j}\leftarrow\nabla f_{j}(\hat{x})$;
$\boldsymbol{\hat{g}}_{t}\leftarrow\nabla f_{t}(\hat{x})$ and if
$\boldsymbol{\hat{g}}_{j}$ or $\boldsymbol{\hat{g}}_{t}$ is null then stop;

4 $\boldsymbol{\hat{V}}\leftarrow\text{argmin}\\{||\boldsymbol{V}||^{2}\text{
st.
}\boldsymbol{\hat{g}}_{i}^{T}\boldsymbol{V}\leq-||\boldsymbol{\hat{g}}_{i}||\text{
for }i=1,...,m\\}$ and if $\boldsymbol{\hat{V}}$ is empty then stop;

5 $\alpha\leftarrow\text{max}_{l=0,1,...,\infty}\alpha=(1/2)^{l}$ st.
$f_{j}(\hat{\boldsymbol{x}}+\alpha\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||)-f_{j}(\hat{\boldsymbol{x}})\leq\beta\alpha\boldsymbol{\hat{g}_{j}}^{T}\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||$;

6
$\hat{\boldsymbol{x}}\leftarrow\hat{\boldsymbol{x}}+\alpha\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||$
and $k\leftarrow k+1$ ;

7 choose $t\neq j$ between $1$ and $m$ and if
$f_{t}(\hat{\boldsymbol{x}})<f_{j}(\hat{\boldsymbol{x}})$ then swap $j$ and
$t$;

8

9 end while

Algorithm 3 Increment central descent w/ inexact line-search

###### Lemma 3.2.

(9)
$\alpha\geq\alpha_{\min}\equiv\min\left\\{\tfrac{1-\beta}{2L_{j}},1\right\\}||\boldsymbol{\hat{g}}_{j}||/||\boldsymbol{\hat{V}}||$

###### Proof.

When $2\alpha$ does not satisfy sufficient decrease condition we have

$f_{j}(\hat{\boldsymbol{x}}+2\alpha\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||)-f_{j}(\hat{\boldsymbol{x}})>\beta
2\alpha\nabla
f_{j}(\hat{\boldsymbol{x}})^{T}\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||$

From Lipschits condition:

$f_{j}(\hat{\boldsymbol{x}}+2\alpha\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||)-f_{j}(\hat{\boldsymbol{x}})\leq
2\alpha\nabla
f_{j}(\hat{\boldsymbol{x}})^{T}\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||+\tfrac{L_{j}}{2}||2\alpha\frac{\boldsymbol{\hat{V}}}{||\boldsymbol{\hat{V}}||}||^{2}$
$\implies 2\alpha(1-\beta)\nabla
f_{j}(\hat{\boldsymbol{x}})^{T}\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||+2L_{j}\alpha^{2}\geq
0$ $\implies-L_{j}\alpha\leq(1-\beta)\nabla
f_{j}(\hat{\boldsymbol{x}})^{T}\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||\leq-(1-\beta)||\nabla
f_{j}(\hat{\boldsymbol{x}})||/||\boldsymbol{\hat{V}}||$
$\implies\alpha\geq\frac{1-\beta}{L_{j}}||\nabla
f_{j}(\hat{\boldsymbol{x}})||/||\boldsymbol{\hat{V}}||=\tfrac{1-\beta}{2L_{j}}||\boldsymbol{\hat{g}}_{j}||/||\boldsymbol{\hat{V}}||$

∎

###### Theorem 3.3.

Suppose all functions $f_{i}$ are bounded from bellow and let $f^{\min}$ be a
lower bound on all $f_{i}$. The incremental central descent method with
inexact line searching generates a sequence such that:

(10) $\min_{0\leq l\leq k-1}\frac{\min_{t=1,...,m}||\nabla
f_{t}(\hat{\boldsymbol{x}}_{l})||}{||\hat{\boldsymbol{V}}_{l}||}\leq\sqrt{\frac{1}{k}\left(\frac{f_{1}(\hat{\boldsymbol{x}}_{0})-f^{\min}}{\min\left\\{\frac{\beta(1-\beta)}{2L},\beta\right\\}}\right)}.$

###### Proof.

In each iteration the following inequality holds for the objective function
indexed by $j$

$f_{j}(\hat{\boldsymbol{x}}^{k+1})-f_{j}(\hat{\boldsymbol{x}}^{k})\leq\beta\alpha^{k}\nabla
f_{j}(\hat{\boldsymbol{x}}^{k})^{T}\boldsymbol{\hat{V}}/||\boldsymbol{\hat{V}}||\leq-\beta\alpha^{k}||\nabla
f_{j}(\hat{\boldsymbol{x}}^{k})||/||\boldsymbol{\hat{V}}^{k}||$

and therefore

$f_{j}(\hat{\boldsymbol{x}}^{k})-f_{j}(\hat{\boldsymbol{x}}^{k+1})\geq\beta\alpha^{k}||\nabla
f_{j}(\hat{\boldsymbol{x}}^{k})||/||\boldsymbol{\hat{V}}||\geq\beta\alpha_{\min}||\nabla
f_{j}(\hat{\boldsymbol{x}}^{k})||/||\boldsymbol{\hat{V}}^{k}||$
$=\beta\min\left\\{\frac{1-\beta}{2L},1\right\\}||\nabla
f_{j}(\hat{\boldsymbol{x}}^{k})||^{2}/||\boldsymbol{\hat{V}}||^{2}\geq\min\left\\{\frac{\beta(1-\beta)}{2L},\beta\right\\}\min_{t=1,...,m}||\nabla
f_{t}(\hat{\boldsymbol{x}}^{k})||^{2}/||\boldsymbol{\hat{V}}||^{2}.$

Now, let the index $j$ of iteration $k^{\prime}$ be represented by
$j(k^{\prime})$. Notice that because of line 7 of Algorithm 3 we have
$f_{j(k^{\prime})}(\hat{\boldsymbol{x}}^{k^{\prime}+1})\geq
f_{j(k^{\prime}+1)}(\hat{\boldsymbol{x}}^{k^{\prime}+1})$. Thus,

$f_{j(k^{\prime})}(\hat{\boldsymbol{x}}^{k^{\prime}})-f_{j(k^{\prime}+1)}(\hat{\boldsymbol{x}}^{k^{\prime}+1})\geq
f_{j(k^{\prime})}(\hat{\boldsymbol{x}}^{k^{\prime}})-f_{j(k^{\prime})}(\hat{\boldsymbol{x}}^{k^{\prime}+1})$

and therefore, between iterations, we obtain a decrease in the function values
indexed by $j$ lower-bounded by

(11)
$f_{j(k^{\prime})}(\hat{\boldsymbol{x}}^{k^{\prime}})-f_{j(k^{\prime}+1)}(\hat{\boldsymbol{x}}^{k^{\prime}+1})\geq\min\left\\{\frac{\beta(1-\beta)}{2L},\beta\right\\}\min_{t=1,...,m}||\nabla
f_{t}(\hat{\boldsymbol{x}}^{k^{\prime}})||^{2}/||\boldsymbol{\hat{V}}^{k^{\prime}}||^{2}.$

By summing the terms in equation (11) for varying for values of $k^{\prime}$
between $0$ and $k-1$ we find:

$f_{j(0)}(\hat{\boldsymbol{x}}^{0})-f_{j(k-1)}(\hat{\boldsymbol{x}}^{k-1})\geq\min\left\\{\frac{\beta(1-\beta)}{2L},\beta\right\\}\sum_{l=0}^{k-1}\min_{t=1,...,m}||\nabla
f_{t}(\hat{\boldsymbol{x}}^{l})||^{2}/||\boldsymbol{\hat{V}}^{l}||^{2}.$

And therefore

$f_{j(0)}(\hat{\boldsymbol{x}}^{0})-f^{\min}\geq
k\min\left\\{\frac{\beta(1-\beta)}{2L},\beta\right\\}\min_{0\leq l\leq
k-1}\min_{t=1,...,m}||\nabla
f_{t}(\hat{\boldsymbol{x}}^{l})||^{2}/||\boldsymbol{\hat{V}}^{l}||^{2}$

$\implies\frac{1}{k}\left(\frac{f_{1}(\hat{\boldsymbol{x}}^{0})-f^{\min}}{\min\left\\{\frac{\beta(1-\beta)}{2L},\beta\right\\}}\right)\geq\min_{0\leq
l\leq k-1}\min_{t=1,...,m}||\nabla
f_{t}(\hat{\boldsymbol{x}}^{l})||^{2}/||\boldsymbol{\hat{V}}^{l}||^{2}.$

Which completes our proof. ∎

Theorem 3.3 provides, for the first time, a positive answer to question Q2;
i.e. it is possible to produce the same $O(1/\sqrt{k})$ query complexity as
mono-objective optimization with a global cost that is unaffected by
increasing values of $m$. The method delineated makes use of two gradients per
iteration and one mono-objective inexact line search irrespective of the value
of $m$. Furthermore, since the inexact search problem solved by Algorithm 3 is
identical to the one tackled in (Oliveira and Takahashi, 2021a), if line 5
were substituted with modern line search alternatives with sub-logarithmic
complexity, such as the ones described in (Oliveira and Takahashi, 2021b, a),
we can furthermore guarantee that the inexact Armijo-type search has a
vanishing contribution to the overall cost when compared to the gradient
computations.

##  4\. Discussions

Current state-of-the-art solvers for multi-objective optimization problems
require computing the gradients of all $m$ objective functions per iteration
and one $m$ dimensional line-search to produce a worst case convergence to
critical conditions at the rate of $O(1/\sqrt{k})$, where $k$ is the iteration
count. Here, we propose an incremental descent method that achieves the same
rate of $O(1/\sqrt{k})$ with at most two gradient computations per iteration
and one mono-objective line search; i.e. a reduction in the computational cost
by a factor of $m$. Furthermore, unlike other incremental strategies developed
in the mono-objective literature which require convexity type requirements,
these results are obtained solely under the assumption that the objective
functions have $L-$Lipschitz continuous gradients.

The methods here developed make use of a brand new descent direction much
similar to the Cauchy’s steepest descent, which we term the _central descent_
direction. The central descent is shown to have improved robustness and
geometric guarantees which are not shared by other directions considered so
far in the literature. And, when approximated incrementally, it allows the
construction of the method here proposed with a computational cost that is
unaffected by increasing values of $m$.

#### Future work

The results here attained produce a convergence with a query complexity
matching that of mono-objective optimization. However, as mentioned in the
discussion of P1 to P3, since multi-objective optimization can be seen as a
relaxation to mono-objective optimization, it is natural to expect that
increasing values of $m$ should reduce the overall computational cost of the
search, specifically when the dependence on the stopping criteria is made
explicit. This is so because a larger area of the solution space is considered
near-critical with the increase in the number of objectives. Since in this
paper we focused solely on the iteration cost, the dependence on the stopping
criteria remained open, and thus, with future work the methods here developed
may prove to have a diminishing cost with increasing values of $m$ rather than
a fixed cost as the results reported here. Furthermore, our formulation
despite having attained a reduced query complexity, it still requires a memory
cost that is dependent and increasing with $m$. It might be possible to
exploit the fact that each gradient only shows up as a restriction in the
formulation of (3), and, formulate an update scheme in the computation of
$\hat{\boldsymbol{V}}$ that might mitigate and even eliminate the increasing
memory cost with increasing values of $m$. Another compelling direction of
research is to investigate if it is possible to exploit the “opposite
direction” of scalarization; i.e. to formulate multi-objective relaxations of
mono-objective problems with the intent of reducing the overall query
complexity of the problem. We are unaware of any research done in this
direction and we believe a mapping of the trade-offs associated with such a
relaxation might prove to open brand new methods of solving classical
problems.

###### Acknowledgements.

This paper was written when the first author was a graduate student at the
Federal University of Minas Gerais.

## References

  * (1)
  * Bertsekas (2017) D.P. Bertsekas. 2017\.  Incremental Gradient, Subgradient, and Proximal Methods for Convex Optimization: A Survey.  arXiv:cs.SY/1507.01030
  * Blatt et al. (2007) D. Blatt, A.O. Hero, and H. Gauchman. 2007.  A convergent incremental gradient method with a constant step size.  _SIAM Journal on Optimization_ 18, 1 (2007), 29–51.
  * Cartis et al. (2010) C. Cartis, N.I.M. Gould, and Ph.L. Toint. 2010.  On the Complexity of Steepest Descent, Newton’s and Regularized Newton’s Methods for Nonconvex Unconstrained Optimization Problems.  _SIAM Journal on Optimization_ 20, 6 (September 2010).
  * Cocchi et al. (2020) G. Cocchi, G. Liuzzi, S. Lucidi, and M. Sciandrone. 2020\.  On the convergence of steepest descent methods for multiobjective optimization.  _Computational Optimization and Applications_ 77 (2020), 1–27.
  * Cruz et al. ([n. d.]) J.Y.B. Cruz, L.R.L. Pérez, and J.G. Melo. [n. d.].  Convergence of the projected gradient method for quasiconvex multiobjective optimization.  _Nonlinear Analysis: Theory, Methods and volume =_ ([n. d.]).
  * Drummond and Iusem (2004) L.M.G. Drummond and A.N. Iusem. 2004.  A projected gradient method for vector optimization problems.  _Computational Optimization and Applications_ 28 (2004), 5–29.
  * Eiger et al. (2009) A. Eiger, K. Sikorski, and F.Stenger. 2009.  An adaptive scalarization method in multiobjective optimization.  _SIAM Journal on Optimization_ 19, 4 (2009), 1694––1718.
  * Fliege et al. (2009) J. Fliege, L.M.G. Drummond, and B.F. Svaiter. 2009\.  Newton’s method for multiobjective optimization.  _Journal on Optimization_ 20, 2 (2009), 602–626.
  * Fliege and Svaiter (2000) J. Fliege and B.F. Svaiter. 2000.  Steepest descent methods for multi-criteria optimization.  _Mathematical Methods of Operations Research_ 51 (2000), 479–494.
  * Fliege et al. (2018) J. Fliege, A.I.F. Vaz, and L.M. Vicente. 2018.  Complexity of gradient descent for multiobjective optimization.  _Optimization Methods and Software_ (2018).
  * Fukuda and Drummond (2014) E.H. Fukuda and L.M.G Drummond. 2014.  A survey on multiobjective descent methods.  _Pesquisa Operacional_ 34, 3 (2014), 585–620.
  * Gebken and Peitz (2021) B. Gebken and S. Peitz. 2021.  An efficient descent method for locally Lipschitz multiobjective optimization problems.  _Journal of Optimization Theory and Applications_ 118 (2021), 696–723.
  * Ghane-Kanafi and Khorram (2015) A. Ghane-Kanafi and E. Khorram. 2015.  A new scalarization method for finding the efficient frontier in non-convex multi-objective problems.  _Applied Mathematical Modelling_ 39, 23-24 (2015), 7483–7498.
  * Gunantara (2018) N. Gunantara. 2018\.  A review of multi-objective optimization: Methods and its applications.  _Cogent Engineering_ 5, 1 (2018).
  * Gürbüzbalaban et al. (2017) M. Gürbüzbalaban, A. Ozdaglar, and P.A. Parrilo. 2017\.  On the convergence rate of incremental aggregated gradient algorithms.  _SIAM Journal on Optimization_ 27, 2 (2017), 1035––1048.
  * Gürbüzbalaban et al. (2019) M. Gürbüzbalaban, A. Ozdaglar, and P.A. Parrilo. 2019\.  Convergence rate of incremental gradient and newton methods.  _SIAM Journal on Optimization_ 29, 4 (2019), 2542––2565.
  * Kasimbeyli et al. (2019) R. Kasimbeyli, Z.K. Ozturk, N. Kasimbeyli, G.D. Yalcin, and B.I. Erdem. 2019.  Comparison of some scalarization methods in multiobjective optimization.  _Bulletin of the Malaysian Mathematical Sciences Society_ 42 (2019), 1875––1905.
  * Liu and Xia (2020) Y.C. Liu and F.Q. Xia. 2020\.  Linear convergence of proximal incremental aggregated gradient method for nonconvex nonsmooth minimization problems.  _Applicable Analysis_ 30 (2020).
  * Luenberger and Ye (2008) D.G. Luenberger and Y. Ye. 2008.  _Linear and Nonlinear Programming_ (4th ed.).  Springer.
  * Mahdavi-Amiri and Sadaghiani (2020) N. Mahdavi-Amiri and F.S. Sadaghiani. 2020.  A superlinearly convergent nonmonotone quasi-Newton method for unconstrained multiobjective optimization.  _Optimization Methods and Sofware_ 35, 6 (2020).
  * Mokhtari et al. (2017) A. Mokhtari, M. Gürbüzbalaban, and A. Ribeiro. 2017\.  A double incremental aggregated gradient method with linear convergence rate for large-scale optimization.  _IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ 188 (2017), 4696–4700.
  * Moudden and Mouatasim (2021) M.E. Moudden and A.E. Mouatasim. 2021.  Accelerated diagonal steepest descent method for unconstrained multiobjective optimization.  _Journal of Optimization Theory and Applications_ 188 (2021), 220–242.
  * N.D. Vanli and Ozdaglar (2018) M. Gürbüzbalaban N.D. Vanli and A. Ozdaglar. 2018.  Global convergence rate of proximal incremental aggregated gradient methods.  _SIAM Journal on Optimization_ 28, 2 (2018), 1282–1300.
  * Nedic and Bertsekas (2006) A. Nedic and D.P. Bertsekas. 2006.  Incremental subgradient methods for nondifferentiable optimization.  _SIAM Journal on Optimization_ 12, 1 (2006), 109–138.
  * Oliveira and Takahashi (2021b) I.F.D. Oliveira and R.H.C. Takahashi. 2021b.  An enhancement of the bisection method average performance preserving minmax optimality.  _ACM Trans. Math. Software_ 47, 1 (January 2021), 1–24.  https://doi.org/10.1145/3423597
  * Oliveira and Takahashi (2021a) I.F.D. Oliveira and R.H.C. Takahashi. Submitted in May 2021a.  Efficient solvers for Armijo-type inexact line searching.  _SIAM Journal on Optimization_ (Submitted in May 2021).
  * Pérez and Prudente (2019) L.R. Lucambio Pérez and L.F. Prudente. 2019.  A Wolfe line search algorithm for vector optimization.  _ACM Trans. Math. Software_ 25, 4 (2019).
  * Povalej (2014) Ž. Povalej. 2014\.  Quasi-Newton’s method for multiobjective optimization.  _J. Comput. Appl. Math._ 255 (2014), 765–777.
  * Ruder (2017) S. Ruder. 2017.  An overview of gradient descent optimization algorithms.  arXiv:cs.LG/1609.04747
  * Ryu and Kim (2014) J. Ryu and S. Kim. 2014\.  A derivative-free trust-region method for biobjective optimization.  _SIAM Journal on Optimization_ 24, 1 (2014), 334–363.
  * Tanabe et al. (2019) H. Tanabe, E.H. Fukuda, and N. Yamashita. 2019.  Proximal gradient methods for multiobjective optimization and their applications.  _Computational Optimization and Applications_ 72 (2019), 339––361.
  * Thomann and Eichfelder (2019) J. Thomann and G. Eichfelder. 2019.  A trust-region algorithm for heterogeneous multiobjective optimization.  _SIAM Journal on Optimization_ 29, 2 (2019), 1017––1047.
  * Tseng and Yun (2014) P. Tseng and S. Yun. 2014\.  Incrementally updated gradient methods for constrained and regularized optimization.  _Journal of Optimization Theory and Applications_ 160 (2014), 832––853.
  * Tsionas (2019) M.G. Tsionas. 2019\.  Multi-objective optimization using statistical models.  _European Journal of Operational Research_ 276, 1 (2019), 364–378.
  * Ulivieri (2014) V. Ulivieri. 2014\.  _Multicriteria optimization: scalarization tecniques_.  Master’s thesis. University of Pisa, Master’s Thesis for the Department of Economics and Management.
  * Vaswani et al. (2019) S. Vaswani, A. Mishkin, I. Laradji, M. Schmidt, G. Gidel, and S. Lacoste-Julieny. 2019\.  Painless stochastic gradient: Interpolation, line-search, and convergence rates. In _Proceedings of the 33rd Conference on Neural Information Processing Systems - NeurIPS)_. Vancouver, Canada.
  * Veldhuizen and Lamont (2000) D.A.V. Veldhuizen and G.B. Lamont. 2000.  Multiobjective Evolutionary Algorithms: Analyzing the State-of-the-Art.  _Evolutionary Computation_ 8, 2 (2000), 125––147.
  * Vieira et al. (2010) D.A.G. Vieira, R.H.C. Takahashi, and R.R. Saldanha. 2010\.  Multicriteria optimization with multiobjetive golden section line search.  _Mathematical Programming_ 131 (2010), 131–161.
  * Villacorta et al. (2014) K.D.V. Villacorta, P.R. Oliveira, and A. Soubeyran. 2014\.  A trust-region method for unconstrained multiobjective problems with applications in satisficing processes.  _Journal of Optimization Theory and Applications_ 160 (2014), 865––889.
  * Zitzler and Thiele (1999) E. Zitzler and L. Thiele. 1999.  Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach.  _IEEE Transactions on Evolutionary Computation_ 3, 4 (1999), 257–271.

##  Appendix A Proof of Auxiliary Lemma 2.3

###### Proof.

Part 1. Define $\epsilon(R)$ as any positive value strictly less than
$\epsilon^{*}(R)\equiv\frac{z(R)+1}{R+1}\min_{j}\\{||\boldsymbol{g}_{j}||\text{
for j = 1, ..., m}\\}$ where $z(R)$ is uniquely defined as:

(12)
$z(R)\equiv\left\\{\begin{array}[]{ll}\min_{z\in\mathbb{R},\boldsymbol{v}\in\mathbb{R}^{n}}&z\\\
\text{st.}&\boldsymbol{g}_{i}^{T}\boldsymbol{v}\leq
z||\boldsymbol{g}_{i}||\text{ for all i = 1,...,m};\\\ &||\boldsymbol{v}||\leq
R.\end{array}\right.$

Notice that since the intersection of $\\{\boldsymbol{v}\text{ st.
}||\boldsymbol{v}||\leq R\\}$ with $\mathcal{S}$ is empty, it must be that
$z(R)$ is strictly greater than $-1$ which implies that $\epsilon^{*}(R)$ is
strictly greater than zero. Furthermore, notice that for any $\boldsymbol{v}$
which satisfies $||\boldsymbol{v}||\leq R$ we will have that for some $i$
between $1$ and $m$ the relation $\boldsymbol{g}_{i}^{T}\boldsymbol{v}\geq
z(R)||\boldsymbol{g}_{i}||$ holds. This is because only for the minimizers
$\boldsymbol{v}^{*},z^{*}$ of (12) that $\boldsymbol{g}_{i}^{T}\boldsymbol{v}$
equates to $z(R)||\boldsymbol{g}_{i}||$ on (at least) one value of i between 1
and m. For non-optimal values of $\boldsymbol{v}$, there will exist an $i$
where the condition $\boldsymbol{g}_{i}^{T}\boldsymbol{v}\leq
z(R)||\boldsymbol{g}_{i}||$ must be broken. Thus, consider a collection of
$\hat{\boldsymbol{g}}_{i}$’s in which
$||\hat{\boldsymbol{g}}_{i}-\boldsymbol{g}_{i}||\leq\epsilon(R)$ for all
$i=1,...,m$ and any $\boldsymbol{v}$ which satisfies $||\boldsymbol{v}||\leq
R$; then, we have that for some $i$ the following must hold:

(13)
$\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}=\boldsymbol{g}_{i}^{T}\boldsymbol{v}+(\hat{\boldsymbol{g}}_{i}-\boldsymbol{g}_{i})^{T}\boldsymbol{v}\geq
z(R)||\boldsymbol{g}_{i}||-\epsilon(R)\cdot R.$

What we must show is that the right hands side of (13) is strictly greater
than $-||\hat{\boldsymbol{g}}_{i}||$. This follows from

$z(R)||\boldsymbol{g}_{i}||-\epsilon(R)\cdot
R>-||\hat{\boldsymbol{g}_{i}}||\iff-\epsilon(R)\cdot
R>-z(R)||\boldsymbol{g}_{i}||-||\hat{\boldsymbol{g}}_{i}||,$

which holds if and only if

(14)
$\tfrac{1}{R}\left[z(R)||\boldsymbol{g}_{i}||+||\hat{\boldsymbol{g}}_{i}||\right]>\epsilon(R).$

Now observing that

$\tfrac{1}{R}\left[z(R)||\boldsymbol{g}_{i}||+||\hat{\boldsymbol{g}}_{i}||\right]\geq\tfrac{1}{R}\left[z(R)||\boldsymbol{g}_{i}||+||\boldsymbol{g}_{i}||-\epsilon(R)\right];$

and, the right hand side is greater then $\epsilon(R)$ because

$\tfrac{1}{R}\left[z(R)||\boldsymbol{g}_{i}||+||\boldsymbol{g}_{i}||-\epsilon(R)\right]>\epsilon(R)$
$\iff\tfrac{1}{R}\left[z(R)||\boldsymbol{g}_{i}||+||\boldsymbol{g}_{i}||\right]>(1+1/R)\epsilon(R)$
$\iff\tfrac{z(R)+1}{R+1}||\boldsymbol{g}_{i}||>\epsilon(R);$

and, by the definition of $\epsilon(R)$, this inequality holds.

Part 2. If $\boldsymbol{v}_{I}$ satisfies
$\boldsymbol{g}_{i}^{T}\boldsymbol{v}_{I}<-||\boldsymbol{g}_{i}||\text{ for
all i = 1, ...,m }$, then clearly
$s_{i}=\boldsymbol{g}_{i}^{T}\boldsymbol{v}_{I}+||\boldsymbol{g}_{i}||<0$ for
all $i=1,...,m$. Now, chose any $\epsilon>0$ such that
$\epsilon(1+||\boldsymbol{v}_{I}||)<-s_{i}$ for all $i=1,...,m$. Notice that

$\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}_{I}=\boldsymbol{g}_{i}^{T}\boldsymbol{v}_{I}+(\hat{\boldsymbol{g}}_{i}-\boldsymbol{g}_{i})^{T}\boldsymbol{v}_{I}=\boldsymbol{g}_{i}^{T}\boldsymbol{v}_{I}+||\boldsymbol{g}_{i}||-||\boldsymbol{g}_{i}||+(\hat{\boldsymbol{g}}_{i}-\boldsymbol{g}_{i})^{T}\boldsymbol{v}_{I};$

and thus

$\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}_{I}\leq
s_{i}-||\boldsymbol{g}_{i}||+\epsilon||\boldsymbol{v}_{I}||\leq
s_{i}-||\hat{\boldsymbol{g}}_{i}||+\epsilon+\epsilon||\boldsymbol{v}_{I}||=s_{i}-||\hat{\boldsymbol{g}}_{i}||+\epsilon(1+||\boldsymbol{v}_{I}||);$

and, since $\epsilon$ was chosen to satisfy
$\epsilon(1+||\boldsymbol{v}_{I}||)<-s_{i}$ for all $i=1,...,m$, we have that
$\hat{\boldsymbol{g}}_{i}^{T}\boldsymbol{v}_{I}<-||\hat{\boldsymbol{g}}_{i}||$
for all $i=1,...,m$.

Part 3. If $\boldsymbol{v}_{E}$ satisfies
$\boldsymbol{g}_{i}^{T}\boldsymbol{v}_{E}>-||\boldsymbol{g}_{i}||\text{ for
some i = 1, ...,m }$, then clearly for one such $i=i^{*}$ that satisfies this
inequality we have
$s_{i^{*}}=\boldsymbol{g}_{i^{*}}^{T}\boldsymbol{v}_{E}+||\boldsymbol{g}_{i^{*}}||>0$.
Now, chose any $\epsilon>0$ such that
$\epsilon(1+||\boldsymbol{v}_{E}||)<s_{i^{*}}$. Notice that

$\hat{\boldsymbol{g}}_{i^{*}}^{T}\boldsymbol{v}_{E}=\boldsymbol{g}_{i^{*}}^{T}\boldsymbol{v}_{E}+(\hat{\boldsymbol{g}}_{i^{*}}-\boldsymbol{g}_{i^{*}})^{T}\boldsymbol{v}_{E}=\boldsymbol{g}_{i^{*}}^{T}\boldsymbol{v}_{E}+||\boldsymbol{g}_{i^{*}}||-||\boldsymbol{g}_{i^{*}}||+(\hat{\boldsymbol{g}}_{i^{*}}-\boldsymbol{g}_{i^{*}})^{T}\boldsymbol{v}_{E};$

and thus

$\hat{\boldsymbol{g}}_{i^{*}}^{T}\boldsymbol{v}_{E}\geq
s_{i^{*}}-||\boldsymbol{g}_{i^{*}}||-\epsilon||\boldsymbol{v}_{E}||\geq
s_{i^{*}}-||\hat{\boldsymbol{g}}_{i^{*}}||-\epsilon-\epsilon||\boldsymbol{v}_{E}||=s_{i^{*}}-||\hat{\boldsymbol{g}}_{i^{*}}||-\epsilon(1+||\boldsymbol{v}_{E}||);$

and, since $\epsilon$ was chosen to satisfy
$\epsilon(1+||\boldsymbol{v}_{E}||)<s_{i^{*}}$ we have that
$\hat{\boldsymbol{g}}_{i^{*}}^{T}\boldsymbol{v}_{E}>-||\hat{\boldsymbol{g}}_{i^{*}}||$.
∎