Properties of Optimal Solution of Indefinite Matrix Constraint in Linear Programming
Abstract
This study investigated characteristics of indefinite random square matrices which represented the constraints of Linear programming problems. MATLAB simulation was used to generate different size of indefinite random non-symmetric square matrices. Solutions of primal problem and dual problem were deliberated and discussed. Based on simulation results, duality gap found in some of the indefinite non-symmetric matrices and those matrices could not obtain optimal solution whereas some ID matrices that fulfill certain conditions could achieve optimal solution and no duality gap is found. An indefinite non-symmetric matrix with all positive off-diagonal entries and alternate signs of determinant of leading principal minors surely confirmed the existence of optimal solution in linear programming problems.
Downloads
References
S. H. P. Moghadam, H. Mina, S. H. Iranmanesh, and A. Keyvandarian, “A new mathematical model for single machine scheduling with learning
effect: continuous approach,“ Int. J. of Mathematics in Operational Research, Vol. 7, No. 3, pp. 348 -360, 2015.
W. X. Xing, S. C. Fang, R. L. Sheu, and Z. T. Wang, “A canonical dual approach for solving linearly constrained quadratic programs,” European Journal of Operational Research, Vol. 218, pp. 21-27, 2012.
R. J. Vanderbei, Linear Programming: Foundations and Extensions, 2nd Edition. Dordrecht, London: Kluwer Academic, 2001.
M. S. Bazarra, and J. J. Jarvis, Linear Programming and Network Flows. Canada: John Wiley and Sons, 1977.
L. A. Wolsey, Integer Programming. USA: John Wiley & Sons, 1998.
S. Y. Leu, and J. S, Li, “Shakedown analysis of framed structures: strong duality and primal-dual analysis,” Procedia Engineering, Vol. 79, pp. 204-211, 2014.
V. Jeyakumar, and G. Y. Li, “New dual constraint qualifications
characterizing zero duality gaps of convex programs and semidefinite
programs,” Nonlinear Analysis: Theory, Methods & Applications, Vol. 71, No. 12, pp. e2239-e2249, 2009.
S. L. Wu, and C. X. Li, “A splitting method for complex symmetric
indefinite linear system,” Mathematics, Vol. 313, pp. 343-354, March 2017.
A. Basu, K. Martin, and C. T. Ryan, “On the sufficiency of finite support duals in semi-infinite linear programming,” Operations Research Letters, Vol. 42, issue 1, pp. 16-20, January 2014.
E.J. Lee, and J. Zhang, “A two-phase preconditioning strategy of a sparse approximate inverse for indefinite matrices,” Computers & Mathematics
with Applications, Vol. 58, issue 6, pp. 1152-1159, September 2009.
W. W. Xu, “On eigenvalue bounds of two classes of two-by-two block indefinite matrices,” Applied Mathematics and Computation, Vol. 219, issue 12, pp. 6669-6679, Feb. 2013.
I. Romli, Taufik, A. Saptari, and M. M. Jusoh, “Symmetric matrices
properties to duality in linear programming problem,” 2011 Fourth
International Conference on Modeling, Simulation and Applied Optimization, Kuala Lumpur, Malaysia, 2011, pp. 1-7.
P. Q. Pan, “A revised dual projective pivot algorithm for linear
programming,” SIAM Journal Optimization, Vol. 16, No. 1, pp. 49-68, 2005.
D. Torres, J. Crichigno, G. Padilla, and R. Rivera, “Scheduling coupled photovoltaic, battery and conventional energy sources to maximize profit using linear programming,” Renewable Energy, Vol. 72, pp. 284-290, 2014.
G. Strang, Linear Algebra and Its Application, 4th edition. United States of America: Thomson Learning, 2006.
O. Guler, Foundations of Optimization. New York: Springer, 2010.
M. Carter, Foundations of Mathematical Economics. Cambridge, United States of America: Massachusetts Institute of Technology, 2001.
A. L. Soyster, and F. H. Murphy, “A unifying framework for duality and modelling in robust linear programs,” Omega, Vol. 41, pp. 984-997, 2013.
A. Jeffrey, Matrix Operations for Engineers and Scientists. United Kingdom: Springer, 2010.
K. Mehlhorn, and S. Saxena, “A still simpler way of introducing interiorpoint method for linear programming,” Computer Science Review, Vol. 22, pp. I-II, 2016.
