A weighted-path following interior-point algorithm for Cartesian P*(k)-LCP over symmetric cones
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Finding an initial feasible solution on the central path is the main difficulty of feasible interior-point methods. Although, some algorithms have been suggested to remedy this difficulty, many practical implementations often do not use perfectly centered starting points. Therefore, it is worth to analyze the case that the starting point is not exactly on the central path. In this paper, we propose a weighted-path following interior-point algorithm for solving the Cartesian $P _*(\kappa)$-linear complementarity problems (LCPs) over symmetric cones. The convergence analysis of the algorithm is shown and it is proved that the algorithm terminates after at most $O\br{(1+4\kappa)\sqrt{r}\log\frac{\textbf{Tr}(x^0\diamond s^0)}{\varepsilon}}$ iterations.
Abstract
Finding an initial feasible solution on the central path is the main difficulty of feasible interior-point methods. Although, some algorithms have been suggested to remedy this difficulty, many practical implementations often do not use perfectly centered starting points. Therefore, it is worth to analyze the case that the starting point is not exactly on the central path. In this paper, we propose a weighted-path following interior-point algorithm for solving the Cartesian $P _*(\kappa)$-linear complementarity problems (LCPs) over symmetric cones. The convergence analysis of the algorithm is shown and it is proved that the algorithm terminates after at most $O\br{(1+4\kappa)\sqrt{r}\log\frac{\textbf{Tr}(x^0\diamond s^0)}{\varepsilon}}$ iterations.
참고문헌 (25)
- M. Achache, "A new primal-dual path-following method for convex quadratic program-ming", Comput. Appl. Math, 25(1), pp.97~110 (2006)
- Z. Darvay, "A weighted-path-following method for linear optimization", Stud. Univ. Babes-Bolyai Inform, 47(2), pp.3~12 (2002)
- Z. Darvay, "New interior point algorithms in linear programming", Adv. Model. Optim, 5(1), pp.51~92 (2003)
- J. Faraut, "Analysis on Symmetric Cones" (1994), Oxford University Press
- L. Faybusovich, "Euclidean Jordan algebras and interior-point algorithms", Positivity, 1(4), pp.331~357 (1997)
- L. Faybusovich, "A Jordan-algebraic approach to potential-reduction algorithms", Math. Z, 239(1), pp.117~129 (2002)
- G. Gu, "Full Nesterov-Todd step interior-point methods for symmetric optimization", European J. Oper. Res, 214(3), pp.473~484 (2011)
- B. Jansen, "Long-step primal-dual target-following algorithms for linear programming", Math. Methods Oper. Res, 44(1), pp.11~30 (1996)
- M. Kojima, "A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems", Lecture Notes in Computer Science, 538 (1991), Springer
- Z. Y. Luo, "Path-following interior-point algorithms for the Cartesian P∗(k)-LCP over symmetric cones", Sci. China Math, 52(8), pp.1769~1784 (2009)
- H. Mansouri, "A polynomial interior-point algorithm for linear comple-mentarity problems", J. Optim. Theory Appl, 157(2), pp.451~461 (2013)
- H. Mansouri, "A full-Newton step O(n) infeasible interior-point algorithm for linear complementarity problems", Nonlinear Anal. Real World Appl, 12(1), pp.545~561 (2011)
- F. A. Potra, "An infeasible interior point method for linear complementarity problems over symmetric cones", Proceedings of the 7th International Conference of Numerical Analysis and Applied Mathematics, pp.1403~1406 (2009), Am. Inst. of Phys.
- B. K. Rangarajan, "Polynomial convergence of infeasible-interior-point methods over symmetric cones", SIAM J. Optim, 16(4), pp.1211~1229 (2006)
- C. Roos, "A full-Newton step O(n) infeasible interior-point algorithm for linear opti-mization", SIAM J. Optim, 16(4), pp.1110~1136 (2006)
- S. H. Schmieta, "Extension of primal-dual interior-point algorithms to symmetric cones", Math. Program, 96(3), pp.409~438 (2003)
- J. F. Sturm, "Similarity and other spectral relations for symmetric cones", Linear Algebra Appl, 312(1-3), pp.135~154 (2000)
- M. V. C. Vieira, "Jordan Algebraic Approach to Symetric Optimization", PhD, pp.2007
- G. Q. Wang, "A primal-dual interior-point algorithm for second-order cone optimization with full Nesterov-Todd step", Appl. Math. Comput, 215(3), pp.1047~1061 (2009)
- G. Q. Wang, "A new primal-dual path-following interior-point algorithm for semidefinite op-timization", J. Math. Anal. Appl, 353(1), pp.339~349 (2009)
- G. Q. Wang, "A new full Nesterov-Todd step primal-dual path-following interior-point algo-rithm for symmetric optimization", J. Optim. Theory Appl, 154(3), pp.966~985 (2012)
- G. Q. Wang, "A class of polynomial interior-point algorithms for the Cartesian P-matrix linear complementarity problem over symmetric cones", J. Optim. Theory Appl, 152(3), pp.739~772 (2012)
- G. Q. Wang, "Full Nesterov-Todd step feasible interior-point method for the Cartesian P∗(k)-SCLCP", Optim. Methods Softw, 28(3), pp.600~618 (2013)
- A. Yoshise, "Interior point trajectories and a homogeneous model for nonlinear comple-mentarity problems over symmetric cones", SIAM J. Optim, 17(4), pp.1129~1153 (2006)
- Y. B. Zhao, "Two interior-point methods for nonlinear P∗(k)-complementari-tarity problems", J. Optim. Theory Appl, 102(3), pp.659~679 (1999)