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

• 成果类型: Article
• 署名作者: Sim, Chee-Khian; Zhao, Gongyun
• 署名单位: National University of Singapore; National University of Singapore
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-006-0010-7
• 发表日期: 2007
• 页码: 475-499
• 关键词: limiting behavior; superlinear convergence; continuous trajectories; local convergence; algorithms; complexity; analyticity; PROGRAMS; Affine

摘要

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 mu ranging over (0, infinity) 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 root mu and have first derivatives which are unbounded as a function of mu at mu = 0 in general. On the other hand, for the same example, we can find a subset of off-central paths which are analytic at mu = 0. These nice paths are characterized by some algebraic equations.