Topological structure and a polynomial-time solution of linear programming over the real numbers
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2018
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916023391748096 |
|---|---|
| author | Wei, Jing-Yuan |
| author_facet | Wei, Jing-Yuan |
| contents | We present an O(mn^2) algorithm for linear programming over the real numbers with n primal and m dual variables through deciding the support set a of an optimal solution. Let z and e be two 2(n+m)-tuples with z representing the primal, dual and slack variables of linear programming, and e the all-one vector. Let Z denote the region including all (tz, t) with z meeting the zero duality gap constraint, all primal and dual constraints except for the non-negativity constraints, and without limit on the real number t. Let L be the projection of Z on the hyperplane defined by t = 0. Consider a squeeze mapping involving the two variables of each complementary pair of z. The projection of e on the image of L of the mapping lies in an (n+m-1)-sphere Q centered at e/2 of a diameter whose square equals 2(n+m). The sum of the two components of a complementary pair of z in Q equals one, and Q is the circumsphere of the hypercube where each component of its vertices takes value in {0, 1}. One vertex v* called the solution vertex is the indicator vector of a. The algorithm uses squeeze mapping to move the aforementioned projection around v* along Q so that a is identified at certain position. It consists of O(n) unidimensional squeeze mappings, each of which uses O(mn) arithmetic operations. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1805_06342 |
| institution | arXiv |
| publishDate | 2018 |
| record_format | arxiv |
| spellingShingle | Topological structure and a polynomial-time solution of linear programming over the real numbers Wei, Jing-Yuan Optimization and Control 68Q15 68Q25 90C05 We present an O(mn^2) algorithm for linear programming over the real numbers with n primal and m dual variables through deciding the support set a of an optimal solution. Let z and e be two 2(n+m)-tuples with z representing the primal, dual and slack variables of linear programming, and e the all-one vector. Let Z denote the region including all (tz, t) with z meeting the zero duality gap constraint, all primal and dual constraints except for the non-negativity constraints, and without limit on the real number t. Let L be the projection of Z on the hyperplane defined by t = 0. Consider a squeeze mapping involving the two variables of each complementary pair of z. The projection of e on the image of L of the mapping lies in an (n+m-1)-sphere Q centered at e/2 of a diameter whose square equals 2(n+m). The sum of the two components of a complementary pair of z in Q equals one, and Q is the circumsphere of the hypercube where each component of its vertices takes value in {0, 1}. One vertex v* called the solution vertex is the indicator vector of a. The algorithm uses squeeze mapping to move the aforementioned projection around v* along Q so that a is identified at certain position. It consists of O(n) unidimensional squeeze mappings, each of which uses O(mn) arithmetic operations. |
| title | Topological structure and a polynomial-time solution of linear programming over the real numbers |
| topic | Optimization and Control 68Q15 68Q25 90C05 |
| url | https://arxiv.org/abs/1805.06342 |