# Charnes-Cooper Scalarization and Convex Vector Optimization

Poonam Kesarwani111Department of Mathematics and Statistics, Indian Institute
of Technology Kanpur, India and Joydeep Dutta222Department of Economics
Sciences, Indian Institute of Technology Kanpur, India

###### Abstract

Our aim in this article is two-fold. We use the Charnes-Cooper scalarization
technique to develop KKT type conditions to completely characterize Pareto
minimizers of convex vector optimization problems and further, we use that
scalarization technique to develop a simple and efficient algorithm for convex
vector optimization problems. Numerical examples are presented to illustrate
the use of our algorithm.

##  1 Introduction

In this paper, we shall focus on the well known convex vector optimization
problem given below, which we label as CVOP:

$\displaystyle\min f(x):=(f_{1}(x),\ldots,f_{m}(x)),$ $\displaystyle{\rm
subject~{}to}~{}~{}x\in X,$

where each $f_{i}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a convex function
and $X$ is a closed convex subset of $\mathbb{R}^{n}$. Let us denote the set
$I:=\\{1,2,\ldots,m\\}$ for the sake of convenience. The “min” in the above
problem is taken in the vector sense where a partial order is induced in the
image space $\mathbb{R}^{m}$, by the non-negative cone $\mathbb{R}^{m}_{+}$.
The partial ordering says that $x\geq y$, if $x-y\in\mathbb{R}^{m}_{+}$, which
can equivalently be written as $x_{i}\geq y_{i}$ for $i\in I$, where $x_{i}$
and $y_{i}$ represents the $i$-th component of the vectors $x$ and $y$
respectively.
Two Types of solution concepts are popular in the literature of vector
optimization problems. These are namely a Pareto minimizer and a weak Pareto
minimizer. A vector $x^{*}\in X$ is called a Pareto minimizer of CVOP if there
exists no ${x}\in X$ such that $f_{i}({x})\leq f_{i}(x^{*})$ for all $i\in I$,
and, $f_{r}({x})\leq f_{r}(x^{*})$ for some $r\in I$. More compactly, it means
that there exists no ${x}\in X$ such that

$f(x)-f(x^{*})\in-\mathbb{R}^{m}_{+}\setminus\\{0\\}.$

On the other hand, a vector $x^{*}\in X$ is called a weak Pareto minimizer if
there exists no ${x}\in X$ such that $f_{i}({x})<f_{i}(x^{*})$ for all $i\in
I$, which equivalently be written as
$f(x)-f(x^{*})\in-\text{int}(\mathbb{R}^{m}_{+})\setminus\\{0\\}.$ Though from
a practical point of view, the notion of a Pareto minimizer is more useful
than its weak counterpart. However, the notion of the weak Pareto minimizer is
mathematically more tractable, and thus, one will find a huge literature on
these solutions. Note that every Pareto minimizer is a weak Pareto minimizer
of the problem and the converse need not be true. The image of the set of
Pareto minimizers of CVOP is called the efficient frontier, and it has been
shown, for example, in Ehrgott [9] that the efficient frontier lies on the
boundary of the image $f(X)$ of the feasible set $X$ under the objective
function $f$.
One of the key approach to study vector optimization problem is by relating a
scalar optimization problem to the given vector optimization problem. This
method is called scalarization and plays a key role in developing a coherent
theory and effective numerical algorithms for the vector optimization problem
(see Chankong and Haimes [4] for more details).
As far as CVOP is concerned, the following result completely characterizes the
weak minimizers through a simple scalarization technique called the weighted
sum scalarization.

###### Proposition 1.1

Consider the problem CVOP and consider weights $\tau_{1}\geq 0$,$\tau_{2}\geq
0$,$\ldots,\tau_{m}\geq 0$, and $x^{*}\in X$ such that $x^{*}$ solves the
problem (CPτ),

$\min\limits_{x\in X}(\tau_{1}f_{1}(x)+\ldots+\tau_{m}f_{m}(x)),$ (1.1)

then $x^{*}$ is a weak Pareto minimizer of CVOP. Conversely, if $x^{*}\in X$
is a weak Pareto minimizer of CVOP, then there exist scalars $\tau_{1}\geq
0$,$\ldots,\tau_{m}\geq 0$, all of which are not simultaneously zero, such
that $x^{*}$ is a minimizer of CPτ.

This result immediately provides us a KKT type necessary and sufficient
condition which completely characterizes a weak minimizer of CVOP. In fact, by
using Proposition 1.1, we can conclude that a vector $x^{*}\in X$ is a weak
minimizer of CVOP if and only if there exists
$0\not=\tau\in\mathbb{R}^{m}_{+}$ such that

$0\in\sum\limits_{i\in I}\tau_{i}\partial f_{i}(x^{*})+N_{X}(x^{*}),$ (1.2)

where $\partial f_{i}(x^{*})$ is the subdifferential at $x^{*}$ of $f$ and
$N_{X}(x^{*})$ denotes the normal cone of $X$ at $x^{*}$. For the definition
of the subdifferential of a convex function and the normal cone to a convex
set at a given point see Rockafellar [19]. Further, if each $f_{i}$ is
differentiable, then we can replace $\partial f_{i}(x^{*})$ by $\nabla
f_{i}(x^{*})$ in (1.2). Moreover, if $X$ is given by convex inequality
constraints, i.e.,

