The strict complementarity in linear fractional optimization

Document Type : Research Article

Authors

• M. Mehdiloo ¹
• K. Tone ²
• M.B. Ahmadi ³

¹ Department of Mathematics and Applications, University of Mohaghegh Ardabili, Ardabil, Iran.

² National Graduate Institute for Policy Studies, Tokyo, Japan.

³ Department of Mathematics, College of Sciences, Shiraz University, Shiraz, Iran.

10.22067/ijnao.2021.11330.0

Abstract

As an important duality result in linear optimization, the Goldman–Tucker theorem establishes strict complementarity between a pair of primal and dual linear programs. Our study extends this result into the framework of linear fractional optimization. Associated with a linear fractional program, a dual program can be defined as the dual of the equivalent linear program obtained from applying the Charnes–Cooper transformation to the given program. Based on this definition, we propose new criteria for primal and  dual optimality by showing that the primal and dual optimal sets can be equivalently modeled as the optimal sets of a pair of primal and dual linear programs. Then, we define the concept of strict complementarity and establish the existence of at least one, called strict complementary, pair of primal and dual optimal solutions such that in every pair of comple mentary variables, exactly one variable is positive and the other is zero. We geometrically interpret the strict complementarity in terms of the relative interiors of two sets that represent the primal and dual optimal setsin higher dimensions. Finally, using this interpretation, we develop two approaches for finding a strict complementary solution in linear fractional optimization. We illustrate our results with two numerical examples.
 

Keywords

• Linear fractional optimization
• Charnes–Cooper transformation
• Duality
• Strict complementarity

20.1001.1.24236977.2021.11.2.4.3

Main Subjects

• Optimization

---

References

1. Bajalinov, E.B. Linear-fractional programming theory, methods, applications and software, Kluwer Academic publishers, Boston, 2003.
2. Balinski, M.L. and Tucker, A.W. Duality theory of linear programs: A constructive approach with applications, SIAM Rev. 11(3) (1969), 347–377.
3. Bazaraa, M.S., Sherali, H.D. and Shetty, C.M. Nonlinear programming: Theory and algorithms. John Wiley & Sons, Hoboken, NJ, 2006.
4. Ben-Tal, A., El Ghaoui, L. and Nemirovski A. Robust optimization, Princeton University Press, Princeton, NJ, 2009.
5. Berkelaar, A.B., Roos, K. and Terlaky, T. The optimal set and the optimal partition approach. Advances in Sensitivity Analysis and ParametricProgramming, edited by T., Gal, and H.J. Greenberg, International Series in Operations Research & Management Science, Vol. 6. Springer, Boston, MA (1997) 6.1–6.45.
6. Bertsimas, D. and Tsitsiklis, J.N. Introduction to linear optimization, Athena Scientific, Massachusetts, 1997.
7. Chadha, S.S. A dual fractional program, Z. Angew. Math. Mech. 51 (1971), 560–561.
8. Chadha, S.S. and Chadha, V. Linear fractional programming and duality, Ann. Oper. Res. 15 (2007), 119–125.
9. Charnes, A. and Cooper, W.W. Programming with linear fractional functional, Naval Res. Logist. Q. 15(3-4) (1962), 181–186.
10. Charnes, A., Cooper, W.W. and Rhodes, E. Measuring the efficiency of decision making units, Eur. J. Oper. Res. 2(6) (1978), 429–444.
11. Craven, B.D. Fractional programming, Sigma Series in Applied Mathe matics, Heldermann Verlag, Berlin, 1988.
12. Goldman, A.J. and Tucker, A.W. Theory of linear programming, Linear inequalities and related systems, edited by Kuhn, H.W. and Tucker, A.W., Princeton University Press, NJ (1956) 53–97.
13. Greenberg, H. J. The use of the optimal partition in a linear programming solution for postoptimal analysis, Oper. Res. Lett. 15(4) (1994), 179–186.
14. Hasan, M.B. and Acharjee, S. Solving LFP by converting it into a single LP, Int. J. Oper. Res. 8(3) (2011), 1–14.
15. Jahanshahloo, G.R., Hosseinzadeh Lotfi, F., Mehdiloozad, M. and Roshdi, I. Connected directional slack-based measure of efficiency in DEA, Appl. Math. Sci. 6(5) (2012), 237–246.
16. Lai, K.K., Mishra, S.K., Panda, G., Chakraborty, S.K., Samei, M.E. and Ram, B. A limited memory q-BFGS algorithm for unconstrained optimization problems, J. Appl. Math. Comut. 66 (2021), 183–202.
17. Mehdiloozad, M. Identifying the global reference set in DEA: A mixed 0-1 LP formulation with an equivalent LP relaxation, Oper. Res. 17 (2017),205–211.
18. Mehdiloozad, M., Mirdehghan, S.M., Sahoo, B.K. and Roshdi, I. On the identification of the global reference set in data envelopment analysis, Eur. J. Oper. Res. 245(3) (2015), 779–788.
19. Mehdiloozad, M. and Sahoo, B.K. Identifying the global reference set in DEA: An application to the determination of returns to scale, Handbook of Operations Analytics Using Data Envelopment Analysis, edited by S.N., Hwang, H.S., Lee and J., Zhu, International Series in Operations Research & Management Science, Vol. 239, Springer, Boston, MA (2016) 299–330.
20. Mehdiloozad, M., Tone, K., Askarpour, R. and Ahmadi, M.B. Finding a maximal element of a nonnegative convex set through its characteristic cone: An application to finding a strictly complementary solution, Comput. Appl. Math. 37 (2018), 53–80.
21. Mishra, S.K., Samei, M.E. and Chakraborty, S.K. On q-variant of Dai–Yuan conjugate gradient algorithm for unconstrained optimization problems, Nonlinear Dyn. (2021). https://doi.org/10.1007/s11071-021-06378-3.
22. Pastor, J.T., Ruiz, J.L. and Sirvent, I. An enhanced DEA Russell graph efficiency measure, Eur. J. Oper. Res. 115(3) (1999), 596–607.
23. Rockafellar, R.T. Convex analysis, Princeton University Press, Prince ton, NJ, 1970.
24. Schaible, S. Fractional programming: Applications and algorithms, Eur. J. Oper. Res. 7(2) (1981), 111–120.
25. Stancu-Minasian, I.M. Fractional programming: Theory, methods and applications, Kluwer Academic publishers, Boston, 1997.
26. Tone, K. A slacks-based measure of efficiency in data envelopment analysis, Eur. J. Oper. Res. 130(3) (2001), 498–509.
27. Tone, K. A slacks-based measure of super-efficiency in data envelopment analysis, Eur. J. Oper. Res. 143(1) (2002), 32–41.
28. Tone, K. Variations on the theme of slacks-based measure of efficiency in DEA, Eur. J. Oper. Res. 200(3) (2009), 901–907.
29. Tone, K. and Tsutsui, M. Network DEA: A slacks-based measure approach, Eur. J. Oper. Res. 197(1) (2009), 243–252.
30. Tone, K., Toloo, M. and Izadikhah, M. A modified slacks-based measure of efficiency in data envelopment analysis, Eur. J. Oper. Res. 287(2) (2020), 560–571.
31. Tone, K. and Tsutsui, M. Dynamic DEA: A slacks-based measure approach, Omega 38(3-4) (2010), 145–156.