Accession Number:

ADA191334

Title:

Iterative Methods for Linear Complementarity and Related Problems.

Descriptive Note:

Final rept. 1 Sep 85-31 Jan 86,

Corporate Author:

MISSOURI UNIV-COLUMBIA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Shiau, Tzong-Huei

Report Date:

1986-01-01

Pagination or Media Count:

4.0

Abstract:

We have established that solutions of linear programs are globally Lipschitz continuous with respect to right-hand side perturbation of the constraints, but are not even locally Lipschitz continuous with respect to perturbation of the cost function. The latter implies that solutions of monotone linear complementarity problems are not Lipschitz continuous with respect to right-hand side perturbation of the constraints. On the other hand, we established that solutions of linear complementary problems with matrices with positive principal minors do have this Lipschitz continuity property. This includes strictly monotone linear complementary problems. We established that the distance between an arbitrary point and the solution set of a monotone linear complementarity problem is bounded by the product of a condition of the complementarity problem conditions by the point considered. When the point violates only the complementary condition, but satisfies the linear equalities, the residual consists of x to the T power times Mxq plus its square root. The square root term is essential and without which the bound cannot hold. The result has import applications in the design and analysis of iterative methods for solving monotone linear complementarity problems.

Descriptors:

• *LINEAR PROGRAMMING
• CONTINUITY
• COSTS
• ITERATIONS
• LINEARITY
• MONOTONE FUNCTIONS
• PERTURBATIONS
• SOLUTIONS(GENERAL)
• SQUARE ROOTS
• INEQUALITIES

Subject Categories:

• Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE