Paper Info
Title
Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem
Abstract
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 $$\sqrt{\mu}$$ 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.
Year
DOI
Venue
2007
10.1007/s10107-006-0010-7
Math. Program.
Keywords
Field
DocType
initial point,interior point,accumulation point,search direction,off-central path,interior point method,ode system,curves off-central path,feasible region,underlying path,monotone semidefinite linear complementarity,well-defined analytic curve,linear complementarity problem
Mathematical optimization,Mathematical analysis,Analytic function,Feasible region,Tangent,Linear complementarity problem,Limit point,Interior point method,Semidefinite programming,Monotone polygon,Mathematics
Journal
Volume
Issue
ISSN
110
3
1436-4646
Citations 
PageRank 
References 
6
0.44
25
Authors
2
Name
Order
Citations
PageRank
Chee-Khian Sim1235.43
Gongyun Zhao215415.68