Return to Article Details Approximations of objective function and constraints in bi-criteria optimization problems

Approximations of objective function and constraints in bi-criteria optimization problems

Ionut Traian Luca $^{*}$ Dorel I. Duca $^{∙}$

June 14, 2018. Accepted: October 23, 2018. Published online: February 7, 2019.

$^{*}$ Faculty of Business, Babes-Bolyai University, e-mail: ionut.luca@tbs.ubbcluj.ro

$∙$ Faculty of Mathematics and Computer Science, Babes-Bolyai University, e-mail: dduca@math.ubbcluj.ro

In this paper we study approximation methods for solving bi-criteria optimization problems. Initial problem is approximated by a new one which has the components of the objective and the constraints replaced by their approximation functions. Components of the objective function are first and second order approximated and constraints are first order approximated. Conditions such that efficient solution of the approximate problem will remain efficient for initial problem and reciprocally are studied. Numerical examples are developed to emphasize the importance of these conditions.

MSC. 90C46, 90C59

Keywords. efficient solution, bi-criteria optimization, $η$ -approximation, invex and incave function

1 Introduction

Bi-criteria optimization problems are quite often used as mathematical models for all kind of phenomena generated by real-world and theoretical situations. As examples we might mention portfolio theory [ 4 ] , energy field [ 5 ] , data analysis [ 3 ] , logistics [ 6 ] .

Among methods widely used to solve bi-criteria optimization problems are “scalarization" methods [ 2 ] (weighting problem, $k^{t h}$ objective Lagrangian problem, $k^{t h}$ objective $ε$ -constrained problem). Sometimes mathematical models are highly complex and thus using approximation problems might be a more efficient method to solve bi-criteria optimization problems.

This article is analyzing conditions such that efficient solution of a certain approximate problem will remain efficient for the initial problem and reciprocally. Approximate problem consists of replacing components of objective function and also constraints with their approximate functions.

2 Basic concepts

Let $X$ be a set in $R^{n}$ , $x_{0}$ an interior point of $X$ , $η : X \times X \to X$ and $f : X \to R$ . If $f$ is differentiable at $x_{0}$ then we denote:

F^{1} (x) = f (x_{0}) + \nabla f (x_{0}) η (x, x_{0})

and call it first $η$ -approximation of $f$ , while if $f$ is twice differentiable at $x_{0}$ then we denote:

F^{2} (x) = f (x_{0}) + \nabla f (x_{0}) η (x, x_{0}) + \frac{1}{2} η {(x, x_{0})}^{T} \nabla^{2} f (x_{0}) η (x, x_{0}) .

and call it second $η$ -approximation of $f$ .

Definition 1

Let $X$ be a nonempty set of $R^{n}$ , $x_{0}$ an interior point of $X$ , $f : X \to R$ a function differentiable at $x_{0}$ and $η : X \times X \to X$ . Then function $f$ is: invex at $x_{0}$ with respect to $η$ if for all $x \in X$ we have:

f (x) - f (x_{0}) \geq \nabla f (x_{0}) η (x, x_{0})

or equivalently:

f (x) \geq F^{1} (x);

incave at $x_{0}$ with respect to $η$ if for all $x \in X$ we have:

f (x) - f (x_{0}) \leq \nabla f (x_{0}) η (x, x_{0})

or equivalently

f (x) \leq F^{1} (x);

avex at $x_{0}$ with respect to $η$ if it is both invex and incave at $x_{0}$ w.r.t. $η$ .

If function $f$ is invex, respectively incave or avex we denote invex $^{1}$ , respectively incave $^{1}$ or avex $^{1}$ .

Definition 2

Let $X$ be a nonempty set of $R^{n}$ , $x_{0}$ an interior point of $X$ , $f : X \to R$ a function twice differentiable at $x_{0}$ and $η : X \times X \to X$ . Then function $f$ is:
second order invex at $x_{0}$ with respect to $η$ if for all $x \in X$ we have:

