Quasi-Newton methods for solving multiobjective optimization

Abstract

This paper presents a quasi-Newton-type algorithm for nonconvex multiobjective optimization. In this algorithm, the iterations are repeated until termination conditions are met, which is when a suitable descent direction cannot be found anymore. Under suitable assumptions, global convergence is established.

Introduction

Consider the following unconstrained nonconvex multiobjective optimization

$$\underset{x\in R^n}{min}F\left(x\right)$$

where $F={(F_1,\dots ,F_m)}^T:X\to R^m$ is continuous differentiable and $X\subseteq R^n$ is the domain of $F$ which is assumed to be open.

We define any $u,v\in R^m$,

$$u\le v⟺v-u\in R_{+}^m⟺v_j-u_j\ge 0\text{,}j\in I\text{,}$$$$u<v⟺v-u\in R_{++}^m⟺v_j-u_j>0\text{,}j\in I\text{,}$$

where $R_{+}^m≔\{y\in R^m|y\ge 0\}$ and $R_{++}^m≔\{y\in R^m|y>0\}$. We first provide the concept of optimality, i.e., Pareto optimality or efficiency, as explained below.

Definition 1

A point $x^{\ast }\in X$ is local efficiency or local Pareto optimum of $F$ if and only if there exists a neighborhood $V\subset X$ such that there does not exist $x\in V$ with

$$F\left(x\right)\le F\left(x^{\ast }\right)\text{,}\text{and}F\left(x\right)\ne F\left(x^{\ast }\right)\text{.}$$

Note that if $X$ is convex and $F$ is $R^m$-convex (i.e., if $F$ is componentwise-convex), then local Pareto optimality is equivalent to global Pareto optimality. But in non-convex situations, the equivalence is invalid and a necessary (but in general not sufficient)condition for Pareto optimality which has already been used in [1], [2] to define a descent-type algorithm for multiobjective optimization is defined as follows.

Definition 2

• A point $x^{\ast }\in X$ is critical (or stationary) for $F$, if

  $$\Re \left(\nabla F\left(x^{\ast }\right)\right)\subset R_{+}^m\text{,}$$

  where $\Re \left(\nabla h\left(x\right)\right)$ denotes the range or image space of the gradient of the continuously differentiable function $h$ at $x$;

• $d\in R^n$ is a descent direction for $F$ at $x$ if for any $j\in I=\{1,\dots ,m\}$, the directional derivative of the corresponding componentwise function $F_j$ in direction $d$ satisfies the following condition:

  $$F_j^{\prime }(x;d)<0\text{,}$$

  where the directional derivative at $x$ in the direction $d$ is defined as

  $$F_j^{\prime }(x;d)=\underset{\alpha \downarrow 0}{lim}\frac{F_j(x+\alpha d)-F_j\left(x\right)}{\alpha }\text{.}$$

In this paper, we propose a quasi-Newton method for computing the critical point of smooth multiobjective optimization problems under non-convexity. We further extend the ideas of [1] and propose an extension of the “classical” quasi-Newton method for computing the descent search direction. This generation is based on the following consideration as in [1]: (i) It does not require to compute the Hessian; (ii) It does not require the convex assumption. This work uses the quasi-Newton method to approximate second-order information of each objective function, with a nontrivial change to the “classical” quasi-Newton’s method. Our algorithm replaces each objective function with a quadratic model for the each objective function until the critical point is found. This model improves the performance by constraining the descent direction norms and an small positive scalar to control the descent direction. For the new algorithm, we propose the global convergent result under suitable assumptions.