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 the solutions of the system of ODEs. In Sim and Zhao (Math. Program. Ser. A, [2007], to appear), 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). Off-central paths for a simple example are also studied in Sim and Zhao (Math. Program. Ser. A, [2007], to appear) and their asymptotic behavior near the solution of the example is analyzed. In this paper, which is an extension of Sim and Zhao (Math. Program. Ser. A, [2007], to appear), we study the asymptotic behavior of the off-central paths for general SDLCPs using the dual HKM direction. We give a necessary and sufficient condition for when an off-central path is analytic as a function of \(\sqrt{\mu}\) at a solution of the SDLCP. Then, we show that, if the given SDLCP has a unique solution, the first derivative of its off-central path, as a function of \(\sqrt{\mu}\) , is bounded. We work under the assumption that the given SDLCP satisfies the strict complementarity condition.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Sonnevend, G.: An analytic center for polyhedrons and new classes for linear programming. In: Prekopa, A. (ed.) System Modelling and Optimization. Lecture Notes in Control and Information Sciences, vol. 84, pp. 866–876. Springer, Berlin (1985)
Bayer, D.A., Lagarias, J.C.: The nonlinear geometry of linear programming, Part I. Trans. Am. Math. Soc. 314, 499–526 (1989)
Bayer, D.A., Lagarias, J.C.: The nonlinear geometry of linear programming, Part II. Trans. Am. Math. Soc. 314, 527–581 (1989)
Bayer, D.A., Lagarias, J.C.: The nonlinear geometry of linear programming, Part III. Trans. Am. Math. Soc. 320, 193–225 (1990)
Sonnevend, G., Stoer, J., Zhao, G.: On the complexity of following the central path of linear programs by linear extrapolation. Method. Oper. Res. 62, 19–31 (1989)
Sonnevend, G., Stoer, J., Zhao, G.: On the complexity of following the central path of linear programs by linear extrapolation II. Math. Program. 52, 527–553 (1991)
Zhao, G., Stoer, J.: Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals. Appl. Math. Optim. 27, 85–103 (1993)
Zhao, G.: On the relationship between the curvature integral and the complexity of path-following methods in linear programming. SIAM J. Optim. 6, 57–73 (1996)
Zhao, G., Zhu, J.: The curvature integral and the complexity of linear complementarity problems. Math. Program. 70, 107–122 (1996)
Vavasis, S.A., Ye, Y.: A primal-dual interior point method whose running time depends only on the contraint matrix. Math. Program. 74, 79–120 (1996)
Mehrotra, S.: Quadratic convergence in a primal-dual method. Math. Oper. Res. 18, 741–751 (1993)
Ye, Y., Anstreicher, K.: On quadratic and \(O(\sqrt{n}L)\) convergence of a predictor-corrector algorithm for LCP. Math. Program. 62, 537–551 (1993)
Ye, Y., Güler, O., Tapia, R.A., Zhang, Y.: A quadratically convergence \(O(\sqrt{n}L)\) -iteration algorithm for linear programming. Math. Program. 59, 151–162 (1993)
Sturm, J.F.: Superlinear convergence of an algorithm for monotone linear complementarity problems, when no strictly complementary solution exists. Math. Oper. Res. 24, 72–94 (1999)
Lu, Z., Monteiro, R.D.C.: Error bounds and limiting behavior of weighted paths associated with the SDP map X 1/2 SX 1/2. SIAM J. Optim. 15, 348–374 (2004)
Lu, Z., Monteiro, R.D.C.: Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming. Optim. Method. Softw. 22, 849–870 (2003)
Preiß, M., Stoer, J.: Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems Math. Program. A 99, 499–520 (2004)
Sim, C.-K., Zhao, G.: Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem. Math. Program. A 110, 475–499 (2007)
Da Cruz Neto, J.X., Ferreira, O.P., Monteiro, R.D.C.: Asymptotic behavior of the central path for a special class of degenerate SDP problems. Math. Program. A 103, 487–514 (2005)
Todd, M.J., Toh, K.C., Tütüncü, R.H.: On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optim. 8, 769–796 (1998)
Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8, 365–386 (1998)
Asymptotic behavior of HKM paths in interior point methods for monotone semidefinite linear complementarity problems: General theory. The Logistics Institute—Asia Pacific Internal Report. See also http://www.math.nus.edu.sg/~matzgy/publist.html
Halická, M., De Klerk, E., Roos, C.: On the convergence of the central path in semidefinite optimization. SIAM J. Optim. 12, 1090–1099 (2002)
Stoer, J., Wechs, M., Mizuno, S.: High order infeasible-interior-point methods for solving sufficient linear complementarity problems. Math. Oper. Res. 23, 832–862 (1998)
Zhao, G., Sun, J.: On the rate of local convergence of high-order-infeasible-path-following algorithms for P * -linear complementarity problems. Comput. Optim. Appl. 14, 293–307 (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by P. Tseng.
This research was done during the first author’s Ph.D. study at the Department of Mathematics, National University of Singapore, and as a Research Engineer at the NUS Business School. The second author’s work was supported in part by NUS Academic Research Grant R-146-000-084-112.
For technical details of the paper, please refer to The Logistics Institute—Asia Pacific Internal Report. See also http://www.math.nus.edu.sg/~matzgy/publist.html.
Rights and permissions
About this article
Cite this article
Sim, C.K., Zhao, G. Asymptotic Behavior of Helmberg-Kojima-Monteiro (HKM) Paths in Interior-Point Methods for Monotone Semidefinite Linear Complementarity Problems: General Theory. J Optim Theory Appl 137, 11–25 (2008). https://doi.org/10.1007/s10957-007-9280-3
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10957-007-9280-3