Plynomial Convergence of Primal-Dual Algorithms for SDLCP Based on the Monteiro-Zhang Family of Directions

Abstract:

The paper establishes the polynomial converge-nce of a new class of path-following methods for semide- finite linear complementarity problems (SDLCP) whos-se search directions belong to the class of directions introduced by Monteiro [7]. Namely, we show that the polynomial iteration complexity bounds of the well known algori-thm for linear programming, namely the short-step path-following algorithm of Kojima et al. and Monteiro and Alder, carry over to the context of SDLCP

• Periodical: Advanced Materials Research (Volumes 532-533)
• Pages: 1857-1860
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.532-533.1857
• Online since: June 2012
• Authors: Guang Zhou Li
• Keywords: Interior-Point Algorithm, Path-Following Method, Semidefinite Linear Complementarity Problems

References

[1] Y. E. Nesterod and A. S. Nemirovskii, Interior Point methods in Convex Programming: Theory and Applications, SIAM, Philadelphia, (1994).

[2] F. Alizadeh, Interior point methods in semidefinite programmi-ing with applications to combinatorial optimization, SIAM J. Optim. 5(1995)13-51.

DOI: 10.1137/0805002

[3] F Alizadeh, JPA Haeberly, ML Overton , Primal-dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM Journal on Optimization, pp.746-768, 1998.

DOI: 10.1137/s1052623496304700

[4] Helmber. C, Rendl. F, Vanderbei R. J, Wolkowicz, An interior point method for semidefinite programming, SIAM Journal on Optimization pp: 342-361, (1996).

DOI: 10.1137/0806020

[5] Kojima. M, Shida. M, Shindoh. S, Local convergence of predict-or-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Mathematical Programming, pp.129-160, (1998).

DOI: 10.1007/bf01581723

[6] M. Kojima S. Shindoh S. Hara, Interior-point methods for the monotone semidefinite linear complementarity problem in symmetric matrices. SIAM Journal on Optimization , vol. 7, No. 1, pp.86-125, (1997).

DOI: 10.1137/s1052623494269035

[7] R.D.C. Monteiro, Primal–Dual Path-Following Algorithms for Semidefinite Programming, SIAM Journal on Optimization, Volume7, Issue3, pp: 663 - 678, (1997).

DOI: 10.1137/s1052623495293056

[8] R.D.C. Monteiro, Polynomial convergence of primal-dual algorithms for semidefinite programming based on the Monteiro and Zhang family of directions , SIAM Journal on Optimization, Volume8, pp: 797-812, (1998).

DOI: 10.1137/s1052623496308618

[9] R.D.C. Monteiro and Y. Zhang, A unified analysis for a class of path-following primal- dual interior-point algorithms for semidefinite programming, Math. program, pp: 281-299, (1998).

DOI: 10.1007/bf01580085

[10] R.D.C. Monteiro and Y. Zhang, Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming, SIAM Journal on Optimization, Volume9, No3, pp: 551-577, (1999).

DOI: 10.1137/s1052623496312836

[11] Yin Zhang, On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM Journal on Optimization, pp: 365-386, (1998).

DOI: 10.1137/s1052623495296115

[12] M. Shida, S. Shindoh and M. Kojima, Existence of Search Direction in Interior-Point Algorithms for the SDP and the Monotone SDLCP. SIAM Journal on Optimization, Vol. 8, 387-396, (1998).

DOI: 10.1137/s1052623496300611