Accession Number:

ADA455580

Title:

The Dikin-Karmarkar Principle for Steepest Descent

Descriptive Note:

Doctoral thesis

Corporate Author:

RICE UNIV HOUSTON TX

Personal Author(s):

• Samuelsen, Catherine M.

Report Date:

1992-09-01

Pagination or Media Count:

53.0

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 or even convergence to non-stationary points zigzagging. In linear programming, both the projective algorithm of Karmarkar 1984 and its affine 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 satisfactory convergence.

Descriptors:

• *LINEAR PROGRAMMING
• *STEEPEST DESCENT METHOD
• ALGORITHMS
• NUMERICAL ANALYSIS
• FEASIBILITY STUDIES
• CONVERGENCE
• THESES
• OPTIMIZATION

Subject Categories:

• Numerical Mathematics
• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE