A Mehrotra-type predictor-corrector infeasible-interior-point method with a new one-norm neighborhood for symmetric optimization

JOURNAL OF COMPUTATIONAL AND APPLIED MATHEMATICS

卷:283

Article

Yang, Ximei^1,2  Liu, Hongwei¹  Liu, Changhe³ 

[1] Xidian Univ, Sch Math & Stat, Xian, Peoples R China

[2] Henan Normal Univ, Coll Math & Informat Sci, Xinxiang, Peoples R China

[3] Henan Univ Sci & Technol, Dept Appl Math, Luoyang, Peoples R China

关键词: Symmetric cones;    Euclidean Jordan algebra;    One-norm;    Infeasible-interior-point method;    Complexity bound;   

DOI  :  10.1016/j.cam.2015.01.027

来源: Elsevier

【 摘 要 】

In this paper, we present a Mehrotra-type predictor-corrector infeasible-interior-point method for symmetric optimization. The proposed algorithm is based on a new one-norm neighborhood, which is an even wider neighborhood than a given negative infinity neighborhood. We are emphatically concerned with the relationship between the one-norm of the Jordan product of x and y and its Frobenius-norm. Based on the relationship, the convergence is shown for a commutative class of search directions. In particular, the complexity bound is O(r log epsilon(-1)) for the Nesterov-Todd search direction, and O(r(3/2) log epsilon(-1)) for the xs and sx search direction, where r is the rank of the associated Euclidean Jordan algebra and epsilon > 0 is a given tolerance. To our knowledge, this is the best complexity result obtained so far for infeasible-interior-point methods with a wide neighborhood over symmetric cones. (C) 2015 Elsevier B.V. All rights reserved.

【 授权许可】

Free