American Institute of Mathematical Sciences

Advanced
October  2011, 7(4): 1003-1011. doi: 10.3934/jimo.2011.7.1003

Duality in linear programming: From trichotomy to quadrichotomy

Yanqun Liu 1,

1. 

School of Mathematical & Geospatial Sciences, RMIT University, Melbourne

Received  September 2010 Revised  July 2011 Published  August 2011

In this paper, we present a new approach to the duality of linear programming. We extend the boundedness to the so called inclusiveness, and show that inclusiveness and feasibility are a pair of coexisting and mutually dual properties in linear programming: one of them is possessed by a primal problem if and only if the other is possessed by the dual problem. This duality relation is consistent with the symmetry between the primal and dual problems and leads to a duality result that is considered a completion of the classical strong duality theorem. From this result, complete solvability information of the primal (or dual) problem can be derived solely from dual (or primal) information. This is demonstrated by applying the new duality results to a recent linear programming method.
Keywords: Linear programming, inclusive normal cone, inclusiveness., duality.
Mathematics Subject Classification: Primary: 90C05; Secondary: 49M2.
Citation: Yanqun Liu. Duality in linear programming: From trichotomy to quadrichotomy. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1003-1011. doi: 10.3934/jimo.2011.7.1003
References:
[1]

M. C. Ferris, O. L. Mangasarian and S. J. Wright, "Linear Programming with MATLAB," MPS-SIAM Series on Optimization, 7, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, Mathemathical Programming, Society (MPS), Philadelphia, PA, 2007. doi: 10.1137/1.9780898718775.  Google Scholar

[2]

H. J. Greenberg, How to analyze the results of linear programs--part 3: Infeasibility diagnosis, Interface, 23 (1993), 120-139. doi: 10.1287/inte.23.6.120.  Google Scholar

[3]

C. Li, X. He, B. Chen, Z. Gong, B. Chen and Q. Zhang, Infeasibility diagnosis on the linear programming model of production planning in refinery, Chinese J. Chem. Eng., 14 (2006), 569-573. doi: 10.1016/S1004-9541(06)60117-1.  Google Scholar

[4]

Y. Liu, An exterior point linear programming method based on inclusive normal cones, Journal of Industrial and Management Optimization, 6 (2010), 825-846. doi: 10.3934/jimo.2010.6.825.  Google Scholar

[5]

D. G. Luenburg and Y. Ye, "Linear and Nonlinear Programming," 3rd edition, International Series in Operations Research & Management Science, 116, Springer, New York, 2008.  Google Scholar

[6]

G. Roodman, Post-infeasibility analysis in linear programming, Management Science, 25 (1979), 916-922. doi: 10.1287/mnsc.25.9.916.  Google Scholar

show all references

References:
[1]

M. C. Ferris, O. L. Mangasarian and S. J. Wright, "Linear Programming with MATLAB," MPS-SIAM Series on Optimization, 7, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, Mathemathical Programming, Society (MPS), Philadelphia, PA, 2007. doi: 10.1137/1.9780898718775.  Google Scholar

[2]

H. J. Greenberg, How to analyze the results of linear programs--part 3: Infeasibility diagnosis, Interface, 23 (1993), 120-139. doi: 10.1287/inte.23.6.120.  Google Scholar

[3]

C. Li, X. He, B. Chen, Z. Gong, B. Chen and Q. Zhang, Infeasibility diagnosis on the linear programming model of production planning in refinery, Chinese J. Chem. Eng., 14 (2006), 569-573. doi: 10.1016/S1004-9541(06)60117-1.  Google Scholar

[4]

Y. Liu, An exterior point linear programming method based on inclusive normal cones, Journal of Industrial and Management Optimization, 6 (2010), 825-846. doi: 10.3934/jimo.2010.6.825.  Google Scholar

[5]

D. G. Luenburg and Y. Ye, "Linear and Nonlinear Programming," 3rd edition, International Series in Operations Research & Management Science, 116, Springer, New York, 2008.  Google Scholar

[6]

G. Roodman, Post-infeasibility analysis in linear programming, Management Science, 25 (1979), 916-922. doi: 10.1287/mnsc.25.9.916.  Google Scholar

[1]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[2]

Liping Tang, Xinmin Yang, Ying Gao. Higher-order symmetric duality for multiobjective programming with cone constraints. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1873-1884. doi: 10.3934/jimo.2019033
[3]

Yi Zhang, Yong Jiang, Liwei Zhang, Jiangzhong Zhang. A perturbation approach for an inverse linear second-order cone programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 171-189. doi: 10.3934/jimo.2013.9.171
[4]

Shiyun Wang, Yong-Jin Liu, Yong Jiang. A majorized penalty approach to inverse linear second order cone programming problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 965-976. doi: 10.3934/jimo.2014.10.965
[5]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[6]

Xinmin Yang. On second order symmetric duality in nondifferentiable multiobjective programming. Journal of Industrial & Management Optimization, 2009, 5 (4) : 697-703. doi: 10.3934/jimo.2009.5.697
[7]

Tone-Yau Huang, Tamaki Tanaka. Optimality and duality for complex multi-objective programming. Numerical Algebra, Control & Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[8]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[9]

Xinmin Yang, Xiaoqi Yang, Kok Lay Teo. Higher-order symmetric duality in multiobjective programming with invexity. Journal of Industrial & Management Optimization, 2008, 4 (2) : 385-391. doi: 10.3934/jimo.2008.4.385
[10]

Xinmin Yang, Xiaoqi Yang. A note on mixed type converse duality in multiobjective programming problems. Journal of Industrial & Management Optimization, 2010, 6 (3) : 497-500. doi: 10.3934/jimo.2010.6.497
[11]

Deepak Singh, Bilal Ahmad Dar, Do Sang Kim. Sufficiency and duality in non-smooth interval valued programming problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 647-665. doi: 10.3934/jimo.2018063
[12]

Yuhua Sun, Laisheng Wang. Optimality conditions and duality in nondifferentiable interval-valued programming. Journal of Industrial & Management Optimization, 2013, 9 (1) : 131-142. doi: 10.3934/jimo.2013.9.131
[13]

Xian-Jun Long, Jing Quan. Optimality conditions and duality for minimax fractional programming involving nonsmooth generalized univexity. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 361-370. doi: 10.3934/naco.2011.1.361
[14]

Xiao-Bing Li, Qi-Lin Wang, Zhi Lin. Optimality conditions and duality for minimax fractional programming problems with data uncertainty. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1133-1151. doi: 10.3934/jimo.2018089
[15]

Cheng Lu, Zhenbo Wang, Wenxun Xing, Shu-Cherng Fang. Extended canonical duality and conic programming for solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[16]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[17]

Ye Tian, Shu-Cherng Fang, Zhibin Deng, Wenxun Xing. Computable representation of the cone of nonnegative quadratic forms over a general second-order cone and its application to completely positive programming. Journal of Industrial & Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[18]

Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial & Management Optimization, 2010, 6 (1) : 259-267. doi: 10.3934/jimo.2010.6.259
[19]

Behrouz Kheirfam. A weighted-path-following method for symmetric cone linear complementarity problems. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 141-150. doi: 10.3934/naco.2014.4.141
[20]

Yanqin Bai, Pengfei Ma, Jing Zhang. A polynomial-time interior-point method for circular cone programming based on kernel functions. Journal of Industrial & Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (252)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy