Duality in linear programming: From trichotomy to quadrichotomy

Previous Article
Global convergence of an inexact operator splitting method for monotone variational inequalities
JIMO Home
This Issue
Next Article
Multiple solutions for a class of semilinear elliptic variational inclusion problems

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

Duality in linear programming: From trichotomy to quadrichotomy

1.	School of Mathematical & Geospatial Sciences, RMIT University, Melbourne

Received September 2010 Revised July 2011 Published August 2011

Abstract
Related Papers

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 and 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.
[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.
[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.
[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.
[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.
[6]	G. Roodman, Post-infeasibility analysis in linear programming, Management Science, 25 (1979), 916-922. doi: 10.1287/mnsc.25.9.916.

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.
[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.
[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.
[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.
[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.
[6]	G. Roodman, Post-infeasibility analysis in linear programming, Management Science, 25 (1979), 916-922. doi: 10.1287/mnsc.25.9.916.

[1]	Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial and 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 and 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 and 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 and 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 and 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 and 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 and Optimization, 2022, 12 (1) : 121-134. doi: 10.3934/naco.2021055
[8]	Charles Fefferman. Interpolation by linear programming I. Discrete and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2010, 6 (4) : 779-793. doi: 10.3934/jimo.2010.6.779
[16]	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 and Management Optimization, 2013, 9 (3) : 703-721. doi: 10.3934/jimo.2013.9.703
[17]	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
[18]	Fengming Ma, Yiju Wang, Hongge Zhao. A potential reduction method for the generalized linear complementarity problem over a polyhedral cone. Journal of Industrial and 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 and 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 and Management Optimization, 2016, 12 (2) : 739-756. doi: 10.3934/jimo.2016.12.739

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Yanqun Liu
on Google Scholar
Yanqun Liu

[Back to Top]