Conical projection algorithms for linear programming

Conical projection algorithms for linear programming

0.00 Avg rating0 Votes
Article ID: iaor1988741
Country: Netherlands
Volume: 43
Issue: 2
Start Page Number: 151
End Page Number: 173
Publication Date: Feb 1989
Journal: Mathematical Programming (Series A)
Authors:
Abstract:

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar’s logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algotithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. The paper shows that Karmarkar’s algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar’s method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.

Reviews

Required fields are marked *. Your email address will not be published.