Solving linear programming problems via linear minimax problems
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\).
- A new polynomial-time algorithm for linear programming
- A penalty linear programming method using reduced-gradient basis-exchange techniques
- A Structure-Exploiting Algorithm for Nonlinear Minimax Problems
- Linear Programming via a Nondifferentiable Penalty Function
- Linearly Constrained Discrete I 1 Problems
This page was built for publication: Solving linear programming problems via linear minimax problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1180710)
