Solving linear programming problems via linear minimax problems (Q1180710): Difference between revisions

The linear programming problem consists of minimizing \(c^ Tx\) subject to \(A^ Tx\geq b\) where \(x\in \mathbb{R}^ n\) is variable, \(c\in \mathbb{R}^ n\), \(b\in \mathbb{R}^ n\) are given, and \(A\) is an \(n\times m\) matrix which is also given. At first a Householder transformation \(\bar x=Hx\) with \(H=I-(2/\| v\|^ 2)v^ Tv\), \(\|\cdot\|\) = Euclidean norm, \(v=c+\| c\| z\), \(z=(0,\dots,0,1)^ T\in\mathbb{R}^ n\) is applied in order to transform the original problem into the equivalent problem of minimizing \(\bar x_ n=\) n-th coordinate of \(\bar x\) subject to \(\bar A^ T\bar x\geq b\) where \(\bar A=HA\). Because of \(\bar c^ T\bar x=\| c\| \bar x_ n\), and hence \(\bar a_{in}={1\over\| c\|}\bar c^ T\bar a_{in}\), it follows that \(\bar a_{in} < 0\) implies that \(\bar a_ i\) is a descent direction for the second problem unless its feasible region has no point of the form \(\bar x=\bar x^*+t\bar a_{in}\) for \(t>0\) where \(\bar x^*\) is any solution of this problem. This is assumed and consequently only those constraints \(\bar a^ T_ i\bar x\geq b_ i\) are admitted for which \(\bar a_{in} \geq 0\) holds true. These constraints are called considerable. The corresponding index set is denoted by \(C\) and the problem of minimizing \(\bar x_ n\) subject to \(\bar a^ T_ i\bar x\geq b_ i\) for \(i\in C\) is solved (as a minimax problem) by a method of weighted centers. The number of multiplications in the whole process of solution is shown to be \(O(n^ 4)\) and the method is demonstrated by two simple examples. Finally it is shown how the original problem can be solved directly by the method of weighted centers with converting the problem into a minimax problem. In this case all constraints \(a^ T_ ix\geq b_ i\) are excluded for which \(c^ Ta_ i < 0\).