f (x) - f (x_{0}) \geq \nabla f (x_{0}) η (x, x_{0}) + \frac{1}{2} η {(x, x_{0})}^{T} \nabla^{2} f (x_{0}) η (x, x_{0})

or equivalently:

f (x) \geq F^{2} (x);

second order incave at $x_{0}$ with respect to $η$ if for all $x \in X$ we have:

f (x) - f (x_{0}) \leq \nabla f (x_{0}) η (x, x_{0}) + \frac{1}{2} η {(x, x_{0})}^{T} \nabla^{2} f (x_{0}) η (x, x_{0})

or equivalently:

f (x) \leq F^{2} (x);

second order avex at $x_{0}$ with respect to $η$ if it is both second order invex and second order incave at $x_{0}$ w.r.t. $η$ .

If function $f$ is second order invex, respectively second order incave or second order avex we denote invex $^{2}$ , respectively incave $^{2}$ or avex $^{2}$ .

Let $X$ be a nonempty set of $R^{n}$ , $x_{0}$ an interior point of $X, η : X \times X \to X$ , $T$ and $S$ index sets, $f = (f_{1}, f_{2}) : X \to R^{2}$ and $g_{t}, h_{s} : X \to R, (t \in T, s \in S)$ functions.

We consider the bi-criteria optimization problem $(P_{0}^{0, 0})$ , defined as:

{\begin{cases} min (f_{1}, f_{2}) (x) \\ x = (x_{1}, x_{2}, . . ., x_{n}) \in X \\ g_{t} (x) \leq 0, t \in T \\ h_{s} (x) = 0, s \in S . \end{cases}

Assuming that functions $f_{1}, f_{2}$ , are differentiable of order $i, j \in {1, 2}$ and functions $g_{t}, (t \in T), h_{s}, (s \in S)$ are first order differentiable, we will approximate original problem $(P_{0}^{0, 0})$ by problems $(P_{1}^{i, j})$ :

{\begin{cases} min (F_{1}^{i}, F_{2}^{j}) (x) \\ x = (x_{1}, x_{2}, . . ., x_{n}) \in X \\ G_{t}^{1} (x) \leq 0, t \in T \\ H_{s}^{1} (x) = 0, s \in S \end{cases}

where $(i, j) \in {(1, 0), (1, 1), (2, 0), (2, 1), (2, 2)}$ and $F_{1}^{0} = f_{1}, F_{2}^{0} = f_{2}$ .

We denote by

F^{k} = {x \in X : G_{t}^{k} (x) \leq 0, t \in T, H_{s}^{k} (x) = 0, s \in S, k \in {0, 1}}

the set of feasible solutions for bi-criteria optimization problem $(P_{k}^{i, j})$ , where $(i, j) \in {(1, 0), (1, 1), (2, 0), (2, 1), (2, 2)}$ and $k \in {0, 1}$ .

3 Approximate problems and relation to initial problem

In this section we will study the conditions such that efficient solution of approximated problems $(P_{1}^{1, 0})$ , $(P_{1}^{2, 0})$ , $(P_{1}^{2, 1})$ and $(P_{1}^{2, 2})$ will remain efficient also for initial problem $(P_{0}^{0, 0})$ and reciprocally.

Conditions for the relation $(P_{0}^{0, 0})$ vs. $(P_{1}^{1, 1})$ have been studied in [ 1 ] so we will not analyze them anymore.

By approximating also the feasible set it is important to determine conditions such that $F^{0} \subseteq F^{1}$ and $F^{1} \subseteq F^{0}$ . These inclusions were studied in [ 1 ] . We will use them in our work, so we will briefly present the Theorems stating these inclusions.

Theorem 3

[ 1 ] . Let $X$ be a nonempty set of $R^{n}$ , $x_{0}$ an interior point of $X, η : X \times X \to X$ , and $g_{t}, h_{s} : X \to R, (t \in T, s \in S)$ .

Assume that:

for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and invex $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,

then

F^{0} \subseteq F^{1} .

Theorem 4

[ 1 ] . Let $X$ be a nonempty set of $R^{n}$ , $x_{0}$ an interior point of $X, η : X \times X \to X$ , and $g_{t}, h_{s} : X \to R, (t \in T, s \in S)$ .

Assume that

for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and incave $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,

then

F^{1} \subseteq F^{0} .

Theorem 5

Assume that:

$x_{0} \in F^{0}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and invex $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is twice differentiable at $x_{0}$ and invex $^{2}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{1}^{2, 0})$ , then $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ .

Proof â–¼

x_{0}

being an efficient solution for

(P_{1}^{2, 0})

, implies that

∄ x \in F^{1} s . t . (F_{1}^{2} (x), f_{2} (x)) \leq (F_{1}^{2} (x_{0}), f_{2} (x_{0})) .

Conditions $b)$ and $c)$ imply that

