Computer Systems Science & Engineering DOI:10.32604/csse.2021.015451
Article

Saddle Point Optimality Criteria of Interval Valued Non-Linear Programming Problem

Md Sadikur Rahman1, Emad E. Mahmoud2, Ali Akbar Shaikh1,*, Abdel-Haleem Abdel-Aty3,4 and Asoke Kumar Bhunia1

1Department of Mathematics, The University of Burdwan, Burdwan, 713104, India
2Department of Mathematics and Statistics, College of Science, Taif University, P.O. Box 11099, Taif, 21944, Saudi Arabia
3Department of Physics, College of Sciences, University of Bisha, P.O. Box 344, Bisha, 61922, Saudi Arabia
4Physics Department, Faculty of Science, Al-Azhar University, Assiut, 71524, Egypt
*Corresponding Author: Ali Akbar Shaikh. Email: aliashaikh@math.buruniv.ac.in
Received: 22 November 2020; Accepted: 17 February 2021

Abstract: The present paper aims to develop the Kuhn-Tucker and Fritz John criteria for saddle point optimality of interval-valued nonlinear programming problem. To achieve the study objective, we have proposed the definition of minimizer and maximizer of an interval-valued non-linear programming problem. Also, we have introduced the interval-valued Fritz-John and Kuhn Tucker saddle point problems. After that, we have established both the necessary and sufficient optimality conditions of an interval-valued non-linear minimization problem. Next, we have shown that both the saddle point conditions (Fritz-John and Kuhn-Tucker) are sufficient without any convexity requirements. Then with the convexity requirements, we have established that these saddle point optimality criteria are the necessary conditions for optimality of an interval-valued non-linear programming with real-valued constraints. Here, all the results are derived with the help of interval order relations. Finally, we illustrate all the results with the help of a numerical example.

Keywords: Convexity of interval valued function; extended Fritz-John theorem; Interval order relation; Karlin’s constraint; saddle point optimality

1  Introduction

The optimality conditions of a constrained nonlinear programming problem with differentiability (especially, Karush-Kuhn-Tucker conditions) and without differentiability (Kuhn-Tucker and Fritz John optimality criteria) play important roles in the area of nonlinear programming. A few decades ago, these familiar results of optimization had been developed in the crisp environment. However, because of the fluctuation and the randomness of the parameters of a real-life decision-making problem, it has become a difficult task for the decision-makers to develop the optimality conditions of such decision-making problems, including optimization problems in which most of the parameters are imprecise. Thus, the study of optimality with or without differentiability of an imprecise optimization problem is an important research topic.

Depending upon the nature of different parameters of a real-life optimization problem, the following types are categorized

•   Crisp optimization problem

•   Fuzzy optimization problem

•   Stochastic optimization problem

•   Interval optimization problem

In a crisp optimization problem, the objective function and all the constraints are deterministic. The generalized form of a crisp optimization problem is

Find x¯(∈X) if it exists such that

f(x¯)=minx∈X⁡f(x),whereX={x:x∈T,gi(x)≤0,i=1,2,...,m}andf,gi:T(⊆Rn)→R

The equivalent saddle point problem of the above-mention minimization problem is Findx∗∈T,s∗=(sk∗:k=1,2,...,l)∈Rl,sk∗≥0, ifexistsuchthatψ(x∗,s)≤ψ(x∗,s∗)≤ψ(x,s∗),s=(sk:k=1,2,...,l)∈Rl,sk≥0,∀x∈T whereψ(x,s)=f(x)+∑k=1lskgk(x)andf,gk:T(⊆Rn)→R.

Here, the point (x∗,s∗) satisfying the above inequality is called the saddle point of ψ(x,s) . Using this saddle point criterion or differentiability assumption, several researchers established optimality criteria of a nonlinear optimization problem. In this area, Karush [1] derived optimality conditions of constrained nonlinear programming. A few years later, the same conditions were developed independently by Kuhn and Tucker [2]. From that time onwards, these conditions were as familiar as KKT conditions. However, a few years ago, using inequality constraint qualifications and saddle point criteria, John [3] developed the same in a different approach before Kuhn and Tucker.

