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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Adler I., Monteiro R.D.C. (1991) Limiting behavior of the affine scaling continuous trajectories for linear programming problems. Math. Program. 50(1): Series A, 29–51
Amann, H. Ordinary Differential Equations : An Introduction to Nonlinear Analysis, (translated from German by Gerhard Metzen) de Gruyter Studies in Mathematics vol 13 (1990)
Bayer, D.A., Lagarias, J.C. The nonlinear geometry of linear programming, I, II, III. Trans. Am. Math. Soc. 314, 499–526, 527–581 (1989) and 320, 193–225 (1990)
Birkhoff, G., Rota, G.-C. Ordinary Differential Equations, 4th edn (1989)
Chua C.B. (2006) A new notion of weighted centers for semidefinite programming. SIAM J. Optimi. 16(4): 1092–1109
Güler, O. Limiting behavior of weighted central paths in linear programming. Math. Program. 65(3),Series A, 347–363 (1994)
Halická M. (2002) Analyticity of the central path at the boundary point in semidefinite programming. European J. Opera. Res. 143, 311–324
Ince, E.L. Ordinary Differential Equations. Dover Publications (1956)
Kojima, M., Shida, M., Shindoh, S. Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Math. Program. 80(72), Series A, 129–160 (1998)
Kojima M., Shindoh S., Hara S. (1997) Interior-point methods for the monotone semidefinite linear complementarity problems. SIAM J. Optimi. 7, 86–125
Lu Z., Monteiro R.D.C. (2004) Error bounds and limiting behavior of weighted paths associated with the SDP map X 1/2 SX 1/2. SIAM J. Optimi. 15(2): 348–374
Lu, Z., Monteiro, R.D.C. Limiting behavior of the Alizadeh-Haeberly-Overton weighted paths in semidefinite programming, Preprint, July 24, 2003
Megiddo N., Mizuno S., Tsuchiya T. (1998) A modified layered-step interior-point algorithm for linear programming. Math. Program. 82, 339–355
Mehrotra S. (1993) Quadratic convergence in a primal-dual method. Math. Opera. Res. 18, 741–751
Monteiro R.D.C. (1997) Primal-dual path following algorithms for semidefinite programming. SIAM J. Optimi. 7, 663–678
Monteiro R.D.C., Pang J.-S. (1996) Properties of an interior-point mapping for mixed complementarity problems. Math. Opera. Res. 21(3): 629–654
Monteiro R.D.C., Pang J.-S. (1998) On two interior-point mappings for nonlinear semidefinite complementarity problems. Math. Opera. Res. 23(1): 39–60
Monteiro R.D.C., Tsuchiya T. (1996) Limiting behavior of the derivatives of certain trajectories associated with a monotone horizontal linear complementarity problem. Math. Oper. Rese. 21(4): 793–814
Monteiro R.D.C., Tsuchiya T. (2003) A variant of the Vavasis-Ye layered-step interior-point algorithm for linear programming. SIAM J. Optimi. 23(4): 1054–1079
Monteiro R.D.C., Zanjácomo P.R. (2000) General interior-point maps and existence of weighted paths for nonlinear semidefinite complementarity problems. Math. Oper. Res. 25(3): 381–399
Potra F.A., Sheng R. (1998) Superlinear convergence of interior-point algorithms for semidefinite programming. J. Optim. Theory Appl. 99(1): 103–119
Preiß M., Stoer, J. Analysis of infeasible-interior-point paths arising with semidefinite linear complementarity problems. Math. Program. 99(3), Series A, 499–520 (2004)
Sim, C.-K. Underlying Paths and Local Convergence Behaviour of Path-following Interior Point Algorithm for SDLCP and SOCP. Ph.D. Thesis, National University of Singapore, (2004)
Sonnevend G. (1985). An analytic center for polyhedrons and new classes for linear programming. In: Prekopa A. (eds). System Modelling and Optimization, Lecture Notes in Control and Information Sciences, vol. 84, Springer, Berlin Heidelberg New York, pp. 866–876
Sonnevend G., Stoer J., Zhao G. (1989) On the complexity of following the central path of linear programs by linear extrapolation. Methods Opera. Res. 62, 19–31
Sonnevend G., Stoer J., Zhao G. (1991) On the complexity of following the central path of linear programs by linear extrapolation II. Math. Program. 52, 527–553
Stoer J., Wechs M. (1999) On the analyticity properties of infeasible-interior-point paths for monotone linear complementarity problems. Nume. Mathe. 81(4): 631–645
Stoer J., Wechs M., Mizuno S. (1998) High order infeasible-interior-point methods for solving sufficient linear complementarity problems. Mathe. Opera. Res. 23(4): 832–862
Sturm J.F. (1999) Superlinear convergence of an algorithm for monotone linear complementarity problems, when no strictly complementary solution exists. Math. Oper. Res. 24(1): 72–94
Todd M.J., Toh K.C., Tütüncü R.H. (1998) On the Nesterov-Todd direction in semidefinite programming. SIAM J. Optimi. 8(3): 769–796
Tütüncü R.H. (2003) Asymptotic behavior of continuous trajectories for primal-dual potential-reduction methods. SIAM J. Optimi. 14(2): 402–414
Vavasis S.A., Ye Y. (1996) A primal-dual interior point method whose running time depends only on the contraint matrix. Math. Program. 74(1): 79–120
Ye Y., Anstreicher K. (1993) On quadratic and \(o(\sqrt{n}l)\) convergence of a predictor-corrector algorithm for LCP. Math. Program. 62, 537–551
Ye Y., Güler O., Tapia R.A., Zhang Y. (1993) A quadratically convergence \(o(\sqrt{n}l)\)-iteration algorithm for linear programming. Math. Program. 59, 151–162
Zhang Y. (1998) On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optimi. 8(2): 365–386
Zhao G. (1996) On the relationship between the curvature integral and the complexity of path-following methods in linear programming. SIAM J. Optimi. 6(1): 57–73
Zhao G., Stoer J. (1993) Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals. Appl. Math. Optim. 27(1): 85–103
Zhao G., Sun J. (1999) On the rate of local convergence of high-order-infeasible-path-following algorithms for P *-linear complementarity problems. Computa. Optim. Appl. 14, 293–307
Zhao G., Zhu J. (1996) The curvature integral and the complexity of linear complementarity problems. Math. Program. 70, 107–122
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was done during the author’s PhD study at the Department of Mathematics, NUS and as a Research Engineer at the NUS Business School.
Rights and permissions
About this article
Cite this article
Sim, CK., Zhao, G. Underlying paths in interior point methods for the monotone semidefinite linear complementarity problem. Math. Program. 110, 475–499 (2007). https://doi.org/10.1007/s10107-006-0010-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-006-0010-7