ISSN:
1432-5217
Keywords:
Convex Programming
;
Primal-dual Methods
;
Path Following
;
Interior Point Algorithm
;
Entropy Optimization
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract We present a primal-dual path following interior algorithm for a class of linearly constrained convex programming problems with non-negative decision variables. We introduce the definition of a Scaled Lipschitz Condition and show that if the objective function satisfies the Scaled Lipschitz Condition then, at each iteration, our algorithm reduces the duality gap by at least a factor of (1−δ/√n), whereδ is positive and depends on the curvature of the objective function, by means of solving a system of linear equations which requires no more than O(n3) arithmetic operations. The class of functions having the Scaled Lipschitz Condition includes linear, convex quadratic and entropy functions.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01416235
Permalink