ISSN:
1436-4646
Keywords:
Linear programming
;
Interior point method
;
Potential function
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We propose a polynomial time primal—dual potential reduction algorithm for linear programming. The algorithm generates sequencesd k andv k rather than a primal—dual interior point (x k ,s k ), where $$d_i^k = \sqrt {{{x_i^k } \mathord{\left/ {\vphantom {{x_i^k } {s_i^k }}} \right. \kern-\nulldelimiterspace} {s_i^k }}} $$ and $$v_i^k = \sqrt {x_i^k s_i^k }$$ fori = 1, 2,⋯,n. Only one element ofd k is changed in each iteration, so that the work per iteration is bounded by O(mn) using rank-1 updating techniques. The usual primal—dual iteratesx k ands k are not needed explicitly in the algorithm, whereasd k andv k are iterated so that the interior primal—dual solutions can always be recovered by aforementioned relations between (x k, sk) and (d k, vk) with improving primal—dual potential function values. Moreover, no approximation ofd k is needed in the computation of projection directions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01584845
Permalink
