On Fritz John Type Optimality Criterion
in Multi-Objective Optimization

1. Introduction

In [1] LIN J.G gave a Fritz John type optimality criterion for a certain class of nonlinear multi-objective optimization. But in the proof of the corresponding theorem there is a mistake. In this note we give another proof for this important theorem. In the second part of the paper modified Fritz John type sufficient conditions for a certain class of multi-objective programming problems are also established.

2. A Frity John theorem for multi-objective optimization

Let $X\subseteq R^n$ be an open set and let $f:X\to R^m,h:X\to R_{p_1},g:X\to R_{p_2},$ be given. Denote

$$\mathrm{\Omega }=\{x\in X:h\left(x\right)=0,g\left(x\right)\le 0\}.$$

Definition 2.1.

$x^0\in \mathrm{\Omega }$ is called Pareto minimal for $f$ and $\mathrm{\Omega }$ if there exists no $x\in \mathrm{\Omega }$ such that

(2.1) $$f\left(x\right)\le f\left(x^0\right),f\left(x\right)\ne f\left(x^0\right).$$

Similarly, $x^0\in \mathrm{\Omega }$ is called weak Pareto minimal for $f$ on $\mathrm{\Omega }$ if there is no $x\in \mathrm{\Omega }$ such that

(2.2)

$x^0\in \mathrm{\Omega }$ is called locally Pareto minimal (locally weak Pareto minimal) if there exists a neighbourhood (for $\epsilon >0$), such that $x^0$ is Pareto minimal (weak Pareto minimal) for$f$ on $\mathrm{\Omega }\cap B(x^0,\epsilon ).$

Definition 2.2.

Let $Y\subseteq R^m$. The vector $q\in R^m$ is called a convergence vector for $Y$ at $y^0\in Y$ if there exist a sequence $\left(y^k\right)$ in $Y$ and a sequence $\left({\alpha }_k\right)$ of strictly positive real numbers such that

(2.3) $$\underset{k\to \mathrm{\infty }}{lim}{y}^k=y^0;\underset{k\to \mathrm{\infty }}{lim}{\alpha }_k=0;\underset{k\to \mathrm{\infty }}{lim}\frac{y^k-y^0}{{\alpha }_k}=q.$$

Theorem 2.1.

[1, pag. 54]. If $x^0\in \mathrm{\Omega }$ is locally minimal or locally weak minimal for $f$ on $\mathrm{\Omega }$ then no convergence vector for $f\left(\mathrm{\Omega }\right)$ at $y^0=f\left(x^0\right)$ is strictly negative.

Theorem 2.2.

(Motzkin’s theorem). Let $A,B$ and $C$ be given real matrices and $A$ be nonzero. Then either there exists $x$ such that

$Ax$ $=0$

$Bx$ $\ge 0$

$Cx$ $>0,$

or there exist $u,v\ge 0,w\ge 0,w\ne 0$ such that

$$A^{T}u+B^{T}v+C^{T}w=0,$$

but never both.

Now let us denote by $C(\mathrm{\Omega },x^0)$ the cone of convergence vectors for $\mathrm{\Omega }$ at $x^0,$ and let

$$I^0=\{i:g\left(x^0\right)=0\}.$$

We say that $h$ and $g$ satisfy the Kuhn-Tucker constraint qualification at $x^0\in \mathrm{\Omega }$ if

(2.4) $$C(\mathrm{\Omega },x^0)=\{d\in R^n:▽h\left(x^0\right)d=0,▽g_{I_0}\left(x^0\right)d\ge 0\},$$

where $▽f\left(x\right)$ is the Jacobian matrix of $f$ at $x$ and $g_{1_0}={\left(g_i\right)}_{i\in I_0}.$

In [1] the following Fritz John type theorem for multi-objective programming is stated.

Theorem 2.3.

Let $x^0\in \mathrm{\Omega }.$ Assume that the functions $f,g$ and $h$ are differentiable at $x^0$ and that $h$ and $g$ satisfy the Kuhn-Tucker constraint qualification at $x^0$. If $x^0$ is a Pareto minimal (or weak Pareto minimal) solution to the problem

(2.5) $$\min \{f\left(x\right):x\in \mathrm{\Omega }\}$$

then there exist $u\in R_{+}^m\setminus \{0\},v\in R^{p_1},w\in R_{+}^{p_2}$ such that

(2.6) ${▽}^{T}f\left(x^0\right)u+{▽}^{T}h\left(x^0\right)v+{▽}^{T}g\left(x^0\right)w$ $=0,$

(2.7) $g^T\left(x^0\right)w$ $=0.$

In the proof of this theorem [1, pag. 59] the following assertion is done: “Let $q$ be a convergence vector for $f\left(\mathrm{\Omega }\right)$ at $y^0=f\left(x^0\right),$ and let $\left(y^k\right)$ and $\left({\alpha }_k\right)$ be the corresponding sequences for $q$. Consequently, there is a sequence $\left(x^k\right)$ in $\mathrm{\Omega }$ converging to $x^0$ such that

