ISSN:
1436-4646
Keywords:
90C05
;
90C25
;
90C31
;
49M30
;
Linear programming
;
Exponential penalty
;
Optimal trajectory
;
Asymptotic expansion
;
Interior point methods
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider the linear program min{c′x: Ax⩽b} and the associated exponential penalty functionf r(x) = c′x + rΣexp[(A ix − bi)/r]. Forr close to 0, the unconstrained minimizerx(r) off r admits an asymptotic expansion of the formx(r) = x * + rd* + η(r) wherex * is a particular optimal solution of the linear program and the error termη(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectoryλ(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to ∞: the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01582220
Permalink