In a fuzzy optimization problem, the objective function f(x) and all the constraints gi(x) are considered either as fuzzy sets or fuzzy numbers and the inequality of the condition of saddle points is not an ordinary sign—it depends upon the ordering of fuzzy numbers. In this area, Bellman and Zadeh [4] first introduced the concept of fuzzy in the decision-making problem. Then, Delgado et al. [5] proposed the advancement of fuzzy optimization. On the other hand, Wu [6] introduced the saddle point optimality criteria of the fuzzy optimization problem. After that, Gong and Li [7] derived the same in the fuzzy optimization problem. Recently, Li et al. [8] and Bao and Bai [9] made their significant contributions to fuzzy nonlinear programming. In a stochastic optimization problem, the objective function f(x) and all the constraints gi(x) are taken as random variables with proper probability density functions and the inequality sign in the definition of the saddle point is dependent on the nature of random variables. Here, a number of researchers, including Nemirovski et al. [10] Chen et al. [11,12], Bedi et al. [13], Nemirovski and Rubinstein [14], and others contributed their works in non-linear stochastic programming.

Alternatively, if the parameters involved in a nonlinear programming problem are in interval form, then the objective function or constraints or both of the corresponding nonlinear programming problems are in interval form. Thus, a nonlinear programming problem in an interval environment is of the form:

Find x¯∈X, if exists, such that

f(x¯)=[f_(x¯),f¯(x¯)]=⟨fc(x¯),fr(x¯)⟩=minx∈X⁡[f_(x),f¯(x)]=minx∈X⁡⟨fc(x),fr(x)⟩,

whereX={x:x∈T,gk(x)=⟨gkc(x),gkr(x)⟩≤min⟨0,0⟩,k=1,2,...,l},f,gkareinterval−valuedfunctiondefinedonT(⊆Rn)andfc,gkcandfr,gkrarecentreandradiusoffandgi,respectively.

And the equivalent saddle point problem is

Findx¯∈T,s∗=(sk∗:k=1,2,...,l)∈Rl,sk∗≥0,

if exist, such that

ψ(x∗,s)≤minψ(x∗,s∗)≤minψ(x,s∗),s=(sk:k=1,2,...,l)∈Rl,sk≥0,∀x∈T whereψ(x,s)=⟨ψc(x,s),ψr(x,s)⟩=⟨fc(x)+∑k=1lskgkc(x),fr(x)+∑k=1lskgkr(x)⟩ .

The inequality ≤min involved in the above-mentioned problem is not the usual inequality sign. This inequality is dependent on an interval order relation. In this area, Wu [15] derived the KKT conditions of interval-valued non-linear programming problems. In his work, he introduced two different optimization techniques with the help of Ishibuchi and Tanaka [16] partial interval order relations. Recently, Rahman et al. [17] established the optimality conditions of nonlinear interval-valued programming using Bhunia and Samanta’s [18] interval ranking. However, no one has derived the Saddle point optimality criteria for an interval-valued non-linear programming problem till now.

2  Research Gap and Contribution

In the existing literature, several researchers contributed their works on interval analysis (especially, interval ordering). Among them, Bhunia and Samanta [18] proposed a complete interval order relation. There are lots of applications of Bhunia and Samanta [18] order relation in the area of inventory management. Among those, the works of Shaikh and Bhunia [19], Shaikh et al. [20], Rahman et al. [21,22], … etc. are worth-mentioning. The above-mentioned works are the application of interval analyses in inventory control. To the best of our knowledge, no one can apply the interval technique in the other part of the optimization and operations research. The major of parameters of the real-life problems, especially optimization problems are imprecise due to uncertainty. Currently, the development of optimization theory in imprecise environments (Fuzzy, Stochastic, and Interval) has become a popular research topic. Hence, this topic has opened a new horizon in the world of mathematics. In this work, for the first time, the saddle point optimality criteria (like Extended Kuhn Tucker and Fritz-John) of interval-valued non-linear programming problems have been established.