F^{0} \subseteq F^{1}

and thus

∄ x \in F^{0} s . t . (F_{1}^{2} (x), f_{2} (x)) \leq (F_{1}^{2} (x_{0}), f_{2} (x_{0})) .

Let’s assume that $x_{0}$ is not an efficient solution for $(P_{0}^{0, 0})$ . Then

\exists y \in F^{0} s . t . (f_{1} (y), f_{2} (y)) \leq (f_{1} (x_{0}), f_{2} (x_{0}))

which implies that $\exists y \in F^{0} s . t .$

\begin{array}{r} {\begin{array}{c} f_{1} (y) < f_{1} (x_{0}) \\ f_{2} (y) ≦ f_{2} (x_{0}) \end{array} \end{array}

\begin{array}{r} {\begin{array}{c} f_{1} (y) ≦ f_{1} (x_{0}) \\ f_{2} (y) < f_{2} (x_{0}) . \end{array} \end{array}

Because $f_{1}$ is invex $^{2}$ at $x_{0}$ with respect to $η$ we get $F_{1}^{2} (y) \leq f_{1} (y), \forall y \in F^{0}$ .
Because $η (x_{0}, x_{0}) = 0$ we get $f_{1} (x_{0}) = F_{1}^{2} (x_{0})$ . Thus from (2) we get that $\exists y \in F^{0} s . t .$

{\begin{matrix} F_{1}^{2} (y) < F_{1}^{2} (x_{0}) \\ f_{2} (y) ≦ f_{2} (x_{0}) \end{matrix}

which contradicts (1) and from (3) we get that $\exists y \in F^{0} s . t .$

{\begin{matrix} F_{1}^{2} (y) ≦ F_{1}^{2} (x_{0}) \\ f_{2} (y) < f_{2} (x_{0}) \end{matrix}

which contradicts (1).
In conclusion $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ .

Proof â–¼

Theorem 6

Assume that:

$x_{0} \in F^{1}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and incave $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is twice differentiable at $x_{0}$ and incave $^{2}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ , then $x_{0}$ is an efficient solution for $(P_{1}^{2, 0})$ .

Proof â–¼

x_{0}

being an efficient solution for

(P_{0}^{0, 0})

, implies that

∄ x \in F^{0} s . t . (f_{1} (x), f_{2} (x)) \leq (f_{1} (x_{0}), f_{2} (x_{0})) .

Conditions $b)$ and $c)$ imply that

F^{1} \subseteq F^{0}

and thus

∄ x \in F^{1} s . t . (f_{1} (x), f_{2} (x)) \leq (f_{1} (x_{0}), f_{2} (x_{0})) .

Let’s assume that $x_{0}$ is not an efficient solution for $(P_{1}^{2, 0})$ . Then

\exists y \in F^{1} s . t . (F_{1}^{2} (y), f_{2} (y)) \leq (F_{1}^{2} (x_{0}), f_{2} (x_{0}))

which implies that $\exists y \in F^{1} s . t .$

\begin{array}{r} {\begin{array}{c} F_{1}^{2} (y) < F_{1}^{2} (x_{0}) \\ f_{2} (y) ≦ f_{2} (x_{0}) \end{array} \end{array}

\begin{array}{r} {\begin{array}{c} F_{1}^{2} (y) ≦ F_{1}^{2} (x_{0}) \\ f_{2} (y) < f_{2} (x_{0}) . \end{array} \end{array}

Because $f_{1}$ is incave $^{2}$ at $x_{0}$ with respect to $η$ we get $f_{1} (y) \leq F_{1}^{2} (y), \forall y \in F^{1}$ .
Because $η (x_{0}, x_{0}) = 0$ we get $f_{1} (x_{0}) = F_{1}^{2} (x_{0})$ . Thus from (5) we get that $\exists y \in F^{1} s . t .$

{\begin{cases} f_{1} (y) < f_{1} (x_{0}) \\ f_{2} (y) ≦ f_{2} (x_{0}) \end{cases}

which contradicts (4) and from (6) we get that $\exists y \in F^{1} s . t .$

{\begin{matrix} f_{1} (y) ≦ f_{1} (x_{0}) \\ f_{2} (y) < f_{2} (x_{0}) \end{matrix}

which contradicts (4).

In conclusion $x_{0}$ is an efficient solution for $(P_{1}^{2, 0})$ .

Proof â–¼

Theorem 7

Assume that:

$x_{0} \in F^{0}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and invex $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is differentiable at $x_{0}$ and invex $^{1}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{1}^{1, 0})$ , then $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ .

Proof â–¼

Proof is similar to Theorem 5.

Proof â–¼

Theorem 8

Assume that:

$x_{0} \in F^{1}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and incave $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is differentiable at $x_{0}$ and incave $^{1}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ , then $x_{0}$ is an efficient solution for $(P_{1}^{1, 0})$ .

Proof â–¼

Proof is similar to Theorem 6.

Proof â–¼

Theorem 9

Assume that:

$x_{0} \in F^{0}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and invex $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is twice differentiable at $x_{0}$ and invex $^{2}$ at $x_{0}$ with respect to $η$ ,
$f_{2}$ is differentiable at $x_{0}$ and invex $^{1}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{1}^{2, 1})$ , then $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ .

Proof â–¼

Proof is similar to Theorem 5.

Proof â–¼

Theorem 10

Assume that:

$x_{0} \in F^{1}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and incave $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is twice differentiable at $x_{0}$ and incave $^{2}$ at $x_{0}$ with respect to $η$ ,
$f_{2}$ is differentiable at $x_{0}$ and incave $^{1}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ , then $x_{0}$ is an efficient solution for $(P_{1}^{2, 1})$ .

Proof â–¼

Proof is similar to Theorem 6.

Proof â–¼

Theorem 11

Assume that:

$x_{0} \in F^{0}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and invex $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is twice differentiable at $x_{0}$ and invex $^{2}$ at $x_{0}$ with respect to $η$ ,
$f_{2}$ is twice differentiable at $x_{0}$ and invex $^{2}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{1}^{2, 2})$ , then $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ .

Proof â–¼

Proof is similar to Theorem 5.

Proof â–¼

Theorem 12

Assume that:

$x_{0} \in F^{1}$ ,
for each $t \in T$ , the function $g_{t}$ is differentiable at $x_{0}$ and incave $^{1}$ at $x_{0}$ with respect to $η$ ,
for each $s \in S$ , the function $h_{s}$ is differentiable at $x_{0}$ and avex $^{1}$ at $x_{0}$ with respect to $η$ ,
$f_{1}$ is twice differentiable at $x_{0}$ and incave $^{2}$ at $x_{0}$ with respect to $η$ ,
$f_{2}$ is twice differentiable at $x_{0}$ and incave $^{2}$ at $x_{0}$ with respect to $η$ ,
$η (x_{0}, x_{0}) = 0$ .

If $x_{0}$ is an efficient solution for $(P_{0}^{0, 0})$ , then $x_{0}$ is an efficient solution for $(P_{1}^{2, 2})$ .

Proof â–¼

Proof is similar to Theorem 6.

Proof â–¼

4 Numerical examples

In the above theorems, conditions referring to invexity, incavity or avexity of functions are essential to ensure that efficient solution of the initial problem remains efficient for the approximate problem and reciprocally. If those conditions are not fulfill it is possible either that efficient solution of initial problem remains efficient for the approximate problem (and reciprocally) or it does not remain efficient.

Example 1

Let the initial bi-criteria optimization problem $(P_{0}^{0, 0})$ be:

{\begin{cases} min (x_{1} - 2 x_{2}; x_{1} + x_{2}) \\ - x_{1} x_{2} + 1 \leq 0 \\ x_{1}; x_{2} \geq 0 \end{cases}

An efficient solution of problem $(P_{0}^{0, 0})$ is $x_{0} = (1, 1) \in F^{0}$ and the value of the objective function in $x_{0}$ is $f (1, 1) = (- 1, 2)$ . First and second approximate functions for the components of the objective function in $x_{0} = (1, 1)$ are:

F_{p}^{1} (x) = f_{p} (x_{0}) + \nabla f_{p} (x_{0}) η (x, x_{0}), p \in {1, 2}

and

F_{p}^{2} (x) = f_{p} (x_{0}) + \nabla f_{p} (x_{0}) η (x, x_{0}) + \frac{1}{2} η {(x, x_{0})}^{T} \nabla^{2} f_{p} (x_{0}) η (x, x_{0}), p \in {1, 2},

while first approximate functions for the constraint is:

G_{t}^{1} (x) = g_{t} (x_{0}) + \nabla g_{t} (x_{0}) η (x, x_{0}), t \in {1, 2, 3} .

Considering $η (x, x_{0}) = x - x_{0}$ we get:

F_{1}^{i} (x) = F_{1}^{i} (x) = x_{1} - 2 x_{2}, i \in {0, 1, 2}

F_{2}^{j} (x) = F_{2}^{j} (x) = x_{1} + x_{2}, j \in {0, 1, 2}

and

G_{1}^{1} (x) = - x_{1} - x_{2} + 2, G_{2}^{1} (x) = x_{1}, G_{3}^{1} (x) = x_{2}

Consequently, the approximate problems $(P_{1}^{i, j})$ , with $(i, j) \in {(1, 0), (1, 1), (2, 0), (2, 1), (2, 2)}$ are:

{\begin{cases} min (x_{1} - 2 x_{2}; x_{1} + x_{2}) \\ - x_{1} - x_{2} + 2 \leq 0 \\ x_{1}; x_{2} \geq 0 \end{cases}

Calculating the value of objective function for problem $(P_{1}^{i, j})$ in $x = (0, 2) \in F^{1}$ we obtain:

(F_{1}^{i}, F_{2}^{j}) (0, 2) = (- 4, 2) < (- 1, 2) = (F_{1}^{i}, F_{2}^{j}) (1, 1)

where $(i, j) \in {(1, 0), (1, 1), (2, 0), (2, 1), (2, 2)}$ , which proves that $x_{0} = (1, 1) \in F^{1}$ is not an efficient solution for approximate problem $(P_{1}^{i, j})$ . â–¡

Example 2

Let the initial bi-criteria optimization problem $(P_{0}^{0, 0})$ be:

\begin{array}{r} {\begin{cases} min (x_{1}^{2} + (x_{2} - π - 1)^{2}; (x_{1} + \frac{1}{10})^{2} - \frac{1}{2} (x_{2} + 1)^{2}) \\ - x_{1} - \sin x_{1} + x_{2} \leq 0 \\ x_{1} - \frac{5 π}{2} \leq 0 \\ x_{1}; x_{2} \geq 0 \end{cases} \end{array}

An efficient solution of problem $(P_{0}^{0, 0})$ is $x_{0} = (\frac{π}{2}, 1 + \frac{π}{2}) \in F^{0}$ and the value of the objective function in $x_{0}$ is $f (\frac{π}{2}, 1 + \frac{π}{2}) = (\frac{π^{2}}{2}; \frac{π^{2}}{8} - \frac{9 π}{10} - \frac{199}{100})$ .