A non-iterative polynomial algorithm for linear programming
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2013
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918509849608192 |
|---|---|
| author | Jing-Yuan, Wei |
| author_facet | Jing-Yuan, Wei |
| contents | Consider a linear programming problem with n primal and m dual variables paired with n dual and m primal slack variables respectively, and aggregately denote these variables and slack variables as a vector z of length 2(n+m). Unlike existing algorithms such as simplex and interior point methods solving linear programming by iteratively generating a sequence of feasible points to approach the optimal solution, the paper defines a function f mapping the constraint matrix and the right-hand side and objective vectors defining the linear programming problem to a binary vector of length n+m. It is shown that, under the uniqueness assumption of the optimal solution z* and for each (primal or dual) variable z_i, f_i is zero if and only if the optimal value z*_i is zero, and f_i is one if and only if z*_i is positive. Computation of f_i for each i consists of solving two groups of linear equations using O(m^2n) operations. Computing f_i is then non-iterative and independent of computing f_j for j <> i. Hence, at most O(m^2n^2) operations are required to compute f and consequently to solve the linear programming problem. The non-iterative and mutually independent features of computing the elements of f enable a parallel polynomial algorithm for linear programming. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1309_6187 |
| institution | arXiv |
| publishDate | 2013 |
| record_format | arxiv |
| spellingShingle | A non-iterative polynomial algorithm for linear programming Jing-Yuan, Wei Optimization and Control 68Q15 68Q25 90C05 Consider a linear programming problem with n primal and m dual variables paired with n dual and m primal slack variables respectively, and aggregately denote these variables and slack variables as a vector z of length 2(n+m). Unlike existing algorithms such as simplex and interior point methods solving linear programming by iteratively generating a sequence of feasible points to approach the optimal solution, the paper defines a function f mapping the constraint matrix and the right-hand side and objective vectors defining the linear programming problem to a binary vector of length n+m. It is shown that, under the uniqueness assumption of the optimal solution z* and for each (primal or dual) variable z_i, f_i is zero if and only if the optimal value z*_i is zero, and f_i is one if and only if z*_i is positive. Computation of f_i for each i consists of solving two groups of linear equations using O(m^2n) operations. Computing f_i is then non-iterative and independent of computing f_j for j <> i. Hence, at most O(m^2n^2) operations are required to compute f and consequently to solve the linear programming problem. The non-iterative and mutually independent features of computing the elements of f enable a parallel polynomial algorithm for linear programming. |
| title | A non-iterative polynomial algorithm for linear programming |
| topic | Optimization and Control 68Q15 68Q25 90C05 |
| url | https://arxiv.org/abs/1309.6187 |