Complexity analysis of primal-dual algorithms for the semidefinite linear complementarity problem

Mohamed Achache; Naima Boudiaf

doi:10.33993/jnaat402-1040

Authors

Mohamed Achache University Ferhat Abbas of Setif, Algeria
Naima Boudiaf University El Hadj Lakhdar, Algeria

DOI:

https://doi.org/10.33993/jnaat402-1040

Keywords:

semidefinite linear complementarity problems, interior point methods, long and small-update primal-dual algorithms, polynomial complexity

Abstract views: 262

Abstract

In this paper a primal-dual path-following interior-point algorithm for the monotone semidefinite linear complementarity problem is presented.
The algorithm is based on Nesterov-Todd search directions and on a suitable proximity for tracing approximately the central-path.
We provide an unified analysis for both long and small-update primal-dual algorithms.
Finally, the iteration bounds for these algorithms are obtained.

Downloads

Download data is not yet available.

References

M. Achache, A new primal-dual path-following method for convex quadratic programming, Comput. Appl. Math., 25, No. 1, pp. 97-110, 2006, https://doi.org/10.1590/s0101-82052006000100005 DOI: https://doi.org/10.1590/S0101-82052006000100005

M. Achache, Complexity analysis and numerical implementation of a short-step primal-dual algorithm for linear complementarity problems, Applied Mathematics and Computation, 216, pp. 1889-1895, 2010, https://doi.org/10.1016/j.amc.2010.03.015 DOI: https://doi.org/10.1016/j.amc.2010.03.015

F. Alizadeh, J.A. Haeberly and M. Overton, Primal-dual interior point methods for semidefinite programming. Convergence rates, stability and numerical results, SIAM J. Optimization, 8, pp. 746-768, 1998, https://doi.org/10.1137/s1052623496304700 DOI: https://doi.org/10.1137/S1052623496304700

J.M. Borwein and A.S. Lewis, Convex Analysis and nonlinear optimization. Theory and Examples, Springer-Verlag, New-York Berlin Heidlberg, pp. 65-96, 2000, https://doi.org/10.1007/978-1-4757-9859-3_4 DOI: https://doi.org/10.1007/978-1-4757-9859-3_4

M. El ghami, New primal-dual interior point methods based on kernels functions, Phd thesis, Delft University, Netherland, 2005.

M.S. Gowda and Y. Song, On semidefinite linear complementarity problem, Mathematical Programming, Series A, 88, pp. 575-587, 2000, https://doi.org/10.1007/pl00011387 DOI: https://doi.org/10.1007/PL00011387

M.S. Gowda, Y. Song, and G. Ravindran, Some interconnections between strong monotonicity, GUS and P properties in semidefinite linear complementarity problems, Linear algebras and its applications, 370, pp. 355-386, 2003. DOI: https://doi.org/10.1016/S0024-3795(03)00425-7

M.S. Gowda and Y. Song, Some new results for the semidefinite linear complementarity problem, SIAM Journal on Matrix Analysis and Applications, 24, no.1, pp. 25-39, 2003. https://doi.org/10.1137/s0895479800377927 DOI: https://doi.org/10.1137/S0895479800377927

M. Kojima, M. Shindoh and S. Hara, Interior point methods for monotone semidefinite linear complementarity problem in symmetric matrices, SIAM J. Optimization, 7, pp. 86-125, 1997, https://doi.org/10.1137/s1052623494269035 DOI: https://doi.org/10.1137/S1052623494269035

Z. Liu and W. Sun, An infeasible interior-point algorithms with full-Newton step for linear optimization, Numer. Algor., 46, pp. 173-188, 2007, https://doi.org/10.1007/s11075-007-9135-x DOI: https://doi.org/10.1007/s11075-007-9135-x

M. Malik and S.R. Mohan, Some geometrical aspects of semidefinite linear complementarity problems, Linear and multilinear algebras, 54 1, pp. 55-70, 2006, https://doi.org/10.1080/03081080512331318463 DOI: https://doi.org/10.1080/03081080512331318463

Y. Nestrov and M. Todd, Self-scaled barriers and interior point methods for convex programming, Mathematics of operations Research, 22, No. 1, pp. 1-42, 1997, https://doi.org/10.1287/moor.22.1.1 DOI: https://doi.org/10.1287/moor.22.1.1

J. Peng, C. Roos and T. Terlaky, A new and efficient large-update interior point method for linear optimization, Vychist. Tekhnol., 6, pp. 61-80, 2001. DOI: https://doi.org/10.1080/1055678021000039175

J. Peng, C. Roos and T. Terlaky, Self-regularity: A new paradigm for primal-dual interior point algorithms. Princeton University Press, Princeton, NJ, 2002.

J. Peng, C. Roos and T. Terlaky, A new class of polynomial primal-dual methods for linear and semidefinite optimization, European J. Oper. Res., 143, pp. 234-256, 2002, https://doi.org/10.1016/s0377-2217(02)00275-8 DOI: https://doi.org/10.1016/S0377-2217(02)00275-8

J. Peng, C. Roos and T. Terlaky, Self-regular functions and new search directions for linear and semidefinite optimization, European Mathematical Programming, 93, pp. 129-171, 2002. https://doi.org/10.1007/s101070200296 DOI: https://doi.org/10.1007/s101070200296

J. Peng, C. Roos and T. Terlaky, New complexity analysis of the primal-dual method for semidefinite optimization based on the Nesterov-Todd direction. Journal of Optimization Theory and Application, 109, No. 2, pp. 327-343, 2001, https://doi.org/10.1023/a:1017514422146 DOI: https://doi.org/10.1023/A:1017514422146

J. Peng, C. Roos and T. Terlaky, New complexity analysis of primal-dual Newton methods for P∗(k) linear complementarity problem, Manuscript, pp. 245-265, 1998, https://doi.org/10.1007/978-1-4757-3216-0_10 DOI: https://doi.org/10.1007/978-1-4757-3216-0_10

C. Roos, T. Terlaky and J.Ph. Vial, Theory and algorithms for linear optimization. An interior point approach, John Wiley and Sons, Chichester, UK, 1997.

Y. Song, The P and globally uniquely solvable properties in semidefinite linear complementarity problem, Phd thesis, University of Maryland, USA, 2000.

J.F. Sturm and S. Zhang, Symmetric primal-dual path-following algorithms for semidefinite programming, Technical report 9554/A, Tinbergen Institute, Erasmus University, Rotterdam, The Netherlands, 1995, https://doi.org/10.1016/s0168-9274(98)00099-3 DOI: https://doi.org/10.1016/S0168-9274(98)00099-3

S.J. Wright, Primal-dual interior point methods, SIAM, Philadelphia, USA, 1997, https://doi.org/10.1137/1.9781611971453 DOI: https://doi.org/10.1137/1.9781611971453