An Adaptive Infeasible Interior-Point Algorithm with Full Nesterov-Todd Step for Semidefinite Optimization

详细信息    查看全文

• 作者：Behrouz Kheirfam
• 关键词：Infeasible interior ; point algorithm ; Semidefinite optimization ; Full Nesterov ; Todd step ; Polynomial complexity ; 90C51 ; 90C22
• 刊名：Journal of Mathematical Modelling and Algorithms in Operations Research
• 出版年：2015
• 出版时间：March 2015
• 年：2015
• 卷：14
• 期：1
• 页码：55-66
• 全文大小：375 KB
• 参考文献：1.Benterki, D., Keraghel, A.: Finding a strict feasible solution of a linear semidefinite program. Appl. Math. Comput. 217, 6437-440 (2011)CrossRef MATH MathSciNet
  2.Darvay, Z.: New interior point algorithms in linear programming. Adv. Model. Optim. 5(1), 51-2 (2003)MATH MathSciNet
  3.De Klerk, E.: Aspects of Semidefinite Programming, Vol. 65. Kluwer Academic, Dordrecht (2002)CrossRef
  4.Karmarkar, N.K.: A new polynomial-time algorithm for linear programming. Combinatorica 4, 375-95 (1984)CrossRef MathSciNet
  5.Kheirfam, B.: Simplified infeasible interior-point algorithm for SDO using full Nesterov-Todd step. Numer. Algorithm. 59(4), 589-06 (2012)CrossRef MATH MathSciNet
  6.Kheirfam, B.: A full NT-step infeasible interior-point algorithm for semidefinite optimization based on a self-regular proximity. ANZIAM J. 53, 48-7 (2011)CrossRef MATH MathSciNet
  7.Kheirfam, B.: A full-Newton step infeasible interior-point algorithm for linear complementarity problems based on a kernel function. Algorithmic Oper. Res. 7, 103-10 (2013)MathSciNet
  8.Kheirfam, B., Mahdavi-Amiri, N.: A full Nesterov-Todd step infeasible interior-point algorithm for symmetric cone linear complementarity problem, Bulletin of the Iranian Mathematical Society, (2013)
  9.Kojima, M., Megiddo, N., Mizuno, S.: A primal-dual infeasible-interior-point algorithm for linear programming. Math. Program. 61(3), 263-80 (1993)CrossRef MATH MathSciNet
  10.Lustig, I.J.: Feasible issues in a primal-dual interior-point method. Math. Program. 67, 145-62 (1990)CrossRef MathSciNet
  11.Mansouri, H., Roos, C.: A new full-Newton step O(n) infeasible interior-point algorithm for semidefinite optimization. Numer. Algorithm. 52, 225-55 (2009)CrossRef MATH MathSciNet
  12.Mansouri, H., Zangiabadi, M.: An adaptive infeasible interior-point algorithm with full-Newton step for linear optimization. Optim. 62(2), 285-97 (2013)CrossRef MATH MathSciNet
  13.Mizuno, S.: Polynomiality of infeasible interior point algorithms for linear programming. Math. Program. 67, 109-19 (1994)CrossRef MATH MathSciNet
  14.Mizuno, S., Todd, M.J., Ye, Y.: On adaptive-step primal-dual interior-point algorithms for linear programming. Math. Oper. Res. 18, 964-81 (1993)CrossRef MATH MathSciNet
  15.Nesterov, Y.E., Todd, M.J.: Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22(1), 1-2 (1997)CrossRef MATH MathSciNet
  16.Potra, A.F.: An infeasible-interior-point predictor-corrector algorithm for linear programming. SIAM J. Optim. 6(1), 19-2 (1996)CrossRef MATH MathSciNet
  17.Potra, A.F.: A quadratically convergent predictor-corrector method for solving linear programs from infeasible starting points. Math. Program. 67(3), 383-06 (1994)CrossRef MATH MathSciNet
  18.Potra, A.F., Sheng, R.: A superlinearly convergent primal-dual infeasible-interior-point algorithm for semidefinite programming. SIAM J. Optim. 8, 1007-028 (1998)CrossRef MATH MathSciNet
  19.Roos, C.: A full-Newton step O(n) infeasible interior-point algorithm for linear optimization. SIAM J. Optim. 16(4), 1110-136 (2006)CrossRef MATH MathSciNet
  20.Roos, C., Terlaky, T., Vial, J.-Ph.: Theory and Algorithms for Linear Optimization. An Interior-Point Approach. Wiley, UK (1997)MATH
  21.Todd, M.J.: A study of search directions in primal-dual interior-point methods for semidefinite programming. Optim. Methods & Softw. 11, 1-6 (1999)CrossRef MathSciNet
  22.Wang, G.Q., Yu, C.J., Teo, K.L.: A full Nesterov-Todd step feasible interior-point method for convex quadratic optimization over symmetric cone. Appl. Math. Comput. 221(15), 329-43 (2013)CrossRef MathSciNet
  23.Wang, G.Q., Bai, Y.Q.: A primal-dual path-following interior-point algorithm for second-order cone optimization with full Nesterov-Todd step. Appl. Math. Comput. 215(3), 1047-061 (2009)CrossRef MATH MathSciNet
  24.Wang, G.Q., Bai, Y.Q.: A new primal-dual path-following interior-point algorithm for semidefinite optimization. J. Math. Anal. Appl. 353(1), 339-49 (2009)CrossRef MATH MathSciNet
  25.Wang, G.Q., Bai, Y.Q.: A new full Nesterov-Todd step primal-dual path-following interior-point algorithm for symmetric optimization. J. Optim. Theory Appl. 154(3), 966-85 (2012)CrossRef MATH MathSciNet
  26.Zangiabadi, M., Gu, G., Roos, C.: A full Nesterov-Todd step infeasible interior-point method for second-order cone optimization. J. Optim. Theory Appl. 158(3), 816-58 (2013)CrossRef MATH MathSciNet
  27.Zhang, Y.: On the convergence of a class of infeasible interior point methods for the horizantal linear complementary problem. SIAM J. Optim. 4, 208-27 (1994)CrossRef MATH MathSciNet
  28.Zhang, L., Sun, L., Xu, Y.: Simplified analysis for full-Newton step infeasible interior-point algorithm for semidefinite programming. Optim. 62(2), 169-91 (2013)CrossRef MATH MathSciNet
  
• 作者单位：Behrouz Kheirfam (1)
  
  1. Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, I. R., Iran
  
• 刊物类别：Operations Research, Management Science; Optimization; Algorithms; Mathematical Modeling and Industr
• 刊物主题：Operations Research, Management Science; Optimization; Algorithms; Mathematical Modeling and Industrial Mathematics; Data Mining and Knowledge Discovery;
• 出版者：Springer Netherlands
• ISSN：2214-2495

文摘

We present an adaptive full Nesterov-Todd step infeasible interior-point method for semidefinite optimization. The proposed algorithm requires two types of full Nesterov-Todd steps are called, feasibility steps and centering steps, respectively. At each iteration both feasibility and optimality are reduced exactly at the same rate. In each iteration of the algorithm we use the largest possible barrier parameter value θ. The value θ varies from iteration to iteration and it lies between the two values \(\frac {1}{4n}\) and \(\frac {1}{5n}\), which results a faster algorithm. Keywords Infeasible interior-point algorithm Semidefinite optimization Full Nesterov-Todd step Polynomial complexity