Linear programming by minimizing distances

The authors consider the linear program (1) minimize \(c^ T\ell\) subject to \(A\ell+b\geq 0\), where \(A\) is an \(n\times d\)-matrix, with rank \(A=d\), \(b\in R^ n\), \(c\in R^ d\backslash\{0\}\) and the equivalent linear program (2) minimize \(t\) subject to \(-c^ T\ell+t\geq 0\), \(A\ell+b\geq 0\). If \(E(t)=\{(x_ 1,x)\in R^{n+1}\mid x_ 1=-c^ T\ell\), \(x=A\ell+b\}\), \(t\in R\), then the feasibility of (2) is equivalent to \(E(t)\cap R_ +^{n+1}\neq\emptyset\). Then the authors give a geometric and an analytic version of an algorithm to determine \(d(E(t),R_ +^{n+1})\) for fixed \(t\in R\), where \(d(.,.)\) denotes Euclidean distance. This algorithm is used to construct another algorithm to find the minimal \(t\) with \(E(t)\cap R_ +^{n+1}\neq\emptyset\), and thus (1) is solved. The authors show that all algorithms are finite.

Recommendations

Cites work

Cited in

(2)

This page was built for publication: Linear programming by minimizing distances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3978454)