数学物理学报(英文版) ›› 2018, Vol. 38 ›› Issue (4): 1269-1284.doi: 10.1016/S0252-9602(18)30813-0

• 论文 • 上一篇    下一篇

A CORRECTOR-PREDICTOR ARC SEARCH INTERIOR-POINT ALGORITHM FOR SYMMETRIC OPTIMIZATION

M. PIRHAJI, M. ZANGIABADI, H. MANSOURI   

  1. Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran
  • 收稿日期:2016-12-06 修回日期:2017-09-08 出版日期:2018-08-25 发布日期:2018-08-25
  • 通讯作者: M.ZANGIABADI,E-mail:Zangiabadi-m@sci.sku.ac.ir E-mail:Zangiabadi-m@sci.sku.ac.ir
  • 作者简介:M.PIRHAJI,E-mail:mojtabapirhaji@yahoo.com;H.MANSOURI,E-mail:mansouri@sci.sku.ac.ir

A CORRECTOR-PREDICTOR ARC SEARCH INTERIOR-POINT ALGORITHM FOR SYMMETRIC OPTIMIZATION

M. PIRHAJI, M. ZANGIABADI, H. MANSOURI   

  1. Department of Applied Mathematics, Faculty of Mathematical Sciences, Shahrekord University, Shahrekord, Iran
  • Received:2016-12-06 Revised:2017-09-08 Online:2018-08-25 Published:2018-08-25
  • Contact: M.ZANGIABADI,E-mail:Zangiabadi-m@sci.sku.ac.ir E-mail:Zangiabadi-m@sci.sku.ac.ir

摘要:

In this paper, a corrector-predictor interior-point algorithm is proposed for symmetric optimization. The algorithm approximates the central path by an ellipse, follows the ellipsoidal approximation of the central-path step by step and generates a sequence of iterates in a wide neighborhood of the central-path. Using the machinery of Euclidean Jordan algebra and the commutative class of search directions, the convergence analysis of the algorithm is shown and it is proved that the algorithm has the complexity bound O(√rL) for the well-known Nesterov-Todd search direction and O(rL) for the xs and sx search directions.

关键词: symmetric optimization, ellipsoidal approximation, wide neighborhood, interior-point methods, polynomial complexity

Abstract:

In this paper, a corrector-predictor interior-point algorithm is proposed for symmetric optimization. The algorithm approximates the central path by an ellipse, follows the ellipsoidal approximation of the central-path step by step and generates a sequence of iterates in a wide neighborhood of the central-path. Using the machinery of Euclidean Jordan algebra and the commutative class of search directions, the convergence analysis of the algorithm is shown and it is proved that the algorithm has the complexity bound O(√rL) for the well-known Nesterov-Todd search direction and O(rL) for the xs and sx search directions.

Key words: symmetric optimization, ellipsoidal approximation, wide neighborhood, interior-point methods, polynomial complexity