We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
An entire space polynomial-time algorithm for linear programming.
- Authors
Tian, Da
- Abstract
We propose an entire space polynomial-time algorithm for linear programming. First, we give a class of penalty functions on entire space for linear programming by which the dual of a linear program of standard form can be converted into an unconstrained optimization problem. The relevant properties on the unconstrained optimization problem such as the duality, the boundedness of the solution and the path-following lemma, etc, are proved. Second, a self-concordant function on entire space which can be used as penalty for linear programming is constructed. For this specific function, more results are obtained. In particular, we show that, by taking a parameter large enough, the optimal solution for the unconstrained optimization problem is located in the increasing interval of the self-concordant function, which ensures the feasibility of solutions. Then by means of the self-concordant penalty function on entire space, a path-following algorithm on entire space for linear programming is presented. The number of Newton steps of the algorithm is no more than $$O(nL\log (nL/ {\varepsilon }))$$, and moreover, in short step, it is no more than $$O(\sqrt{n}\log (nL/{\varepsilon }))$$.
- Subjects
POLYNOMIAL time algorithms; LINEAR programming; CONCORDANCES (Topology); MATHEMATICAL optimization; DUALITY theory (Mathematics)
- Publication
Journal of Global Optimization, 2014, Vol 58, Issue 1, p109
- ISSN
0925-5001
- Publication type
Article
- DOI
10.1007/s10898-013-0048-z