This assertion is not true, as we can see from the following example.

Example 2.1.

Consider $f:R\to R_{+},$

Obviously $f$ is a differentiable function on $R$. Consider $x_0=\frac{3}{2}$ and $\left(y_k\right)$ a sequence in $R_{+}$ converging to $0=f\left(\frac{3}{2}\right)$. It is clear that there is no sequence $\left(x_k\right),x_k\in f^{-1}\left(y_k\right)$ converging to $x_0$. For instance, if $y_k=\frac{1}{n^2}\to 0,$ than $f^{-1}\left(\frac{1}{n^2}\right)=\{1-\frac{1}{2},2+\frac{1}{n}\}.$

Each convergent sequence $\left(x_k\right),x_k\in \{1-\frac{1}{n},2+\frac{1}{n}\},$ converges to 1 or to 2 $\left(\text{and not to }\frac{3}{2}\right).$

Proof of Theorem 2.3. Let $x^0\in \mathrm{\Omega }$ be Pareto minimal (weak minimal) for $f$ on $\mathrm{\Omega }$. Then the vector $y^0=f\left(x^0\right)$ is Pareto minimal (weak minimal) for the set $f\left(\mathrm{\Omega }\right)$. Let $d\in R^n$ be a converge vector for $\mathrm{\Omega }$ at $x^0$ and $\left(x^k\right)\subset \mathrm{\Omega },\left({\alpha }_k\right)\in R_{+}$ the corresponding sequences. Consider $y_k\subset f\left(\mathrm{\Omega }\right),$ $y^k=f\left(x^k\right).$ In view of differentiability (and so of continuity) of $f$ at $x^0,$ the sequence $\left(y^k\right)$ is convergent to $y^0=f\left(x^0\right)$.

But from the differentiability of $f$ we have also

$$f\left(x^k\right)-f\left(x^0\right)=▽f\left(x^0\right)\left(x^k-x^0\right)+\alpha \left(\Vert x^k-x^0\Vert \right),$$

where

$$\frac{\alpha \left(\Vert x^k-x^0\Vert \right)}{\Vert x^k-x^0\Vert }\to 0,x^k\to x^0.$$

From the relationship

$$\frac{y^k-y^0}{{\alpha }_k}=\frac{f\left(x^k\right)-f\left(x^0\right)}{{\alpha }_k}=▽f\left(x^0\right)\frac{x^k-x^0}{{\alpha }_k}+\frac{\alpha \left(\Vert x^k-x^0\Vert \right)}{\Vert x^k-x^0\Vert }\cdot \frac{\Vert x^k-x^0\Vert }{{\alpha }_k}$$

we persuade that

(2.8) $$q=\underset{k\to \mathrm{\infty }}{lim}\frac{y^k-y^0}{{\alpha }_k}=▽f\left(x^0\right)d$$

is a convergence vector for $f\left(\mathrm{\Omega }\right)$ $y^0$.

From the Kuhn-Tucker constraint qualification it follows that $d$ is a convergence vector for $\mathrm{\Omega }$ at $x^0$ iff $d$ is a solution to the system

(2.9) $▽h\left(x^0\right)d$ $=0$

$▽g_{1_0}\left(x^0\right)d$ $\le 0.$

Since $y^0$ is Pareto minimal (weak minimal) for $f\left(\mathrm{\Omega }\right),$ there is no convergence vector for $f\left(\mathrm{\Omega }\right)$ at $y^0$ strictly negative (2.1). Therefore, the system

(2.10) $▽h\left(x^0\right)d$ $=0$

$▽g_{1_0}\left(x^0\right)d$ $\le 0$

$▽f\left(x^0\right)d$

is inconsistent.

System (2.10) can be written under the from

(f.2.10’) $-▽h\left(x^0\right)d$ $=0$

$-▽g_{J_0}\left(x^0\right)d$ $\ge 0$

$-▽f\left(x^0\right)d$ $>0.$

From Motzkin’s theorem (2.2) it follows that system

(2.11) $-$ ${▽}^{T}h\left(x^0\right)v-{▽}^T{g}_{1_0}\left(x^0\right)w-{▽}^{T}f\left(x^0\right)u=0$

$w\ge 0,u\ge 0,u\ne 0$

is consistent.

Let $(v,\rho ,u)$ be a solution to the system (2.11). Then, considering $w\in R_{+}^{p_2}$, defined as follows:

$w_i$ $={\rho }_i\ge 0,i\in I_0$

$w_i$ $=0,i\ne I_0,$

we conclude that $(u,v,w)$ satisfy the conditions (2.6)-(2.7), and so Theorem 2.3 is proved.

3. Sufficient conditions for Pareto optimality

Theorem 3.1.

