TY - JOUR

T1 - Error bounds for analytic systems and their applications

AU - Luo, Zhi Quan

AU - Pang, Jong Shi

PY - 1994/10

Y1 - 1994/10

N2 - Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vector x in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated at x. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush-Kuhn-Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0-1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.

AB - Using a 1958 result of Lojasiewicz, we establish an error bound for analytic systems consisting of equalities and inequalities defined by real analytic functions. In particular, we show that over any bounded region, the distance from any vector x in the region to the solution set of an analytic system is bounded by a residual function, raised to a certain power, evaluated at x. For quadratic systems satisfying certain nonnegativity assumptions, we show that this exponent is equal to 1/2. We apply the error bounds to the Karush-Kuhn-Tucker system of a variational inequality, the affine variational inequality, the linear and nonlinear complementarity problem, and the 0-1 integer feasibility problem, and obtain new error bound results for these problems. The latter results extend previous work for polynomial systems and explain why a certain square-root term is needed in an error bound for the (monotone) linear complementarity problem.

KW - Affine variational inequality

KW - Analytic systems

KW - Complementarity problem

KW - Error bound

KW - Integer feasibility problem

KW - Karush-Kuhn-Tucker conditions

UR - http://www.scopus.com/inward/record.url?scp=0028524430&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028524430&partnerID=8YFLogxK

U2 - 10.1007/BF01582210

DO - 10.1007/BF01582210

M3 - Article

AN - SCOPUS:0028524430

SN - 0025-5610

VL - 67

SP - 1

EP - 28

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -