TAILIEUCHUNG - New complexity analysis of full nesterov-todd step infeasible interior point method for second-order cone optimization

We present a full Nesterov-Todd (NT) step infeasible interior point algorithm for second-order cone optimization based on a different way to calculate feasibility direction. In each iteration of the algorithm we use the largest possible barrier parameter value θ. Moreover, each main iteration of the algorithm consists of a feasibility step and a few centering steps. The feasibility step differs from the feasibility step of the other existing methods. We derive the complexity bound which coincides with the best known bound for infeasible interior point methods. | Yugoslav Journal of Operations Research 28 (2018), Number 1, 21–38 DOI: NEW COMPLEXITY ANALYSIS OF FULL NESTEROV-TODD STEP INFEASIBLE INTERIOR POINT METHOD FOR SECOND-ORDER CONE OPTIMIZATION Behrouz KHEIRFAM Department of Applied Mathematics, Azarbaijan Shahid Madani University, Tabriz, . Iran Received: December 2016 / Accepted: June 2017 Abstract: We present a full Nesterov-Todd (NT) step infeasible interior-point algorithm for second-order cone optimization based on a different way to calculate feasibility direction. In each iteration of the algorithm we use the largest possible barrier parameter value θ. Moreover, each main iteration of the algorithm consists of a feasibility step and a few centering steps. The feasibility step differs from the feasibility step of the other existing methods. We derive the complexity bound which coincides with the best known bound for infeasible interior point methods. Keywords: Second-order Cone Optimization, Infeasible Interior-point Method, Full NesterovTodd Atep, Polynomial Complexity. MSC: 90C51. 1. INTRODUCTION A second order cone optimization (SOCO) problem is a linear optimization problem over a cross product of second order convex cones. The second order cone in Rn is given by Ln := {x ∈ Rn : x21 ≥ n X i=2 x2i , x1 ≥ 0}. 22 B. Kheirfam / New Complexity Analysis of Full Nesterov-Todd Step Infeasible We consider the following standard primal and dual SOCO problems min{cT x : Ax = b, x ∈ K }, max{bT y : AT y + s = c, s ∈ K }, (P) (D) n where K ⊆ R is the Cartesian product of several second-order cones, ., K = K 1 × K 2 × · · · × K N, P with K j = Ln j for each j( j = 1, 2, . . . , N) and n = Nj=1 n j . Furthermore, x = (x1 ; x2 ; . . . ; xN ), s = (s1 ; s2 ; . . . ; sN ) with x j , s j ∈ K j , c = (c1 ; c2 ; . . . ; cN ) with c j ∈ Rn j , A = (A1 ; A2 ; . . . ; AN ) with A j ∈ Rm×n j and b ∈ Rm . Without loss of generality, we assume that the .

• Toán học
• Second order cone optimization
• Infeasible interior point method
• Full nesterov todd step
• Polynomial complexity
• Feasibility direction