An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood
- PDF / 871,281 Bytes
- 21 Pages / 439.642 x 666.49 pts Page_size
- 37 Downloads / 210 Views
An arc-search infeasible interior-point method for semidefinite optimization with the negative infinity neighborhood Behrouz Kheirfam1
· Naser Osmanpour2 · Mohammad Keyanpour2
Received: 11 February 2020 / Accepted: 14 October 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We present an arc-search infeasible interior-point algorithm for semidefinite optimization using the Nesterov-Todd search directions. The algorithm is based on the negative infinity neighborhood of the central path. The algorithm searches an εapproximate solution of the problem along the ellipsoidal approximation of the entire central path. The convergence analysis of the algorithm is presented and shows that the algorithm has the iteration complexity bound O n3/2 log ε−1 . Here, n is the dimension of the problem and ε is the required precision. The numerical results show that our algorithm is efficient and promising. Keywords Semidefinite optimization · Arc-search strategy · Infeasible interior-point method · Polynomial complexity Mathematics subject classification (2010) 90C22 · 90C51
1 Introduction Semidefinite optimization (SDO) is a subfield of convex optimization concerned with the optimization of a linear objective function over the intersection of the cone of positive semidefinite matrices with an affine space. Due to the important applications of Behrouz Kheirfam
[email protected] Naser Osmanpour [email protected] Mohammad Keyanpour [email protected] 1
Department of Mathematics, Azarbaijan Shahid Madani University, Tabriz, Iran
2
Faculty of Mathematical Sciences, University of Guilan, Rasht, Iran
Numerical Algorithms
SDOs in many optimization fields, such as combinatorial optimization [2, 3], system and control theory [5], and applications in polynomial optimization problems [15, 26], in recent years, most interior-point methods (IPMs) have been extended from linear optimization (LO) to SDO. For details, reader are referred to references Nesterov and Nemirovskii [21], Alizadeh [2], Kojima et al. [14], Nesterov and Todd [22, 23], Monteiro [17–19], and Monteiro and Zhang [20]. Among others, primal-dual pathfollowing IPMs have been studied intensively. These methods trace approximately the so-called central path, which is a curve that lies completely within the feasible region of the underlying problem, along the straight lines related to the first-order and higher-order derivatives of the central path [10]. Since the central path is a curve, then the search ideal should be along arcs, not straight lines. Yang [28, 29] first introduced the arc-search algorithm that searches for optimizers along an ellipsoidal approximation of the central path and gave some of the advantages of the arc-search algorithm from the computational point of view. However, Yang’s algorithms [28, 29] require the starting point is strictly feasible. Usually such a starting point is not at hand. To overcome this problem, a so-called infeasible IPM (IIPM) is suggested. In accordance with the Yang’s o
Data Loading...