$X=\\{x\in\mathbb{R}^{n}:g_{j}(x)\leq 0,~{}\text{for all }j=1,\ldots,k\\},$
(1.3)

where each $g_{j}:\mathbb{R}^{n}\rightarrow\mathbb{R}$ is a convex function,
for all $j=1,\ldots,k$, and, the Slater condition holds, i.e., there exists
$\hat{x}\in\mathbb{R}^{n}$ such that $g_{j}(\hat{x})<0$ for all
$j=1,\ldots,k$, then we have (see Rockafellar [19]),

$N_{X}(x^{*})=\\{v\in\mathbb{R}^{n}:v=\sum\limits_{j\in
K}\lambda_{j}\xi^{j},\lambda_{j}\geq 0,\xi^{j}\in\partial
g_{j}(x^{*}),\lambda_{j}g_{j}(x^{*})=0,\forall~{}j\in K\\},$

where the set $K:=\\{1,2,\ldots,k\\}$. This immediately allows us to state a
KKT type optimality condition for CVOP, which we do through the following
theorem.

###### Theorem 1.2

Consider the problem CVOP, with $X$ described by (1.3). Let the Slater
condition holds. Then $x^{*}\in X$ is a weak Pareto minimizer of CVOP if and
only if there exists vectors $\tau\in\mathbb{R}^{m}_{+}$, $\tau\neq 0$ and
$\lambda\in\mathbb{R}^{k}_{+}$ such that

$(i)$ $0\in\sum\limits_{i\in I}\tau_{i}\partial f_{i}(x^{*})+\sum\limits_{j\in
K}\lambda_{j}\partial g_{j}(x^{*})$,

$(ii)$ $\lambda_{j}g_{j}(x^{*})=0,$ for all $j\in K$.

For a more detailed analysis of the above results and their proofs, the reader
is referred to the monographs by Jahn [15], Ehrgott [9], Chankong & Haimes
[4], Miettinen [18] and the references therein.
Thus, Theorem 1.2 shows that it is possible to completely characterize a weak
Pareto minimizer of CVOP through KKT conditions. Now we ask ourself a
question: Can this type of result is true for a Pareto minimizer, i.e., can we
completely characterize a Pareto minimizer using KKT type optimality
conditions?
Developing a necessary condition for a Pareto minimizer is indeed simple. By
observing that a Pareto minimizer is a weak Pareto minimizer, Theorem 1.2
guarantees the existence of a vector $\tau\in\mathbb{R}^{m}_{+}$, $\tau\neq 0$
and $\lambda\in\mathbb{R}^{k}_{+}$ such that $(i)$ and $(ii)$ hold. The
problem comes when we are considering the sufficiency of the conditions.
Unfortunately, the conditions $(i)$ and $(ii)$ can only show that $x^{*}$ is a
weak Pareto minimizer of CVOP and no way, it can guarantee that $x^{*}$ is a
Pareto minimizer. However, in $(i)$ if we have
$\tau\in\text{int}(\mathbb{R}^{m}_{+})$, then we can show that $x^{*}$ is a
Pareto minimizer. Therefore, in order to completely characterize a Pareto
minimizer for CVOP through optimality condition, we need to develop a
necessary optimality condition in which we must have
$\tau\in\text{int}(\mathbb{R}^{m}_{+})$. For this, one either needs the Pareto
minimizer to have some additional properties or some regularity conditions are
needed involving the objective functions and the constraint functions. When
$\tau\in\text{int}(\mathbb{R}^{m}_{+})$ in the condition $(i)$, the KKT
conditions are called the strong KKT conditions. Historically, it was Kuhn and
Tucker in their seminal paper [16] of 1951 develops a notion of KT- proper
Pareto solutions for which the strong KKT holds. To prove the strong KKT
conditions Kuhn-Tucker used a regularity condition called Kuhn-Tucker
constraint qualification [16]. Later in 1994, Maeda [17] showed that under
Guignard type regularity condition a Pareto minimizer becomes a KT-proper
Pareto minimizer. However, the simplest approach to strong KKT conditions can
be shown using the notion of Geoffrion proper minimizers, a notion developed
by Geoffrion [14] in 1968.

###### Definition 1.3

(Geoffrion [14]) A vector $x^{*}\in X$ is called a Geoffrion proper minimizer
of CVOP if $x^{*}$ is a Pareto minimizer and if there exists a number $M>0$
such that for all $i\in I$ and $x\in X$ satisfying $f_{i}(x)<f_{i}(x^{*})$,
there exists a $j\in I$ such that $f_{j}(x^{*})<f_{j}(x)$ and

$\displaystyle\frac{f_{i}(x^{*})-f_{i}(x)}{f_{j}(x)-f_{j}(x^{*})}\leq M.$
(1.4)

Geoffrion [14] shows that if $x^{*}$ is Geoffrion proper minimizer of CVOP
with smooth input data and the Kuhn-Tucker constraint qualification [16] is
satisfied at $x^{*}$, then there exists vectors
$\tau\in\text{int}(\mathbb{R}^{m}_{+})$, and $\lambda\in\mathbb{R}^{k}_{+}$
such that

  * •

$\sum\limits_{i\in I}\tau_{i}\nabla f_{i}(x^{*})+\sum\limits_{j\in
K}\lambda_{j}\nabla g_{j}(x^{*})=0$,

  * •

$\lambda_{j}g_{j}(x^{*})=0,$ for all $j\in K$.

