An arc search interior-point algorithm for monotone linear complementarity problems over symmetric cones
Abstract
An arc search interior-point algorithm for monotone symmetric cone linear complementarity problem is presented. The algorithm estimates the central path by an ellipse and follows an ellipsoidal approximation of the central path to reach an ε-approximate solution of the problem in a wide neighborhood of the central path. The convergence analysis of the algorithm is derived. Furthermore, we prove that the algorithm has the complexity bound O (√rL) using Nesterov-Todd search direction and O (√rL) by the xs and sx search directions. The obtained iteration complexities coincide with the best-known ones obtained by any proposed interior-point algorithm for this class of mathematical problems.
Keyword : linear complementarity problem, symmetric cone, ellipsoidal approximation, interior-point methods, polynomial complexity
How to Cite
Pirhaji, M., Zangiabadi, M., Mansouri, H., & Amin, S. H. (2018). An arc search interior-point algorithm for monotone linear complementarity problems over symmetric cones. Mathematical Modelling and Analysis, 23(1), 1-16. https://doi.org/10.3846/mma.2018.001
This work is licensed under a Creative Commons Attribution 4.0 International License.
References
W. Ai and S.Z Zhang. An o(√nl) iteration primal-dual path-following method,based on wide neighborhoods and large updates, for monotone LCP. SIAM J.Optim, 16(2):400–417, 2005. https://doi.org/10.1137/040604492
M.P. Carmo. Differential Geometry of Curves and Surfaces. Prentice-Hall, New Jersey, 1976.
J. Faraut and A. Korányi. Analysis on Symmetric Cones. Oxford University Press, Oxford, UK, 1994.
L. Faybusovich. Euclidean Jordan algebras and interior-point algorithms. Positivity, 1(4):331–357, 1997. https://doi.org/10.1023/A:1009701824047
M.S Gowda and R. Sznajder. Some global uniquness and solvability results for linear complementarity problems over symmetric cones. SIAM J. Optim,18(2):461–481, 2007. https://doi.org/10.1137/06065943X
G. Gu. Full-step interior point methods for symmetric optimization. Faculty of Mathematics and Computer Science, TU Delft, NL–2628 CD Delft, The Netherlands, 2009.
N. Karmarkar. A new polynomial-time algorithm for linear programming. Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp.302–311, 1984. https://doi.org/10.1145/800057.808695
B. Kheirfam and N. Mahdavi-Amiri. A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem. Optim. Lett., 8(3):1017–1029, 2014. https://doi.org/10.1007/s11590-013-0618-5
B. Kheirfam and N. Mahdavi-Amiri. An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem. Optimization, 64(7):1577–1591, 2015. https://doi.org/10.1080/02331934.2013.869877
Y. Li and T. Terlaky. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with $O\br{\sqrt{n}\log\br{\frac{Tr\br{X^0S^0}}{\varepsilon}} }$ iteration complexity. SIAM J. Optim, 20(6):2853–2875,2010. https://doi.org/10.1137/080729311
Y. Lim. Geometric means on symmetric cones. Arch. Math., 75(1):39–56, 2000. https://doi.org/10.1007/s000130050471
C. Liu. Study on complexity of some interior-point algorithms in conic programming. Xixian University, 2012.
X. Yang, H. Liu and Y. Zhang. A new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming. J. Optim.Theory Appl., 166(2):572–587, 2015. https://doi.org/10.1007/s10957-014-0670-z
X. Yang, H. Liu and Y. Zhang. An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path. Optim.Lett., 11(1):135–152, 2016. https://doi.org/10.1007/s11590-016-0997-5
B.K. Rangarajan. Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim., 16(4):1211–1229, 2006. https://doi.org/10.1137/040606557
C. Roos. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim., 16(2):1110–1136, 2006. https://doi.org/10.1137/050623917
S.H. Schmieta and F. Alizadeh. Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. Ser A, 96(3):409–438, 2003. https://doi.org/10.1007/s10107-003-0380-z
H. Liu, X. Yang and C. Liu. A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. J. Optim. Theory Appl.,158(3):796–815, 2013. https://doi.org/10.1007/s10957-013-0303-y
Y. Yang. A polynomial arc-search interior-point algorithm for convex quadratic programming. Eur. J. Oper. Res., 215(1):25–38, 2011. https://doi.org/10.1016/j.ejor.2011.06.020
Y. Yang. A polynomial arc-search interior-point algorithm for linear programming. J. Optim. Theory Appl., 158(3):859–873, 2013. https://doi.org/10.1007/s10957-013-0281-0
Y. Yoshise. Interior-point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM J. Optim., 17(4):1129–1153, 2006. https://doi.org/10.1137/04061427X
G.Q. Wang, M. Li, Y. Yue and X. Cai. New complexity analysis of interior-point methods for the Cartesian p∗(κ)-SCLCP. J. Ineq. Appl., 285:1–23, 2013.
G. Gu, M. Zangiabadi and C. Roos. Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. European J. Oper. Res., 214(3):473–484, 2011. https://doi.org/10.1016/j.ejor.2011.02.022
M. Pirhaji, M. Zangiabadi and H. Mansouri. An ℓ2-neighborhood infeasible interior-point algorithm for linear complementarity problems. 4OR-Q. J. Oper.Res., 15(2):111–131, 2016. https://doi.org/10.1007/s10288-016-0325-z
X. Yang, Y. Zhang and H. Liu. A wide neighborhood infeasible-interior-point method with arc-search for linear programming. J. Appl. Math. Comput., 51(1-2):209–225, 2016. https://doi.org/10.1007/s12190-015-0900-z
M.P. Carmo. Differential Geometry of Curves and Surfaces. Prentice-Hall, New Jersey, 1976.
J. Faraut and A. Korányi. Analysis on Symmetric Cones. Oxford University Press, Oxford, UK, 1994.
L. Faybusovich. Euclidean Jordan algebras and interior-point algorithms. Positivity, 1(4):331–357, 1997. https://doi.org/10.1023/A:1009701824047
M.S Gowda and R. Sznajder. Some global uniquness and solvability results for linear complementarity problems over symmetric cones. SIAM J. Optim,18(2):461–481, 2007. https://doi.org/10.1137/06065943X
G. Gu. Full-step interior point methods for symmetric optimization. Faculty of Mathematics and Computer Science, TU Delft, NL–2628 CD Delft, The Netherlands, 2009.
N. Karmarkar. A new polynomial-time algorithm for linear programming. Proceedings of the 16th Annual ACM Symposium on Theory of Computing, pp.302–311, 1984. https://doi.org/10.1145/800057.808695
B. Kheirfam and N. Mahdavi-Amiri. A new interior-point algorithm based on modified Nesterov-Todd direction for symmetric cone linear complementarity problem. Optim. Lett., 8(3):1017–1029, 2014. https://doi.org/10.1007/s11590-013-0618-5
B. Kheirfam and N. Mahdavi-Amiri. An infeasible interior-point algorithm based on modified Nesterov and Todd directions for symmetric linear complementarity problem. Optimization, 64(7):1577–1591, 2015. https://doi.org/10.1080/02331934.2013.869877
Y. Li and T. Terlaky. A new class of large neighborhood path-following interior point algorithms for semidefinite optimization with $O\br{\sqrt{n}\log\br{\frac{Tr\br{X^0S^0}}{\varepsilon}} }$ iteration complexity. SIAM J. Optim, 20(6):2853–2875,2010. https://doi.org/10.1137/080729311
Y. Lim. Geometric means on symmetric cones. Arch. Math., 75(1):39–56, 2000. https://doi.org/10.1007/s000130050471
C. Liu. Study on complexity of some interior-point algorithms in conic programming. Xixian University, 2012.
X. Yang, H. Liu and Y. Zhang. A new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming. J. Optim.Theory Appl., 166(2):572–587, 2015. https://doi.org/10.1007/s10957-014-0670-z
X. Yang, H. Liu and Y. Zhang. An arc-search infeasible-interior-point method for symmetric optimization in a wide neighborhood of the central path. Optim.Lett., 11(1):135–152, 2016. https://doi.org/10.1007/s11590-016-0997-5
B.K. Rangarajan. Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim., 16(4):1211–1229, 2006. https://doi.org/10.1137/040606557
C. Roos. A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim., 16(2):1110–1136, 2006. https://doi.org/10.1137/050623917
S.H. Schmieta and F. Alizadeh. Extension of primal-dual interior-point algorithms to symmetric cones. Math. Program. Ser A, 96(3):409–438, 2003. https://doi.org/10.1007/s10107-003-0380-z
H. Liu, X. Yang and C. Liu. A new wide neighborhood primal-dual infeasible-interior-point method for symmetric cone programming. J. Optim. Theory Appl.,158(3):796–815, 2013. https://doi.org/10.1007/s10957-013-0303-y
Y. Yang. A polynomial arc-search interior-point algorithm for convex quadratic programming. Eur. J. Oper. Res., 215(1):25–38, 2011. https://doi.org/10.1016/j.ejor.2011.06.020
Y. Yang. A polynomial arc-search interior-point algorithm for linear programming. J. Optim. Theory Appl., 158(3):859–873, 2013. https://doi.org/10.1007/s10957-013-0281-0
Y. Yoshise. Interior-point trajectories and a homogeneous model for nonlinear complementarity problems over symmetric cones. SIAM J. Optim., 17(4):1129–1153, 2006. https://doi.org/10.1137/04061427X
G.Q. Wang, M. Li, Y. Yue and X. Cai. New complexity analysis of interior-point methods for the Cartesian p∗(κ)-SCLCP. J. Ineq. Appl., 285:1–23, 2013.
G. Gu, M. Zangiabadi and C. Roos. Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. European J. Oper. Res., 214(3):473–484, 2011. https://doi.org/10.1016/j.ejor.2011.02.022
M. Pirhaji, M. Zangiabadi and H. Mansouri. An ℓ2-neighborhood infeasible interior-point algorithm for linear complementarity problems. 4OR-Q. J. Oper.Res., 15(2):111–131, 2016. https://doi.org/10.1007/s10288-016-0325-z
X. Yang, Y. Zhang and H. Liu. A wide neighborhood infeasible-interior-point method with arc-search for linear programming. J. Appl. Math. Comput., 51(1-2):209–225, 2016. https://doi.org/10.1007/s12190-015-0900-z