Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/4444
Title: Asymptotic behavior of underlying NT paths in interior point methods for monotone semidefinite linear complementarity problems
Authors: Sim, CK
Keywords: Semidefinite linear complementarity problem
Interior point methods
NT direction
Local convergence
Ordinary differential equations
Issue Date: Jan-2011
Publisher: Springer
Source: Journal of optimization theory and applications, Jan. 2011, v. 148, no. 1, p. 79-106 How to cite?
Journal: Journal of optimization theory and applications 
Abstract: An interior point method (IPM) defines a search direction at each interior point of the feasible region. These search directions form a direction field, which in turn gives rise to a system of ordinary differential equations (ODEs). Thus, it is natural to define the underlying paths of the IPM as solutions of the system of ODEs. In Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007), these off-central paths are shown to be well-defined analytic curves and any of their accumulation points is a solution to the given monotone semidefinite linear complementarity problem (SDLCP). In Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007; J. Optim. Theory Appl. 137:11–25, 2008) and Sim (J. Optim. Theory Appl. 141:193–215, 2009), the asymptotic behavior of off-central paths corresponding to the HKM direction is studied. In particular, in Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007), the authors study the asymptotic behavior of these paths for a simple example, while, in Sim and Zhao (J. Optim. Theory Appl. 137:11–25, 2008) and Sim (J. Optim. Theory Appl. 141:193–215, 2009), the asymptotic behavior of these paths for a general SDLCP is studied. In this paper, we study off-central paths corresponding to another well-known direction, the Nesterov-Todd (NT) direction. Again, we give necessary and sufficient conditions for these off-central paths to be analytic w.r.t. √μ and then w.r.t. μ, at solutions of a general SDLCP. Also, as in Sim and Zhao (Math. Program. Ser. A 110:475–499, 2007), we present off-central path examples using the same SDP, whose first derivatives are likely to be unbounded as they approach the solution of the SDP. We work under the assumption that the given SDLCP satisfies a strict complementarity condition.
URI: http://hdl.handle.net/10397/4444
ISSN: 0022-3239
EISSN: 1573-2878
DOI: 10.1007/s10957-010-9746-6
Rights: ©Springer Science+Business Media, LLC 2010. The original publication is available at http://www.springerlink.com.
Appears in Collections:Journal/Magazine Article

Files in This Item:
File Description SizeFormat 
SDLCPNTDirectionSubmittedRevisedFinal_r.pdfPre-published version259.43 kBAdobe PDFView/Open
Access
View full-text via PolyU eLinks SFX Query
Show full item record

Page view(s)

338
Last Week
4
Last month
Checked on Aug 20, 2017

Download(s)

299
Checked on Aug 20, 2017

Google ScholarTM

Check

Altmetric



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.