A procedure of Chvátal for testing feasibility in linear programming and matrix scaling

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

The problems of testing the feasibility of a system of linear inequalities, or strict inequalities, are well-known to be the most fundamental problems in the theory and practice of linear programming. From Gordan's Theorem it follows that Ax < b is feasible if and only if the homogeneous problem A Ty = 0, b Ty + s = 0, (0, 0) ≠ (y, s) {greater than or slanted equal to} (0, 0), is infeasible. We prove a stronger result: if Ax < b is feasible, then there is a feasible point satisfying x = A Tw, for some w < 0. Moreover, there exists a feasible x = A Tw satisfying AA Tw = b + δw -1, where δ is a positive scalar and w -1 = (1/w 1, ..., 1/w n) T. The existence of w and its computation is motivated by a procedure suggested by Chvátal for solving linear programming as homogeneous problems, as well as results on diagonal matrix scaling of positive semidefinite matrices. Not only these reveal the significance of the homogeneous problem, but also practical and theoretical relevance of Khachiyan and Kalantari's diagonal matrix scaling algorithm, in computing an interior point of a linear system of inequalities, or in solving linear programming itself, over the reals or the rationals.

Original languageEnglish (US)
Pages (from-to)795-798
Number of pages4
JournalLinear Algebra and Its Applications
Volume416
Issue number2-3
DOIs
StatePublished - Jul 15 2006

Fingerprint

Linear programming
Scaling
Testing
Diagonal matrix
Linear systems
Positive Semidefinite Matrix
Interior Point
Linear Inequalities
Linear Systems
Scalar
If and only if
Computing
Theorem

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Numerical Analysis

Cite this

@article{685b16616c42498aaa4aa43434adaba8,
title = "A procedure of Chv{\'a}tal for testing feasibility in linear programming and matrix scaling",
abstract = "The problems of testing the feasibility of a system of linear inequalities, or strict inequalities, are well-known to be the most fundamental problems in the theory and practice of linear programming. From Gordan's Theorem it follows that Ax < b is feasible if and only if the homogeneous problem A Ty = 0, b Ty + s = 0, (0, 0) ≠ (y, s) {greater than or slanted equal to} (0, 0), is infeasible. We prove a stronger result: if Ax < b is feasible, then there is a feasible point satisfying x = A Tw, for some w < 0. Moreover, there exists a feasible x = A Tw satisfying AA Tw = b + δw -1, where δ is a positive scalar and w -1 = (1/w 1, ..., 1/w n) T. The existence of w and its computation is motivated by a procedure suggested by Chv{\'a}tal for solving linear programming as homogeneous problems, as well as results on diagonal matrix scaling of positive semidefinite matrices. Not only these reveal the significance of the homogeneous problem, but also practical and theoretical relevance of Khachiyan and Kalantari's diagonal matrix scaling algorithm, in computing an interior point of a linear system of inequalities, or in solving linear programming itself, over the reals or the rationals.",
author = "Yi Jin and Bahman Kalantari",
year = "2006",
month = "7",
day = "15",
doi = "10.1016/j.laa.2005.12.022",
language = "English (US)",
volume = "416",
pages = "795--798",
journal = "Linear Algebra and Its Applications",
issn = "0024-3795",
publisher = "Elsevier Inc.",
number = "2-3",

}

A procedure of Chvátal for testing feasibility in linear programming and matrix scaling. / Jin, Yi; Kalantari, Bahman.

In: Linear Algebra and Its Applications, Vol. 416, No. 2-3, 15.07.2006, p. 795-798.

Research output: Contribution to journalArticle

TY - JOUR

T1 - A procedure of Chvátal for testing feasibility in linear programming and matrix scaling

AU - Jin, Yi

AU - Kalantari, Bahman

PY - 2006/7/15

Y1 - 2006/7/15

N2 - The problems of testing the feasibility of a system of linear inequalities, or strict inequalities, are well-known to be the most fundamental problems in the theory and practice of linear programming. From Gordan's Theorem it follows that Ax < b is feasible if and only if the homogeneous problem A Ty = 0, b Ty + s = 0, (0, 0) ≠ (y, s) {greater than or slanted equal to} (0, 0), is infeasible. We prove a stronger result: if Ax < b is feasible, then there is a feasible point satisfying x = A Tw, for some w < 0. Moreover, there exists a feasible x = A Tw satisfying AA Tw = b + δw -1, where δ is a positive scalar and w -1 = (1/w 1, ..., 1/w n) T. The existence of w and its computation is motivated by a procedure suggested by Chvátal for solving linear programming as homogeneous problems, as well as results on diagonal matrix scaling of positive semidefinite matrices. Not only these reveal the significance of the homogeneous problem, but also practical and theoretical relevance of Khachiyan and Kalantari's diagonal matrix scaling algorithm, in computing an interior point of a linear system of inequalities, or in solving linear programming itself, over the reals or the rationals.

AB - The problems of testing the feasibility of a system of linear inequalities, or strict inequalities, are well-known to be the most fundamental problems in the theory and practice of linear programming. From Gordan's Theorem it follows that Ax < b is feasible if and only if the homogeneous problem A Ty = 0, b Ty + s = 0, (0, 0) ≠ (y, s) {greater than or slanted equal to} (0, 0), is infeasible. We prove a stronger result: if Ax < b is feasible, then there is a feasible point satisfying x = A Tw, for some w < 0. Moreover, there exists a feasible x = A Tw satisfying AA Tw = b + δw -1, where δ is a positive scalar and w -1 = (1/w 1, ..., 1/w n) T. The existence of w and its computation is motivated by a procedure suggested by Chvátal for solving linear programming as homogeneous problems, as well as results on diagonal matrix scaling of positive semidefinite matrices. Not only these reveal the significance of the homogeneous problem, but also practical and theoretical relevance of Khachiyan and Kalantari's diagonal matrix scaling algorithm, in computing an interior point of a linear system of inequalities, or in solving linear programming itself, over the reals or the rationals.

UR - http://www.scopus.com/inward/record.url?scp=33646925930&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33646925930&partnerID=8YFLogxK

U2 - 10.1016/j.laa.2005.12.022

DO - 10.1016/j.laa.2005.12.022

M3 - Article

VL - 416

SP - 795

EP - 798

JO - Linear Algebra and Its Applications

JF - Linear Algebra and Its Applications

SN - 0024-3795

IS - 2-3

ER -