This work is enhanced by introducing the concepts of interval order relations in derivative-free optimization. With the help of Bhunia and Samanta’s [18] interval ranking, the definitions of the minimizer, maximizer, and some beautiful concepts of interval non-linear programming have been proposed. With these concepts, the Interval Fritz-John Saddle point problem and Interval Kuhn-Tucker Saddle point problem are defined. After that, the necessary and sufficient optimality criteria of those problems are derived. Finally, using these saddle optimality criteria, the optimality conditions of a non-linear programming problem have been established. These are the contributions of this work.

3  Some Basic Definitions and Results

In this section, we have mentioned Bhunia and Samanta’s [18] interval order relations. Then, using these definitions of order relations, we have brought into the definitions of convexity, minimizer of an interval-valued function, and some simple results.

3.1 Interval Order Relations

The definitions of Bhunia and Samanta’s [18] ordering, ≥maxand≤min between two intervals in I(R) for both maximization and minimization problem are given below.

where, I(R)={[a¯,a_]:a_,a¯∈Randa_≤a¯}

Definition 1. Let C=[c_,c¯] = ⟨cc,cr⟩ , B = D=[d_,d¯]=⟨dc,dr⟩ ∈I(R).

Then, C ≥max D ⇔{cc≥dc,ifcc≠dccr≤dr,ifcc=dc and C >max D ⇔C≥maxD&C≠D

Definition 2.

C ≤min D ⇔{cc≤dc,ifcc≠dccr≤dr,ifcc=dc and C <min D ⇔C≤minD&C≠D

3.2 Minimizer and Convexity of an Interval-valued Function

Let T⊆Rn and G:T→I(R) be an interval valued function defined by G(x)=[g_(x),g¯(x)]=⟨gc(x),gr(x)⟩ ,

where gc(x)=g¯(x)+g_(x)2,gr(x)=g¯(x)−g_(x)2,

Definition 3. A point x∗∈T is the local minimizer of the interval valued function G(x) if ∃aδ>0suchthat [g_(x∗),g¯(x∗)]≤min[g_(x),g¯(x)],∀x∈B(x∗,δ)∩T,

where B(x∗,δ) is an open ball whose center is at x∗ and radius δ .

Definition 4. A point x∗∈T is a global minimizer of G(x) if

[g_(x∗),g¯(x∗)]≤min[g_(x),g¯(x)],∀x∈T.

Proposition 1. The point x∗∈T is a local minimizer of G(x) iff {x∗islocalminimizerofgc(x),whengc(x)≠constantx∗islocalminimizerofgr(x),whengc(x)=constant

Proof. The proof is immediately followed from the definition of interval ordering.

Definition 5. The interval-valued function G is said to be c-r convex over a convex subset T if G(λx1+(1−λ)x2)≤minλG(x1)+(1−λ)G(x2) for each λ∈(0,1)and∀x1,x2∈T.

Proposition 2. Let T ⊆Rn be convex set and G be an interval valued function of the form G(x)=⟨gc(x),gr(x)⟩. Ifgcandgr are convex, then G(x) is c-r convex.

Proof. The proof follows from the definition of c-r convex and the ≤min order relation.

Lemma 1. Let A=[a_,a¯]=⟨ac,ar⟩,B=[b_,b¯]=⟨bc,br⟩andC=[c_,c¯]=⟨cc,cr⟩∈I(R) .

Then, A≤minB≤minCiff {ac≤bc≤ccifac≠bc≠ccac≤bcandbr≤crifac≠bc=ccar≤brandbc≤ccifac=bc≠ccar≤br≤crifac=bc=cc

Proof. The proof of this Lemma follows from the definitions of interval order relations.

4  The Interval-Valued Minimization and Saddle Point Problems

Here, we have introduced Interval-valued Minimization Problem (IMP), local interval-valued minimization problem, and interval-valued saddle points (Fritz-John and Kuhn-Tucker) problems respectively. Then, we have established the relation between their solutions.

Let T⊆Rn and f,gi:T→I(R) is the interval-valued functions of the form:

F(x)=[f_(x),f¯(x)]=⟨fc(x),fr(x)⟩Gi(x)=[g_k(x),g¯k(x)]=⟨gkc(x),gkr⟩,k=1,2,...,l.

4.1 The Interval-Valued Minimization Problem (IMP)

(IMP)

Find x¯∈X, if exists, such that F(x∗)=⟨fc(x∗),fr(x∗)⟩=minx∈X⁡F(x)=minx∈X⁡⟨fc(x),fr(x)⟩,whereX={x:x∈T,gk(x)=⟨gkc(x),gkr(x)⟩≤min⟨0,0⟩,k=1,2,...,l}

The set X is called the feasible region, x∗ is the solution and F(x∗) is the minimum of the problem IMP.

4.2 The Local Interval-Valued Minimization Problem (LIMP)

(LIMP)

Find x∗inX, such that there exists some open ball B(x∗,δ)centreatx∗withradiousδ>0 x∈B(x∗,δ)∩X⇒F(x∗)≤minF(x)

4.3 The Interval-Valued Fritz John Saddle-Point Problem (IFJSP)

(IFJSP)

Find x∗∈T,ro∗∈R,r∗=(rk∗:k=1,2,...,l)∈Rl,ro∗,rk∗≥0,

If exist, such that

π(x∗,ro∗,r)≤minπ(x∗,ro∗,r∗)≤minπ(x,ro∗,r∗),r=(rk:k=1,2,...,l)∈Rl,rk≥0,∀x∈T where

π(x,ro,r)=⟨πc(x,ro,r),πr(x,ro,r)⟩=roF(x)+∑k=1lrkGk(x)=⟨rofc(x)∑k=1lrkgkc(x),rofr(x)+∑k=1mrkgkr(x)⟩

4.4 The Interval-Valued Kuhn-Tucker Saddle-Point Problem (IKTSP)

(IKTSP)

Find x∗∈T,s∗=(sk∗:k=1,2,...,l)∈Rl,sk∗≥0,

if exist, such that

ψ(x∗,s)≤minψ(x∗,s∗)≤minψ(x,s∗),s=(sk:k=1,2,...,l)∈Rl,sk≥0,∀x∈T

where ψ(x,s)=⟨ψc(x,s),ψr(x,s)⟩=F(x)+∑k=1lskGk(x)=⟨fc(x)+∑k=1lskgkc(x),fr(x)+∑k=1lskgkr(x)⟩

Theorem 1.

If (x∗,ro∗,r∗) is the solution of IFJSP and ro∗>0,then(x∗,r∗/ro∗) is a solution of IKTSP. Conversely, if (x∗,s∗) is the solution of IKTSP, then (x∗,1,s∗) is the solution of IFJSP.

Proof.

First, let (x∗,ro∗,r∗) be a solution of IFJSP, then

π(x∗,ro∗,r)≤minπ(x∗,ro∗,r∗)≤minπ(x,ro∗,r∗),r=(rk:k=1,2,...,l)∈Rl,rk≥0,∀x∈T

Now, by Lemma 1, four cases may arise:

Case−1:πc(x∗,ro∗,r)≠πc(x∗,ro∗,r∗)≠πc(x,ro∗,r∗)Case−2:πc(x∗,ro∗,r)≠πc(x∗,ro∗,r∗)=πc(x,ro∗,r∗)Case−3:πc(x∗,ro∗,r)=πc(x∗,ro∗,r∗)≠πc(x,ro∗,r∗)Case−4:πc(x∗,ro∗,r)=πc(x∗,ro∗,r∗)=πc(x,ro∗,r∗)

Case-1 If πc(x∗,ro∗,r)≠πc(x∗,ro∗,r∗)≠πc(x,ro∗,r∗) ,

then, πc(x∗,ro∗,r)<πc(x∗,ro∗,r∗)<πc(x,ro∗,r∗)

i.e.,

ro∗fc(x∗)+∑k=1lrkgkc(x∗)<ro∗fc(x∗)+∑k=1lrk∗gkc(x∗)<ro∗fc(x)+∑k=1lrk∗gkc(x)

i.e.,

fc(x∗)+∑k=1l(rk/ro∗)gkc(x∗)<fc(x∗)+∑k=1l(rk/ro∗)gkc(x∗)<fc(x)+∑k=1l(rk/ro∗)gkc(x)

i.e.,

ψc(x∗,r/ro∗)<ψc(x∗,r∗/ro∗)<ψc(x,r∗/ro∗)i.e.,ψ(x∗,r/ro∗)≤minψ(x∗,r∗/ro∗)≤minψc(x,r∗/ro∗)

Case-2 If πc(x∗,ro∗,r)≠πc(x∗,ro∗,r∗)=πc(x,ro∗,r∗) ,

then,

πc(x∗,ro∗,r)<πc(x∗,ro∗,r∗)andπr(x∗,ro∗,r∗)≤πr(x,ro∗,r∗)ro∗fc(x∗)+∑k=1lrkgkc(x∗)<ro∗fc(x∗)+∑k=1lrk∗gkc(x∗)andro∗fr(x∗)+∑k=1lrkgkr(x∗)≤ro∗fr(x)+∑k=1lrk∗gkr(x)

i.e.,fc(x∗)+∑k=1l(rk/ro∗)gkc(x∗)<fc(x∗)+∑k=1l(rk/ro∗)gkc(x∗)

andfr(x∗)+∑k=1l(rk/ro∗)gkr(x∗)≤fr(x∗)+∑k=1l(rk/ro∗)gkr(x∗)[sincero∗>0]i.e.,ψc(x∗,ri/ro∗)<ψc(x∗,ri∗/ro∗)andψr(x∗,ri∗/ro∗)≤ψr(x,ri∗/ro∗)i.e.,ψ(x∗,ri/ro∗)≤minψ(x∗,ri∗/ro∗)≤minψr(x,ri∗/ro∗).

Case-3 If πc(x∗,ro∗,r)=πc(x∗,ro∗,r∗)≠πc(x,ro∗,r∗)

then, similarly as Case-2, we have obtained ψ(x∗,ri/ro∗)≤minψ(x∗,ri∗/ro∗)≤minψr(x,ri∗/ro∗).

Case-4 If πc(x∗,ro∗,r)=πc(x∗,ro∗,r∗)=πc(x,ro∗,r∗) , then similarly as Case-1, we get ψr(x∗,ri/ro∗)≤ψr(x∗,ri∗/ro∗)≤ψr(x,ri∗/ro∗)i.e.,ψ(x∗,ri/ro∗)≤minψ(x∗,ri∗/ro∗)≤minψr(x,ri∗/ro∗).

Hence, combining all the cases first part of the theorem is proved.

Conversely, let (x∗,s∗) be a solution of IKTSP.

Then,

ψ(x∗,s)≤minψ(x∗,s∗)≤minψ(x,s∗),s=(sk:k=1,2,...,l)∈Rl,sk≥0,∀x∈T.

where =1.F(x)+∑k=1lskGk(x)=⟨1.fc(x)+∑k=1lskgkc(x),1.fr(x)+∑k=1lskgkr(x)⟩=π(x,1,s)

Hence, π(x∗,1,s)≤minπ(x∗,1,s∗)≤minπ(x,1,s∗),s=(sk:k=1,2,...,l)∈Rl,sk≥0,∀x∈T.

This completes the proof.

5  Optimality Conditions of IMP

5.1 Sufficient Optimality of IMP

The sufficient optimality criterion has been derived without convexity assumption of the interval minimization problem (IMP).

Theorem 2. If (x∗,s∗) is the solution of IKTSP, then x∗ is a solution of IMP. If (x∗,so∗,s∗) is a solution of IFJSP and so∗>0, then x∗ is a solution of IMP.

Proof.

First Part.

Let (x∗,s∗) be a solution of IKTSP.

Then, ∀s=(sk:k=1,2,...,l)∈Rl,sk≥0,∀x∈T, ψ(x∗,s)≤minψ(x∗,s∗)≤minψ(x,s∗). where ψ(x,s)=⟨ψc(x,s),ψr(x,s)⟩=F(x)+∑k=1lskGk(x)=⟨fc(x)+∑k=1lskgkc(x),fr(x)+∑k=1lskgkr(x)⟩.

Then, by Lemma 1., four cases may arise.

Case-1. If ψc(x∗,s)≠ψc(x∗,s∗)≠ψc(x,s∗) ,

then ψc(x∗,s)<ψc(x∗,s∗)<ψc(x,s∗),∀x∈T,s∈Rl, where, ψc(x,s)=fc(x)+∑k=1lskgkc(x). By the Sufficient Optimality Criteria for real-valued objective function, we can say that fc(x∗)<fc(x),i.e.,F(x∗)≤minF(x).

Case-2. If ψc(x∗,s)≠ψc(x∗,s∗)=ψc(x,s∗) ,

then ψc(x∗,s)<ψc(x∗,s∗)andψr(x∗,s∗)≤ψr(x,s∗),∀x∈T,s∈Rl.

Now, from first inequality, we have

fc(x∗)+∑k=1lskgkc(x∗)<fc(x∗)+∑k=1lsk∗gkc(x∗) (1)

⇒∑k=1l(sk−sk∗)gkc(x∗)<0∀sk≥0,k=1,2,...,lNow,foranyj,1≤j≤l,letsk=sk∗,i=1,2,...,j−1,j+1,...,m,sj=s∗j+1

Which gives gjc(x∗)<0. Repeating this ∀k,wegetgkc(x∗)<0 .

Now, since,sk∗≥0,andgkc(x∗)<0,∑k=1lsk∗gkc(x∗)≤0 (2)

But, again from (1) by setting sk=0 ,we obtain

fc(x∗)<fc(x∗)+∑k=1lsk∗gkc(x∗)or,∑k=1lsk∗gkc(x∗)>0 (3)

Hence, from (2) and (3), we have ∑k=1lsk∗gkc(x∗)=0

Now, from ψc(x∗,s∗)=ψc(x,s∗) , we get

fc(x∗)+∑k=1lsk∗gkc(x∗)=fc(x)+∑k=1lsk∗gkc(x)i.e.,fc(x∗)=fc(x)+∑k=1lsk∗gkc(x)[∵∑k=1lsk∗gkc(x)=0],∀x∈T

which is possible only if sk∗=0,∀k=1,2,...,landfc(x) is constant function.

So, in this case fc(x∗)=fc(x) .

Thus, from ψr(x∗,u∗)≤ψr(x,u∗) , we get

fr(x∗)+∑k=1lsk∗gkr(x∗)≤fr(x)+∑k=1lsk∗gkr(x)i.e.,fr(x∗)≤fr(x),[∵sk∗=0]

Hence, F(x∗)≤minF(x).

Case-3 If ψc(x¯,u)=ψc(x¯,u¯)≠ψc(x,u¯)

then,

ψr(x∗,s)≤ψr(x∗,s∗)andψc(x∗,s∗)<ψc(x,s∗),∀x∈T,s∈Rl.Fromψc(x∗,s)=ψc(x∗,s∗),wegetsk=0,∀k=1,2,...,landfromψc(x∗,s∗)ltψc(x,s∗),wegetfc(x∗)+∑k=1lsk∗gkc(x∗)ltfc(x∗)+∑k=1lskgkc(x),∀sk⇒fc(x∗)+∑k=1lsk∗gkc(x∗)ltfc(x)+∑k=1lsk∗gkc(x),forsk=sk∗⇒fc(x∗)ltfc(x)[∵sk∗=0]i.e.,F(x∗)≤minF(x)