A New Strategy in the Complexity Analysis of an Infeasible-Interior-Point Method for Symmetric Cone Programming

详细信息    查看全文

• 作者：Ximei Yang ; Hongwei Liu ; Yinkui Zhang
• 关键词：Jordan algebra ; Symmetric cone programming ; Infeasible ; interior ; point method ; Polynomial complexity ; 90C05 ; 90C51
• 刊名：Journal of Optimization Theory and Applications
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：166
• 期：2
• 页码：572-587
• 全文大小：451 KB
• 参考文献：1.Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica. 4, 302-11 (1984)MathSciNet View Article
  2.Peng, J., Roos, C., Terlaky, T.: Self-Regularity. A New Paradigm for Primal-Dual Interior-Point Algorithms. Princeton University Press, Princeton (2002)
  3.Roos, C., Terlaky, T., Vial, J.P.: Theory and Algorithms for Linear Optimization: An Interior Point Approach. Wiley, Chichester (1997)MATH
  4.Vanderbei, R.J.: Linear Programming: Foundations and Extensions. Kluwer Academic Publishers, Boston (1996)
  5.Nesterov, Y., Todd, M.: Primal-dual interior-point methods for self-scaled cones. SIAM J. Optim. 8, 324-64 (1998)MathSciNet View Article
  6.Nesterov, Y., Todd, M.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22, 1-2 (1997)MathSciNet View Article MATH
  7.Güler, O.: Barrier functions in interior-point methods. Math. Oper. Res. 21, 860-85 (1996)MathSciNet View Article MATH
  8.Faybusovich, L.: Linear systems in Jordan algebras and primal-dual interior-point algorithms. J. Comput. Appl. Math. 86, 149-75 (1997)MathSciNet View Article
  9.Schmieta, S.H., Alizadeh, F.: Extension of primal-dual interior point algorithm to symmetric cones. Math. Program. 96, 409-38 (2003)MathSciNet View Article
  10.Vieira, M.V.C.: Jordan algebras approach to symmetric optimization. Ph.D. thesis, Delft University of Technology (2007)
  11.Vieira, M.V.C.: Interior-point methods based on kernel functions for symmetric optimization. Optim. Methods Softw. 27, 513-37 (2012)MathSciNet View Article
  12.Wang, G., Bai, Y.: A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154, 966-85 (2012)MathSciNet View Article
  13.Liu, C., Liu, H., Liu, X.: Polynomial convergence of second-order Mehrotra-type predictor-corrector algorithms over symmetric cones. J. Optim. Theory Appl. 154, 949-65 (2012)MathSciNet View Article
  14.Lustig, I.J.: Feasible issues in a primal-dual interior-point method. Math. Program. 67, 145-62 (1990)MathSciNet View Article MATH
  15.Tanabe, K.: Centered Newton method for linear programming: interior and ‘exterior-point method (in Janpanese). In: Tone, K. (ed.) New Methods for Linear Programming 3, pp. 98-00. Wiley, New York (1990)
  16.Mizuno, S.: Polynomiality of infeasible-interior-point algorithms for linear programming. Math. Program. 67, 109-19 (1994)MathSciNet View Article MATH
  17.Potra, F.A., Sheng, R.: Superlinear convergence of interior-point algorithms for semidefinite programming. J. Optim. Theory Appl. 99, 103-19 (1998)MathSciNet View Article MATH
  18.Potra, F.A., Sheng, R.: A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Optim. 8, 1007-028 (1998)MathSciNet View Article
  19.Zhang, Y.: On extending some primal-dual interior-point algorithms from linear programming to semidefinite programming. SIAM J. Optim. 8, 365-86 (1998)MathSciNet View Article MATH
  20.Rangarajan, B.K.: Polynomial convergence of infeasible-interior-point methods over symmetric cones. SIAM J. Optim. 16, 1211-229 (2006)MathSciNet View Article
  21.Zhang, J., Zhang, K.: Polynomial complexity of an interior point algorithm with a second order corrector step for symmetric cone programming. Math. Meth. Oper. Res. 73, 75-0 (2011)View Article
  22.Potra, F.A.: An infeasible interior point method for linear complementarity problems over symmetric cones. Numer. Anal. Appl. Math. 1168, 1403-406 (2009)View Article
  23.Liu, H., Yang, X., Liu, C.: A new wide neighborhood primal-dual infeasible-interior- point method for symmetric cone programming. J. Optim. Theory Appl. 158, 796-15 (2013)MathSciNet View Article
  24.Faraut, J., Korányi, A.: Analysis on Symmetric Cone. Oxford University Press, New York (1994)
  25.Luo, Z., Xiu, N.: Path-following interior point algorithms for the Cartesian \(P_*(\kappa )\) -LCP over symmetric cones. Sci. China. Ser. A 52, 1769-784 (2009)MathSciNet View Article MATH
  26.Gu, G., Zangiabadi, M., Roos, C.: Full Nesterov-Todd step infeasible interior-point method for symmetric optimization. Eur. J. Oper. Res. 214, 473-84 (2011)MathSciNet View Article
  27.Liu, C.: Study on complexity of some interior-point algorithms in conic programming (in chinese). Ph.D. thesis, Xidian University (2012)
  
• 作者单位：Ximei Yang (1) (2)
  Hongwei Liu (1)
  Yinkui Zhang (2)
  
  1. School of Mathematics and Statistics, Xidian University, Xi’an, 710071, People’s Republic of China
  2. School of Mathematics and Information Science, Henan Normal University, Xinxiang, 453007, Henan, Peoples Republic of China
  
• 刊物主题：Calculus of Variations and Optimal Control; Optimization; Optimization; Theory of Computation; Applications of Mathematics; Engineering, general; Operations Research/Decision Theory;
• 出版者：Springer US
• ISSN：1573-2878

文摘

In this paper, we give a new strategy in the complexity analysis of an infeasible-interior-point method for symmetric cone programming. Using the strategy, we improve the theoretical complexity bound of an infeasible-interior-point method. Convergence is shown for a commutative class of search directions, which includes the Nesterov–Todd direction and the \(xs\) and \(sx\) directions.