If we replace the Kuhn-Tucker Constraint qualification by the Slater condition
in the above result, we will get the same strong KKT condition for Geoffrion
proper minimizer. We would like to mention here that the strong KKT conditions
for a Geoffrion proper minimizer also holds even if some of the objective
functions are not differentiable. For such functions, we just have to replace
the gradient with the subdifferential of the functions. Therefore, Geoffrion
proper minimizer gives rise to strong KKT type optimality conditions. It is
well known that every Pareto minimizer is not a Geoffrion proper minimizer
(see Example 2.48 of [9]). Hence, we are now asking whether it is possible to
develop a strong KKT type optimality conditions for Pareto minimizers.
In Section 2, we shall show that this could be achieved by a combination of
Charnes and Cooper scalarization [5] and Abadie type regularity condition
which we shall describe at the beginning of the section. In Section 3, we
shall show that Charnes and Cooper scalarization can be efficiently used to
develop an algorithm to solve convex vector optimization problems where we
need the feasible set to be closed and $f_{i}$’s to be a proper lower semi-
continuous function for all $i\in I$. We shall also illustrate our algorithm
through numerical examples.

##  2 Strong KKT conditions for Pareto minimizers

There two main purposes for which the Charnes-Cooper scalarization is
introduced. The first is to completely characterize Pareto minimizer through
KKT conditions. This is what we do in this section by showing how the Charnes-
Cooper scalarization scheme can be used to derive strong KKT condition. The
second purpose is to develop an algorithm to generate Pareto minimizer of CVOP
which is done in the next section.

Consider an arbitrary feasible point $x_{0}\in X$ of CVOP and define the
following scalar problem $P(f,X,x_{0})$ ([10]):