Let $x^0\in X$ and let $f$ and $g$ be convex and differentiable at $x^0$ functions and $h$ affine function. If at $x^0$ conditions (2.6)-(2.7) are satisfied with $u\in R_{+}^m,$ and $x^0\in \mathrm{\Omega },$ i.e. $h\left(x^0\right)=0,g\left(x^0\right)\le 0,$ then $x^0$ is Pareto minimal for $f$ on $\mathrm{\Omega }$.

Proof.

Assume that $(u,v,w)\in R_{+}^m\times R^{p_1}\times R_{+}^{p_2}$ satisfy (2.7)-(2.6) and consider the function $F:X\to R,$

$$F\left(x\right)=\sum _{i=1}^m{u}_i{f}_i\left(x\right)$$

From (2.6)-(2.7) we derive

${▽}^{T}F\left(x^0\right)+{▽}^{T}h\left(x^0\right)v+{▽}^{T}g\left(x^0\right)w=0.$

$g^T\left(x^0\right)w=0,w\ge 0.$

In view of the Kuhn-Tucker theorem (see [3, pag. 65]) we conclude that $x^0$ is a minimal point of $F$ on $\mathrm{\Omega }$.

Since $u>0$ it follows (see [1, Theorem 6.1]) that $x^0$ is Pareto minimal for $f$ on $\mathrm{\Omega }$.

In order to generalize 3.1 we introduce the notion of weak strictly pseudo convex vector function. ∎

Definition 3.1.

Let $X\subseteq R^n$ be an open set and let $f:X\to R^m$ be differentiable at $x^0\in X$. Then is said to be weak strictly pseudo convex at tx⁰ if for any $x\in X,$ $x\ne x^0$.

(3.1)

This definition is a slight extension of that of the vector pseudo convex functions. This class of functions does not contain the class of convex functions, but does contain the class of strictly convex functions.

Theorem 3.2.

Let $f:X\to R^m$ be a weak strictly pseudo convex, $g:X\to R^{p_1}$ quasiconvex, $h:X\to R_{p_1}$ affine function, and are all differentiable at $x^0\in \mathrm{\Omega }=\{x\in R^n:h\left(x\right)=0,g\left(x\right)\le 0\}.$ If there exist $u\in R_{+}^m\setminus \{0\},v\in R^{p_1},w\in R^{p_2}$ such that (2.6)-(2.7) hold, then $x^0$ is a Pareto minimal point for $f$ on $\mathrm{\Omega }$.

Proof.

If $I_0$ and $g_{I_0}$ have the same meaning as in §2, then conditions (2.6) can be written under the form:

$-$ ${▽}^{T}f\left(x^0\right)u-{▽}^{T}h\left(x^0\right)v-{▽}^T{g}_{1_0}\left(x_0\right)w_{I_2}=0$

$u\ge 0,u\ne 0,w\ge 0,$

where $w_{I_2}={\left(w_i\right)}_{i\in I_0}$.

From Motzkin’s theorem it follows that the system

$-▽h\left(x^0\right)z$ $=0$

$-▽g_{I_0}\left(x^0\right)z$ $\ge 0$

$-▽f\left(x^0\right)z$ $>0$

or equivalently

(3.2) $▽h\left(x^0\right)yz$ $=0$

$▽g_{I_0}\left(x^0\right)z$ $\le 0$

$▽f\left(x^0\right)z$

is inconsistent.

Assume that $x^0$ is not Pareto minimal for $f$ on $\mathrm{\Omega }$. Then there is $\overline{x}\in \mathrm{\Omega }$ such that

$f\left(\overline{x}\right)$ $\le f\left(x^0\right),f\left(\overline{x}\right)\ne f\left(x^0\right),$

$h\left(\overline{x}\right)$ $=0,$

$g\left(\overline{x}\right)$ $\le 0,$

i.e.

(3.3) $f\left(\overline{x}\right)-f\left(x^0\right)$ $\le 0,f\left(\overline{x}\right)-f\left(x^0\right)\ne 0,$

$h\left(\overline{x}\right)-h\left(x^0\right)$ $=0,$

$g_{I_0}\left(\overline{x}\right)-g_{I_0}\left(x^0\right)$ $\le 0.$

From the weak strictly pseudo convexity of $f$, quasiconvexity of $g$ and affinity of $h$, from (3.3) we obtain

(3.4) $▽f\left(x^0\right)\left(\overline{x}-x^0\right)$

$▽h\left(x^0\right)\left(\overline{x}-x^0\right)$ $=0$

$▽g_{I_0}\left(x^0\right)\left(\overline{x}-x^0\right)$ $\le 0.$

For $z=\overline{x}-x^0,$ system (3.4) shows that (3.2) is consistent, i.e. a contradiction. Therefore, $x_0$ is Pareto minimal for $f$ on $\mathrm{\Omega }$. ∎

Received 8.XI.1981

Universitatea Babeş-Bolyai

Facultatea de matematică

3400 Cluj-Napoca

Str. Kogălniceanu 1