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

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)

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

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

Similar to case-1, we can say that F(x∗)≤minF(x) .

Combining all the cases, the proof of the first part completes.

Second Part. The proof of this part follows from Theorem 1. and First part of this theorem.

5.2 Extended Fritz-John Saddle-Point Optimality Theorem

Here, we have derived the conditions for which the solution of IMP will be necessarily the solution of IFJSP. For this purpose, we have stated and proved Extended Fritz-John saddle point necessary optimality theorem. Before stating the theorem, we have stated the following Lemma (Mangasarian [23]):

Lemma 2. Let T (≠ϕ)⊆ Rn . Also, let f1,f2andf3bem1,m2,m3 dimensional convex vector-valued function on T and gk(k=1,2,...,l) be convex functions on T .

If ⟨f1(x)<0,f2(x)≤0,f3(x)≤0gk(x)≤0,k=1,2,...,l⟩ has no solution, x∈T then there exist p1∈Rm1,p2∈Rm2,p3∈Rm3andq=(qk:k=1,2,...,l)∈Rl

such that

∑i=1m1p1if1i(x)+∑i=1m2p2if2i(x)+∑i=1m3p3if3i(x)+∑k=1lqkgk(x)≥0,∀x∈Tandp1i,p2i,p3i≥0

where fj=(fji:i=1,2,...,mj,j=1,2,3),pj=(pji:i=1,2,...,mj)

Theorem 3. Let T ⊆Rn be a non-empty convex set, f be interval-valued c-r convex function on T and gk(k=1,2,...,l) be real-valued convex functions on T . If x∗ is a solution of IMP, then (x∗,ro∗,r∗)(ro∗∈R,r∗=(rk∗:k=1,2,...,l),ro∗≥0,rk∗≥0) is a solution of IFJSP and ∑k=1lrk∗gk(x∗)=0 , where F(x)=⟨fc(x),fr(x)⟩ .

Proof. Since x∗ is a solution of MP, then

F(x∗)≤minF(x),∀x∈T.i.e.,either,fc(x∗)<fc(x)iffc(x∗)≠fc(x)or,fr(x∗)≤fr(x)iffc(x∗)=fc(x).

Now, two cases may arise:

Case-1.

Iffc(x∗)≠fc(x),then⟨fc(x)−fc(x∗)<0gk(x)<0,k=1,2,...,l⟩ has no solution ∀x∈T.

By Lemma 2, there exist ro∗∈R,r=(rk:k=1,2,...,l)∈Rl,ro∗≥0,rk≥0 such that

ro∗[fc(x)−fc(x∗)]+∑k=1lrk∗gk(x)≥0∀x∈T. (4)

Now,puttingx=x∗in(4),wehave∑k=1lrk∗gk(x∗)≥0 (5)

But,sincerk≥0,gk(x∗)<0,wehave∑k=1lrk∗gk(x∗)≤0 (6)

Hence from (5) and (6), we have ∑k=1lrk∗gk(x∗)=0

Again from (4), we have

ro∗[fc(x)−fc(x∗)]+∑k=1lro∗gk(x)≥0or,ro∗fc(x∗)≤ro∗fc(x)+∑k=1lro∗gk(x)

or,ro∗fc(x∗)+∑k=1lro∗gk(x∗)≤ro∗fc(x)+∑k=1lro∗gk(x) (7)

Asgk(x∗)≤0,then∑k=1lrkgk(x∗)≤0∀r=(rk:k=1,2,...,l)∈Rl,rk≥0.Hence,ro∗fc(x∗)+∑k=1lrkgk(x∗)≤ro∗fc(x∗)+∑k=1lrk∗gk(x∗)[∵∑k=1lrk∗gk(x∗)=0] (8)

Therefore, from (7) and (8), we obtain

ro∗fc(x∗)+∑k=1lrkgk(x∗)≤ro∗fc(x∗)+∑k=1lrk∗gk(x∗)≤ro∗fc(x)+∑k=1lrk∗gk(x)

Case-2. If fc(x∗)=fc(x) ,

then

fr(x∗)≤fr(x)i.e.,fr(x∗)≤fr(x∗)≤fr(x)

i.e.,ro∗fr(x∗)+∑k=1lrk.0≤ro∗fr(x∗)+∑k=1lrk∗.0≤ro∗fr(x)+∑k=1lrk∗.0

Combining both cases, we have obtained

ro∗⟨fc(x∗),fr(x∗)⟩+∑k=1lrk⟨gk(x∗),0⟩≤minro∗⟨fc(x∗),fr(x∗)⟩+∑k=1lrk∗⟨gk(x∗),0⟩≤minro∗⟨fc(x),fr(x)⟩+∑k=1lrk∗⟨gk(x),0⟩

Hence, the proof is complete.

5.3 Extended Kuhn-Tucker Saddle-Point Optimality Theorem

Here, we have derived the necessary conditions (Extended Kuhn-Tucker saddle point optimality) for which the solution of (IMP) will be necessarily the solution of (IKTSP). Before stating this theorem, we have first stated Karlin’s constraint qualification which will be required as a hypothesis of this theorem:

Karlin’s Type Constraint Qualification

Let T ⊆ Rn be non-empty convex set and g=(gk:k=1,2,...,l) l-dimensional convex vector-valued function on T . Then, g is said to satisfy constraint qualification of Karlin (onT) if there exists no p∈Rl,p=(pk:k=1,2,...,l),pk≥0 such that ∑k=1lpkgk(x)≥0,∀x∈T.

Theorem 4. Let T be convex set in Rn , F(x)=⟨fc(x),fr(x)⟩ be interval-valued c-r convex function defined on T and g=(gk:k=1,2,...,l) be vector-valued function which satisfies Karlin’s constraints qualification on T . If x∗ is the solution of IMP, then (x∗,s∗)(so∗∈R,s=(sk:k=1,2,...,l),so∗≥0,si≥0) is a solution of IKTSP.

Proof. Since g=(gk:k=1,2,...,l) satisfies the constraint qualification of Karlin, thereexistsnop∈Rl,p=(pk:k=1,2,...l),pk≥0suchthat∑k=1lpkgk(x)≥0,∀x∈T.

Also, since x∗ is a solution of MP,

F(x∗)≤minF(x),∀x∈T.i.e.,fc(x∗)<fc(x)iffc(x∗)≠fc(x)fr(x∗)≤fr(x)iffc(x∗)=fc(x).

Here, two cases may arise:

Case-1.

iffc(x∗)≠fc(x),then⟨fc(x)−fc(x∗)<0gk(x)<0,k=1,2,...,l⟩ has no solution ∀x∈T.

Then, there exist ro∗∈R,r=(rk:k=1,2,...,l)∈Rl,ro∗≥0,ri≥0 such that

ro∗[fc(x)−fc(x∗)]+∑k=1lro∗gk(x)≥0∀x∈T. (9)

Similar to Case-1 of Theorem 3, we obtain

∑k=1lro∗gk(x∗)=0andro∗fc(x∗)+∑k=1lrkgk(x∗)≤ro∗fc(x∗)+∑k=1lrk∗gi(x∗)≤r¯ofc(x)+∑i=1mr¯igi(x) (10)

Let ro∗=0,thenri≥0, [from (9)]

Now, from the second inequality of (10) we get

ro∗fc(x∗)+∑k=1lrk∗gk(x∗)≤ro∗fc(x)+∑k=1lrk∗gk(x)or,0≤0+∑k=1lrk∗gk(x)[∵ro∗=0and∑k=1lrk∗gk(x∗)=0]or,∑k=1lrk∗gk(x)≥0,∀x∈T.

which is a contradiction (According to Karlin’s constraint qualification). Hence, ro∗>0.

Now, from (10), we have

fc(x∗)+∑k=1l(rk/ro∗)gk(x∗)≤fc(x∗)+∑k=1l(rk∗/ro∗)gk(x∗)≤fc(x)+∑k=1l(rk∗/ro∗)gk(x)i.e.,fc(x∗)+∑k=1lskgk(x∗)≤fc(x∗)+∑k=1lsk∗gk(x∗)≤fc(x)+∑k=1lsk∗gk(x),wheresk=rk/ro∗

Case-2. If fc(x∗)=fc(x) ,

then

fr(x∗)≤fr(x)i.e.,fr(x∗)≤fr(x∗)≤fr(x)

i.e.,fr(x∗)+∑k=1lsk.0≤fr(x∗)+∑k=1lsk∗.0≤fr(x)+∑k=1lsk∗.0

Combining both cases, we have

⟨fc(x∗),fr(x∗)⟩+∑k=1lsk⟨gk(x∗),0⟩≤min⟨fc(x∗),fr(x∗)⟩+∑k=1lsk∗⟨gk(x∗),0⟩≤min⟨fc(x),fr(x)⟩+∑k=1lsk∗⟨gk(x),0⟩

Hence, the proof is completed.

6  Numerical Example

To illustrate the saddle point optimality criteria, we have considered the following simple example:

Findx¯∈X={x∈R:−x+3≤0},suchthatf(x¯)=minx∈X⁡f(x),wheref(x)=[−(x2+1),3x2+1]

Solution. fc(x)=x2≠constant.Hence,minimizersoffcandfarethesame.

Clearly,x¯=3istheminimizeroffc(x),andsothatoff(x).Therefore,theminimumvalueoff(x)is[−10,28]

Now, the saddle point optimality criterion for this problem is that:

A necessary and sufficient condition that x¯=3 is that there exists a real number u¯suchthat

ϕ(x¯,u)≤minϕ(x¯,u¯)≤minϕ(x,u¯),∀x∈Rand∀u∈R,u≥0 (11)

whereϕ(x,u)=[−(x2+1),3x2+1]+u(−x+3)

Clearly, for x¯=3,u¯=6,ϕ(x¯,u)=ϕ(x¯,u¯)andϕc(x¯,u¯)≤ϕc(x,u¯) ,

then, interval inequality (11) holds for x¯=3,u¯=6 .

Hence, ϕ(x,u) has saddle point at x¯=3,u¯=6 .

7  Conclusion

In this paper, the derived saddle point (Fritz-John & Kuhn-Tucker) optimality criteria of interval-valued non-linear programming are called Extended Fritz-John and Extended Kuhn-Tucker saddle point criteria. Furthermore, we have shown that the Extended saddle point criteria are the sufficient conditions, so the point x¯∈Xistheminimizerof the IMP. After considering all constraints of the IMP as real-valued convex functions and Karlin’s constraint qualification, we illustrated that Extended Fritz-John and Extended Kuhn-Tucker Type saddle point criteria are also necessary conditions. For these purposes, the paper has introduced the definition of the minimizer, convexity of an interval-valued function, as well as Interval-valued Fritz-John and Interval-valued Kuhn-Tucker saddle point problems. Here, all the results have been established without differentiability assumptions of the objective function and constraints. Thus, these saddle point optimality criteria are called optimality criteria without differentiability. The concepts of this work will help to solve imprecise real-life problems like inventory control, supply chain management, problems of game theory,… etc.

For future work, one may attempt to establish the duality theory of IMP, saddle point optimality criteria of an interval optimization problem with several objective functions. One may also attempt to extend the concept of this paper in fuzzy, Type-2 fuzzy, and Type-2 interval environment [24].

Acknowledgement: The authors acknowledge Taif University Researchers Supporting Project Number (TURSP-2020/20), Taif University, Taif, Saudi Arabia. All authors are thankful to the anonymous reviewers for their valuable comments and suggestions that improved this manuscript.

Funding Statement: Taif University Researchers Supporting Project number (TURSP-2020/20), Taif University, Taif, Saudi Arabia.

Conflicts of Interest: The authors declare that they have no conflicts of interest regarding the present study.

References

 1.  W. Karush, “Minima of functions of several variables with inequalities as side constraints,” Master’s thesis. Dept. of Mathematics, Univ. of Chicago, 1939.

 2.  H. W. Kuhn and A. W. Tucker, “Nonlinear Programming,” Traces and Emergence of Nonlinear Programming. Birkhäuser, Basel, pp. 247–258, 2014.

 3.  F. John, “Extremum Problem with inequalities as subsidiary condition,” in Studies and Essays, Courant Anniversary, K. O. Friedrichs, O. E. Neugebauer and J. J. Stoker, eds. New York: Wiley—Inter science, pp. 187–204, 1948.

 4.  R. E. Bellman and L. A. Zadeh, “Decision making in a fuzzy environment,” Management Science, vol. 17B, no. 4, pp. 141–164, 1970.

 5.  M. Delgado, F. Herrera, J. L. Verdegay and M. A. Vila, “Post-optimality analysis on the membership functions of a fuzzy linear programming problem,” Fuzzy Sets and Systems, vol. 53, no. 3, pp. 289–297, 1993.

 6.  H. C. Wu, “Saddle point optimality conditions in fuzzy optimization problems,” Fuzzy Optimization and Decision Making, vol. 2, no. 3, pp. 261–273, 2003.

 7.  Z. T. Gong and H. X. Li, “Saddle point optimality conditions in fuzzy optimization problems,” Advances in Intelligent and Soft Computing, vol. 54, pp. 7–14, 2009.

 8.  H. X. Li, Y. J. Bai and Z. T. Gong, “The convexity of n-dimensional fuzzy mappings and the saddle point conditions of the fuzzy optimization problems,” Journal of Computational Analysis & Applications, vol. 25, no. 8, pp. 1480–1489, 2018.

 9.  Y. E. Bao and E. D. Bai, “Optimality conditions for fuzzy programming problems with differentiable fuzzy objective mappings,” Journal of Information Science & Engineering, vol. 35, no. 6, pp. 1311–1327, 2019.

