Show simple item record

dc.contributor.authorSamuelsen, Catherine M.
dc.date.accessioned 2018-06-18T17:39:40Z
dc.date.available 2018-06-18T17:39:40Z
dc.date.issued 1992-09
dc.identifier.citation Samuelsen, Catherine M.. "The Dikin-Karmarkar Principle for Steepest Descent." (1992) https://hdl.handle.net/1911/101769.
dc.identifier.urihttps://hdl.handle.net/1911/101769
dc.descriptionThis work was also published as a Rice University thesis/dissertation: http://hdl.handle.net/1911/16565
dc.description.abstract Steepest feasible descent methods for inequality constrained optimization problems have commonly been plagued by short steps. The consequence of taking short steps is slow convergence to non-stationary points (zigzagging). In linear programming, both the projective algorithm of Karmarkar (1984) and its affined-variant, originally proposed by Dikin (1967), can be viewed as steepest feasible descent methods. However, both of these algorithms have been demonstrated to be effective and seem to have overcome the problem of short steps. These algorithms share a common norm. It is this choice of norm, in the context of steepest feasible descent, that we refer to as the Dikin-Karmarkar Principle. This research develops mathematical theory to quantify the short step behavior of Euclidean norm steepest feasible descent methods and the avoidance of short steps for steepest feasible descent with respect to the Dikin-Karmarkar norm. While the theory is developed for linear programming problems with only nonnegativity constraints on the variables. Our numerical experimentation demonstrates that this behavior occurs for the more general linear program with equality constraints added. Our numerical results also suggest that taking longer steps is not sufficient to ensure the efficiency of a steepest feasible descent algorithm. The uniform way in which the Dikin-Karmarkar norm treats every boundary is important in obtaining a satisfactory convergence.
dc.format.extent 60 pp
dc.title The Dikin-Karmarkar Principle for Steepest Descent
dc.type Technical report
dc.date.note September 1992
dc.identifier.digital TR92-29
dc.type.dcmi Text


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record