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

Article |

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

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

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

The equivalent saddle point problem of the above-mention minimization problem is

Here, the point

In a fuzzy optimization problem, the objective function

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

And the equivalent saddle point problem is

if exist, such that

The inequality

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.

The definitions of Bhunia and Samanta’s [18] ordering,

where,

Definition 1. Let

Then, C

Definition 2.

C

3.2 Minimizer and Convexity of an Interval-valued Function

Let

where

Definition 3. A point

where

Definition 4. A point

Proposition 1. The point

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

Definition 5. The interval-valued function

Proposition 2. Let T

Proof. The proof follows from the definition of c-r convex and the

Lemma 1. Let

Then,

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

4.1 The Interval-Valued Minimization Problem (IMP)

(IMP)

Find

The set

4.2 The Local Interval-Valued Minimization Problem (LIMP)

(LIMP)

Find

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

(IFJSP)

Find

If exist, such that

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

(IKTSP)

Find

if exist, such that

where

Theorem 1.

If

Proof.

First, let

Now, by Lemma 1, four cases may arise:

Case-1 If

then,

i.e.,

i.e.,

i.e.,

Case-2 If

then,

Case-3 If

then, similarly as Case-2, we have obtained

Case-4 If

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

Conversely, let

Then,

where

Hence,

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

Proof.

First Part.

Let

Then,

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

Case-1. If

then

Case-2. If

then

Now, from first inequality, we have

Which gives

But, again from (1) by setting

Hence, from (2) and (3), we have

Now, from

which is possible only if

So, in this case

Thus, from

Hence,

Case-3 If

then,

Case-4. If

Then,

Similar to case-1, we can say that

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

If

such that

where

Theorem 3. Let

Proof. Since

Now, two cases may arise:

Case-1.

By Lemma 2, there exist

Hence from (5) and (6), we have

Again from (4), we have

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

Case-2. If

then

Combining both cases, we have obtained

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

Theorem 4. Let

Proof. Since

Also, since

Here, two cases may arise:

Case-1.

Then, there exist

Similar to Case-1 of Theorem 3, we obtain

Let

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

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

Now, from (10), we have

Case-2. If

then

Combining both cases, we have

Hence, the proof is completed.

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

Solution.

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

A necessary and sufficient condition that

Clearly, for

then, interval inequality (11) holds for

Hence,

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

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.

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

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

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. [Google Scholar]

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

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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. [Google Scholar]

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

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. [Google Scholar] [CrossRef]

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. |