10. A. Nemirovski, A. Juditsky, G. Lan and A. Shapiro, “Robust stochastic approximation approach to stochastic programming,” SIAM Journal on Optimization, vol. 19, no. 4, pp. 1574–1609, 2009.

11. P. Chen, A. Quarteroni and G. Rozza, “Stochastic optimal Robin boundary control problems of advection-dominated elliptic equations,” SIAM Journal on Numerical Analysis, vol. 51, no. 5, pp. 2700–2722, 2013.

12. Y. Chen, G. Lan and Y. Ouyang, “Optimal primal-dual methods for a class of saddle point problems,” SIAM Journal on Optimization, vol. 24, no. 4, pp. 1779–1814, 2014.

13. A. S. Bedi, A. Koppel and K. Rajawat, “Asynchronous saddle point algorithm for stochastic optimization in heterogeneous networks,” IEEE Transactions on Signal Processing, vol. 67, no. 7, pp. 1742–1757, 2019.

14. A. Nemirovski and R. Y. Rubinstein, “An efficient stochastic approximation algorithm for stochastic saddle point problems,” In: M. Dror, P. L’Ecuyer and F. Szidarovszky (eds.Modeling Uncertainty. Int. Series in Operations Research & Management Science. Springer, New York, NY: Springer, vol. 46, 2002.

15. H. C. Wu, “The Karush–Kuhn–Tucker optimality conditions in an optimization problem with interval-valued objective function,” European Journal of Operational Research, vol. 176, no. 1, pp. 46–59, 2007.

16. H. Ishibuchi and H. Tanaka, “Multi-objective programming in optimization of the interval objective function,” European Journal of Operational Research, vol. 48, no. 2, pp. 219–225, 1990.

17. M. S. Rahman, A. A. Shaikh and A. K. Bhunia, “Necessary and sufficient optimality conditions for non-linear unconstrained and constrained optimization problem with interval valued objective function,” Computers & Industrial Engineering, vol. 147, no. 1, pp. 106634, 2020.

18. A. K. Bhunia and S. S. Samanta, “A study of interval metric and its application in multi-objective optimization with interval objectives,” Computers & Industrial Engineering, vol. 74, no. 1, pp. 169–178, 2014.

19. A. K. Bhunia and A. A. Shaikh, “Investigation of two-warehouse inventory problems in interval environment under inflation via particle swarm optimization,” Mathematical and Computer Modelling of Dynamical Systems, vol. 22, no. 2, pp. 160–179, 2016.

20. A. A. Shaikh, S. C. Das, A. K. Bhunia, G. C. Panda and M. A. A. Khan, “A two-warehouse EOQ model with interval-valued inventory cost and advance payment for deteriorating item under particle swarm optimization,” Soft Computing, vol. 23, no. 24, pp. 13531–13546, 2019.

21. M. S. Rahman, A. Duary, A. A. Shaikh and A. K. Bhunia, “An application of parametric approach for interval differential equation in inventory model for deteriorating items with selling-price-dependent demand,” Neural Computing and Applications, vol. 32, no. 17, pp. 14069–140857, 2020.

22. M. S. Rahman, A. K. Manna, A. A. Shaikh and A. K. Bhunia, “An application of interval differential equation on a production inventory model with interval-valued demand via center-radius optimization technique and particle swarm optimization,” International Journal of Intelligent Systems, vol. 35, no. 8, pp. 1280–1326, 2020.

23. O. L. Mangasarian, Nonlinear programming. New York: McGraw-Hill, 1969, ISBN 0-89871-341-2.

24. M. S. Rahman, A. A. Shaikh and A. K. Bhunia, “On Type-2 interval with interval mathematics and order relations: Its applications in inventory control,” International Journal of Systems Science: Operations & Logistics, pp. 1–13, 2020. DOI 10.1080/23302674.2020.1754499.

images
This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.