TY - JOUR

T1 - Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem

AU - Sim, Chee-Khian

AU - Zhao, Gongyun

PY - 2007/9

Y1 - 2007/9

N2 - An interior point method defines a search direction at each interior point of the feasible region. The search directions at all interior points together form a direction field, which gives rise to a system of ordinary differential equations (ODEs). Given an initial point in the interior of the feasible region, the unique solution of the ODE system is a curve passing through the point, with tangents parallel to the search directions along the curve. We call such curves off-central paths. We study off-central paths for the monotone semidefinite linear complementarity problem (SDLCP). We show that each off-central path is a well-defined analytic curve with parameter μ ranging over (0, ∞) and any accumulation point of the off-central path is a solution to SDLCP. Through a simple example we show that the off-central paths are not analytic as a function of μ √ and have first derivatives which are unbounded as a function of μ at μ = 0 in general. On the other hand, for the same example, we can find a subset of off-central paths which are analytic at μ = 0. These “nice” paths are characterized by some algebraic equations.

AB - An interior point method defines a search direction at each interior point of the feasible region. The search directions at all interior points together form a direction field, which gives rise to a system of ordinary differential equations (ODEs). Given an initial point in the interior of the feasible region, the unique solution of the ODE system is a curve passing through the point, with tangents parallel to the search directions along the curve. We call such curves off-central paths. We study off-central paths for the monotone semidefinite linear complementarity problem (SDLCP). We show that each off-central path is a well-defined analytic curve with parameter μ ranging over (0, ∞) and any accumulation point of the off-central path is a solution to SDLCP. Through a simple example we show that the off-central paths are not analytic as a function of μ √ and have first derivatives which are unbounded as a function of μ at μ = 0 in general. On the other hand, for the same example, we can find a subset of off-central paths which are analytic at μ = 0. These “nice” paths are characterized by some algebraic equations.

U2 - 10.1007/s10107-006-0010-7

DO - 10.1007/s10107-006-0010-7

M3 - Article

VL - 110

SP - 475

EP - 499

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 3

ER -