$\left\\{\begin{array}[]{ll}\min\sum\limits_{i\in I}f_{i}(x),&\\\
{\text{subject to }}~{}~{}f_{i}(x)-f_{i}(x_{0})\leq 0,&\text{ for all }i\in
I,\\\ x\in X.&\end{array}\right.$ (2.1)

The advantage of the above scalar problem is that it provides a one-one
correspondence between Pareto minimizer of CVOP and optimal solutions of the
problem $P(f,X,x_{0})$.

######  Theorem 2.1 (Ehrgott[10])

A point $x_{0}\in X$ is a Pareto minimizer of CVOP if and only if $x_{0}$ is
an optimal solution of the problem $P(f,X,x_{0})$.

Observe that even if we consider the objective functions to be non-convex,
Theorem 2.1 is true, in other words, the characterization of a Pareto-
minimizer through Charnes-Cooper scalarization still holds. However, computing
the global minimizer of a non-convex optimization problem is hard, and we can
only assure the computation of local Pareto minimizers which are not of
special interest. So, we shall focus only on convex problems.
Note that if $x_{0}$ is a Pareto minimizer of CVOP, then Slater constraint
qualification cannot be satisfied for the problem $P(f,X,x_{0})$. Therefore,
if we want to use the scalar problem $P(f,X,x_{0})$ to figure out the
necessary and optimality condition for Pareto minimizer, we need some
regularity condition to be satisfied. In this direction, we define the
following Abadie type regularity condition for CVOP which helps us in further
investigation.

###### Definition 2.2

Consider CVOP with feasible set $X$ and for given $x_{0}\in X$, define the set
$\hat{X}(x_{0}):=\\{x\in X:f_{i}(x)\leq f_{i}(x_{0}),~{}i\in I\\}.$ Then, we
say that the problem satisfies the strong Abadie type regularity condition at
a point $x_{0}\in X$ if the tangent cone $T_{\hat{X}}(x_{0})$ of the set
$\hat{X}$ at the point $x_{0}$ equals

$V(x_{0}):=\\{h\in\mathbb{R}^{n}:f_{i}^{{}^{\prime}}(x_{0},h)\leq
0,~{}g_{k}^{{}^{\prime}}(x_{0},h)\leq 0,\text{ for all }i\in I\text{ and
}k\in\mathcal{R}(x_{0})\\}.$ (2.2)

Recall that $\mathcal{R}(x_{0})$ is the active constraint set, i.e.,
$\mathcal{R}(x_{0})=\\{k\in K:g_{k}(x_{0})=0\\}$ and and the tangent cone
$T_{X}(x_{0}):=\\{d\in\mathbb{R}^{n}:\exists~{}\\{t_{k}\\}\subseteq\mathbb{R}_{+},\\{y_{k}\\}\subseteq
X~{}\text{ subject to }~{}y_{k}\rightarrow
x_{0},~{}t_{k}(y_{k}-x_{0})\rightarrow d\\}.$
Note that the feasible set of $(f,X,x)$ is ${\hat{X}}(x_{0})$. One can observe
that the strong Abadie type regularity condition is same as the Abadie
constraint qualification (see [7]) for the scalar problem $P(f,X,x_{0})$.
Before we derive the KKT conditions for Pareto minimizer, let us establish
that the problem CVOP satisfies the strong Abadie type regularity condition
through two examples in which one is for smooth CVOP and other is for non-
smooth CVOP.

###### Example 2.3

(Chandra et al.[3]) Consider the bi-objective optimization problem, where
$f=(f_{1},f_{2})$ with
$f_{1}(x)=x^{2},~{}f_{2}(x)=x~{}{and}~{}X=\\{x\in\mathbb{R}:g(x)\leq 0\\}$,
where $g(x)=-x$. It is clear that $x_{0}=0$ is a Pareto minimizer of the
problem. Here, the set $\hat{X}(x_{0})=\\{x\in\mathbb{R}:x^{2}\leq 0,x\leq
0,-x\leq 0\\}=\\{0\\}$ and it is clear that $T_{\hat{X}(x_{0})}(0)=\\{0\\}$.
Further, since the constraint function $g$ is active at $x_{0}=0$ and
$f_{1}^{{}^{\prime}}(x_{0},h)=0$, the set

$V(x_{0})=\\{h\in\mathbb{R}:h\leq 0,-h\leq 0\\}=\\{0\\}.$

Hence, $T_{\hat{X}(x_{0})}=V(x_{0})$, which implies that considered problem
satisfies the strong Abadie type regularity condition at the point $x_{0}=0$.

###### Example 2.4

Consider the bi-objective optimization problem with $f=(f_{1},f_{2})$ where
$f_{1}(x)=x,~{}f_{2}(x)=|x|~{}{and}~{}X=\mathbb{R}.$ It is clear that
$x_{0}=0$ is a Pareto minimizer of the problem. Here, the set
$\hat{X}(x_{0})=\\{x\in\mathbb{R}:x\leq 0,|x|\leq 0\\}=\\{0\\}$ and hence,
$T_{\hat{X}(x_{0})}(0)=\\{0\\}$. Now form (2.2), the set
$V(x_{0})=\\{h\in\mathbb{R}:h\leq 0,|h|\leq 0\\}=\\{0\\},$ which implies that
$T_{\hat{X}(x_{0})}=V(x_{0})$. Hence,the strong Abadie type regularity
condition holds at the point $x_{0}=0$.

The idea of using the term strong Abadie type regularity is motivated by the
fact that all the objective functions of CVOP appear in the formulation of the
Abadie type regularity condition. For a weaker version of the Abadie type
regularity condition for a multiobjective optimization problem see [3].

###### Theorem 2.5

Consider CVOP in which all objective functions $f_{i}$’s and constraint
functions $g_{r}$’s are smooth. Let $x_{0}$ be a Pareto minimizer of CVOP and
the strong Abadie type regularity condition be satisfied at $x_{0}$. Then
there exists $\lambda^{*}\in\mathbb{R}^{m}_{+}$ and
$\mu^{*}\in\mathbb{R}^{k}_{+}$ such that

$\displaystyle\sum\limits_{i\in I}\lambda_{i}^{*}\nabla
f_{i}(x_{0})+\sum\limits_{j\in K}\mu_{j}^{*}\nabla g_{j}(x_{0})=0,$ (2.3)
$\displaystyle\mu_{j}^{*}g_{j}(x_{0})=0,\text{ for all }j\in K,$ (2.4)
$\displaystyle\lambda_{i}^{*}>0,\text{ for all }i\in I.$ (2.5)

Conversely, if there exists $\lambda^{*}\in\mathbb{R}^{m}_{+}$ and
$\mu^{*}\in\mathbb{R}^{k}_{+}$ satisfying (2.3)-(2.5). Then $x_{0}$ is a
Pareto minimizer of CVOP.

Proof: Let $x_{0}$ be a Pareto minimizer of CVOP. Then, using Theorem 2.1,
$x_{0}$ is an optimal solution of the problem $P(f,X,x_{0})$. Hence, from the
standard necessary optimiality conditions, we know that

$\left\langle\sum\limits_{i\in I}\nabla f_{i}(x_{0}),d\right\rangle\geq
0,\text{ for all }d\in T_{\hat{X}(x_{0})}(x_{0}).$ (2.6)

Since, $\hat{X}(x_{0})$ is a convex set, the tangent cone
$T_{\hat{X}(x_{0})}(x_{0})$ is a closed convex cone. Using the fact that the
strong Abadie type regularity condition satisfies at $x_{0}$, (2.6) becomes,

$\displaystyle-\sum\limits_{i\in I}\nabla
f_{i}(x_{0})\in(T_{\hat{X}(x_{0})}(x_{0}))^{\circ}=(V(x_{0}))^{\circ}$ (2.7)

Using (2.2) and the definition of polar cone, we have

$(V(x_{0}))^{\circ}=\\{\sum\limits_{i\in I}\lambda_{i}\nabla
f_{i}(x_{0})+\sum\limits_{r\in K}\mu_{r}\nabla
g_{r}(x_{0}):\lambda\in\mathbb{R}^{m}_{+},\mu\in\mathbb{R}^{k}_{+},\mu_{r}g_{r}(x_{0})=0,\text{
for all }r\in K\\}.$ (2.8)

Therefore, (2.7) says that there exists
$\lambda\in\mathbb{R}^{m}_{+},\mu\in\mathbb{R}^{k}_{+}$ such that
$\mu_{r}g_{r}(x_{0})=0$ for all $r\in K$ and

$0=\sum\limits_{i\in I}\nabla f_{i}(x_{0})+\sum\limits_{i\in
I}\lambda_{i}\nabla f_{i}(x_{0})+\sum\limits_{r\in K}\mu_{r}\nabla
g_{r}(x_{0}).$

Further, the above conditions can be rewritten as

  1. 1.

$0=\sum\limits_{i\in I}\lambda^{*}_{i}\nabla f_{i}(x_{0})+\sum\limits_{r\in
K}\mu^{*}_{r}\nabla g_{r}(x_{0}),$

  2. 2.

$\mu_{r}^{*}g_{r}(x_{0})$ for all $r\in K$,

  3. 3.

$\lambda^{*}_{i}>0$, for all $i\in I$.

where $\lambda^{*}_{i}=\lambda_{i}+1$ for all $i\in I$ and
$\mu^{*}_{r}=\mu_{r}$ for all $r\in K$, which completes the necessary part.
For sufficient part, let there exists $\lambda^{*}\in\mathbb{R}^{m}_{+}$ and
$\mu^{*}\in\mathbb{R}^{k}_{+}$ satisfying (2.3)-(2.5). Then from the Theorem
3.26 of [9], $x_{0}$ is a Geoffrion proper minimizer of CVOP. Hence $x_{0}$ is
a Pareto minimizer of CVOP which completes the proof. $\Box$

###### Remark 2.6

When input data is non-smooth, then we only get necessary optimality condition
which is not same (2.3)-(2.5). Since, for non-smooth case, (2.8) turns out to
be

$(V(x_{0}))^{\circ}=cl\\{\sum\limits_{i\in
I}\lambda_{i}u_{i}+\sum\limits_{r\in
K}\mu_{r}v_{r}:\lambda\in\mathbb{R}^{m}_{+},\mu\in\mathbb{R}^{k}_{+},u_{i}\in\partial
f_{i}(x_{0}),\\\ v_{r}\in\partial g_{r}(x_{0}),\mu_{r}g_{r}(x_{0})=0,\text{
for all }i\in I\text{ and }r\in K\\},$ (2.9)

Hence, the necessary condition for $x_{0}$ to be a Pareto minimizer under the
strong Abadie type regularity condition is given by

$0\in\sum\limits_{i\in I}\partial f_{i}(x_{0})+(V(x_{0}))^{\circ},$

where $V(x_{0})$ is given by (2.9). The verification of the strong Abadie type
regularity condition is not easy which makes Pareto minimizer less algorithm
friendly and, almost all algorithms focus on computing weak Pareto minimizer.

##  3 An Algorithm for computing Pareto minimizers

It is well known that there are lots of scalarization technique to solve CVOP
consider for example, weighted sum scalarization, $\epsilon$-constraint
method, Benson method and many more. The way by which Charnes and Cooper
scalarization is different form others is that there is no need of any
parameters (e.g. weighted sum scalarization needs weights and
$\epsilon\in\mathbb{R}_{+}^{m}$-constraint method needs $\epsilon$ etc.) when
we use this scalarization to compute Pareto minimizers in the algorithm.
Hence, using Charnes and Cooper scalarization for computing Pareto minimizers
is more suitable rather than using other scalarization techniques. Let us
discuss the algorithm to find Pareto minimizers using Charnes and Cooper
scalarization and we shall call the proposed algorithm as CC1. In the
algorithm below, the set $Sol(P_{k})$, denotes the solution set of the scalar
program $P_{k}$.

Step 1. (Initialization) Choose $x_{0}\in X$, set $k:=0$ and
$\hat{\mathbb{N}}=\mathbb{N}\cup\\{0\\}$.

Step 2. (Iterations)

$(i)$ If for $k\in\hat{\mathbb{N}}$, $y_{k}$ be a solution of $P_{k}$ : =
$\left\\{\begin{array}[]{ll}\min\sum\limits_{i\in I}f_{i}(x),&\\\ \text{s. t.
}X_{k}:=\\{x\in X:f_{i}(x)\leq f_{i}(x_{k}),i\in I\\}\end{array}\right.$
i.e., $y_{k}\in Sol(P_{k})$ and $y_{k}=x_{k}$, then stop.

$(ii)$ Else, set $x_{k+1}:=y_{k}$ and $k:=k+1$. Go to step $2(i)$,

The idea of the algorithm can be implemented in the following way. Consider a
tolerance factor $\epsilon_{k}\geq 0$ for $k\geq 1$ associated with the
problem $P_{k}$. If $y_{k}$ solves $P_{k}$ and $y_{k}\neq x_{k}$ but
$\|y_{k}-x_{k}\|\leq\epsilon_{k}$, then accept $x_{k}$ as the solution,
otherwise set $x_{k+1}=y_{k}$ and solve $P_{k+1}$. As $k$ increases, we can
keep on decreasing the tolerance limit $\epsilon_{k}$, i.e.,
$\epsilon_{k}\downarrow 0$ as $k\rightarrow\infty$.

###### Theorem 3.1

Let us consider the problem CVOP with each $f_{i}$ be a convex function and
the feasible set $X$ be a compact set. Then,

  * •

the iterates of the algorithm CC1 is well-defined.

  * •

If $\\{x_{k}\\}$ is a sequence generated by the above algorithm. Then any
limit point of the sequence $\\{x_{k}\\}$ is a Pareto minimizer of the problem
CVOP.

Proof: As $x_{k}\in X_{k}$, each $f_{i}$ is convex and the set $X_{k}$ is non
empty, closed, convex and bounded, the set $Sol(P_{k})$ is non-empty which
proves the first part of the theorem.
If for some $k$, the solution $y_{k}$ of $P_{k}$ is equal to $x_{k}$, then one
stops since by the Theorem 2.1, $x_{k}$ is a Pareto minimizer of the problem
CVOP.
Now suppose for all $k\in\mathbb{N}$, the solution $y_{k}$ of $P_{k}$ is such
that $y_{k}\neq x_{k}$. We shall now generate a sequence
$\\{x_{k}\\}_{k\in\mathbb{N}}$, by defining $x_{k+1}=y_{k}$ for
$k=0,1,\ldots$. Now since $X_{k}$’s are non-empty compact sets which are non-
increasing,i.e., $X_{k+1}\subset X_{k}$, for all $k\in\mathbb{N}$, then by
using Cantor’s Intersection Theorem, we have
$\bigcap\limits_{k=1}^{\infty}X_{k}\not=\emptyset$. Further, as $x_{k}\in
X_{k}$ for all $k\in\mathbb{N}$, $\\{x_{k}\\}$ is bounded and thus has a limit
point, say $x^{*}$. Thus, there exists a subsequence
$\\{x_{k_{j}}\\}_{j\in\mathbb{N}}$ such that $x_{k_{j}}\rightarrow x^{*}$.
Further $x^{*}\in\bigcap\limits_{k=1}^{\infty}X_{k_{j}}$, using the fact that
$\bigcap\limits_{k=1}^{\infty}X_{k_{j}}\neq\emptyset$ as $X_{k_{j+1}}\subset
X_{k_{j}}$ for all $j\in\mathbb{N}$. Hence, $x^{*}\in X_{k_{j}}$ for all
$j\in\mathbb{N}$. Now let us assume on the contrary that $x^{*}$ is not a
Pareto minimizer, i.e., there exists $\hat{x}\in X$ such that

$f_{i}(\hat{x})\leq f_{i}(x^{*}),\text{for all }i\in I\text{ and
}f_{r}(\hat{x})<f_{r}(x^{*}),\text{for some }r\in I.$ (3.1)

Hence,

$\sum\limits_{i\in I}f_{i}(\hat{x})<\sum\limits_{i\in I}f_{i}({x}^{*}).$ (3.2)

Now as $x^{*}\in X_{k_{j}}$ for all $j\in\mathbb{N}$, $f_{i}(x^{*})\leq
f_{i}(x_{k_{j}})$ for all $j$. Thus, (3.1) implies that $f_{i}(\hat{x})\leq
f_{i}(x_{k_{j}})$ for all $j\geq 0$ and $i\in I$. Hence $\hat{x}\in X_{k}$ for
all $k\in\mathbb{N}$. Further, $x_{k_{j}}\in Sol(P_{k_{j-1}})$, for
$j\in\mathbb{N}$ which shows that

$\sum\limits_{i\in I}f_{i}(x_{k_{j}})\leq\sum\limits_{i\in I}f_{i}(x)\text{
for all }x\in X_{k_{j-1}}.$ (3.3)

As we have argued that $\hat{x}\in X_{k}$ for all $k\in\mathbb{N}$, from (3.3)
we have

$\sum\limits_{i\in I}f_{i}(x_{k_{j}})\leq\sum\limits_{i\in I}f_{i}(\hat{x}).$
(3.4)

As $j\rightarrow\infty$ in (3.4) and using the continuity of the functions
$f_{i}$ for all $i\in I$, we get

$\sum\limits_{i\in I}f_{i}(x^{*})\leq\sum\limits_{i\in I}f_{i}(\hat{x}),$

which contradicts the inequality (3.2). Hence $x^{*}$ is a Pareto minimizer of
the problem CVOP which completes the proof of the second part of the theorem.
$\Box$

###### Remark 3.2

We can generalize the Theorem 3.1 by replacing the assumption of convexity of
each function $f_{i}$ by proper, lower semicontinuous and
$\mathbb{R}^{m}_{+}$-convex objective function $f$ and compactness of the
feasible set $X$ by $\mathbb{R}^{m}_{+}$-completeness of the set
$(f(x_{0})-\mathbb{R}^{m}_{+})\cap f(X)$ which means that for all sequences
$\\{a_{n}\\}\subset X$ with $a_{0}=x_{0}$ such that $f(a_{n+1})\leq f(a_{n})$
for all $n\in\mathbb{N}$, there exists $a\in X$ such that $f(a)\leq f(a_{n})$
for all $n\in\mathbb{N}$ (see [2]).

Let us again take a careful look at the algorithm CC1. We don not build any
separate subroutine for solving $P_{k}$ but use the CVX tool box in MATLAB.
Given the problem $P_{k}$ , one of the key ideas here is to see how near the
solution of $P_{k}$ is to $x_{k}$. What may happen that one might have
$x_{k}\in Sol(P_{k})$ and CVX provides a solution $y_{k}\neq x_{k}$. Then we
have missed the Pareto minimizer $x^{k}$ and the run time of the algorithm
gets increased. How does one address this particular issue? An intuitive idea
that comes into mind is that for each $k\in\hat{\mathbb{N}}$, one can try to
see what will happen if we choose $x_{k}$ as the starting solution for
$P_{k}$? Will the algorithm CVX return $x_{k}$ as the solution if $x_{k}$ is
indeed a member of $Sol(P_{k})$ or at least it gives us an $y_{k}$ with
$\|y_{k}-x_{k}\|\leq\epsilon_{k}$, where $\epsilon_{k}>0$ is a threshold value
for rejecting $x_{k}$ as the solution of $P_{k}$. We did some numerical
experiments and found that at least in those cases when $x_{k}\in Sol(P_{k})$
and we consider $x_{k}$ as our starting solution, the algorithm CVX indeed
returned $x_{k}$ as the solution.

Another route often suggested under such circumstances is to convert $P_{k}$
into a strongly convex program so that CVX will give us just a unique solution
for each $k\in\hat{\mathbb{N}}$. In fact let us consider the following scalar
problem $\hat{P}(f,X,x^{*})$ given as

$\left\\{\begin{array}[]{ll}\min\sum\limits_{i\in
I}(f_{i}(x)+\frac{1}{2}\|x-x^{*}\|^{2}),&\\\ {\text{subject to
}}~{}~{}f_{i}(x)-f_{i}(x_{0})\leq 0,&\text{ for all }i\in I,\\\ x\in
X.&\end{array}\right.$

It can be easily proved that $x^{*}$ is a Pareto minimizer of CVOP if and only
if $x^{*}$ is a solution of the scalar strongly convex program
$\hat{P}(f,X,x^{*})$. In fact in the algorithm CC1, we can replace $P_{k}$
with $\hat{P_{k}}$ given as

$\left\\{\begin{array}[]{ll}\min\sum\limits_{i\in
I}(f_{i}(x)+\frac{1}{2}\|x-x^{*}\|^{2}),&\\\ x\in X_{k}.&\end{array}\right.$

However, having a strongly convex problem $P_{k}$ does not completely
alleviate the issue at hand. If we are looking for a solution with very high
accuracy, then for each $k$, our threshold limit is very small and even for
the problem $\hat{P_{k}}$, the routine CVX might return $y_{k}$ as the
solution where $\|y_{k}-x_{k}\|>\epsilon_{k}$. Thus, we believe that we can
just work with $P_{k}$ and the numerical experiments given below showed us
that the algorithm CC1 is working efficiently. The use of scalar problems
similar to $\hat{P}(f,X,x^{*})$ does not appear to be new. In the study of
proximal point method for vector optimization problem, Bonnel et al. [2] use
the following scalar problem at $k$-th step of their algorithm denoted by
ALG1:

$\left\\{\begin{array}[]{ll}\min~{}\langle
f(x)+\frac{\alpha_{k}}{2}\|x-x_{k}\|^{2}e_{k},z_{k}\rangle,&\\\ {\text{subject
to }}~{}~{}f_{i}(x)-f_{i}(x_{k})\leq 0,&\text{ for all }i\in I,\\\ x\in
X,&\end{array}\right.$

where $\\{z_{k}\\}$, $\\{e_{k}\\}$ and $\\{\alpha_{k}\\}$ are some sequences
in the considered ordering cone $C\subset\mathbb{R}^{m}$ and in our case
$C=\mathbb{R}^{m}_{+}$. There are two major differences between our algorithms
CC1 and the algorithm AGL1 of [2]. Firstly, ALG1 needs a new set of parameters
such as $z_{k}$, $e_{k}$ and $\alpha_{k}$ at every step of the algorithm
whereas CC1 does not need any such parameters. Secondly, the stopping criteria
of ALG1 involve solving the multiobjective problem which is not a practical
approach when it comes to implementing the algorithm. On the other hand,
stopping criteria of CC1 is fairly simple which only involve checking the
error is within the considered threshold limit. Further, Bonnel et al. [2]
admitted that it is not easy to implement their algorithm to numerical test
problems whereas the algorithm CC1 is easily applicable to the test problems
using MATLAB software. Similar to Bonnel et al. [2], there are several point-
by-point algorithms to solve vector optimization problems. Some algorithms can
only guarantee that the resultant solution is a weak Pareto minimizer or
critical point, for example, [8], [13], whereas some algorithms need lots of
assumption on objective functions which narrows down the applicability of the
algorithm for applications, for example, [11], [12].

##  4 Numerical Computations

In this section, we consider some convex vector optimization test problems to
show the efficiency of the proposed algorithm CC1. The design of the algorithm
CC1 has a advantage which makes it more useful than evolutionary algorithms,
for example, NSGA-II [6] used to solve CVOP. Firstly, algorithm CC1 has a
convergence analysis which assures that the solution will be a Pareto
solution. On the other hand, NSGA-II does not have any convergence analysis.
Secondly, we can trace Pareto solution corresponding to the efficient frontier
of the problem in the algorithm CC1 while NSGA-II only gives the information
of the efficient frontier. But we need to admit that the run time of algorithm
CC1 is higher than NSGA-II.

In each of the examples considered below, we consider convex bi-objective test
problems where the objective functions $f_{1}$ and $f_{2}$ and the feasible
set $X$ are separately defined. All problems are solved for 200 randomly
generated starting points between the lower bound and upper bound of the
decision variables of the considered problem. At each step, we use CVX
software on the MATLAB platform to solve the scalar problem $P_{k}$ of the
algorithm CC1. In figures,“+” denotes the image of starting point and “o”
denotes the image of the resultant point of the algorithm CC1 under the
objective function $f=(f_{1},f_{2})$. We tested algorithm CC1 on convex vector
optimization problems with smooth as well as non-smooth input data to check
the efficiency of this algorithm. First three examples deals with convex
vector optimization with smooth objective functions and the objective
functions of the last example is non-smooth. For simplicity, we consider only
two dimensional problems but the algorithm CC1 is applicable for higher
dimensional problems as well.

###### Example 4.1

Let $f_{1},f_{2}:\mathbb{R}\to\mathbb{R}$ be defined by
$f_{1}(x)=x^{2},~{}f_{2}(x)=(x-2)^{2}$ and let $X=\\{x\in\mathbb{R}:-10\leq
x\leq 10\\}$ (Schaffer problem [20]).

Figure 1:  Efficient frontier of Example 4.1

###### Example 4.2

Let $f_{1},f_{2}:\mathbb{R}^{2}\to\mathbb{R}$ be defined by
$f_{1}(x_{1},x_{2})=x_{1},~{}f_{2}(x_{1},x_{2})=x_{2}$ and let
$X=\\{(x_{1},x_{2})\in\mathbb{R}^{2}:x_{1}^{2}+x_{2}^{2}\leq 1\\}$ (Jahn
problem [15]).

Figure 2:  Efficient frontier of Example 4.2

###### Example 4.3

Let $f_{1},f_{2}:\mathbb{R}^{2}\to\mathbb{R}$ be defined by
$f_{1}(x_{1},x_{2})=4x_{1}^{2}+4x_{2}^{2},~{}f_{2}(x_{1},x_{2})=(x_{1}-5)^{2}+(x_{2}-5)^{2}$
and $X=\\{(x_{1},x_{2})\in\mathbb{R}^{2}:-5\leq x_{1}\leq 10,-5\leq x_{2}\leq
10\\}$ (Binh problem [1]).

Figure 3:  Efficient frontier of Example 4.3

###### Example 4.4

Let $f_{1},f_{2}:\mathbb{R}^{2}\to\mathbb{R}$ be defined by
$f_{1}(x_{1},x_{2})=\max\\{x_{1},x_{2}\\},~{}f_{2}(x_{1},x_{2})=|x_{1}|+|x_{2}|$
and $X=\\{(x_{1},x_{2})\in\mathbb{R}^{2}:-2\leq x_{1}\leq 2,-2\leq x_{2}\leq
2\\}$.

Figure 4:  Efficient frontier of Example 4.4

## References

  * [1] T. T. Binh.  A multiobjective evolutionary algorithm: The study cases.  In Proceedings of the 1999 Genetic and Evolutionary Computation Conference. Workshop Program, pages 127–128, 1999.
  * [2] H. Bonnel, A. N. Iusem, and B. F. Svaiter.  Proximal methods in vector optimization.  SIAM Journal on Optimization, 15(4):953–970, 2005.
  * [3] S. Chandra, J. Dutta, and C.S. Lalitha.  Regularity conditions and optimality in vector optimization.  Numerical Functional Analysis and Optimization, 25(5-6):479–501, 2004.
  * [4] V. Chankong and Y. Y. Haimes.  Multiobjective decision making: theory and methodology.  Courier Dover Publications, 2008.
  * [5] A. Charnes and W. W. Cooper.  Management models and industrial applications of linear programming.  Technical report, 1961.
  * [6] Kalyanmoy Deb, Amrit Pratap, Sameer Agarwal, and TAMT Meyarivan.  A fast and elitist multiobjective genetic algorithm: NSGA-II.  IEEE transactions on evolutionary computation, 6(2):182–197, 2002\.
  * [7] A. Dhara and J. Dutta.  Optimality conditions in convex optimization: a finite-dimensional view.  CRC Press, 2011.
  * [8] L. M. G. Drummond and A. N. Iusem.  A projected gradient method for vector optimization problems.  Computational Optimization and applications, 28(1):5–29, 2004.
  * [9] M. Ehrgott.  Multicriteria optimization.  Springer-Verlag, Berlin, second edition, 2005.
  * [10] M. Ehrgott and M. M. Wiecek.  Saddle points and pareto points in multiple objective programming.  Journal of Global Optimization, 32(1):11–33, 2005.
  * [11] J. Fliege, LM G. Drummond, and Benar Fux Svaiter.  Newton’s method for multiobjective optimization.  SIAM Journal on Optimization, 20(2):602–626, 2009.
  * [12] J. Fliege and B. F. Svaiter.  Steepest descent methods for multicriteria optimization.  Mathematical Methods of Operations Research, 51(3):479–494, 2000\.
  * [13] E. H. Fukuda and L. M. G. Drummond.  On the convergence of the projected gradient method for vector optimization.  Optimization, 60(8-9):1009–1021, 2011.
  * [14] A. M. Geoffrion.  Proper efficiency and the theory of vector maximization.  Journal of Mathematical Analysis and Applications, 22:618–630, 1968\.
  * [15] J. Jahn.  Vector Optimization.  Springer-Verlag, Berlin, 2004.
  * [16] H. W. Kuhn and A. W. Tucker.  Nonlinear Programming.  Proceedings of 2nd berkeley symposium, 1951.
  * [17] T. Maeda.  Constraint qualifications in multiobjective optimization problems: differentiable case.  Journal of Optimization Theory and Applications, 80(3):483–500, 1994.
  * [18] K. Miettinen.  Nonlinear Multiobjective Optimization.  International Series in Operations Research & Management Science, 12\. Kluwer Academic Publishers, Boston, MA, 1999.
  * [19] R. T. Rockafellar.  Convex Analysis.  Princeton university press, 2015.
  * [20] J. D. Schaffer.  Some experiments in machine learning using vector evaluated genetic algorithms (artificial intelligence, optimization, adaptation, pattern recognition).  PhD Thesis, 1986.